]>
gitweb.michael.orlitzky.com - dead/census-tools.git/blob - src/Geometry.py
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.
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')
18 import shapely
.geometry
25 Represents a two-dimensional vector.
28 def __init__(self
, x
=0, y
=0):
35 We have to define __hash__ in order to override __eq__.
36 Just return the hash of our ordered pair.
38 return (self
.x
, self
.y
).__hash
__()
43 We would like to override equality to compare against our
44 underlying ordered pair.
49 if isinstance (v
, TwoVector
):
50 return ( (self
.x
== v
.x
) and (self
.y
== v
.y
) )
52 # If it's not a TwoVector, assume that it's a tuple.
54 return (self
.x
== v
[0]) and (self
.y
== v
[1])
56 # If v is neither a TwoVector nor a tuple, we ain't it.
60 def __add__(self
, other_vector
):
62 Add other_vector to this vector, and return a new TwoVector
63 containing the result.
65 return TwoVector(self
.x
+ other_vector
.x
, self
.y
+ other_vector
.y
)
68 def __sub__(self
, other_vector
):
70 Subtract other_vector from this vector. Return a new
73 return TwoVector(self
.x
- other_vector
.x
, self
.y
- other_vector
.y
)
78 Print the contents of our ordered pair.
80 return "TwoVector<%d, %d>" % (self
.x
, self
.y
)
85 Returns the two-tuple underlying this TwoVector.
87 return (self
.x
, self
.y
)
90 def perpendicular(self
):
92 Return a vector perpendicular to ourself.
94 return TwoVector(-self
.y
, self
.x
)
97 def dot_product(self
, other_vector
):
99 Return the dot product of this vector with other_vector.
101 return (self
.x
* other_vector
.x
) + (self
.y
* other_vector
.y
)
107 Wraps shapely.geometry.Polygon.
110 def __init__(self
, points
=None):
112 We can initialize from either a set of two-tuples, or a set of
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
)
123 self
._shapely
_polygon
= shapely
.geometry
.Polygon(points
)
128 Override equality to test whether or not our boundary is equal
129 to the passed polygon's boundary.
134 # Shapely polygon exteriors know how to compare themselves.
135 ext1
= self
._shapely
_polygon
.exterior
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
)
148 Needed when we implement __eq__. Delegate it to our
149 shapely.geometry.Polygon.
151 return self
._shapely
_polygon
.__hash
__()
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..
160 return "Geometry.Polygon<%s>" % self
._shapely
_polygon
.to_wkt()
165 Return just the well-known text for this Polygon.
167 return self
._shapely
_polygon
.to_wkt()
171 def from_shapely(self
, shapely_polygon
):
173 Create a Geometry.Polygon from the shapely.geometry.Polygon.
176 p
._shapely
_polygon
= shapely_polygon
182 An alias to retrieve our coordinates.
184 tuples
= self
._shapely
_polygon
.exterior
.coords
185 vectors
= map ( (lambda v
: TwoVector(v
[0], v
[1])), tuples
)
189 def union(self
, other_polygon
):
191 Return a new Polygon representing the union of this polygon
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
)
198 # Then, create a new Geometry.Polygon from that union.
199 return Polygon
.from_shapely(u
)
202 def translate(self
, v
):
204 Translate the self polygon by the TwoVector v.
206 regular_coords
= self
.coords()
207 f
= (lambda p
: p
+ v
)
208 translated_coords
= map(f
, regular_coords
)
209 return Polygon(translated_coords
)
213 def drag_vertices(self
, v
):
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
221 v_perp
= v
.perpendicular()
223 current_min_vertex
= self
.coords()[0]
224 current_max_vertex
= self
.coords()[0]
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
230 if (w
.dot_product(v_perp
) > current_max_vertex
.dot_product(v_perp
)):
231 current_max_vertex
= w
233 return [current_min_vertex
, current_max_vertex
]
239 Create a Polygon from a Well-Known Text string.
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):
246 sp
= shapely
.wkt
.loads(text
)
247 return Polygon
.from_shapely(sp
)
250 def drag_rectangle(self
, v
):
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.
259 initial_dv
= self
.drag_vertices(v
)
261 terminal_dv
= [0, 0] # Just initializing it.
262 terminal_dv
[0] = initial_dv
[0] + v
263 terminal_dv
[1] = initial_dv
[1] + v
265 return Polygon( (initial_dv
[1],
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.
277 terminal_p
= self
.translate(v
)
278 dv_rect
= self
.drag_rectangle(v
)
280 return self
.union(dv_rect
).union(terminal_p
)