in lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java [1385:1662]
private static Boolean findConvexPolygon(
final PlanetModel planetModel,
final Edge currentEdge,
final GeoCompositePolygon rval,
final EdgeBuffer edgeBuffer,
final List<GeoPolygon> holes,
final GeoPoint testPoint)
throws TileException {
// System.out.println("Looking at edge "+currentEdge+" with startpoint
// "+currentEdge.startPoint+" endpoint "+currentEdge.endPoint);
// Initialize the structure.
// We don't keep track of order here; we just care about membership.
// The only exception is the head and tail pointers.
final Set<Edge> includedEdges = new HashSet<>();
includedEdges.add(currentEdge);
Edge firstEdge = currentEdge;
Edge lastEdge = currentEdge;
// First, walk towards the end until we need to stop
while (true) {
if (firstEdge.startPoint == lastEdge.endPoint) {
break;
}
final Edge newLastEdge = edgeBuffer.getNext(lastEdge);
if (Plane.arePointsCoplanar(lastEdge.startPoint, lastEdge.endPoint, newLastEdge.endPoint)) {
break;
}
// Planes that are almost identical cannot be properly handled by the standard polygon logic.
// Detect this case and, if found, give up on the tiling -- we'll need to create a large poly
// instead.
if (lastEdge.plane.isFunctionallyIdentical(newLastEdge.plane)) {
throw new TileException(
"Two adjacent edge planes are effectively parallel despite filtering; give up on tiling");
}
if (isWithin(newLastEdge.endPoint, includedEdges)) {
// System.out.println(" maybe can extend to next edge");
// Found a candidate for extension. But do some other checks first. Basically, we need to
// know if we construct a polygon here will overlap with other remaining points?
final SidedPlane returnBoundary;
if (firstEdge.startPoint != newLastEdge.endPoint) {
if (Plane.arePointsCoplanar(
firstEdge.endPoint, firstEdge.startPoint, newLastEdge.endPoint)
|| Plane.arePointsCoplanar(
firstEdge.startPoint, newLastEdge.endPoint, newLastEdge.startPoint)) {
break;
}
returnBoundary =
new SidedPlane(firstEdge.endPoint, firstEdge.startPoint, newLastEdge.endPoint);
} else {
returnBoundary = null;
}
// The complete set of sided planes for the tentative new polygon include the ones in
// includedEdges, plus the one from newLastEdge, plus the new tentative return boundary.
// We have to make sure there are no points from elsewhere within the tentative convex
// polygon.
boolean foundPointInside = false;
final Iterator<Edge> edgeIterator = edgeBuffer.iterator();
while (edgeIterator.hasNext()) {
final Edge edge = edgeIterator.next();
if (!includedEdges.contains(edge) && edge != newLastEdge) {
// This edge has a point to check
if (edge.startPoint != newLastEdge.endPoint) {
// look at edge.startPoint
if (isWithin(edge.startPoint, includedEdges, newLastEdge, returnBoundary)) {
// System.out.println(" nope; point within found: " + edge.startPoint);
foundPointInside = true;
break;
}
}
if (edge.endPoint != firstEdge.startPoint) {
// look at edge.endPoint
if (isWithin(edge.endPoint, includedEdges, newLastEdge, returnBoundary)) {
// System.out.println(" nope; point within found: " + edge.endPoint);
foundPointInside = true;
break;
}
}
}
}
if (!foundPointInside) {
// System.out.println(" extending!");
// Extend the polygon by the new last edge
includedEdges.add(newLastEdge);
lastEdge = newLastEdge;
// continue extending in this direction
continue;
}
}
// We can't extend any more in this direction, so break from the loop.
break;
}
// Now, walk towards the beginning until we need to stop
while (true) {
if (firstEdge.startPoint == lastEdge.endPoint) {
break;
}
final Edge newFirstEdge = edgeBuffer.getPrevious(firstEdge);
if (Plane.arePointsCoplanar(
newFirstEdge.startPoint, newFirstEdge.endPoint, firstEdge.endPoint)) {
break;
}
// Planes that are almost identical cannot be properly handled by the standard polygon logic.
// Detect this case and, if found, give up on the tiling -- we'll need to create a large poly
// instead.
if (firstEdge.plane.isFunctionallyIdentical(newFirstEdge.plane)) {
throw new TileException(
"Two adjacent edge planes are effectively parallel despite filtering; give up on tiling");
}
if (isWithin(newFirstEdge.startPoint, includedEdges)) {
// System.out.println(" maybe can extend to previous edge");
// Found a candidate for extension. But do some other checks first. Basically, we need to
// know if we construct a polygon here will overlap with other remaining points?
final SidedPlane returnBoundary;
if (newFirstEdge.startPoint != lastEdge.endPoint) {
if (Plane.arePointsCoplanar(
lastEdge.startPoint, lastEdge.endPoint, newFirstEdge.startPoint)
|| Plane.arePointsCoplanar(
lastEdge.endPoint, newFirstEdge.startPoint, newFirstEdge.endPoint)) {
break;
}
returnBoundary =
new SidedPlane(lastEdge.startPoint, lastEdge.endPoint, newFirstEdge.startPoint);
} else {
returnBoundary = null;
}
// The complete set of sided planes for the tentative new polygon include the ones in
// includedEdges, plus the one from newLastEdge, plus the new tentative return boundary.
// We have to make sure there are no points from elsewhere within the tentative convex
// polygon.
boolean foundPointInside = false;
final Iterator<Edge> edgeIterator = edgeBuffer.iterator();
while (edgeIterator.hasNext()) {
final Edge edge = edgeIterator.next();
if (!includedEdges.contains(edge) && edge != newFirstEdge) {
// This edge has a point to check
if (edge.startPoint != lastEdge.endPoint) {
// look at edge.startPoint
if (isWithin(edge.startPoint, includedEdges, newFirstEdge, returnBoundary)) {
// System.out.println(" nope; point within found: " + edge.startPoint);
foundPointInside = true;
break;
}
}
if (edge.endPoint != newFirstEdge.startPoint) {
// look at edge.endPoint
if (isWithin(edge.endPoint, includedEdges, newFirstEdge, returnBoundary)) {
// System.out.println(" nope; point within found: " + edge.endPoint);
foundPointInside = true;
break;
}
}
}
}
if (!foundPointInside) {
// System.out.println(" extending!");
// Extend the polygon by the new last edge
includedEdges.add(newFirstEdge);
firstEdge = newFirstEdge;
// continue extending in this direction
continue;
}
}
// We can't extend any more in this direction, so break from the loop.
break;
}
// Ok, figure out what we've accumulated. If it is enough for a polygon, build it.
if (includedEdges.size() < 2) {
// System.out.println("Done edge " + currentEdge + ": no poly found");
return false;
}
// It's enough to build a convex polygon
// System.out.println("Edge " + currentEdge + ": Found complex poly");
// Create the point list and edge list, starting with the first edge and going to the last. The
// return edge will be between the start point of the first edge and the end point of the last
// edge. If the first edge start point is the same as the last edge end point, it's a
// degenerate case and we want to just clean out the edge buffer entirely.
final List<GeoPoint> points = new ArrayList<GeoPoint>(includedEdges.size() + 1);
final BitSet internalEdges = new BitSet(includedEdges.size());
final boolean returnIsInternal;
if (firstEdge.startPoint == lastEdge.endPoint) {
// Degenerate case!! There is no return edge -- or rather, we already have it.
if (includedEdges.size() < 3) {
// This means we found a degenerate cycle of edges. If we emit a polygon at this point it
// has no contents, so we generate no polygon.
return false;
}
if (firstEdge.plane.isFunctionallyIdentical(lastEdge.plane)) {
throw new TileException(
"Two adjacent edge planes are effectively parallel despite filtering; give up on tiling");
}
// Now look for completely planar points. This too is a degeneracy condition that we should
// return "false" for.
Edge edge = firstEdge;
points.add(edge.startPoint);
int k = 0;
while (true) {
if (edge == lastEdge) {
break;
}
points.add(edge.endPoint);
internalEdges.set(k++, edge.isInternal);
edge = edgeBuffer.getNext(edge);
}
returnIsInternal = lastEdge.isInternal;
edgeBuffer.clear();
} else {
// Build the return edge (internal, of course)
final SidedPlane returnSidedPlane =
new SidedPlane(firstEdge.endPoint, false, firstEdge.startPoint, lastEdge.endPoint);
final Edge returnEdge =
new Edge(firstEdge.startPoint, lastEdge.endPoint, returnSidedPlane, true);
if (returnEdge.plane.isFunctionallyIdentical(lastEdge.plane)
|| returnEdge.plane.isFunctionallyIdentical(firstEdge.plane)) {
throw new TileException(
"Two adjacent edge planes are effectively parallel despite filtering; give up on tiling");
}
// Build point list and edge list
final List<Edge> edges = new ArrayList<Edge>(includedEdges.size());
returnIsInternal = true;
// Now look for completely planar points. This too is a degeneracy condition that we should
// return "false" for.
Edge edge = firstEdge;
points.add(edge.startPoint);
int k = 0;
while (true) {
points.add(edge.endPoint);
internalEdges.set(k++, edge.isInternal);
edges.add(edge);
if (edge == lastEdge) {
break;
}
edge = edgeBuffer.getNext(edge);
}
// Modify the edge buffer
edgeBuffer.replace(edges, returnEdge);
}
// Now, construct the polygon
// Failures in construction mean we have a polygon that is too large (>180 degrees)
try {
if (testPoint != null && holes != null && holes.size() > 0) {
// No holes, for test
final GeoPolygon testPolygon =
new GeoConvexPolygon(planetModel, points, null, internalEdges, returnIsInternal);
if (testPolygon.isWithin(testPoint)) {
return null;
}
}
final GeoPolygon realPolygon =
new GeoConvexPolygon(planetModel, points, holes, internalEdges, returnIsInternal);
if (testPoint != null && (holes == null || holes.size() == 0)) {
if (realPolygon.isWithin(testPoint)) {
return null;
}
}
rval.addShape(realPolygon);
return true;
} catch (IllegalArgumentException e) {
throw new TileException(e.getMessage());
}
}