lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Hoss Man (JIRA)" <j...@apache.org>
Subject [jira] [Updated] (LUCENE-7222) Improve Polygon.contains()
Date Mon, 09 May 2016 23:09:12 GMT

     [ https://issues.apache.org/jira/browse/LUCENE-7222?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Hoss Man updated LUCENE-7222:
-----------------------------
    Fix Version/s:     (was: 6.0)
                   master (7.0)


Manually correcting fixVersion per Step #S5 of LUCENE-7271


> 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: 6.1, master (7.0)
>
>         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


Mime
View raw message