[
https://issues.apache.org/jira/browse/LUCENE-7270?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15268819#comment-15268819
]
Karl Wright commented on LUCENE-7270:
-------------------------------------
For reference, here's my entire tree implementation.
{code}
private static abstract class Tree {
private final Node rootNode;
protected static final Edge[] EMPTY_ARRAY = new Edge[0];
/** Constructor.
* @param allEdges is the list of all edges for the tree.
*/
public Tree(final List<Edge> allEdges) {
// Dump edges into an array and then sort it
final Node[] edges = new Node[allEdges.size()];
int i = 0;
for (final Edge edge : allEdges) {
edges[i++] = new Node(edge, getMinimum(edge), getMaximum(edge));
}
Arrays.sort(edges, (left, right) -> {
int ret = Double.compare(left.low, right.low);
if (ret == 0) {
ret = Double.compare(left.max, right.max);
}
return ret;
});
rootNode = createTree(edges, 0, edges.length - 1);
}
private static Node createTree(final Node[] edges, final int low, final int
high) {
if (low > high) {
return null;
}
// add midpoint
int mid = (low + high) >>> 1;
final Node newNode = edges[mid];
// add children
newNode.left = createTree(edges, low, mid - 1);
newNode.right = createTree(edges, mid + 1, high);
// pull up max values to this node
if (newNode.left != null) {
newNode.max = Math.max(newNode.max, newNode.left.max);
}
if (newNode.right != null) {
newNode.max = Math.max(newNode.max, newNode.right.max);
}
return newNode;
}
/** Get the minimum value from the edge.
* @param edge is the edge.
* @return the minimum value.
*/
protected abstract double getMinimum(final Edge edge);
/** Get the maximum value from the edge.
* @param edge is the edge.
* @return the maximum value.
*/
protected abstract double getMaximum(final Edge edge);
/** Traverse the tree, finding all edges that intersect the provided value.
* @param edgeIterator provides the method to call for any encountered
matching edge.
* @param value is the value to match.
* @return false if the traversal was aborted before completion.
*/
public boolean traverse(final EdgeIterator edgeIterator, final double
value) {
return traverse(edgeIterator, value, value);
}
/** Traverse the tree, finding all edges that intersect the provided value
range.
* @param edgeIterator provides the method to call for any encountered
matching edge.
* Edges will not be invoked more than once.
* @param minValue is the minimum value.
* @param maxValue is the maximum value.
* @return false if the traversal was aborted before completion.
*/
public boolean traverse(final EdgeIterator edgeIterator, final double
minValue, final double maxValue) {
return traverse(rootNode, edgeIterator, minValue, maxValue);
}
private static boolean traverse(final Node node, final EdgeIterator
edgeIterator, final double minValue, final double maxValue) {
if (node == null) {
return true;
}
if (minValue <= node.max) {
// Does this node overlap?
if (minValue <= node.high && maxValue >= node.low) {
if (edgeIterator.matches(node.edge) == false) {
return false;
}
}
if (traverse(node.left, edgeIterator, minValue, maxValue) == false) {
return false;
}
if (traverse(node.right, edgeIterator, minValue, maxValue) == false) {
return false;
}
}
return true;
}
}
{code}
> 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
>
> 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: [email protected]
For additional commands, e-mail: [email protected]
