src/Geometry.py

   1 """
   2 Geometry classes and functions. We don't want to rely completely on
   3 some huge third-party library, nor do we want implement everything
   4 from scratch. We use Shapely for the hard stuff (Geos integration),
   5 and wrap its classes with our own.
   6 """
   7
   8 from math import sqrt
   9 import os
  10 import site
  11 import sys
  12
  13 # Basically, add '../src' and '../lib/Shapely' to our path.
  14 # Needed for the imports that follow.
  15 site.addsitedir(os.path.dirname(os.path.abspath(sys.argv[0])) + '/../src')
  16 site.addsitedir(os.path.dirname(os.path.abspath(sys.argv[0])) + '/../lib/Shapely')
  17
  18 import shapely.geometry
  19 import shapely.wkt
  20
  21
  22
  23 class TwoVector:
  24     """
  25     Represents a two-dimensional vector.
  26     """
  27
  28     def __init__(self, x=0, y=0):
  29         self.x = x
  30         self.y = y
  31
  32
  33     def __hash__(self):
  34         """
  35         We have to define __hash__ in order to override __eq__.
  36         Just return the hash of our ordered pair.
  37         """
  38         return (self.x, self.y).__hash__()
  39
  40
  41     def __eq__(self, v):
  42         """
  43         We would like to override equality to compare against our
  44         underlying ordered pair.
  45         """
  46         if (v == None):
  47             return False
  48
  49         if isinstance (v, TwoVector):
  50             return ( (self.x == v.x) and (self.y == v.y) )
  51
  52         # If it's not a TwoVector, assume that it's a tuple.
  53         if (len(v) > 1):
  54             return (self.x == v[0]) and (self.y == v[1])
  55
  56         # If v is neither a TwoVector nor a tuple, we ain't it.
  57         return False
  58
  59
  60     def __str__(self):
  61         """
  62         Print the contents of our ordered pair.
  63         """
  64         return "TwoVector<%d, %d>" % (self.x, self.y)
  65
  66
  67     def to_tuple(self):
  68         """
  69         Returns the two-tuple underlying this TwoVector.
  70         """
  71         return (self.x, self.y)
  72
  73
  74     def perpendicular(self):
  75         """
  76         Return a vector perpendicular to ourself.
  77         """
  78         return TwoVector(-self.y, self.x)
  79
  80
  81     def dot_product(self, other_vector):
  82         """
  83         Return the dot product of this vector with other_vector.
  84         """
  85         return (self.x * other_vector.x) + (self.y * other_vector.y)
  86
  87
  88     def add(self, other_vector):
  89         """
  90         Add other_vector to this vector, and return a new TwoVector
  91         containing the result.
  92         """
  93         return TwoVector(self.x + other_vector.x, self.y + other_vector.y)
  94
  95
  96
  97 class Polygon:
  98     """
  99     Wraps shapely.geometry.Polygon.
 100     """
 101
 102     def __init__(self, points=None):
 103         """
 104         We can initialize from either a set of two-tuples, or a set of
 105         TwoVectors.
 106         """
 107         if (points == None):
 108             return
 109
 110         # Is the first element of points a TwoVector?
 111         if ( (len(points) > 0) and isinstance(points[0], TwoVector) ):
 112             # If so, convert points to a list of two-tuples.
 113             points = map ( (lambda p: p.to_tuple()), points )
 114
 115         self._shapely_polygon = shapely.geometry.Polygon(points)
 116
 117
 118     def __eq__(self, p):
 119         """
 120         Override equality to test whether or not our boundary is equal
 121         to the passed polygon's boundary.
 122         """
 123         if (p == None):
 124             return False
 125
 126         # Shapely polygon exteriors know how to compare themselves.
 127         ext1 = self._shapely_polygon.exterior
 128
 129         if isinstance(p, Polygon):
 130             ext2 = p._shapely_polygon.exterior
 131             return ext1.equals(ext2)
 132         elif isinstance(p, shapely.geometry.Polygon):
 133             return ext1.equals(p)
 134         else:
 135             return False
 136
 137
 138     def __hash__(self):
 139         """
 140         Needed when we implement __eq__. Delegate it to our
 141         shapely.geometry.Polygon.
 142         """
 143         return self._shapely_polygon.__hash__()
 144
 145
 146     def __str__(self):
 147         """
 148         Write out the well-known text representation of this polygon.
 149         """
 150         return "Geometry.Polygon<%s>" % self._shapely_polygon.to_wkt()
 151
 152
 153     @classmethod
 154     def from_shapely(self, shapely_polygon):
 155         """
 156         Create a Geometry.Polygon from the shapely.geometry.Polygon.
 157         """
 158         p = Polygon()
 159         p._shapely_polygon = shapely_polygon
 160         return p
 161
 162
 163     def coords(self):
 164         """
 165         An alias to retrieve our coordinates.
 166         """
 167         tuples = self._shapely_polygon.exterior.coords
 168         vectors = map ( (lambda v: TwoVector(v[0], v[1])), tuples)
 169         return vectors
 170
 171
 172     def union(self, other_polygon):
 173         """
 174         Return a new Polygon representing the union of this polygon
 175         and other_polygon.
 176         """
 177         # First, get the union of self and other_polygon as a
 178         # shapely.geometry.Polygon.
 179         u = self._shapely_polygon.union(other_polygon._shapely_polygon)
 180
 181         # Then, create a new Geometry.Polygon from that union.
 182         return Polygon.from_shapely(u)
 183
 184
 185     def translate(self, v):
 186         """
 187         Translate the self polygon by the TwoVector v.
 188         """
 189         regular_coords = self.coords()
 190         f = (lambda p: p.add(v))
 191         translated_coords = map(f, regular_coords)
 192         return Polygon(translated_coords)
 193
 194
 195
 196     def drag_vertices(self, v):
 197         """
 198         The vector v is that vector along which we are 'dragging' the
 199         polygon. If we are dragging from p1 = (x1,y1) to p2 = (x2,y2),
 200         then v = (x2-x1, y2-y1). The 'drag' vertices of a polygon are
 201         those two vertices which are most/least in the direction of
 202         the v_perp.
 203         """
 204         v_perp = v.perpendicular()
 205
 206         current_min_vertex = self.coords()[0]
 207         current_max_vertex = self.coords()[0]
 208
 209         for w in self.coords():
 210             if (w.dot_product(v_perp) < current_min_vertex.dot_product(v_perp)):
 211                 current_min_vertex = w
 212
 213             if (w.dot_product(v_perp) > current_max_vertex.dot_product(v_perp)):
 214                 current_max_vertex = w
 215
 216         return [current_min_vertex, current_max_vertex]
 217
 218
 219     @staticmethod
 220     def from_wkt(text):
 221         """
 222         Create a Polygon from a Well-Known Text string.
 223         """
 224         # The WKT string must contain the word "polygon" at least.
 225         # Ex: POLYGON((1 1,5 1,5 5,1 5,1 1),(2 2, 3 2, 3 3, 2 3,2 2))
 226         if (text.lower().find('polygon') == -1):
 227             return None
 228
 229         return shapely.wkt.loads(text)
 230
 231
 232     def drag_rectangle(self, v):
 233         """
 234         When we dtag a polygon in the plane, we drag it from its
 235         starting position to some terminal position. Since there are
 236         two 'drag vertices' on the polygon, we have two points
 237         corresponding to the drag vertices at both the initial
 238         location and the terminal location. From these four points, we
 239         can form a rectangle.
 240         """
 241         initial_dv = self.drag_vertices(v)
 242
 243         terminal_dv = [0, 0] # Just initializing it.
 244         terminal_dv[0] = initial_dv[0].add(v)
 245         terminal_dv[1] = initial_dv[1].add(v)
 246
 247         return Polygon( (initial_dv[1],
 248                          initial_dv[0],
 249                          terminal_dv[0],
 250                          terminal_dv[1]) )
 251
 252
 253     def drag(self, v):
 254         """
 255         Drag this polygon along the line v = (x2-x1, y2-y1), and
 256         return the new polygon consisting of the union of all points
 257         that I've contained along the way.
 258         """
 259         terminal_p = self.translate(v)
 260         dv_rect = self.drag_rectangle(v)
 261
 262         return self.union(dv_rect).union(terminal_p)