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

Improve algorithm for randomly finding an interior point for Geo3D polygons

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Resolved
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 6.0
    • Fix Version/s: 6.0
    • Component/s: modules/spatial3d
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      Michael McCandless's benchmark for polygon search shows that constructing Geo3D polygon queries is quite expensive compared to other technologies. My belief is that this is due largely to how an interior point for determination of clockwise/counterclockwise are found: this is currently searched for randomly across the entire globe.

      I suspect that we could replace this algorithm with a random algorithm that uses one of the polygon's edge points and looks randomly within a small distance of that point. This would greatly reduce the number of failed attempts to find a "pole" (as I call it).

        Attachments

          Activity

            People

            • Assignee:
              kwright@metacarta.com Karl Wright
              Reporter:
              kwright@metacarta.com Karl Wright
            • Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: