#!/usr/bin/env python

import inkex
import sys
import numpy as n

# for more power
import simpletransform
import cubicsuperpath
import simplepath
import simplestyle
import cspsubdiv
import bezmisc

link = lambda a,b: n.concatenate((a,b[1:]))
edge = lambda a,b: n.concatenate(([a],[b]))

# Python Q_hull routine from here; https://github.com/flengyel/REST/blob/master/quickhull.py
# See copyright disclaimer in original file.
def qhull(sample):
    def dome(sample,base): 
        h, t = base
        dists = n.dot(sample-h, n.dot(((0,-1),(1,0)),(t-h)))
        outer = n.repeat(sample, dists>0, 0)

        if len(outer):
            pivot = sample[n.argmax(dists)]
            return link(dome(outer, edge(h, pivot)),
                        dome(outer, edge(pivot, t)))
        else:
            return base
    if len(sample) > 2:
    	axis = sample[:,0]
    	base = n.take(sample, [n.argmin(axis), n.argmax(axis)], 0)
    	return link(dome(sample, base),
                    dome(sample, base[::-1]))
    else:
        return sample
   
class TemplateEffect(inkex.Effect):
    def __init__(self):
        # Call base class construtor.
        inkex.Effect.__init__(self)
        self.paths = {}
        self.paths_clone_transform = {}
        
    def joinWithNode ( self, node, path, makeGroup=False, cloneTransform=None ):
        if ( not path ) or ( len( path ) == 0 ):
            return

        
        g = self.document.getroot()
            
        # Now make a <path> element which contains the twist & is a child
        # of the new <g> element
        style = { 'stroke': '#000000', 'fill': 'none', 'stroke-width': '1' }
        line_attribs = { 'style':simplestyle.formatStyle( style ), 'd': path }
        if ( cloneTransform != None ) and ( cloneTransform != '' ):
            line_attribs['transform'] = cloneTransform
        inkex.etree.SubElement( g, inkex.addNS( 'path', 'svg' ), line_attribs )  


    def effect(self):
        global output_nodes, points
        #Loop through all the selected items in Inkscape
        for node in self.selected.values():
            #create numpy array of nodes
            n_array = []
                    
            #Iterate through all the selected objects in Inkscape
            for  node in self.selected.values():
                #Check if the node is a path ( "svg:path" node in XML )
                #id = node.id
                if node.tag == inkex.addNS('path','svg'):
                    
                    # bake (or fuse) transform
                    simpletransform.fuseTransform(node)
                    #turn into cubicsuperpath
                    d = node.get('d')
                    p = cubicsuperpath.parsePath(d)
                    for subpath in p: # there may be several paths joined together (e.g. holes)
                        for csp in subpath: # groups of three to handle control points.
                            # just the points no control points (handles)

                            n_array.append(csp[1][0])
                            n_array.append(csp[1][1])

        k = n.asarray(n_array)
        length = int(len(k)/2)
        c = k.reshape(length,2)
        hull_pts = qhull(c)
        
        pdata = ''
        for vertex in hull_pts:
            if pdata == '':
                pdata = 'M%f,%f' % ( vertex[0], vertex[1] )
            else:
                pdata += 'L %f,%f' %  ( vertex[0], vertex[1] )
        pdata += ' Z'        
        path = 'polygon'
        makeGroup = False
        paths_clone_transform = None
        self.joinWithNode( path, pdata, makeGroup, paths_clone_transform )
    
# Create effect instance and apply it.

effect = TemplateEffect()
effect.affect()