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 __add__(self, other_vector):
  61         """
  62         Add other_vector to this vector, and return a new TwoVector
  63         containing the result.
  64         """
  65         return TwoVector(self.x + other_vector.x, self.y + other_vector.y)
  66
  67
  68     def __sub__(self, other_vector):
  69         """
  70         Subtract other_vector from this vector. Return a new
  71         TwoVector.
  72         """
  73         return TwoVector(self.x - other_vector.x, self.y - other_vector.y)
  74
  75
  76     def __str__(self):
  77         """
  78         Print the contents of our ordered pair.
  79         """
  80         return "TwoVector<%d, %d>" % (self.x, self.y)
  81
  82
  83     def to_tuple(self):
  84         """
  85         Returns the two-tuple underlying this TwoVector.
  86         """
  87         return (self.x, self.y)
  88
  89
  90     def perpendicular(self):
  91         """
  92         Return a vector perpendicular to ourself.
  93         """
  94         return TwoVector(-self.y, self.x)
  95
  96
  97     def dot_product(self, other_vector):
  98         """
  99         Return the dot product of this vector with other_vector.
 100         """
 101         return (self.x * other_vector.x) + (self.y * other_vector.y)
 102
 103
 104
 105 class Polygon:
 106     """
 107     Wraps shapely.geometry.Polygon.
 108     """
 109
 110     def __init__(self, points=None):
 111         """
 112         We can initialize from either a set of two-tuples, or a set of
 113         TwoVectors.
 114         """
 115         if (points == None):
 116             return
 117
 118         # Is the first element of points a TwoVector?
 119         if ( (len(points) > 0) and isinstance(points[0], TwoVector) ):
 120             # If so, convert points to a list of two-tuples.
 121             points = map ( (lambda p: p.to_tuple()), points )
 122
 123         self._shapely_polygon = shapely.geometry.Polygon(points)
 124
 125
 126     def __eq__(self, p):
 127         """
 128         Override equality to test whether or not our boundary is equal
 129         to the passed polygon's boundary.
 130         """
 131         if (p == None):
 132             return False
 133
 134         # Shapely polygon exteriors know how to compare themselves.
 135         ext1 = self._shapely_polygon.exterior
 136
 137         if isinstance(p, Polygon):
 138             ext2 = p._shapely_polygon.exterior
 139             return ext1.equals(ext2)
 140         elif isinstance(p, shapely.geometry.Polygon):
 141             return ext1.equals(p)
 142         else:
 143             return False
 144
 145
 146     def __hash__(self):
 147         """
 148         Needed when we implement __eq__. Delegate it to our
 149         shapely.geometry.Polygon.
 150         """
 151         return self._shapely_polygon.__hash__()
 152
 153
 154     def __str__(self):
 155         """
 156         Write out the well-known text representation of this polygon,
 157         as well as the class name, which helps distinguish
 158         Geometry.Polygon from shapely.geometry.Polygon..
 159         """
 160         return "Geometry.Polygon<%s>" % self._shapely_polygon.to_wkt()
 161
 162
 163     def wkt(self):
 164         """
 165         Return just the well-known text for this Polygon.
 166         """
 167         return self._shapely_polygon.to_wkt()
 168
 169
 170     @classmethod
 171     def from_shapely(self, shapely_polygon):
 172         """
 173         Create a Geometry.Polygon from the shapely.geometry.Polygon.
 174         """
 175         p = Polygon()
 176         p._shapely_polygon = shapely_polygon
 177         return p
 178
 179
 180     def coords(self):
 181         """
 182         An alias to retrieve our coordinates.
 183         """
 184         tuples = self._shapely_polygon.exterior.coords
 185         vectors = map ( (lambda v: TwoVector(v[0], v[1])), tuples)
 186         return vectors
 187
 188
 189     def union(self, other_polygon):
 190         """
 191         Return a new Polygon representing the union of this polygon
 192         and other_polygon.
 193         """
 194         # First, get the union of self and other_polygon as a
 195         # shapely.geometry.Polygon.
 196         u = self._shapely_polygon.union(other_polygon._shapely_polygon)
 197
 198         # Then, create a new Geometry.Polygon from that union.
 199         return Polygon.from_shapely(u)
 200
 201
 202     def translate(self, v):
 203         """
 204         Translate the self polygon by the TwoVector v.
 205         """
 206         regular_coords = self.coords()
 207         f = (lambda p: p + v)
 208         translated_coords = map(f, regular_coords)
 209         return Polygon(translated_coords)
 210
 211
 212
 213     def drag_vertices(self, v):
 214         """
 215         The vector v is that vector along which we are 'dragging' the
 216         polygon. If we are dragging from p1 = (x1,y1) to p2 = (x2,y2),
 217         then v = (x2-x1, y2-y1). The 'drag' vertices of a polygon are
 218         those two vertices which are most/least in the direction of
 219         the v_perp.
 220         """
 221         v_perp = v.perpendicular()
 222
 223         current_min_vertex = self.coords()[0]
 224         current_max_vertex = self.coords()[0]
 225
 226         for w in self.coords():
 227             if (w.dot_product(v_perp) < current_min_vertex.dot_product(v_perp)):
 228                 current_min_vertex = w
 229
 230             if (w.dot_product(v_perp) > current_max_vertex.dot_product(v_perp)):
 231                 current_max_vertex = w
 232
 233         return [current_min_vertex, current_max_vertex]
 234
 235
 236     @staticmethod
 237     def from_wkt(text):
 238         """
 239         Create a Polygon from a Well-Known Text string.
 240         """
 241         # The WKT string must contain the word "polygon" at least.
 242         # Ex: POLYGON((1 1,5 1,5 5,1 5,1 1),(2 2, 3 2, 3 3, 2 3,2 2))
 243         if (text.lower().find('polygon') == -1):
 244             return None
 245
 246         sp = shapely.wkt.loads(text)
 247         return Polygon.from_shapely(sp)
 248
 249
 250     def drag_rectangle(self, v):
 251         """
 252         When we dtag a polygon in the plane, we drag it from its
 253         starting position to some terminal position. Since there are
 254         two 'drag vertices' on the polygon, we have two points
 255         corresponding to the drag vertices at both the initial
 256         location and the terminal location. From these four points, we
 257         can form a rectangle.
 258         """
 259         initial_dv = self.drag_vertices(v)
 260
 261         terminal_dv = [0, 0] # Just initializing it.
 262         terminal_dv[0] = initial_dv[0] + v
 263         terminal_dv[1] = initial_dv[1] + v
 264
 265         return Polygon( (initial_dv[1],
 266                          initial_dv[0],
 267                          terminal_dv[0],
 268                          terminal_dv[1]) )
 269
 270
 271     def drag(self, v):
 272         """
 273         Drag this polygon along the vector v = (x2-x1, y2-y1), and
 274         return the new polygon consisting of the union of all points
 275         that we've contained along the way.
 276         """
 277         terminal_p = self.translate(v)
 278         dv_rect = self.drag_rectangle(v)
 279
 280         return self.union(dv_rect).union(terminal_p)