[jira] [Commented] (LUCENE-7222) Improve Polygon.contains()

["Michael McCandless (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/LUCENE-7222?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15242657#comment-15242657 ] 

Michael McCandless commented on LUCENE-7222:
--------------------------------------------

+1, nice!

> Improve Polygon.contains()
> --------------------------
>
>                 Key: LUCENE-7222
>                 URL: https://issues.apache.org/jira/browse/LUCENE-7222
>             Project: Lucene - Core
>          Issue Type: Bug
>            Reporter: Robert Muir
>         Attachments: LUCENE-7222.patch
>
>
> The current PIP algorithm could use some improvements. I think we should swap in the algorithm here: https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html
> It is a bit faster for complex polygons:
> {noformat}
> n=50   
> 19.3 QPS -> 20.4 QPS
> n=500   
> 9.8 QPS -> 11.2 QPS
> n=1000 
> 6.3 QPS -> 7.4 QPS
> {noformat}
> It also has some nice properties:
> {quote}
>  if you partition a region of the plane into polygons, i.e., form a planar graph, then PNPOLY will locate each point into exactly one polygon. In other words, PNPOLY considers each polygon to be topologically a semi-open set. This makes things simpler, i.e., causes fewer special cases, if you use PNPOLY as part of a larger system. Examples of this include locating a point in a planar graph, and intersecting two planar graphs. 
> {quote}
> You can see the current issues here by writing tests that pick numbers that won't suffer from rounding errors, to see how the edges behave. For a rectangle as an example, the current code will treat all edges and corners as "contains=true", except for the top edge. This means that if you tried to e.g. form a grid of rectangles (like described above), some points would exist in more than one square.
> On the other hand if you port this same test to java.awt.Polygon, you will see that only the bottom left corner, bottom side, and left side are treated as "contains=true". So then your grid would work without any corner cases. This algorithm behaves the same way.
> Finally, it supports multiple components and holes directly. this is nice for the future because for a complex multipolygon, we can just have one tight loop.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org