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

Use better balanced trees for Geo3d complex polygons

    Details

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

      Description

      The current tree data structure in GeoComplexPolygon has a lot of weaknesses. A better algorithm maybe can be taken from Polygon2D, which basically does the following:

      Each node has:

      • low value (which is for that edge alone)
      • max value (which is for that edge and all children)

      Balanced tree building:

      • sort by low value (which is for the individual edge), and use max value as tie breaker (which is max for edge and all children)
      • build tree after sorting, picking midpoint and recursively building lesser and greater children that way

      Balanced tree traversal (looking for range minValue -> maxValue):

      • Descend the entire tree until the node fails this test:
        if (minValue <= max) { ... }

        So if the minimum value being sought is greater than the max for this edge and all children, we stop and don't look at children.
        (Q: does this represent a good split and a targeted range? Maybe... We can certainly try it.)

        Attachments

          Activity

            People

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

              Dates

              • Created:
                Updated:
                Resolved: