LUCENE-8680: Refactor EdgeTree#relateTriangle method

diff --git a/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java b/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
index 084c9a8..55a3379 100644 (file)
--- a/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
@@ -124,12 +124,12 @@ public abstract class EdgeTree {
     return Relation.CELL_OUTSIDE_QUERY;
   }
 
-  protected Relation componentRelate(double minLat, double maxLat, double minLon, double maxLon) {
-    return null;
-  }
-  protected Relation componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
-    return null;
-  }
+  /** Returns relation to the provided rectangle for this component */
+  protected abstract Relation componentRelate(double minLat, double maxLat, double minLon, double maxLon);
+
+  /** Returns relation to the provided triangle for this component */
+  protected abstract Relation componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy);
+
 
   private Relation internalComponentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
     // compute bounding box of triangle
@@ -140,22 +140,7 @@ public abstract class EdgeTree {
     if (maxLon < this.minLon || minLon > this.maxLon || maxLat < this.minLat || minLat > this.maxLat) {
       return Relation.CELL_OUTSIDE_QUERY;
     }
-
-    Relation shapeRelation = componentRelateTriangle(ax, ay, bx, by, cx, cy);
-    if (shapeRelation != null) {
-      return shapeRelation;
-    }
-
-    // we cross
-    if ((shapeRelation = tree.relateTriangle(ax, ay, bx, by, cx, cy)) != Relation.CELL_OUTSIDE_QUERY) {
-      return shapeRelation;
-    }
-
-    if (pointInTriangle(tree.lon1, tree.lat1, ax, ay, bx, by, cx, cy) == true) {
-      return Relation.CELL_CROSSES_QUERY;
-    }
-
-    return Relation.CELL_OUTSIDE_QUERY;
+    return componentRelateTriangle(ax, ay, bx, by, cx, cy);
   }
 
 
@@ -169,18 +154,7 @@ public abstract class EdgeTree {
     if (minLat <= this.minLat && maxLat >= this.maxLat && minLon <= this.minLon && maxLon >= this.maxLon) {
       return Relation.CELL_CROSSES_QUERY;
     }
-
-    Relation shapeRelation = componentRelate(minLat, maxLat, minLon, maxLon);
-    if (shapeRelation != null) {
-      return shapeRelation;
-    }
-
-    // we cross
-    if (tree.crosses(minLat, maxLat, minLon, maxLon)) {
-      return Relation.CELL_CROSSES_QUERY;
-    }
-
-    return Relation.CELL_OUTSIDE_QUERY;
+    return componentRelate(minLat, maxLat, minLon, maxLon);
   }
 
   /** Creates tree from sorted components (with range low and high inclusive) */
@@ -402,7 +376,7 @@ public abstract class EdgeTree {
   //This should be moved when LatLonShape is moved from sandbox!
   /**
    * Compute whether the given x, y point is in a triangle; uses the winding order method */
-  private static boolean pointInTriangle (double x, double y, double ax, double ay, double bx, double by, double cx, double cy) {
+  protected static boolean pointInTriangle (double x, double y, double ax, double ay, double bx, double by, double cx, double cy) {
     double minX = StrictMath.min(ax, StrictMath.min(bx, cx));
     double minY = StrictMath.min(ay, StrictMath.min(by, cy));
     double maxX = StrictMath.max(ax, StrictMath.max(bx, cx));

diff --git a/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java b/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
index c90970a..0ba3d51 100644 (file)
--- a/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
@@ -79,52 +79,63 @@ public final class Polygon2D extends EdgeTree {
   }
 
   @Override
-  protected Relation componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
+  protected Relation componentRelate(double minLat, double maxLat, double minLon, double maxLon) {
     // check any holes
     if (holes != null) {
-      Relation holeRelation = holes.relateTriangle(ax, ay, bx, by, cx, cy);
+      Relation holeRelation = holes.relate(minLat, maxLat, minLon, maxLon);
       if (holeRelation == Relation.CELL_CROSSES_QUERY) {
         return Relation.CELL_CROSSES_QUERY;
       } else if (holeRelation == Relation.CELL_INSIDE_QUERY) {
         return Relation.CELL_OUTSIDE_QUERY;
       }
     }
-    // check each corner: if < 3 are present, its cheaper than crossesSlowly
-    int numCorners = numberOfTriangleCorners(ax, ay, bx, by, cx, cy);
-    if (numCorners == 3) {
-      if (tree.relateTriangle(ax, ay, bx, by, cx, cy) == Relation.CELL_CROSSES_QUERY) {
+    // check each corner: if < 4 && > 0 are present, its cheaper than crossesSlowly
+    int numCorners = numberOfCorners(minLat, maxLat, minLon, maxLon);
+    if (numCorners == 4) {
+      if (tree.crosses(minLat, maxLat, minLon, maxLon)) {
         return Relation.CELL_CROSSES_QUERY;
       }
       return Relation.CELL_INSIDE_QUERY;
-    } else if (numCorners > 0) {
-      return Relation.CELL_CROSSES_QUERY;
+    }  else if (numCorners == 0) {
+      if (minLat >= tree.lat1 && maxLat <= tree.lat1 && minLon >= tree.lon2 && maxLon <= tree.lon2) {
+        return Relation.CELL_CROSSES_QUERY;
+      }
+      if (tree.crosses(minLat, maxLat, minLon, maxLon)) {
+        return Relation.CELL_CROSSES_QUERY;
+      }
+      return Relation.CELL_OUTSIDE_QUERY;
     }
-    return null;
+    return Relation.CELL_CROSSES_QUERY;
   }
 
-  /** Returns relation to the provided rectangle for this component */
   @Override
-  protected Relation componentRelate(double minLat, double maxLat, double minLon, double maxLon) {
+  protected Relation componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
     // check any holes
     if (holes != null) {
-      Relation holeRelation = holes.relate(minLat, maxLat, minLon, maxLon);
+      Relation holeRelation = holes.relateTriangle(ax, ay, bx, by, cx, cy);
       if (holeRelation == Relation.CELL_CROSSES_QUERY) {
         return Relation.CELL_CROSSES_QUERY;
       } else if (holeRelation == Relation.CELL_INSIDE_QUERY) {
         return Relation.CELL_OUTSIDE_QUERY;
       }
     }
-    // check each corner: if < 4 are present, its cheaper than crossesSlowly
-    int numCorners = numberOfCorners(minLat, maxLat, minLon, maxLon);
-    if (numCorners == 4) {
-      if (tree.crosses(minLat, maxLat, minLon, maxLon)) {
+    // check each corner: if < 3 && > 0 are present, its cheaper than crossesSlowly
+    int numCorners = numberOfTriangleCorners(ax, ay, bx, by, cx, cy);
+    if (numCorners == 3) {
+      if (tree.relateTriangle(ax, ay, bx, by, cx, cy) == Relation.CELL_CROSSES_QUERY) {
         return Relation.CELL_CROSSES_QUERY;
       }
       return Relation.CELL_INSIDE_QUERY;
-    } else if (numCorners > 0) {
-      return Relation.CELL_CROSSES_QUERY;
+    } else if (numCorners == 0) {
+      if (pointInTriangle(tree.lon1, tree.lat1, ax, ay, bx, by, cx, cy) == true) {
+        return Relation.CELL_CROSSES_QUERY;
+      }
+      if (tree.relateTriangle(ax, ay, bx, by, cx, cy) == Relation.CELL_CROSSES_QUERY) {
+        return Relation.CELL_CROSSES_QUERY;
+      }
+      return Relation.CELL_OUTSIDE_QUERY;
     }
-    return null;
+    return Relation.CELL_CROSSES_QUERY;
   }
 
   private int numberOfTriangleCorners(double ax, double ay, double bx, double by, double cx, double cy) {

diff --git a/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java b/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java
index 0f9441f..94d9222 100644 (file)
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java
@@ -16,6 +16,8 @@
  */
 package org.apache.lucene.geo;
 
+import org.apache.lucene.index.PointValues;
+
 /**
  * 2D line implementation represented as a balanced interval tree of edges.
  * <p>
@@ -37,4 +39,17 @@ public final class Line2D extends EdgeTree {
     }
     return (Line2D)createTree(components, 0, components.length - 1, false);
   }
+
+  @Override
+  protected PointValues.Relation componentRelate(double minLat, double maxLat, double minLon, double maxLon) {
+    if (tree.crosses(minLat, maxLat, minLon, maxLon)) {
+      return PointValues.Relation.CELL_CROSSES_QUERY;
+    }
+    return PointValues.Relation.CELL_OUTSIDE_QUERY;
+  }
+
+  @Override
+  protected PointValues.Relation componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
+    return tree.relateTriangle(ax, ay, bx, by, cx, cy);
+  }
 }
\ No newline at end of file