/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.lucene.spatial3d.geom;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
import java.util.HashMap;
import java.util.Map;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.IOException;

GeoConcavePolygon objects are generic building blocks of more complex structures. The only restrictions on these objects are: (1) they must be concave; (2) they must have a maximum extent larger than PI. Violating either one of these limits will cause the logic to fail.
@lucene.internal
/** * GeoConcavePolygon objects are generic building blocks of more complex structures. * The only restrictions on these objects are: (1) they must be concave; (2) they must have * a maximum extent larger than PI. Violating either one of these limits will * cause the logic to fail. * * @lucene.internal */
class GeoConcavePolygon extends GeoBasePolygon {
The list of polygon points
/** The list of polygon points */
protected final List<GeoPoint> points;
A bitset describing, for each edge, whether it is internal or not
/** A bitset describing, for each edge, whether it is internal or not */
protected final BitSet isInternalEdges;
The list of holes. If a point is in the hole, it is *not* in the polygon
/** The list of holes. If a point is in the hole, it is *not* in the polygon */
protected final List<GeoPolygon> holes;
A list of edges
/** A list of edges */
protected SidedPlane[] edges = null;
A list of inverted edges
/** A list of inverted edges */
protected SidedPlane[] invertedEdges = null;
The set of notable points for each edge
/** The set of notable points for each edge */
protected GeoPoint[][] notableEdgePoints = null;
A point which is on the boundary of the polygon
/** A point which is on the boundary of the polygon */
protected GeoPoint[] edgePoints = null;
Set to true when the polygon is complete
/** Set to true when the polygon is complete */
protected boolean isDone = false;
A bounds object for each sided plane
/** A bounds object for each sided plane */
protected Map<SidedPlane, Membership> eitherBounds = null;
Map from edge to its previous non-coplanar brother
/** Map from edge to its previous non-coplanar brother */
protected Map<SidedPlane, SidedPlane> prevBrotherMap = null;
Map from edge to its next non-coplanar brother
/** Map from edge to its next non-coplanar brother */
protected Map<SidedPlane, SidedPlane> nextBrotherMap = null;
Create a concave polygon from a list of points. The first point must be on the external edge.
Params:
  • planetModel – is the planet model.
  • pointList – is the list of points to create the polygon from.
/** * Create a concave polygon from a list of points. The first point must be on the * external edge. *@param planetModel is the planet model. *@param pointList is the list of points to create the polygon from. */
public GeoConcavePolygon(final PlanetModel planetModel, final List<GeoPoint> pointList) { this(planetModel, pointList, null); }
Create a concave polygon from a list of points. The first point must be on the external edge.
Params:
  • planetModel – is the planet model.
  • pointList – is the list of points to create the polygon from.
  • holes – is the list of GeoPolygon objects that describe holes in the concave polygon. Null == no holes.
/** * Create a concave polygon from a list of points. The first point must be on the * external edge. *@param planetModel is the planet model. *@param pointList is the list of points to create the polygon from. *@param holes is the list of GeoPolygon objects that describe holes in the concave polygon. Null == no holes. */
public GeoConcavePolygon(final PlanetModel planetModel, final List<GeoPoint> pointList, final List<GeoPolygon> holes) { super(planetModel); this.points = pointList; if (holes != null && holes.size() == 0) { this.holes = null; } else { this.holes = holes; } this.isInternalEdges = new BitSet(); done(false); }
Create a concave polygon from a list of points, keeping track of which boundaries are internal. This is used when creating a polygon as a building block for another shape.
Params:
  • planetModel – is the planet model.
  • pointList – is the set of points to create the polygon from.
  • internalEdgeFlags – is a bitset describing whether each edge is internal or not.
  • returnEdgeInternal – is true when the final return edge is an internal one.
/** * Create a concave polygon from a list of points, keeping track of which boundaries * are internal. This is used when creating a polygon as a building block for another shape. *@param planetModel is the planet model. *@param pointList is the set of points to create the polygon from. *@param internalEdgeFlags is a bitset describing whether each edge is internal or not. *@param returnEdgeInternal is true when the final return edge is an internal one. */
public GeoConcavePolygon(final PlanetModel planetModel, final List<GeoPoint> pointList, final BitSet internalEdgeFlags, final boolean returnEdgeInternal) { this(planetModel, pointList, null, internalEdgeFlags, returnEdgeInternal); }
Create a concave polygon from a list of points, keeping track of which boundaries are internal. This is used when creating a polygon as a building block for another shape.
Params:
  • planetModel – is the planet model.
  • pointList – is the set of points to create the polygon from.
  • holes – is the list of GeoPolygon objects that describe holes in the concave polygon. Null == no holes.
  • internalEdgeFlags – is a bitset describing whether each edge is internal or not.
  • returnEdgeInternal – is true when the final return edge is an internal one.
/** * Create a concave polygon from a list of points, keeping track of which boundaries * are internal. This is used when creating a polygon as a building block for another shape. *@param planetModel is the planet model. *@param pointList is the set of points to create the polygon from. *@param holes is the list of GeoPolygon objects that describe holes in the concave polygon. Null == no holes. *@param internalEdgeFlags is a bitset describing whether each edge is internal or not. *@param returnEdgeInternal is true when the final return edge is an internal one. */
public GeoConcavePolygon(final PlanetModel planetModel, final List<GeoPoint> pointList, final List<GeoPolygon> holes, final BitSet internalEdgeFlags, final boolean returnEdgeInternal) { super(planetModel); this.points = pointList; if (holes != null && holes.size() == 0) { this.holes = null; } else { this.holes = holes; } this.isInternalEdges = internalEdgeFlags; done(returnEdgeInternal); }
Create a concave polygon, with a starting latitude and longitude. Accepts only values in the following ranges: lat: -PI/2 -> PI/2, lon: -PI -> PI
Params:
  • planetModel – is the planet model.
  • startLatitude – is the latitude of the first point.
  • startLongitude – is the longitude of the first point.
/** * Create a concave polygon, with a starting latitude and longitude. * Accepts only values in the following ranges: lat: {@code -PI/2 -> PI/2}, lon: {@code -PI -> PI} *@param planetModel is the planet model. *@param startLatitude is the latitude of the first point. *@param startLongitude is the longitude of the first point. */
public GeoConcavePolygon(final PlanetModel planetModel, final double startLatitude, final double startLongitude) { this(planetModel, startLatitude, startLongitude, null); }
Create a concave polygon, with a starting latitude and longitude. Accepts only values in the following ranges: lat: -PI/2 -> PI/2, lon: -PI -> PI
Params:
  • planetModel – is the planet model.
  • startLatitude – is the latitude of the first point.
  • startLongitude – is the longitude of the first point.
  • holes – is the list of GeoPolygon objects that describe holes in the concave polygon. Null == no holes.
/** * Create a concave polygon, with a starting latitude and longitude. * Accepts only values in the following ranges: lat: {@code -PI/2 -> PI/2}, lon: {@code -PI -> PI} *@param planetModel is the planet model. *@param startLatitude is the latitude of the first point. *@param startLongitude is the longitude of the first point. *@param holes is the list of GeoPolygon objects that describe holes in the concave polygon. Null == no holes. */
public GeoConcavePolygon(final PlanetModel planetModel, final double startLatitude, final double startLongitude, final List<GeoPolygon> holes) { super(planetModel); points = new ArrayList<>(); if (holes != null && holes.size() == 0) { this.holes = null; } else { this.holes = holes; } isInternalEdges = new BitSet(); points.add(new GeoPoint(planetModel, startLatitude, startLongitude)); }
Add a point to the polygon. Accepts only values in the following ranges: lat: -PI/2 -> PI/2, lon: -PI -> PI
Params:
  • latitude – is the latitude of the next point.
  • longitude – is the longitude of the next point.
  • isInternalEdge – is true if the edge just added with this point should be considered "internal", and not intersected as part of the intersects() operation.
/** * Add a point to the polygon. * Accepts only values in the following ranges: lat: {@code -PI/2 -> PI/2}, lon: {@code -PI -> PI} * * @param latitude is the latitude of the next point. * @param longitude is the longitude of the next point. * @param isInternalEdge is true if the edge just added with this point should be considered "internal", and not * intersected as part of the intersects() operation. */
public void addPoint(final double latitude, final double longitude, final boolean isInternalEdge) { if (isDone) throw new IllegalStateException("Can't call addPoint() if done() already called"); if (isInternalEdge) isInternalEdges.set(points.size() - 1); points.add(new GeoPoint(planetModel, latitude, longitude)); }
Finish the polygon, by connecting the last added point with the starting point.
Params:
  • isInternalReturnEdge – is true if the return edge (back to start) is an internal one.
/** * Finish the polygon, by connecting the last added point with the starting point. *@param isInternalReturnEdge is true if the return edge (back to start) is an internal one. */
public void done(final boolean isInternalReturnEdge) { if (isDone) throw new IllegalStateException("Can't call done() more than once"); // If fewer than 3 points, can't do it. if (points.size() < 3) throw new IllegalArgumentException("Polygon needs at least three points."); if (isInternalReturnEdge) isInternalEdges.set(points.size() - 1); isDone = true; // Time to construct the planes. If the polygon is truly concave then any adjacent point // to a segment can provide an exterior measurement. Note: We build the true planes // here and use the logic to return what *isn't* inside all of them. edges = new SidedPlane[points.size()]; invertedEdges = new SidedPlane[points.size()]; notableEdgePoints = new GeoPoint[points.size()][]; for (int i = 0; i < points.size(); i++) { final GeoPoint start = points.get(i); final GeoPoint end = points.get(legalIndex(i + 1)); // We have to find the next point that is not on the plane between start and end. // If there is no such point, it's an error. final Plane planeToFind = new Plane(start, end); int endPointIndex = -1; for (int j = 0; j < points.size(); j++) { final int index = legalIndex(j + i + 2); if (!planeToFind.evaluateIsZero(points.get(index))) { endPointIndex = index; break; } } if (endPointIndex == -1) { throw new IllegalArgumentException("Polygon points are all coplanar"); } final GeoPoint check = points.get(endPointIndex); //System.out.println("Created edge "+sp+" using start="+start+" end="+end+" check="+check); edges[i] = new SidedPlane(check, false, start, end); invertedEdges[i] = new SidedPlane(edges[i]); notableEdgePoints[i] = new GeoPoint[]{start, end}; } // For each edge, create a bounds object. eitherBounds = new HashMap<>(edges.length); prevBrotherMap = new HashMap<>(edges.length); nextBrotherMap = new HashMap<>(edges.length); for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) { final SidedPlane edge = edges[edgeIndex]; final SidedPlane invertedEdge = invertedEdges[edgeIndex]; int bound1Index = legalIndex(edgeIndex+1); while (invertedEdges[bound1Index].isNumericallyIdentical(invertedEdge)) { if (bound1Index == edgeIndex) { throw new IllegalArgumentException("Constructed planes are all coplanar: "+points); } bound1Index = legalIndex(bound1Index + 1); } int bound2Index = legalIndex(edgeIndex-1); while (invertedEdges[bound2Index].isNumericallyIdentical(invertedEdge)) { if (bound2Index == edgeIndex) { throw new IllegalArgumentException("Constructed planes are all coplanar: "+points); } bound2Index = legalIndex(bound2Index - 1); } // Also confirm that all interior points are within the bounds int startingIndex = bound2Index; while (true) { startingIndex = legalIndex(startingIndex+1); if (startingIndex == bound1Index) { break; } final GeoPoint interiorPoint = points.get(startingIndex); if (!invertedEdges[bound1Index].isWithin(interiorPoint) || !invertedEdges[bound2Index].isWithin(interiorPoint)) { throw new IllegalArgumentException("Concave polygon has a side that is more than 180 degrees"); } } eitherBounds.put(edge, new EitherBound(invertedEdges[bound1Index], invertedEdges[bound2Index])); // When we are done with this cycle, we'll need to build the intersection bound for each edge and its brother. // For now, keep track of the relationships. nextBrotherMap.put(invertedEdge, invertedEdges[bound1Index]); prevBrotherMap.put(invertedEdge, invertedEdges[bound2Index]); } // Pick an edge point arbitrarily from the outer polygon. Glom this together with all edge points from // inner polygons. int edgePointCount = 1; if (holes != null) { for (final GeoPolygon hole : holes) { edgePointCount += hole.getEdgePoints().length; } } edgePoints = new GeoPoint[edgePointCount]; edgePointCount = 0; edgePoints[edgePointCount++] = points.get(0); if (holes != null) { for (final GeoPolygon hole : holes) { final GeoPoint[] holeEdgePoints = hole.getEdgePoints(); for (final GeoPoint p : holeEdgePoints) { edgePoints[edgePointCount++] = p; } } } if (isWithinHoles(points.get(0))) { throw new IllegalArgumentException("Polygon edge intersects a polygon hole; not allowed"); } }
Check if a point is within the provided holes.
Params:
  • point – point to check.
Returns:true if the point is within any of the holes.
/** Check if a point is within the provided holes. *@param point point to check. *@return true if the point is within any of the holes. */
protected boolean isWithinHoles(final GeoPoint point) { if (holes != null) { for (final GeoPolygon hole : holes) { if (!hole.isWithin(point)) { return true; } } } return false; }
Compute a legal point index from a possibly illegal one, that may have wrapped.
Params:
  • index – is the index.
Returns:the normalized index.
/** Compute a legal point index from a possibly illegal one, that may have wrapped. *@param index is the index. *@return the normalized index. */
protected int legalIndex(int index) { while (index >= points.size()) index -= points.size(); while (index < 0) { index += points.size(); } return index; }
Constructor for deserialization.
Params:
  • planetModel – is the planet model.
  • inputStream – is the input stream.
/** * Constructor for deserialization. * @param planetModel is the planet model. * @param inputStream is the input stream. */
public GeoConcavePolygon(final PlanetModel planetModel, final InputStream inputStream) throws IOException { super(planetModel); this.points = java.util.Arrays.asList(SerializableObject.readPointArray(planetModel, inputStream)); final List<GeoPolygon> holes = java.util.Arrays.asList(SerializableObject.readPolygonArray(planetModel, inputStream)); if (holes != null && holes.size() == 0) { this.holes = null; } else { this.holes = holes; } this.isInternalEdges = SerializableObject.readBitSet(inputStream); done(this.isInternalEdges.get(points.size()-1)); } @Override public void write(final OutputStream outputStream) throws IOException { SerializableObject.writePointArray(outputStream, points); SerializableObject.writePolygonArray(outputStream, holes); SerializableObject.writeBitSet(outputStream, isInternalEdges); } @Override public boolean isWithin(final double x, final double y, final double z) { if (!localIsWithin(x, y, z)) { return false; } if (holes != null) { for (final GeoPolygon polygon : holes) { if (!polygon.isWithin(x, y, z)) { return false; } } } return true; } protected boolean localIsWithin(final Vector v) { return localIsWithin(v.x, v.y, v.z); } protected boolean localIsWithin(final double x, final double y, final double z) { // If present within *any* plane, then it is a member, except where there are holes. boolean isMember = false; for (final SidedPlane edge : edges) { if (edge.isWithin(x, y, z)) { isMember = true; break; } } return isMember; } @Override public GeoPoint[] getEdgePoints() { return edgePoints; } @Override public boolean intersects(final Plane p, final GeoPoint[] notablePoints, final Membership... bounds) { // The bounding planes are inverted and complementary. For intersection computation, we // cannot use them as bounds. They are independent hemispheres. for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) { final SidedPlane edge = edges[edgeIndex]; final SidedPlane invertedEdge = invertedEdges[edgeIndex]; final GeoPoint[] points = this.notableEdgePoints[edgeIndex]; if (!isInternalEdges.get(edgeIndex)) { //System.err.println("Checking concave edge "+edge+" for intersection against plane "+p); if (invertedEdge.intersects(planetModel, p, notablePoints, points, bounds, eitherBounds.get(edge))) { //System.err.println(" intersects!"); return true; } } } if (holes != null) { // Each hole needs to be looked at for intersection too, since a shape can be entirely within the hole for (final GeoPolygon hole : holes) { if (hole.intersects(p, notablePoints, bounds)) { return true; } } } //System.err.println(" no intersection"); return false; } @Override public boolean intersects(GeoShape geoShape) { for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) { final SidedPlane edge = edges[edgeIndex]; final GeoPoint[] points = this.notableEdgePoints[edgeIndex]; if (!isInternalEdges.get(edgeIndex)) { if (geoShape.intersects(edge, points, eitherBounds.get(edge))) { return true; } } } if (holes != null) { for (final GeoPolygon hole : holes) { if (hole.intersects(geoShape)) { return true; } } } return false; }
A membership implementation representing polygon edges that must apply.
/** A membership implementation representing polygon edges that must apply. */
protected static class EitherBound implements Membership { protected final SidedPlane sideBound1; protected final SidedPlane sideBound2;
Constructor.
Params:
  • sideBound1 – is the first side bound.
  • sideBound2 – is the second side bound.
/** Constructor. * @param sideBound1 is the first side bound. * @param sideBound2 is the second side bound. */
public EitherBound(final SidedPlane sideBound1, final SidedPlane sideBound2) { this.sideBound1 = sideBound1; this.sideBound2 = sideBound2; } @Override public boolean isWithin(final Vector v) { return sideBound1.isWithin(v) && sideBound2.isWithin(v); } @Override public boolean isWithin(final double x, final double y, final double z) { return sideBound1.isWithin(x,y,z) && sideBound2.isWithin(x,y,z); } @Override public String toString() { return "(" + sideBound1 + "," + sideBound2 + ")"; } } @Override public void getBounds(Bounds bounds) { // Because of holes, we don't want to use superclass method if (localIsWithin(planetModel.NORTH_POLE)) { bounds.noTopLatitudeBound().noLongitudeBound() .addPoint(planetModel.NORTH_POLE); } if (localIsWithin(planetModel.SOUTH_POLE)) { bounds.noBottomLatitudeBound().noLongitudeBound() .addPoint(planetModel.SOUTH_POLE); } if (localIsWithin(planetModel.MIN_X_POLE)) { bounds.addPoint(planetModel.MIN_X_POLE); } if (localIsWithin(planetModel.MAX_X_POLE)) { bounds.addPoint(planetModel.MAX_X_POLE); } if (localIsWithin(planetModel.MIN_Y_POLE)) { bounds.addPoint(planetModel.MIN_Y_POLE); } if (localIsWithin(planetModel.MAX_Y_POLE)) { bounds.addPoint(planetModel.MAX_Y_POLE); } bounds.isWide(); // Add all the points for (final GeoPoint point : points) { bounds.addPoint(point); } // Add planes with membership. for (final SidedPlane edge : edges) { bounds.addPlane(planetModel, edge, eitherBounds.get(edge)); } for (final SidedPlane invertedEdge : invertedEdges) { final SidedPlane nextEdge = nextBrotherMap.get(invertedEdge); bounds.addIntersection(planetModel, invertedEdge, nextEdge, prevBrotherMap.get(invertedEdge), nextBrotherMap.get(nextEdge)); } } @Override protected double outsideDistance(final DistanceStyle distanceStyle, final double x, final double y, final double z) { double minimumDistance = Double.POSITIVE_INFINITY; for (final GeoPoint edgePoint : points) { final double newDist = distanceStyle.computeDistance(edgePoint, x,y,z); if (newDist < minimumDistance) { minimumDistance = newDist; } } for (final SidedPlane edgePlane : edges) { final double newDist = distanceStyle.computeDistance(planetModel, edgePlane, x, y, z, eitherBounds.get(edgePlane)); if (newDist < minimumDistance) { minimumDistance = newDist; } } if (holes != null) { for (final GeoPolygon hole : holes) { double holeDistance = hole.computeOutsideDistance(distanceStyle, x, y, z); if (holeDistance != 0.0 && holeDistance < minimumDistance) { minimumDistance = holeDistance; } } } return minimumDistance; } @Override public boolean equals(Object o) { if (!(o instanceof GeoConcavePolygon)) return false; final GeoConcavePolygon other = (GeoConcavePolygon) o; if (!super.equals(other)) return false; if (!other.isInternalEdges.equals(isInternalEdges)) return false; if (other.holes != null || holes != null) { if (other.holes == null || holes == null) { return false; } if (!other.holes.equals(holes)) { return false; } } return (other.points.equals(points)); } @Override public int hashCode() { int result = super.hashCode(); result = 31 * result + points.hashCode(); if (holes != null) { result = 31 * result + holes.hashCode(); } return result; } @Override public String toString() { return "GeoConcavePolygon: {planetmodel=" + planetModel + ", points=" + points + ", internalEdges=" + isInternalEdges + ((holes== null)?"":", holes=" + holes) + "}"; } }