Polygon operations: primarily intersection testing, point-contains,
polygon->edges, bounding boxes, normal vectors, linear coordinates,
bisections, box intersections, bounded-space partitioning, and so on.


(bisect-region region)
Takes a region and returns two new regions, each representing one side of the axis-aligned
bisection of the original. Any edge crossing the bisecting line is split, and any gaps created by
bisection are filled by using segments from the bisecting line.


(bounded-space-partition region max-edge-length)
Returns an indexed structure that can be used to test points. The structure is repeatedly
bisected until each dimension is smaller than the given amount.


(box-contains? [[minlat minlng] [maxlat maxlng]] [lat lng])
Returns true if a bounding box contains the given point.


(boxes-intersect? [[x11 y11] [x12 y12]] [[x21 y21] [x22 y22]])
Returns true if two bounding boxes contain any common area. (Algorithm from


(degenerate? p1 p2)
Returns true if the edge's points are identical (i.e. the edge has no length).


(dist² v)


(dot [x1 y1] [x2 y2])


(edge-intersection [p11 p12] [p21 p22])
Returns the point of intersection of two edges. Behavior is undefined if the edges do not
intersect (use edges-intersect? to test), or if the two lines are parallel.


(edges->region bisecting-line edges)
Combines edges to form a new region. The bisecting line is required here because we need to infer
edges where there are gaps.


(edges-intersect? [p11 p12 :as e1] [p21 p22 :as e2])
Returns true if two edges intersect.



(line-contains? [p1 p2] p)
Returns true if a line contains a point.


(line-coordinate [p1 p2] p)
Returns the line-coordinate of the given point. Works best when the point is on the line.


(minus [x1 y1] [x2 y2])


(normal [x1 y1] [x2 y2])
Returns a normal vector for the given line. You can then take the dot product of points against
this vector to see which side of the line they are on.


(partitioned-poly-contains? partitioned-poly p)
Returns true if the partitioned poly contains the given point.


(partitioned-poly-intersects? partitioned-poly box)
Returns true if the partitioned polygon intersects the given box. The poly must be partitioned
such that the bounding boxes end up being no larger than the one being tested for.


(plus* [x y] [dx dy] factor)


(poly-contains? lat lng poly)
Used for implicitly-closed polys. Count the number of side-intersections for a ray extending from
[lat, ∞]; if even, the point is outside.

poly should be of this form:

[[[lat1 lng1 lat2 lng2 ... latk lngk] [latk+1 lngk+1 ... ]]   ; one poly with a hole
 [[latj lngj latj+1 lngj+1 ...] ...]                          ; another poly with a hole


[[[& include] [& exclude] [& exclude] ...]
 [[& include] [& exclude] ...]

The toplevel array is considered to be the union of its elements.


(positive-side? [p1 p2] p)
Returns true if the given point is on the "positive side" of the line. Positive and negative
sides are deterministic and consistent, so you can use this with a line to partition space.


(region-bounding-box region)
Returns a bounding box for the given region. The bounding box is returned as [[minlat minlng]
[maxlat maxlng]].


(region-contains? lat lng points)
Returns true if the bounded region contains the point. The region need not
be convex, and its edges may intersect. It must contain at least three
points. Algorithm from

This would normally be written as a reduction, but the first/last points wrap


(region-edges region)
Returns a list of [[lat1 lng1] [lat2 lng2]], each of which describes an edge of the region. The
region is implicitly closed.


(single-poly-contains? lat lng [include & exclude])
Uses edge intersection testing to determine whether a single bounded shape
contains the given point.


(split-edge line [p1 p2 :as edge])
Takes a line and an edge, and returns two new edges, the first of which is on the positive side
of the line and the second of which is on the negative side. The line and the edge must