"""
Geometry classes and functions. We don't want to rely completely on
some huge third-party library, nor do we want implement everything
from scratch. We use Shapely for the hard stuff (Geos integration),
and wrap its classes with our own.
"""

from math import sqrt
import os
import site
import sys

# Basically, add '../src' and '../lib/Shapely' to our path.
# Needed for the imports that follow.
site.addsitedir(os.path.dirname(os.path.abspath(sys.argv[0])) + '/../src')
site.addsitedir(os.path.dirname(os.path.abspath(sys.argv[0])) + '/../lib/Shapely')

import shapely.geometry
import shapely.wkt



class TwoVector:
    """
    Represents a two-dimensional vector.
    """
    
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y


    def __hash__(self):
        """
        We have to define __hash__ in order to override __eq__.
        Just return the hash of our ordered pair.
        """
        return (self.x, self.y).__hash__()


    def __eq__(self, v):
        """
        We would like to override equality to compare against our
        underlying ordered pair.
        """
        if (v == None):
            return False

        if isinstance (v, TwoVector):
            return ( (self.x == v.x) and (self.y == v.y) )

        # If it's not a TwoVector, assume that it's a tuple.
        if (len(v) > 1):
            return (self.x == v[0]) and (self.y == v[1])

        # If v is neither a TwoVector nor a tuple, we ain't it.
        return False
    

    def __add__(self, other_vector):
        """
        Add other_vector to this vector, and return a new TwoVector
        containing the result.
        """
        return TwoVector(self.x + other_vector.x, self.y + other_vector.y)
    

    def __sub__(self, other_vector):
        """
        Subtract other_vector from this vector. Return a new
        TwoVector.
        """
        return TwoVector(self.x - other_vector.x, self.y - other_vector.y)


    def __str__(self):
        """
        Print the contents of our ordered pair.
        """
        return "TwoVector<%d, %d>" % (self.x, self.y)

    
    def to_tuple(self):
        """
        Returns the two-tuple underlying this TwoVector.
        """
        return (self.x, self.y)

        
    def perpendicular(self):
        """
        Return a vector perpendicular to ourself.
        """
        return TwoVector(-self.y, self.x)


    def dot_product(self, other_vector):
        """
        Return the dot product of this vector with other_vector.
        """
        return (self.x * other_vector.x) + (self.y * other_vector.y)


    
class Polygon:
    """
    Wraps shapely.geometry.Polygon.
    """

    def __init__(self, points=None):
        """
        We can initialize from either a set of two-tuples, or a set of
        TwoVectors.
        """
        if (points == None):
            return

        # Is the first element of points a TwoVector?
        if ( (len(points) > 0) and isinstance(points[0], TwoVector) ):
            # If so, convert points to a list of two-tuples.
            points = map ( (lambda p: p.to_tuple()), points )

        self._shapely_polygon = shapely.geometry.Polygon(points)


    def __eq__(self, p):
        """
        Override equality to test whether or not our boundary is equal
        to the passed polygon's boundary.
        """
        if (p == None):
            return False

        # Shapely polygon exteriors know how to compare themselves.
        ext1 = self._shapely_polygon.exterior
        
        if isinstance(p, Polygon):
            ext2 = p._shapely_polygon.exterior
            return ext1.equals(ext2)
        elif isinstance(p, shapely.geometry.Polygon):
            return ext1.equals(p)
        else:
            return False


    def __hash__(self):
        """
        Needed when we implement __eq__. Delegate it to our
        shapely.geometry.Polygon.
        """
        return self._shapely_polygon.__hash__()

    
    def __str__(self):
        """
        Write out the well-known text representation of this polygon,
        as well as the class name, which helps distinguish
        Geometry.Polygon from shapely.geometry.Polygon..
        """
        return "Geometry.Polygon<%s>" % self._shapely_polygon.to_wkt()


    def wkt(self):
        """
        Return just the well-known text for this Polygon.
        """
        return self._shapely_polygon.to_wkt()

    
    @classmethod
    def from_shapely(self, shapely_polygon):
        """
        Create a Geometry.Polygon from the shapely.geometry.Polygon.
        """
        p = Polygon()
        p._shapely_polygon = shapely_polygon
        return p

    
    def coords(self):
        """
        An alias to retrieve our coordinates.
        """
        tuples = self._shapely_polygon.exterior.coords
        vectors = map ( (lambda v: TwoVector(v[0], v[1])), tuples)
        return vectors


    def union(self, other_polygon):
        """
        Return a new Polygon representing the union of this polygon
        and other_polygon.
        """
        # First, get the union of self and other_polygon as a
        # shapely.geometry.Polygon.
        u = self._shapely_polygon.union(other_polygon._shapely_polygon)
        
        # Then, create a new Geometry.Polygon from that union.
        return Polygon.from_shapely(u)

        
    def translate(self, v):
        """
        Translate the self polygon by the TwoVector v.
        """
        regular_coords = self.coords()
        f = (lambda p: p + v)
        translated_coords = map(f, regular_coords)
        return Polygon(translated_coords)



    def drag_vertices(self, v):
        """
        The vector v is that vector along which we are 'dragging' the
        polygon. If we are dragging from p1 = (x1,y1) to p2 = (x2,y2),
        then v = (x2-x1, y2-y1). The 'drag' vertices of a polygon are
        those two vertices which are most/least in the direction of
        the v_perp.
        """
        v_perp = v.perpendicular()

        current_min_vertex = self.coords()[0]
        current_max_vertex = self.coords()[0]

        for w in self.coords():
            if (w.dot_product(v_perp) < current_min_vertex.dot_product(v_perp)):
                current_min_vertex = w
                
            if (w.dot_product(v_perp) > current_max_vertex.dot_product(v_perp)):
                current_max_vertex = w
            
        return [current_min_vertex, current_max_vertex]


    @staticmethod
    def from_wkt(text):
        """
        Create a Polygon from a Well-Known Text string.
        """
        # The WKT string must contain the word "polygon" at least.
        # Ex: POLYGON((1 1,5 1,5 5,1 5,1 1),(2 2, 3 2, 3 3, 2 3,2 2))
        if (text.lower().find('polygon') == -1):
            return None

        sp = shapely.wkt.loads(text)
        return Polygon.from_shapely(sp)


    def drag_rectangle(self, v):
        """
        When we dtag a polygon in the plane, we drag it from its
        starting position to some terminal position. Since there are
        two 'drag vertices' on the polygon, we have two points
        corresponding to the drag vertices at both the initial
        location and the terminal location. From these four points, we
        can form a rectangle.
        """
        initial_dv = self.drag_vertices(v)
    
        terminal_dv = [0, 0] # Just initializing it.
        terminal_dv[0] = initial_dv[0] + v
        terminal_dv[1] = initial_dv[1] + v

        return Polygon( (initial_dv[1],
                         initial_dv[0],
                         terminal_dv[0],
                         terminal_dv[1]) )


    def drag(self, v):
        """
        Drag this polygon along the vector v = (x2-x1, y2-y1), and
        return the new polygon consisting of the union of all points
        that we've contained along the way.
        """
        terminal_p = self.translate(v)
        dv_rect = self.drag_rectangle(v)

        return self.union(dv_rect).union(terminal_p)