#! /usr/bin/env python
import framework
import gtk
from copy import deepcopy
from math import pi

# returns an array of all the two element subsets of a given array
def alltwosubsets(array):
    l = len(array)
    result = []
    
    for i in range(0, len(array)-1):
        for j in range(i+1, len(array)):
            result.append((array[i], array[j]))

    return result

# given an edge as a tuple of indices into the pts array, e.g. (2 3) is the
# edge connecting pts[2] and pts[3], determines whether or not that edge
# determines a line such that all the pts are on one side.
def separatesq(edge, pts):
    pt1 = pts[edge[0]]
    pt2 = pts[edge[1]]
    
    det = pt1[0]*pt2[1] - pt2[0]*pt1[1]
    A = (pt2[1] - pt1[1])/(det*1.0)
    B = (pt1[0] - pt2[0])/(det*1.0)
    
    side = []
    onesideq = True
    for j in range(0, len(pts)):
        if j in edge: continue
        level = A*pts[j][0] + B*pts[j][1]
        side.append(level)
        if max(side) > 1 and min(side) < 1:
            onesideq = False
            break

    return onesideq

# given a list of edges ((v1, v2), (v3, v6), ...) defining a polygon,
# reorder them to a counterclockwise enumeration of the edges of the polygon
def orient(edges):
    oriented = edges
    return oriented

class Triangle(framework.Screen):
    pts = []
    triangles = []
    edges = []
    
    def do_button_press_event(self, event):
        
        if event.button == 1:
            width, height = self.window.get_size()
            self.pts.append((event.x/width, event.y/height))
            self.updatetriangles()
        if event.button == 2:
            self.pts = []
            self.triangles = []
        
        # figure out how to say what rectangular area to expose,
        # so can reenable clipping in framework
        self.emit('expose-event', gtk.gdk.Event(gtk.gdk.EXPOSE))
            
    def draw(self, cr, width, height):
        cr.set_source_rgb(1,1,1)
        cr.rectangle(0,0,width,height)
        cr.fill()

        # fill triangles
        cr.set_source_rgb(0.8,0.8,0.8)
        for (i,j,k) in self.triangles:
            cr.move_to(self.pts[i][0]*width, self.pts[i][1]*height)
            cr.line_to(self.pts[j][0]*width, self.pts[j][1]*height)
            cr.line_to(self.pts[k][0]*width, self.pts[k][1]*height)
            cr.line_to(self.pts[i][0]*width, self.pts[i][1]*height)
            cr.fill()

        # draw bounding polygon
        cr.set_source_rgb(0.8,0.2,0)
        for (i,j) in self.edges:
            cr.move_to(self.pts[i][0]*width, self.pts[i][1]*height)
            cr.line_to(self.pts[j][0]*width, self.pts[j][1]*height)
            cr.stroke()
            
        # draw points
        cr.set_source_rgb(0.2,0.8,0.2)
        for pt in self.pts:
            cr.arc(pt[0]*width, pt[1]*height, 5, 0, 2*pi)
            cr.fill()

            
    
    def updatetriangles(self):
        if len(self.pts) < 3: return

        newtriangles = []
        # determine all the new triangles the added point has created
        for (node1, node2) in alltwosubsets(range(0, len(self.pts)-1)):
            newtriangles.append((node1, node2, len(self.pts)-1))
        self.triangles.extend(newtriangles)

        # find edges
        edges = alltwosubsets(range(0, len(self.pts)))

        # identify boundary edges by seeing if the convex hull lies entirely
        # to one side
        self.edges = []
        for e in edges:
            if separatesq(e,self.pts): self.edges.append(e)

        # orient the boundary, counterclockwise
        self.edges = orient(self.edges)
        
framework.run(Triangle)