[
https://issues.apache.org/jira/browse/LUCENE-7906?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16101694#comment-16101694
]
Karl Wright commented on LUCENE-7906:
-------------------------------------
The 2D tree creation code now looks like this:
{code}
/**
* Creates an edge interval tree from a set of polygon vertices.
* @return root node of the tree.
*/
private static Edge createTree(double polyLats[], double polyLons[]) {
Edge edges[] = new Edge[polyLats.length - 1];
for (int i = 1; i < polyLats.length; i++) {
double lat1 = polyLats[i-1];
double lon1 = polyLons[i-1];
double lat2 = polyLats[i];
double lon2 = polyLons[i];
edges[i - 1] = new Edge(lat1, lon1, lat2, lon2, Math.min(lat1, lat2),
Math.max(lat1, lat2));
}
// sort the edges then build a balanced tree from them
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;
});
return createTree(edges, 0, edges.length - 1);
}
/** Creates tree from sorted edges (with range low and high inclusive) */
private static Edge createTree(Edge edges[], int low, int high) {
if (low > high) {
return null;
}
// add midpoint
int mid = (low + high) >>> 1;
Edge 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;
}
{code}
If we adopt the new membership code we would need to adapt the new tree
construction code as well.
> Spatial relationship between Geoshapes
> --------------------------------------
>
> Key: LUCENE-7906
> URL: https://issues.apache.org/jira/browse/LUCENE-7906
> Project: Lucene - Core
> Issue Type: Improvement
> Components: modules/spatial3d
> Reporter: Ignacio Vera
> Assignee: Karl Wright
> Attachments: LUCENE-7906.patch
>
>
> Hi,
> Working with geosahpes and trying to resolve spatial relationships between
> them I came accross a big limitation when trying to solve the relationship
> between two geopolygons. This object does not expose the internal structure.
> In particular at some point, it is necessary to check if one polygon
> intersects the edges of the other polygon which currently is not possible as
> edges are not exposed.
> To be able to perform such operation it can be several options. The ones I
> can think of are:
> 1) Expose the edges of the polygon ( and probably the notable points for the
> edges) adding getters in the GeoPolygon interface. Easy to implement and
> leave users the responsability of coding the spatial relationship.
> 2) Extends GeoPolygon interface to extends geoarea and leave the object make
> the spatial relationship.
> 3) Extends GeoShape interface so all shapes can infer the spatial
> relationship with other GeoShapes.
> I might be bias as my interest is in 2d Shapes in the unit sphere and there
> might be some cases which what I propose cannot be implemented or are againts
> the aim of the library.
> What do you think?
> Cheers,
> Ignacio
--
This message was sent by Atlassian JIRA
(v6.4.14#64029)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
