- It is implemented as an iteration over a data structure representing a sequence of line segments. This ties the algorithm to a fixed data structure, which leads to code duplication
- It handles simple rings, but not fully general polygons (which may contain holes and/or multiple shells)
- It does not detect the case where the query point lies on one of the segments in the polygon
- It runs in O(n) time. This is reasonable for a single query point, but is not the most efficient way to perform many point queries against a single fixed polygon
- It uses conventional floating-point arithmetic. This makes it non-robust (i.e. potentially incorrect for some inputs)

Most recently, I've revisited P-I-P in the course of some work on improving the performance of spatial predicates. And I think I've finally arrived at the ultimate Point-In-Polygon implementation. It removes all of the above limitations with the following design features:

- It uses an incremental design, which frees the algorithm from being tied to any particular segment data structure
- It handles all polygonal geometry types defined in JTS. (Implementing this was made much cleaner by the pleasant realization that the PIP algorithm really doesn't care where in a polygonal geometry the segments come from. The only thing that matters is the parity of the segment crossings. This holds true for any number of holes and shells.)
- It detcts the point-on-segment case, and reports it via a trivalent return value (in the set {INTERIOR, BOUNDARY, EXTERIOR}).
- It is straightforward to use with a spatial index on the segments of the polygon (such as STRtree or BinTree), thus providing O(log n) performance
- Thanks to the RobustDeterminant class in JTS, the implementation is much more robust. (Due to some remaining floating-point arithmetic it may still not be 100% robust - but I hope to address that sometime as well.)

Coming soon to a JTS version near you...

## 1 comment:

Hi Martin, I think I will come more often back to this blog, you should have told at the conference :)

I already used some of your tricks from the foss4g presentation. Now I can't wait to try the 1.9 whenever it comes.

Great job man!

Post a Comment