From: Michael Orlitzky Date: Sat, 24 Oct 2009 23:43:15 +0000 (-0400) Subject: Added the Geometry module and its tests. X-Git-Url: http://gitweb.michael.orlitzky.com/?p=dead%2Fcensus-tools.git;a=commitdiff_plain;h=27ce45a6f4e2844f3d7bc5d570f3cb06e087bb5a Added the Geometry module and its tests. --- diff --git a/bin/run_tests b/bin/run_tests index 4c7a1a3..009a3ef 100755 --- a/bin/run_tests +++ b/bin/run_tests @@ -8,9 +8,11 @@ import unittest from Tests.Unit import CensusTest from Tests.Unit import SummaryFile1Test from Tests.Unit import StringUtilsTest +from Tests.Unit import GeometryTest suite = unittest.TestSuite() suite.addTest(CensusTest.suite()) suite.addTest(SummaryFile1Test.suite()) suite.addTest(StringUtilsTest.suite()) +suite.addTest(GeometryTest.suite()) unittest.TextTestRunner(verbosity=2).run(suite) diff --git a/src/Geometry.py b/src/Geometry.py new file mode 100644 index 0000000..89a6cdb --- /dev/null +++ b/src/Geometry.py @@ -0,0 +1,262 @@ +""" +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) diff --git a/src/Tests/Unit/GeometryTest.py b/src/Tests/Unit/GeometryTest.py new file mode 100644 index 0000000..49fa113 --- /dev/null +++ b/src/Tests/Unit/GeometryTest.py @@ -0,0 +1,98 @@ +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