[postgis-devel] Point in polygon using winding order

[Martin Davis]

This appears to be the well-known "stabbing-line" algorithm for computing
point-in-polygon.  This is implemented in JTS [1] and GEOS, and hence
presumably PostGIS as well?

The paper does not address the robustness issues which can occur when
determining whether a nearly-horizontal segment crosses the X axis to the
left or right of the query point (this causes an ill-conditioned deteminant
evaluation in step 2 of the algorithm given.)  The JTS/GEOS algorithm
contains special code to ensure that this case is handled robustly.

Possibly also of interest, the JTS code is structured in a way which allows
pre-computing a segment index on a polygon, to provide O(log n) performance
in the case of repeated tests against the same polygon.

[1]
https://sourceforge.net/p/jts-topo-suite/code/HEAD/tree/trunk/jts/java/src/com/vividsolutions/jts/algorithm/RayCrossingCounter.java

On Sun, Aug 30, 2015 at 7:43 PM, Stephen Woodbridge <woodbri at swoodbridge.com
> wrote:

> Hi,
>
> I needed to implement a fast point in polygon test in a script I was
> writing and came across this paper that I thought might be of interest
> here. PostGIS probably does not need it, but I thought it might be of
> interest to anyway.
>
> http://www.engr.colostate.edu/~dga/dga/papers/point_in_polygon.pdf
>
> Enjoy,
>   -Steve
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at lists.osgeo.org
> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20150830/3803cd4e/attachment.html>