You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by iv...@apache.org on 2019/02/08 15:21:32 UTC
[lucene-solr] branch branch_8x updated: LUCENE-8680: Refactor
EdgeTree#relateTriangle method
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a commit to branch branch_8x
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
The following commit(s) were added to refs/heads/branch_8x by this push:
new d7d4d64 LUCENE-8680: Refactor EdgeTree#relateTriangle method
d7d4d64 is described below
commit d7d4d64f346136d34399226a4bf19c3eb28f45a3
Author: iverase <iv...@apache.org>
AuthorDate: Fri Feb 8 16:19:38 2019 +0100
LUCENE-8680: Refactor EdgeTree#relateTriangle method
---
.../src/java/org/apache/lucene/geo/EdgeTree.java | 44 ++++---------------
.../src/java/org/apache/lucene/geo/Polygon2D.java | 49 +++++++++++++---------
.../src/java/org/apache/lucene/geo/Line2D.java | 15 +++++++
3 files changed, 54 insertions(+), 54 deletions(-)
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
--- 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
--- 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
--- 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