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

Speed up LatLonPoint's polygon queries when there are many vertices

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • 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

      This is inspired by the "reliability and numerical stability" recommendations at the end of http://www-ma2.upc.es/geoc/Schirra-pointPolygon.pdf.

      Basically our polys need to answer two questions that are slow today:
      contains(point)
      crosses(rectangle)

      Both of these ops only care about a subset of edges: the ones overlapping a y interval range. We can organize these edges in an interval tree to be practical and speed things up a lot. Worst case is still O but those solutions are more complex to do.

        Attachments

        1. LUCENE-7239.patch
          26 kB
          Robert Muir
        2. LUCENE-7239.patch
          27 kB
          Robert Muir

          Issue Links

            Activity

              People

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

                Dates

                • Created:
                  Updated:
                  Resolved: