Details
-
Improvement
-
Status: Resolved
-
Major
-
Resolution: Fixed
-
None
-
None
-
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.)