geo.poly — factual/geo 3.0.0-rc-2

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 clj

(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 clj

(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? clj

(box-contains? [[minlat minlng] [maxlat maxlng]] [lat lng])

Returns true if a bounding box contains the given point.

boxes-intersect? clj

(boxes-intersect? [[x11 y11] [x12 y12]] [[x21 y21] [x22 y22]])

Returns true if two bounding boxes contain any common area. (Algorithm from http://stackoverflow.com/questions/306316/determine-if-two-rectangles-overlap-each-other)

degenerate? clj

(degenerate? p1 p2)

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

dist² clj

(dist² v)

dot clj

(dot [x1 y1] [x2 y2])

edge-intersection clj

(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 clj

(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? clj

(edges-intersect? [p11 p12 :as e1] [p21 p22 :as e2])

Returns true if two edges intersect.

EPSILON clj

line-contains? clj

(line-contains? [p1 p2] p)

Returns true if a line contains a point.

line-coordinate clj

(line-coordinate [p1 p2] p)

Returns the line-coordinate of the given point. Works best when the point is on the line.

minus clj

(minus [x1 y1] [x2 y2])

normal clj

(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? clj

(partitioned-poly-contains? partitioned-poly p)

Returns true if the partitioned poly contains the given point.

partitioned-poly-intersects? clj

(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* clj

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

poly-contains? clj

(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 ...]

Specifically:

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

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

positive-side? clj

(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 clj

(region-bounding-box region)

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

region-contains? clj

(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 http://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test.

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

region-edges clj

(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? clj

(single-poly-contains? lat lng [include & exclude])

Uses edge intersection testing to determine whether a single bounded shape contains the given point.

split-edge clj

(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 intersect.