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

Improve Polygon.relate

    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 method is currently quite slow and in many cases does more work than is required. The speed actually directly impacts queries (tree traversal) and bounds grid size to something tiny making it less effective.

      I think we should replace it line intersections based on orientation methods described here http://www.cs.berkeley.edu/~jrs/meshpapers/robnotes.pdf and https://www.cs.cmu.edu/~quake/robust.html

      For one, a naive implementation is considerably faster than the method today: both because it reduces the cost of BKD tree traversals and also because it makes grid construction cheaper. This means we can increase its level of detail with similar or lower startup cost. Now its more like a Mario Brothers 2 picture of your polygon instead of Space Invaders.

      Synthetic polygons from luceneUtil

      vertices old QPS new QPS old startup cost new startup cost
      50 20.4 21.7 1ms 1ms
      500 11.2 14.4 5ms 4ms
      1000 7.4 10.0 9ms 8ms

      Real polygons (33 london districts: http://data.london.gov.uk/2011-boundary-files)

      vertices old QPS new QPS old startup cost new startup cost
      avg 5.6k 4.9 8.6 94ms 85ms

      But I also like using this method because its possible to extend it to remove floating point error completely in the future with techniques described in those links. This may be necessary if we want to do smarter things (e.g. not linear time).

        Attachments

        1. LUCENE-7229.patch
          7 kB
          Robert Muir
        2. LUCENE-7229.patch
          7 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: