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

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

Details

    • Improvement
    • Status: Closed
    • Major
    • Resolution: Fixed
    • None
    • 6.1, 7.0
    • None
    • None
    • 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

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

              Dates

                Created:
                Updated:
                Resolved: