Uploaded image for project: 'Lucene - Core'
  1. Lucene - Core
  2. LUCENE-7222

Improve Polygon.contains()

    XMLWordPrintableJSON

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 6.1, 7.0
    • Component/s: None
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      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:

      n=50   
      19.3 QPS -> 20.4 QPS
      n=500   
      9.8 QPS -> 11.2 QPS
      n=1000 
      6.3 QPS -> 7.4 QPS
      

      It also has some nice properties:

      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.

      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.

        Attachments

        1. LUCENE-7222.patch
          11 kB
          Robert Muir

          Issue Links

            Activity

              People

              • Assignee:
                Unassigned
                Reporter:
                rcmuir Robert Muir
              • Votes:
                0 Vote for this issue
                Watchers:
                3 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: