You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by kw...@apache.org on 2016/04/29 02:30:58 UTC
[14/25] lucene-solr:branch_6x: Restructure DualCrossing counter so
that the plane inside and outside boundaries are used to detect inside and
outside crossings. Also identify the case for special treatment of edges
lying on the intersection point.
Restructure DualCrossing counter so that the plane inside and outside boundaries are used to detect inside and outside crossings. Also identify the case for special treatment of edges lying on the intersection point.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/3e18d935
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/3e18d935
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/3e18d935
Branch: refs/heads/branch_6x
Commit: 3e18d9356ea607160b469c89d6321a3e4e8b0d43
Parents: 9688932
Author: Karl Wright <Da...@gmail.com>
Authored: Tue Apr 26 13:49:47 2016 -0400
Committer: Karl Wright <Da...@gmail.com>
Committed: Thu Apr 28 20:24:19 2016 -0400
----------------------------------------------------------------------
.../spatial3d/geom/GeoComplexPolygon.java | 285 +++++++++++--------
1 file changed, 163 insertions(+), 122 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/3e18d935/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
index 7e4d01c..b5c29d6 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
@@ -729,6 +729,9 @@ class GeoComplexPolygon extends GeoBasePolygon {
private final SidedPlane testPointOtherCutoffPlane;
private final SidedPlane checkPointOtherCutoffPlane;
+ private final SidedPlane insideTestPointCutoffPlane;
+ private final SidedPlane insideTravelCutoffPlane;
+
public int crossingCount = 0;
public DualCrossingEdgeIterator(final Plane testPointPlane, final Plane testPointAbovePlane, final Plane testPointBelowPlane,
@@ -762,28 +765,36 @@ class GeoComplexPolygon extends GeoBasePolygon {
assert aboveAbove.length + aboveBelow.length + belowBelow.length + belowAbove.length == 1 : "Can be exactly one inside point";
+ final GeoPoint insideIntersection;
if (aboveAbove.length > 0) {
travelInsidePlane = travelAbovePlane;
testPointInsidePlane = testPointAbovePlane;
travelOutsidePlane = travelBelowPlane;
testPointOutsidePlane = testPointBelowPlane;
+ insideIntersection = aboveAbove[0];
} else if (aboveBelow.length > 0) {
travelInsidePlane = travelAbovePlane;
testPointInsidePlane = testPointBelowPlane;
travelOutsidePlane = travelBelowPlane;
testPointOutsidePlane = testPointAbovePlane;
+ insideIntersection = aboveBelow[0];
} else if (belowBelow.length > 0) {
travelInsidePlane = travelBelowPlane;
testPointInsidePlane = testPointBelowPlane;
travelOutsidePlane = travelAbovePlane;
testPointOutsidePlane = testPointAbovePlane;
+ insideIntersection = belowBelow[0];
} else {
travelInsidePlane = travelBelowPlane;
testPointInsidePlane = testPointAbovePlane;
travelOutsidePlane = travelAbovePlane;
testPointOutsidePlane = testPointBelowPlane;
+ insideIntersection = belowAbove[0];
}
-
+
+ insideTravelCutoffPlane = new SidedPlane(thePoint, travelInsidePlane, insideIntersection);
+ insideTestPointCutoffPlane = new SidedPlane(testPoint, testPointInsidePlane, insideIntersection);
+
}
public void setSecondLeg() {
@@ -796,6 +807,9 @@ class GeoComplexPolygon extends GeoBasePolygon {
if (thePoint != null && edge.plane.evaluateIsZero(thePoint) && edge.startPlane.isWithin(thePoint) && edge.endPlane.isWithin(thePoint)) {
return false;
}
+ // If the intersection point lies on this edge, we should still be able to consider crossing points only.
+ // Even if an intersection point is eliminated because it's not a crossing of one plane, it will have to be a crossing
+ // for at least one of the two planes in order to be a legitimate crossing of the combined path.
final GeoPoint[] crossingPoints;
if (isSecondLeg) {
crossingPoints = travelPlane.findCrossings(planetModel, edge.plane, checkPointCutoffPlane, checkPointOtherCutoffPlane, edge.startPlane, edge.endPlane);
@@ -812,139 +826,166 @@ class GeoComplexPolygon extends GeoBasePolygon {
}
private void countCrossingPoint(final GeoPoint crossingPoint, final Edge edge) {
- final Plane plane;
- final Plane insidePlane;
- final Plane outsidePlane;
- final SidedPlane bound1;
- final SidedPlane bound2;
- if (isSecondLeg) {
- plane = travelPlane;
- insidePlane = travelInsidePlane;
- outsidePlane = travelOutsidePlane;
- bound1 = checkPointCutoffPlane;
- bound2 = checkPointOtherCutoffPlane;
+ // We consider crossing points only in this method.
+ // Unlike the linear case, there are additional cases when:
+ // (1) The crossing point and the intersection point are the same, but are not the endpoint of an edge;
+ // (2) The crossing point and the intersection point are the same, and they *are* the endpoint of an edge.
+ // The other logical difference is that crossings of all kinds have to be considered so that:
+ // (a) both inside edges are considered together at all times;
+ // (b) both outside edges are considered together at all times;
+ // (c) inside edge crossings that are between the other leg's inside and outside edge are ignored.
+ if (crossingPoint.isNumericallyIdentical(intersectionPoint)) {
+ // Intersection point crossing
+
+ // MHL to deal with intersection point crossing!!
+
} else {
- plane = testPointPlane;
- insidePlane = testPointInsidePlane;
- outsidePlane = testPointOutsidePlane;
- bound1 = testPointCutoffPlane;
- bound2 = testPointOtherCutoffPlane;
- }
-
- // MHL - this code below is temporary code copied from LinearCrossing above
+ // Standard plane crossing, either first leg or second leg
- if (crossingPoint.isNumericallyIdentical(edge.startPoint)) {
- // We have to figure out if this crossing should be counted.
-
- // Does the crossing for this edge go up, or down? Or can't we tell?
- final GeoPoint[] insideIntersections = insidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane);
- final GeoPoint[] outsideIntersections = outsidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane);
-
- assert !(insideIntersections.length > 0 && outsideIntersections.length > 0) : "edge that ends in a crossing can't both up and down";
-
- if (insideIntersections.length == 0 && outsideIntersections.length == 0) {
- return;
- }
-
- final boolean edgeCrossesInside = insideIntersections.length > 0;
-
- // This depends on the previous edge that first departs from identicalness.
- Edge assessEdge = edge;
- GeoPoint[] assessInsideIntersections;
- GeoPoint[] assessOutsideIntersections;
- while (true) {
- assessEdge = assessEdge.previous;
- assessInsideIntersections = insidePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane);
- assessOutsideIntersections = outsidePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane);
-
- assert !(assessInsideIntersections.length > 0 && assessOutsideIntersections.length > 0) : "assess edge that ends in a crossing can't both up and down";
-
- if (assessInsideIntersections.length == 0 && assessOutsideIntersections.length == 0) {
- continue;
- }
- break;
+ final Plane plane;
+ final Plane insidePlane;
+ final Plane outsidePlane;
+ final SidedPlane bound1;
+ final SidedPlane bound2;
+ if (isSecondLeg) {
+ plane = travelPlane;
+ insidePlane = travelInsidePlane;
+ outsidePlane = travelOutsidePlane;
+ bound1 = checkPointCutoffPlane;
+ bound2 = checkPointOtherCutoffPlane;
+ } else {
+ plane = testPointPlane;
+ insidePlane = testPointInsidePlane;
+ outsidePlane = testPointOutsidePlane;
+ bound1 = testPointCutoffPlane;
+ bound2 = testPointOtherCutoffPlane;
}
- // Basically, we now want to assess whether both edges that come together at this endpoint leave the plane in opposite
- // directions. If they do, then we should count it as a crossing; if not, we should not. We also have to remember that
- // each edge we look at can also be looked at again if it, too, seems to cross the plane.
-
- // To handle the latter situation, we need to know if the other edge will be looked at also, and then we can make
- // a decision whether to count or not based on that.
-
- // Compute the crossing points of this other edge.
- final GeoPoint[] otherCrossingPoints = plane.findCrossings(planetModel, assessEdge.plane, bound1, bound2, assessEdge.startPlane, assessEdge.endPlane);
-
- // Look for a matching endpoint. If the other endpoint doesn't show up, it is either out of bounds (in which case the
- // transition won't be counted for that edge), or it is not a crossing for that edge (so, same conclusion).
- for (final GeoPoint otherCrossingPoint : otherCrossingPoints) {
- if (otherCrossingPoint.isNumericallyIdentical(assessEdge.endPoint)) {
- // Found it!
- // Both edges will try to contribute to the crossing count. By convention, we'll only include the earlier one.
- // Since we're the latter point, we exit here in that case.
+ if (crossingPoint.isNumericallyIdentical(edge.startPoint)) {
+ // We have to figure out if this crossing should be counted.
+
+ // Does the crossing for this edge go up, or down? Or can't we tell?
+ final GeoPoint[] insideTestPointPlaneIntersections = testPointInsidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane, insideTestPointCutoffPlane);
+ final GeoPoint[] insideTravelPlaneIntersections = travelInsidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane, insideTravelCutoffPlane);
+ final GeoPoint[] outsideTestPointPlaneIntersections = testPointOutsidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane);
+ final GeoPoint[] outsideTravelPlaneIntersections = travelOutsidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane);
+
+ assert !(insideTestPointPlaneIntersections.length + insideTravelPlaneIntersections.length > 0 && outsideTestPointPlaneIntersections.length + outsideTravelPlaneIntersections.length > 0) : "edge that ends in a crossing can't both up and down";
+
+ if (insideTestPointPlaneIntersections.length + insideTravelPlaneIntersections.length == 0 && outsideTestPointPlaneIntersections.length + outsideTravelPlaneIntersections.length == 0) {
return;
}
- }
-
- // Both edges will not count the same point, so we can proceed. We need to determine the direction of both edges at the
- // point where they hit the plane. This may be complicated by the 3D geometry; it may not be safe just to look at the endpoints of the edges
- // and make an assessment that way, since a single edge can intersect the plane at more than one point.
-
- final boolean assessEdgeInside = assessInsideIntersections.length > 0;
- if (assessEdgeInside != edgeCrossesInside) {
- crossingCount++;
- }
-
- } else if (crossingPoint.isNumericallyIdentical(edge.endPoint)) {
- // Figure out if the crossing should be counted.
-
- // Does the crossing for this edge go up, or down? Or can't we tell?
- final GeoPoint[] insideIntersections = insidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane);
- final GeoPoint[] outsideIntersections = outsidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane);
-
- assert !(insideIntersections.length > 0 && outsideIntersections.length > 0) : "edge that ends in a crossing can't both up and down";
-
- if (insideIntersections.length == 0 && outsideIntersections.length == 0) {
- return;
- }
-
- final boolean edgeCrossesInside = insideIntersections.length > 0;
- // This depends on the previous edge that first departs from identicalness.
- Edge assessEdge = edge;
- GeoPoint[] assessInsideIntersections;
- GeoPoint[] assessOutsideIntersections;
- while (true) {
- assessEdge = assessEdge.next;
- assessInsideIntersections = insidePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane);
- assessOutsideIntersections = outsidePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane);
-
- assert !(assessInsideIntersections.length > 0 && assessOutsideIntersections.length > 0) : "assess edge that ends in a crossing can't both up and down";
+ final boolean edgeCrossesInside = insideTestPointPlaneIntersections.length + insideTravelPlaneIntersections.length > 0;
+
+ // This depends on the previous edge that first departs from identicalness.
+ Edge assessEdge = edge;
+ GeoPoint[] assessInsideTestPointIntersections;
+ GeoPoint[] assessInsideTravelIntersections;
+ GeoPoint[] assessOutsideTestPointIntersections;
+ GeoPoint[] assessOutsideTravelIntersections;
+ while (true) {
+ assessEdge = assessEdge.previous;
+ assessInsideTestPointIntersections = testPointInsidePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane, insideTestPointCutoffPlane);
+ assessInsideTravelIntersections = travelInsidePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane, insideTravelCutoffPlane);
+ assessOutsideTestPointIntersections = testPointOutsidePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane);
+ assessOutsideTravelIntersections = travelOutsidePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane);
+
+ assert !(assessInsideTestPointIntersections.length + assessInsideTravelIntersections.length > 0 && assessOutsideTestPointIntersections.length + assessOutsideTravelIntersections.length > 0) : "assess edge that ends in a crossing can't both up and down";
+
+ if (assessInsideTestPointIntersections.length + assessInsideTravelIntersections.length == 0 && assessOutsideTestPointIntersections.length + assessOutsideTravelIntersections.length == 0) {
+ continue;
+ }
+ break;
+ }
- if (assessInsideIntersections.length == 0 && assessOutsideIntersections.length == 0) {
- continue;
+ // Basically, we now want to assess whether both edges that come together at this endpoint leave the plane in opposite
+ // directions. If they do, then we should count it as a crossing; if not, we should not. We also have to remember that
+ // each edge we look at can also be looked at again if it, too, seems to cross the plane.
+
+ // To handle the latter situation, we need to know if the other edge will be looked at also, and then we can make
+ // a decision whether to count or not based on that.
+
+ // Compute the crossing points of this other edge.
+ final GeoPoint[] otherCrossingPoints = plane.findCrossings(planetModel, assessEdge.plane, bound1, bound2, assessEdge.startPlane, assessEdge.endPlane);
+
+ // Look for a matching endpoint. If the other endpoint doesn't show up, it is either out of bounds (in which case the
+ // transition won't be counted for that edge), or it is not a crossing for that edge (so, same conclusion).
+ for (final GeoPoint otherCrossingPoint : otherCrossingPoints) {
+ if (otherCrossingPoint.isNumericallyIdentical(assessEdge.endPoint)) {
+ // Found it!
+ // Both edges will try to contribute to the crossing count. By convention, we'll only include the earlier one.
+ // Since we're the latter point, we exit here in that case.
+ return;
+ }
+ }
+
+ // Both edges will not count the same point, so we can proceed. We need to determine the direction of both edges at the
+ // point where they hit the plane. This may be complicated by the 3D geometry; it may not be safe just to look at the endpoints of the edges
+ // and make an assessment that way, since a single edge can intersect the plane at more than one point.
+
+ final boolean assessEdgeInside = assessInsideTestPointIntersections.length + assessInsideTravelIntersections.length > 0;
+ if (assessEdgeInside != edgeCrossesInside) {
+ crossingCount++;
+ }
+
+ } else if (crossingPoint.isNumericallyIdentical(edge.endPoint)) {
+ // Figure out if the crossing should be counted.
+
+ // Does the crossing for this edge go up, or down? Or can't we tell?
+ final GeoPoint[] insideTestPointPlaneIntersections = testPointInsidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane, insideTestPointCutoffPlane);
+ final GeoPoint[] insideTravelPlaneIntersections = travelInsidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane, insideTravelCutoffPlane);
+ final GeoPoint[] outsideTestPointPlaneIntersections = testPointOutsidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane);
+ final GeoPoint[] outsideTravelPlaneIntersections = travelOutsidePlane.findIntersections(planetModel, edge.plane, edge.startPlane, edge.endPlane);
+
+ assert !(insideTestPointPlaneIntersections.length + insideTravelPlaneIntersections.length > 0 && outsideTestPointPlaneIntersections.length + outsideTravelPlaneIntersections.length > 0) : "edge that ends in a crossing can't both up and down";
+
+ if (insideTestPointPlaneIntersections.length + insideTravelPlaneIntersections.length == 0 && outsideTestPointPlaneIntersections.length + outsideTravelPlaneIntersections.length == 0) {
+ return;
}
- break;
- }
-
- // Basically, we now want to assess whether both edges that come together at this endpoint leave the plane in opposite
- // directions. If they do, then we should count it as a crossing; if not, we should not. We also have to remember that
- // each edge we look at can also be looked at again if it, too, seems to cross the plane.
-
- // By definition, we're the earlier plane in this case, so any crossing we detect we must count, by convention. It is unnecessary
- // to consider what the other edge does, because when we get to it, it will look back and figure out what we did for this one.
-
- // We need to determine the direction of both edges at the
- // point where they hit the plane. This may be complicated by the 3D geometry; it may not be safe just to look at the endpoints of the edges
- // and make an assessment that way, since a single edge can intersect the plane at more than one point.
- final boolean assessEdgeInside = assessInsideIntersections.length > 0;
- if (assessEdgeInside != edgeCrossesInside) {
+ final boolean edgeCrossesInside = insideTestPointPlaneIntersections.length + insideTravelPlaneIntersections.length > 0;
+
+ // This depends on the previous edge that first departs from identicalness.
+ Edge assessEdge = edge;
+ GeoPoint[] assessInsideTestPointIntersections;
+ GeoPoint[] assessInsideTravelIntersections;
+ GeoPoint[] assessOutsideTestPointIntersections;
+ GeoPoint[] assessOutsideTravelIntersections;
+ while (true) {
+ assessEdge = assessEdge.next;
+ assessInsideTestPointIntersections = testPointInsidePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane, insideTestPointCutoffPlane);
+ assessInsideTravelIntersections = travelInsidePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane, insideTravelCutoffPlane);
+ assessOutsideTestPointIntersections = testPointOutsidePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane);
+ assessOutsideTravelIntersections = travelOutsidePlane.findIntersections(planetModel, assessEdge.plane, assessEdge.startPlane, assessEdge.endPlane);
+
+ assert !(assessInsideTestPointIntersections.length + assessInsideTravelIntersections.length > 0 && assessOutsideTestPointIntersections.length + assessOutsideTravelIntersections.length > 0) : "assess edge that ends in a crossing can't both up and down";
+
+ if (assessInsideTestPointIntersections.length + assessInsideTravelIntersections.length == 0 && assessOutsideTestPointIntersections.length + assessOutsideTravelIntersections.length == 0) {
+ continue;
+ }
+ break;
+ }
+
+ // Basically, we now want to assess whether both edges that come together at this endpoint leave the plane in opposite
+ // directions. If they do, then we should count it as a crossing; if not, we should not. We also have to remember that
+ // each edge we look at can also be looked at again if it, too, seems to cross the plane.
+
+ // By definition, we're the earlier plane in this case, so any crossing we detect we must count, by convention. It is unnecessary
+ // to consider what the other edge does, because when we get to it, it will look back and figure out what we did for this one.
+
+ // We need to determine the direction of both edges at the
+ // point where they hit the plane. This may be complicated by the 3D geometry; it may not be safe just to look at the endpoints of the edges
+ // and make an assessment that way, since a single edge can intersect the plane at more than one point.
+
+ final boolean assessEdgeInside = assessInsideTestPointIntersections.length + assessInsideTravelIntersections.length > 0;
+ if (assessEdgeInside != edgeCrossesInside) {
+ crossingCount++;
+ }
+ } else {
+ // Not a special case, so we can safely count a crossing.
crossingCount++;
}
-
- } else {
- crossingCount++;
}
}
}