[jira] [Commented] (LUCENE-7272) See if there's a way to cheapen geo3d's relationship calculations to make BKD Trees faster

["Karl Wright (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/LUCENE-7272?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15270566#comment-15270566 ] 

Karl Wright commented on LUCENE-7272:
-------------------------------------

The code for computing the relationship is as follows:

{code}
  public int getRelationship(final GeoShape path) {
    if (isWholeWorld) {
      if (path.getEdgePoints().length > 0)
        return WITHIN;
      return OVERLAPS;
    }
    
    /*
    for (GeoPoint p : getEdgePoints()) {
      System.err.println(" Edge point "+p+" path.isWithin()? "+path.isWithin(p));
    }
    
    for (GeoPoint p : path.getEdgePoints()) {
      System.err.println(" path edge point "+p+" isWithin()? "+isWithin(p)+" minx="+minXPlane.evaluate(p)+" maxx="+maxXPlane.evaluate(p)+" miny="+minYPlane.evaluate(p)+" maxy="+maxYPlane.evaluate(p)+" minz="+minZPlane.evaluate(p)+" maxz="+maxZPlane.evaluate(p));
    }
    */
    
    //System.err.println(this+" getrelationship with "+path);
    final int insideRectangle = isShapeInsideArea(path);
    if (insideRectangle == SOME_INSIDE) {
      //System.err.println(" some shape points inside area");
      return OVERLAPS;
    }

    // Figure out if the entire XYZArea is contained by the shape.
    final int insideShape = isAreaInsideShape(path);
    if (insideShape == SOME_INSIDE) {
      //System.err.println(" some area points inside shape");
      return OVERLAPS;
    }

    if (insideRectangle == ALL_INSIDE && insideShape == ALL_INSIDE) {
      //System.err.println(" inside of each other");
      return OVERLAPS;
    }

    if ((minXPlaneIntersects && path.intersects(minXPlane, notableMinXPoints, maxXPlane, minYPlane, maxYPlane, minZPlane, maxZPlane)) ||
        (maxXPlaneIntersects && path.intersects(maxXPlane, notableMaxXPoints, minXPlane, minYPlane, maxYPlane, minZPlane, maxZPlane)) ||
        (minYPlaneIntersects && path.intersects(minYPlane, notableMinYPoints, maxYPlane, minXPlane, maxXPlane, minZPlane, maxZPlane)) ||
        (maxYPlaneIntersects && path.intersects(maxYPlane, notableMaxYPoints, minYPlane, minXPlane, maxXPlane, minZPlane, maxZPlane)) ||
        (minZPlaneIntersects && path.intersects(minZPlane, notableMinZPoints, maxZPlane, minXPlane, maxXPlane, minYPlane, maxYPlane)) ||
        (maxZPlaneIntersects && path.intersects(maxZPlane, notableMaxZPoints, minZPlane, minXPlane, maxXPlane, minYPlane, maxYPlane))) {
      //System.err.println(" edges intersect");
      return OVERLAPS;
    }

    if (insideRectangle == ALL_INSIDE) {
      //System.err.println(" all shape points inside area");
      return WITHIN;
    }

    if (insideShape == ALL_INSIDE) {
      //System.err.println(" all area points inside shape");
      return CONTAINS;
    }
    //System.err.println(" disjoint");
    return DISJOINT;
  }
{code}

Note that it cannot decide between DISJOINT and CONTAINS until the very end, after it has done the expensive step of looking for intersections between the six planes and the shape.  So unfortunately it doesn't look like any shortcut is possible here.

> 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: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org