]>
gitweb.michael.orlitzky.com - dead/census-tools.git/blob - src/Geometry.py
8207b40465df1f23672c4173069f09016cfd6b80
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.
62 Print the contents of our ordered pair.
64 return "TwoVector<%d, %d>" % (self
.x
, self
.y
)
69 Returns the two-tuple underlying this TwoVector.
71 return (self
.x
, self
.y
)
74 def perpendicular(self
):
76 Return a vector perpendicular to ourself.
78 return TwoVector(-self
.y
, self
.x
)
81 def dot_product(self
, other_vector
):
83 Return the dot product of this vector with other_vector.
85 return (self
.x
* other_vector
.x
) + (self
.y
* other_vector
.y
)
88 def add(self
, other_vector
):
90 Add other_vector to this vector, and return a new TwoVector
91 containing the result.
93 return TwoVector(self
.x
+ other_vector
.x
, self
.y
+ other_vector
.y
)
99 Wraps shapely.geometry.Polygon.
102 def __init__(self
, points
=None):
104 We can initialize from either a set of two-tuples, or a set of
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
)
115 self
._shapely
_polygon
= shapely
.geometry
.Polygon(points
)
120 Override equality to test whether or not our boundary is equal
121 to the passed polygon's boundary.
126 # Shapely polygon exteriors know how to compare themselves.
127 ext1
= self
._shapely
_polygon
.exterior
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
)
140 Needed when we implement __eq__. Delegate it to our
141 shapely.geometry.Polygon.
143 return self
._shapely
_polygon
.__hash
__()
148 Write out the well-known text representation of this polygon.
150 return "Geometry.Polygon<%s>" % self
._shapely
_polygon
.to_wkt()
154 def from_shapely(self
, shapely_polygon
):
156 Create a Geometry.Polygon from the shapely.geometry.Polygon.
159 p
._shapely
_polygon
= shapely_polygon
165 An alias to retrieve our coordinates.
167 tuples
= self
._shapely
_polygon
.exterior
.coords
168 vectors
= map ( (lambda v
: TwoVector(v
[0], v
[1])), tuples
)
172 def union(self
, other_polygon
):
174 Return a new Polygon representing the union of this polygon
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
)
181 # Then, create a new Geometry.Polygon from that union.
182 return Polygon
.from_shapely(u
)
185 def translate(self
, v
):
187 Translate the self polygon by the TwoVector v.
189 regular_coords
= self
.coords()
190 f
= (lambda p
: p
.add(v
))
191 translated_coords
= map(f
, regular_coords
)
192 return Polygon(translated_coords
)
196 def drag_vertices(self
, v
):
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
204 v_perp
= v
.perpendicular()
206 current_min_vertex
= self
.coords()[0]
207 current_max_vertex
= self
.coords()[0]
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
213 if (w
.dot_product(v_perp
) > current_max_vertex
.dot_product(v_perp
)):
214 current_max_vertex
= w
216 return [current_min_vertex
, current_max_vertex
]
222 Create a Polygon from a Well-Known Text string.
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):
229 return shapely
.wkt
.loads(text
)
232 def drag_rectangle(self
, v
):
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.
241 initial_dv
= self
.drag_vertices(v
)
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
)
247 return Polygon( (initial_dv
[1],
255 Drag this polygon along the vector v = (x2-x1, y2-y1), and
256 return the new polygon consisting of the union of all points
257 that we've contained along the way.
259 terminal_p
= self
.translate(v
)
260 dv_rect
= self
.drag_rectangle(v
)
262 return self
.union(dv_rect
).union(terminal_p
)