--- /dev/null
+"""
+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 __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)
+
+
+ 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)
+
+
+
+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.
+ """
+ return "Geometry.Polygon<%s>" % 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.add(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
+
+ return shapely.wkt.loads(text)
+
+
+ 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].add(v)
+ terminal_dv[1] = initial_dv[1].add(v)
+
+ return Polygon( (initial_dv[1],
+ initial_dv[0],
+ terminal_dv[0],
+ terminal_dv[1]) )
+
+
+ def drag(self, v):
+ """
+ Drag this polygon along the line v = (x2-x1, y2-y1), and
+ return the new polygon consisting of the union of all points
+ that I've contained along the way.
+ """
+ terminal_p = self.translate(v)
+ dv_rect = self.drag_rectangle(v)
+
+ return self.union(dv_rect).union(terminal_p)
--- /dev/null
+import unittest
+
+import Tests.Fixtures
+from Geometry import *
+
+
+class TwoVectorTest(unittest.TestCase):
+
+ def testAdd(self):
+ """
+ Add a couple of test vectors and check that they sum
+ correctly.
+ """
+ v1 = TwoVector(0,0)
+ v2 = TwoVector(100, -19)
+ self.assertTrue(v2 == v1.add(v2))
+
+ v1 = TwoVector(23, -10)
+ v2 = TwoVector(-23, 10)
+ zero = TwoVector(0, 0)
+ self.assertTrue(v1.add(v2) == zero)
+
+
+ def testDotProduct(self):
+ """
+ The dot product of a vector v with a vector to which it's
+ perpendicular, v_perp, should always be zero.
+
+ The dot product of any vector with the zero vector should be
+ zero.
+ """
+ v1 = TwoVector(235, -2352)
+ v2 = TwoVector(9382335.024, -235235.1242)
+ self.assertEqual(0, v1.dot_product(v1.perpendicular()))
+ self.assertEqual(0, v2.dot_product(v2.perpendicular()))
+
+ zero = TwoVector(0, 0)
+ self.assertEqual(0, v1.dot_product(zero))
+
+
+
+class PolygonTest(unittest.TestCase):
+
+ def testEquals(self):
+ """
+ We defined our own __eq__ method; make sure it works.
+ """
+ unit_square1 = Polygon([ (0,0), (1,0), (1,1), (0,1) ])
+ unit_square2 = Polygon([ (0,0), (1,0), (1,1), (0,1) ])
+ self.assertTrue(unit_square1 == unit_square2)
+
+ hexagon = Polygon([ (1,0),
+ (0.5, sqrt(3)/2.0),
+ (-0.5, sqrt(3)/2.0),
+ (-1, 0),
+ (-0.5, -sqrt(3)/2.0),
+ (0.5, -sqrt(3)/2.0) ])
+
+ self.assertFalse(unit_square1 == hexagon)
+
+
+ def testDrag(self):
+ """
+ Drag the unit square 5 units to the right.
+ """
+ unit_square = Polygon([ (0,0), (1,0), (1,1), (0,1) ])
+ v = TwoVector(5,0)
+ result = unit_square.drag(v)
+ expected_result = Polygon([ (0,0), (6,0), (6,1), (0,1) ])
+ self.assertTrue(result == expected_result)
+
+
+
+ def testDragVertices(self):
+ """
+ A diamond shape has nice drag vertices which we can calculate
+ by hand.
+ """
+ diamond = Polygon([ (0,1), (-1,0), (0,-1), (1,0) ])
+
+ # First, we drag it to the right along the x-axis.
+ drag_vector = TwoVector(5,0)
+ dvs = set(diamond.drag_vertices(drag_vector))
+ expected_dvs = set([(0,1), (0,-1)])
+ self.assertTrue(dvs == expected_dvs)
+
+ # Now, drag it up.
+ drag_vector = TwoVector(0,5)
+ dvs = set(diamond.drag_vertices(drag_vector))
+ expected_dvs = set([(1,0), (-1,0)])
+ self.assertTrue(dvs == expected_dvs)
+
+
+def suite():
+ suite = unittest.TestSuite()
+ suite.addTest(unittest.makeSuite(TwoVectorTest))
+ suite.addTest(unittest.makeSuite(PolygonTest))
+ return suite
projects / dead / census-tools.git / commitdiff