Karl Wright created LUCENE-7272:
-----------------------------------
Summary: See if there's a way to cheapen geo3d's relationship
calculations to make BKD Trees faster
Key: LUCENE-7272
URL: https://issues.apache.org/jira/browse/LUCENE-7272
Project: Lucene - Core
Issue Type: Improvement
Components: modules/spatial3d
Affects Versions: master
Reporter: Karl Wright
Assignee: Karl Wright
BKD Tree code does not make use of most of the fine relationship detail
returned by getRelationship(). This means a lot of computation is going into
figuring out fine details that gets simply wasted. We should consider having a
much simpler related relationship method that returns only what BKD trees need
to proceed.
Here's the current code:
{code}
// First, check bounds. If the shape is entirely contained, return
CELL_CROSSES_QUERY.
if (shapeBounds.getMinimumX() >= xMin && shapeBounds.getMaximumX() <= xMax
&&
shapeBounds.getMinimumY() >= yMin && shapeBounds.getMaximumY() <= yMax &&
shapeBounds.getMinimumZ() >= zMin && shapeBounds.getMaximumZ() <= zMax) {
return Relation.CELL_CROSSES_QUERY;
}
// Quick test failed so do slower one...
GeoArea xyzSolid = GeoAreaFactory.makeGeoArea(PlanetModel.WGS84, xMin,
xMax, yMin, yMax, zMin, zMax);
switch(xyzSolid.getRelationship(shape)) {
case GeoArea.CONTAINS:
// Shape fully contains the cell
//System.out.println(" inside");
return Relation.CELL_INSIDE_QUERY;
case GeoArea.OVERLAPS:
// They do overlap but neither contains the other:
//System.out.println(" crosses1");
return Relation.CELL_CROSSES_QUERY;
case GeoArea.WITHIN:
// Cell fully contains the shape:
//System.out.println(" crosses2");
// return Relation.SHAPE_INSIDE_CELL;
return Relation.CELL_CROSSES_QUERY;
case GeoArea.DISJOINT:
// They do not overlap at all
//System.out.println(" outside");
return Relation.CELL_OUTSIDE_QUERY;
default:
assert false;
return Relation.CELL_CROSSES_QUERY;
}
{code}
It looks like only CELL_CROSSES_QUERY, CELL_OUTSIDE_QUERY, and
CELL_INSIDE_QUERY are ever returned. This means we could (if computationally
helpful) have a getRelationship() variant that only distinguishes between:
GeoArea.DISJOINT
GeoArea.CONTAINS
GeoArea.OVERLAPS
... with no GeoArea.WITHIN detection. The question is, would this save
significant computation?
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
