nknize commented on a change in pull request #878: LUCENE-8746: Refactor
EdgeTree
URL: https://github.com/apache/lucene-solr/pull/878#discussion_r333706202
##########
File path: lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
##########
@@ -269,138 +157,109 @@ boolean crossesTriangle(double ax, double ay, double
bx, double by, double cx, d
}
}
- if (left != null && left.crossesTriangle(ax, ay, bx, by, cx, cy)) {
+ if (left != null && left.crossesTriangle(minX, maxX, minY, maxY, ax,
ay, bx, by, cx, cy)) {
return true;
}
- if (right != null && triMaxLat >= low && right.crossesTriangle(ax, ay,
bx, by, cx, cy)) {
+ if (right != null && maxY >= low && right.crossesTriangle(minX, maxX,
minY, maxY, ax, ay, bx, by, cx, cy)) {
return true;
}
}
return false;
}
- /** Returns true if the box crosses any edge in this edge subtree */
- boolean crossesBox(double minLat, double maxLat, double minLon, double
maxLon, boolean includeBoundary) {
- // we just have to cross one edge to answer the question, so we descend
the tree and return when we do.
- if (minLat <= max) {
- // we compute line intersections of every polygon edge with every box
line.
- // if we find one, return true.
- // for each box line (AB):
- // for each poly line (CD):
- // intersects = orient(C,D,A) * orient(C,D,B) <= 0 &&
orient(A,B,C) * orient(A,B,D) <= 0
- double cy = lat1;
- double dy = lat2;
- double cx = lon1;
- double dx = lon2;
-
- // optimization: see if either end of the line segment is contained by
the rectangle
- if (Rectangle.containsPoint(cy, cx, minLat, maxLat, minLon, maxLon) ||
- Rectangle.containsPoint(dy, dx, minLat, maxLat, minLon, maxLon)) {
- return true;
- }
-
- // optimization: see if the rectangle is outside of the "bounding box"
of the polyline at all
- // if not, don't waste our time trying more complicated stuff
- boolean outside = (cy < minLat && dy < minLat) ||
- (cy > maxLat && dy > maxLat) ||
- (cx < minLon && dx < minLon) ||
- (cx > maxLon && dx > maxLon);
-
- if (outside == false) {
- if (includeBoundary == true &&
- lineCrossesLineWithBoundary(cx, cy, dx, dy, minLon, minLat,
maxLon, minLat) ||
- lineCrossesLineWithBoundary(cx, cy, dx, dy, maxLon, minLat,
maxLon, maxLat) ||
- lineCrossesLineWithBoundary(cx, cy, dx, dy, maxLon, maxLat,
maxLon, minLat) ||
- lineCrossesLineWithBoundary(cx, cy, dx, dy, minLon, maxLat,
minLon, minLat)) {
- // include boundaries: ensures box edges that terminate on the
polygon are included
- return true;
- } else if (lineCrossesLine(cx, cy, dx, dy, minLon, minLat, maxLon,
minLat) ||
- lineCrossesLine(cx, cy, dx, dy, maxLon, minLat, maxLon, maxLat)
||
- lineCrossesLine(cx, cy, dx, dy, maxLon, maxLat, maxLon, minLat)
||
- lineCrossesLine(cx, cy, dx, dy, minLon, maxLat, minLon, minLat))
{
- return true;
- }
- }
+ /** Returns true if the box crosses any edge in this edge subtree */
+ public boolean crossesBox(double minX, double maxX, double minY, double
maxY, boolean includeBoundary) {
+ // we just have to cross one edge to answer the question, so we descend
the tree and return when we do.
+ if (minY <= max) {
+ // we compute line intersections of every polygon edge with every box
line.
+ // if we find one, return true.
+ // for each box line (AB):
+ // for each poly line (CD):
+ // intersects = orient(C,D,A) * orient(C,D,B) <= 0 && orient(A,B,C)
* orient(A,B,D) <= 0
+ double cy = y1;
+ double dy = y2;
+ double cx = x1;
+ double dx = x2;
+
+ // optimization: see if either end of the line segment is contained by
the rectangle
+ if (Rectangle.containsPoint(cy, cx, minY, maxY, minX, maxX) ||
+ Rectangle.containsPoint(dy, dx, minY, maxY, minX, maxX)) {
+ return true;
+ }
- if (left != null && left.crossesBox(minLat, maxLat, minLon, maxLon,
includeBoundary)) {
+ // optimization: see if the rectangle is outside of the "bounding box"
of the polyline at all
+ // if not, don't waste our time trying more complicated stuff
+ boolean outside = (cy < minY && dy < minY) ||
+ (cy > maxY && dy > maxY) ||
+ (cx < minX && dx < minX) ||
+ (cx > maxX && dx > maxX);
+
+ if (outside == false) {
+ if (includeBoundary == true &&
+ lineCrossesLineWithBoundary(cx, cy, dx, dy, minX, minY, maxX,
minY) ||
+ lineCrossesLineWithBoundary(cx, cy, dx, dy, maxX, minY, maxX,
maxY) ||
+ lineCrossesLineWithBoundary(cx, cy, dx, dy, maxX, maxY, minX,
maxY) ||
+ lineCrossesLineWithBoundary(cx, cy, dx, dy, minX, maxY, minX,
minY)) {
+ // include boundaries: ensures box edges that terminate on the
polygon are included
return true;
- }
-
- if (right != null && maxLat >= low && right.crossesBox(minLat, maxLat,
minLon, maxLon, includeBoundary)) {
+ } else if (lineCrossesLine(cx, cy, dx, dy, minX, minY, maxX, minY) ||
+ lineCrossesLine(cx, cy, dx, dy, maxX, minY, maxX, maxY) ||
+ lineCrossesLine(cx, cy, dx, dy, maxX, maxY, minX, maxY) ||
+ lineCrossesLine(cx, cy, dx, dy, minX, maxY, minX, minY)) {
return true;
}
}
- return false;
- }
- /** Returns true if the line crosses any edge in this edge subtree */
- boolean crossesLine(double a2x, double a2y, double b2x, double b2y) {
- double minY = StrictMath.min(a2y, b2y);
- double maxY = StrictMath.max(a2y, b2y);
- if (minY <= max) {
- double a1x = lon1;
- double a1y = lat1;
- double b1x = lon2;
- double b1y = lat2;
-
- double minX = StrictMath.min(a2x, b2x);
- double maxX = StrictMath.max(a2x, b2x);
-
- boolean outside = (a1y < minY && b1y < minY) ||
- (a1y > maxY && b1y > maxY) ||
- (a1x < minX && b1x < minX) ||
- (a1x > maxX && b1x > maxX);
- if (outside == false && lineCrossesLineWithBoundary(a1x, a1y, b1x,
b1y, a2x, a2y, b2x, b2y)) {
- return true;
- }
+ if (left != null && left.crossesBox(minX, maxX, minY, maxY,
includeBoundary)) {
+ return true;
+ }
- if (left != null && left.crossesLine(a2x, a2y, b2x, b2y)) {
- return true;
- }
- if (right != null && maxY >= low && right.crossesLine(a2x, a2y, b2x,
b2y)) {
- return true;
- }
+ if (right != null && maxY >= low && right.crossesBox(minX, maxX, minY,
maxY, includeBoundary)) {
+ return true;
}
- return false;
}
+ return false;
}
- //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 */
- 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));
- double maxY = StrictMath.max(ay, StrictMath.max(by, cy));
- //check the bounding box because if the triangle is degenerated, e.g
points and lines, we need to filter out
- //coplanar points that are not part of the triangle.
- if (x >= minX && x <= maxX && y >= minY && y <= maxY ) {
- int a = orient(x, y, ax, ay, bx, by);
- int b = orient(x, y, bx, by, cx, cy);
- if (a == 0 || b == 0 || a < 0 == b < 0) {
- int c = orient(x, y, cx, cy, ax, ay);
- return c == 0 || (c < 0 == (b < 0 || a < 0));
+ /** Returns true if the line crosses any edge in this edge subtree */
+ public boolean crossesLine(double minX, double maxX, double minY, double
maxY, double a2x, double a2y, double b2x, double b2y) {
+ if (minY <= max) {
+ double a1x = x1;
+ double a1y = y1;
+ double b1x = x2;
+ double b1y = y2;
+
+ boolean outside = (a1y < minY && b1y < minY) ||
+ (a1y > maxY && b1y > maxY) ||
+ (a1x < minX && b1x < minX) ||
+ (a1x > maxX && b1x > maxX);
+ if (outside == false && lineCrossesLineWithBoundary(a1x, a1y, b1x, b1y,
a2x, a2y, b2x, b2y)) {
+ return true;
+ }
+
+ if (left != null && left.crossesLine(minX, maxX, minY, maxY, a2x, a2y,
b2x, b2y)) {
+ return true;
+ }
+ if (right != null && maxY >= low && right.crossesLine(minX, maxX, minY,
maxY, a2x, a2y, b2x, b2y)) {
+ return true;
}
- return false;
- } else {
- return false;
}
+ return false;
}
/**
* Creates an edge interval tree from a set of geometry vertices.
* @return root node of the tree.
*/
- private static Edge createTree(double[] lats, double[] lons) {
- Edge edges[] = new Edge[lats.length - 1];
- for (int i = 1; i < lats.length; i++) {
- double lat1 = lats[i-1];
- double lon1 = lons[i-1];
- double lat2 = lats[i];
- double lon2 = lons[i];
- edges[i - 1] = new Edge(lat1, lon1, lat2, lon2, Math.min(lat1, lat2),
Math.max(lat1, lat2));
+ public static EdgeTree createTree(double[] x, double[] y) {
Review comment:
```suggestion
protected static EdgeTree createTree(double[] x, double[] y) {
```
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
