<div dir="ltr">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?<div><br></div><div>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.  </div><div><br></div><div>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.<br><div><br></div><div>[1] <a href="https://sourceforge.net/p/jts-topo-suite/code/HEAD/tree/trunk/jts/java/src/com/vividsolutions/jts/algorithm/RayCrossingCounter.java">https://sourceforge.net/p/jts-topo-suite/code/HEAD/tree/trunk/jts/java/src/com/vividsolutions/jts/algorithm/RayCrossingCounter.java</a></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Aug 30, 2015 at 7:43 PM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi,<br>
<br>
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.<br>
<br>
<a href="http://www.engr.colostate.edu/~dga/dga/papers/point_in_polygon.pdf" rel="noreferrer" target="_blank">http://www.engr.colostate.edu/~dga/dga/papers/point_in_polygon.pdf</a><br>
<br>
Enjoy,<br>
  -Steve<br>
_______________________________________________<br>
postgis-devel mailing list<br>
<a href="mailto:postgis-devel@lists.osgeo.org" target="_blank">postgis-devel@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel" rel="noreferrer" target="_blank">http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel</a><br>
</blockquote></div><br></div>