[
https://issues.apache.org/jira/browse/LUCENE-7222?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Robert Muir resolved LUCENE-7222.
---------------------------------
Resolution: Fixed
Fix Version/s: 6.1
master
> Improve Polygon.contains()
> --------------------------
>
> Key: LUCENE-7222
> URL: https://issues.apache.org/jira/browse/LUCENE-7222
> Project: Lucene - Core
> Issue Type: Bug
> Reporter: Robert Muir
> Fix For: master, 6.1
>
> 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: [email protected]
For additional commands, e-mail: [email protected]
