[postgis-devel] Point in polygon using winding order

[Stephen Woodbridge]

Hi Martin, Nicklas,

Thank you for the additional pointers. I figured you guys were probably 
aware of this, but it was new to me. Thank you for pointing out the 
robustness issue of dividing by zero or near zero.

Thanks,
   -Steve

PS: I spent 18 yrs in corporate life working for ComputerVision Corp 
building CAD/CAM systems, so I have had a long love of geometry and 
algorithms.

On 8/31/2015 1:20 AM, Martin Davis wrote:
> 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 <mailto: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 <mailto:postgis-devel at lists.osgeo.org>
>     http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel
>
>
>
>
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at lists.osgeo.org
> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel
>