Quickly and robustly determines which region contains a given query point
Locates a point in a collection of regions. Point location is exact, takes O(log(n)) time, and the data structure has a space requirement of O(n log(n)).
//First create a list of verticesvar vertices =0 01 01 10 12 03 03 12 12.25 0.252.75 0.252.75 0.752.25 0.75//Regions are defined by lists of loops of vertex indicesvar regions =//First region, just a square, one loop0 1 2 3//Second region, square with a hole in the middle4 5 6 711 10 9 8 //Note inner loop has opposite orientation//Now we create the data structurevar classifyPoint = require"point-in-region"vertices regions//And we can use it to classify which region contains a given pointvar assert = require"assert"assertequalclassifyPoint0.5 0.5 0assertequalclassifyPoint2.1 0.1 1assertequalclassifyPoint100000 10000 -1 //Outside points return -1assertequalclassifyPoint2.5 0.5 -1 //Point in center hole is outside region
npm install point-in-region
Preprocesses a collection of regions to answer point location queries efficiently.
positionsis a list of vertex positions for each of the regions
regionsis a list of regions encoded as lists of clockwise oriented loops of indices
Returns A point membership classification function for the region set
Note The regions must obey certain topological and geometric properties for this classification to be correct. Specifically:
- Any two edges are either disjoint, identical, or meet at exactly one common end point
- The interior of each edge touches at most two regions
Returns the index of the region containing
pointis a 2D point encoded as a length 2 array
Returns The index of the region containing
-1 if it is not in any region.
(c) 2014 Mikola Lysenko. MIT License