You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Karl Wright (JIRA)" <ji...@apache.org> on 2016/05/03 19:20:13 UTC
[jira] [Resolved] (LUCENE-7270) Use better balanced trees for Geo3d
complex polygons
[ https://issues.apache.org/jira/browse/LUCENE-7270?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Karl Wright resolved LUCENE-7270.
---------------------------------
Resolution: Fixed
Fix Version/s: 6.x
master
> Use better balanced trees for Geo3d complex polygons
> ----------------------------------------------------
>
> Key: LUCENE-7270
> URL: https://issues.apache.org/jira/browse/LUCENE-7270
> Project: Lucene - Core
> Issue Type: Improvement
> Components: modules/spatial3d
> Reporter: Karl Wright
> Assignee: Karl Wright
> Fix For: master, 6.x
>
>
> 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.)
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org