I will remove this branch. Let's debate on the issue instead: https://issues.apache.org/jira/browse/LUCENE-7157
Mike McCandless http://blog.mikemccandless.com On Sun, Apr 3, 2016 at 9:08 AM, Robert Muir <rcm...@gmail.com> wrote: > I'm not going to argue with you about why GeoConcavePolygon.java > should not be public. > > Instead, you can convince me why it should be. public should not be the > default. > > On Sun, Apr 3, 2016 at 8:56 AM, Karl Wright <daddy...@gmail.com> wrote: >>>>>>>> >> No, I responded to the commit, because I already said on the ticket "i >> don't think a user should have to know about concaveness", and then I >> see GeoConcavePolygon.java added in this commit!!!!!!!! >> <<<<<< >> >> The API that you helped define uses point clockwise/counter-clockwise >> ordering to determine what side of the polygon edge is the "inside" of the >> polygon. I do not see how you can finesse this. >> >> Users use GeoPolygonFactory.makeGeoPolygon() to construct complex polygons. >> They don't need to know about convexity or concavity. They only need to >> know about point ordering. >> >> So I fail to understand your point? >> >> Karl >> >> >> >> <<<<<< >> >> >> >> On Sun, Apr 3, 2016 at 8:48 AM, Robert Muir <rcm...@gmail.com> wrote: >>> >>> No, I responded to the commit, because I already said on the ticket "i >>> don't think a user should have to know about concaveness", and then I >>> see GeoConcavePolygon.java added in this commit!!!!!!!! >>> >>> >>> >>> On Sun, Apr 3, 2016 at 8:40 AM, Karl Wright <daddy...@gmail.com> wrote: >>> > Hi Robert, >>> > >>> > In case you are unaware, I am not a committer. I just uploaded the >>> > patch. >>> > Mike created a branch to allow us to collaborate more easily. I do not >>> > think anything has hit trunk -- but if it did, I'm unaware of it. >>> > >>> > Do you want me to remove the patch from the ticket? >>> > >>> > Karl >>> > >>> > >>> > On Sun, Apr 3, 2016 at 8:37 AM, Robert Muir <rcm...@gmail.com> wrote: >>> >> >>> >> My concern has everything to do with the ticket. Please back the change >>> >> out. >>> >> >>> >> We are an API and so adding a public class is a very serious thing. >>> >> >>> >> On Sun, Apr 3, 2016 at 8:14 AM, Karl Wright <daddy...@gmail.com> wrote: >>> >> > Robert, >>> >> > >>> >> > Your concern is noted but that has nothing really to do with this >>> >> > ticket. >>> >> > Would you mind creating another ticket for re-engineering Geo3D so >>> >> > that >>> >> > it >>> >> > has fewer public classes? Doing things piecemeal as part of another >>> >> > ticket, >>> >> > especially one as complex as this one, does not seem like the right >>> >> > way >>> >> > to >>> >> > go. >>> >> > >>> >> > Karl >>> >> > >>> >> > >>> >> > On Sun, Apr 3, 2016 at 8:09 AM, Robert Muir <rcm...@gmail.com> wrote: >>> >> >> >>> >> >> Why does this change need to add so many public classes? I already >>> >> >> mentioned on the issue: the user need not concern themselves with >>> >> >> these impl details. >>> >> >> >>> >> >> It is frustrating that this package has 60 public classes (and if >>> >> >> everything is public, why the hell does it need factories?). Can we >>> >> >> please make these classes package private? If this cannot be done in >>> >> >> an obvious way, then can you please back out the commit and we do >>> >> >> whatever redesign is necessary. Certainly, I think we can all agree >>> >> >> that having both public factories and making the things they create >>> >> >> public too (which all of this is impl detail) is completely bogus. >>> >> >> >>> >> >> I know that I will frustrate you with this response, but we have to >>> >> >> stop the patient from bleeding or it will never get better. >>> >> >> >>> >> >> On Sat, Apr 2, 2016 at 5:58 PM, <mikemcc...@apache.org> wrote: >>> >> >> > Repository: lucene-solr >>> >> >> > Updated Branches: >>> >> >> > refs/heads/lucene-7157 [created] 98e04cf49 >>> >> >> > >>> >> >> > >>> >> >> > LUCENE_7157: current patch >>> >> >> > >>> >> >> > >>> >> >> > Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo >>> >> >> > Commit: >>> >> >> > http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/98e04cf4 >>> >> >> > Tree: >>> >> >> > http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/98e04cf4 >>> >> >> > Diff: >>> >> >> > http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/98e04cf4 >>> >> >> > >>> >> >> > Branch: refs/heads/lucene-7157 >>> >> >> > Commit: 98e04cf49c7a4d5a551679792da7c3fa9559013f >>> >> >> > Parents: 9ed95bc >>> >> >> > Author: Mike McCandless <mikemcc...@apache.org> >>> >> >> > Authored: Sat Apr 2 18:00:43 2016 -0400 >>> >> >> > Committer: Mike McCandless <mikemcc...@apache.org> >>> >> >> > Committed: Sat Apr 2 18:00:43 2016 -0400 >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > ---------------------------------------------------------------------- >>> >> >> > .../org/apache/lucene/spatial3d/Geo3DPoint.java | 8 +- >>> >> >> > .../spatial3d/geom/GeoConcavePolygon.java | 380 ++++++++ >>> >> >> > .../lucene/spatial3d/geom/GeoConvexPolygon.java | 162 +++- >>> >> >> > .../spatial3d/geom/GeoPolygonFactory.java | 857 >>> >> >> > ++++++++++++++++--- >>> >> >> > .../lucene/spatial3d/geom/SidedPlane.java | 20 +- >>> >> >> > .../lucene/spatial3d/geom/GeoPolygonTest.java | 78 +- >>> >> >> > 6 files changed, 1355 insertions(+), 150 deletions(-) >>> >> >> > >>> >> >> > >>> >> >> > ---------------------------------------------------------------------- >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/98e04cf4/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java >>> >> >> > >>> >> >> > >>> >> >> > ---------------------------------------------------------------------- >>> >> >> > diff --git >>> >> >> > >>> >> >> > >>> >> >> > a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java >>> >> >> > >>> >> >> > >>> >> >> > b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java >>> >> >> > index 45e17b7..f0f2020 100644 >>> >> >> > --- >>> >> >> > >>> >> >> > >>> >> >> > a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java >>> >> >> > +++ >>> >> >> > >>> >> >> > >>> >> >> > b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java >>> >> >> > @@ -22,6 +22,7 @@ import java.util.ArrayList; >>> >> >> > import org.apache.lucene.document.Field; >>> >> >> > import org.apache.lucene.document.FieldType; >>> >> >> > import org.apache.lucene.index.PointValues; >>> >> >> > +import org.apache.lucene.spatial3d.geom.Vector; >>> >> >> > import org.apache.lucene.spatial3d.geom.GeoPoint; >>> >> >> > import org.apache.lucene.spatial3d.geom.GeoShape; >>> >> >> > import org.apache.lucene.spatial3d.geom.PlanetModel; >>> >> >> > @@ -149,11 +150,8 @@ public final class Geo3DPoint extends Field { >>> >> >> > checkLongitude(longitude); >>> >> >> > polyPoints.add(new GeoPoint(PlanetModel.WGS84, >>> >> >> > fromDegrees(latitude), fromDegrees(longitude))); >>> >> >> > } >>> >> >> > - // We don't know what the sense of the polygon is without >>> >> >> > providing >>> >> >> > the index of one vertex we know to be convex. >>> >> >> > - // Since that doesn't fit with the "super-simple API" >>> >> >> > requirements, >>> >> >> > we just use the index of the first one, and people have to just >>> >> >> > - // know to do it that way. >>> >> >> > - final int convexPointIndex = 0; >>> >> >> > - final GeoShape shape = >>> >> >> > GeoPolygonFactory.makeGeoPolygon(PlanetModel.WGS84, polyPoints, >>> >> >> > convexPointIndex); >>> >> >> > + // We use the polygon constructor that looks at point order. >>> >> >> > + final GeoShape shape = >>> >> >> > GeoPolygonFactory.makeGeoPolygon(PlanetModel.WGS84, polyPoints, >>> >> >> > null); >>> >> >> > return newShapeQuery(field, shape); >>> >> >> > } >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/98e04cf4/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConcavePolygon.java >>> >> >> > >>> >> >> > >>> >> >> > ---------------------------------------------------------------------- >>> >> >> > diff --git >>> >> >> > >>> >> >> > >>> >> >> > a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConcavePolygon.java >>> >> >> > >>> >> >> > >>> >> >> > b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConcavePolygon.java >>> >> >> > new file mode 100644 >>> >> >> > index 0000000..9c60f69 >>> >> >> > --- /dev/null >>> >> >> > +++ >>> >> >> > >>> >> >> > >>> >> >> > b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConcavePolygon.java >>> >> >> > @@ -0,0 +1,380 @@ >>> >> >> > +/* >>> >> >> > + * 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; >>> >> >> > + >>> >> >> > +/** >>> >> >> > + * 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.experimental >>> >> >> > + */ >>> >> >> > +public class GeoConcavePolygon extends GeoBasePolygon { >>> >> >> > + /** The list of polygon points */ >>> >> >> > + protected final List<GeoPoint> points; >>> >> >> > + /** 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 */ >>> >> >> > + protected final List<GeoPolygon> holes; >>> >> >> > + >>> >> >> > + /** A list of edges */ >>> >> >> > + protected SidedPlane[] edges = null; >>> >> >> > + /** A list of inverted edges */ >>> >> >> > + protected SidedPlane[] invertedEdges = null; >>> >> >> > + /** The set of notable points for each edge */ >>> >> >> > + protected GeoPoint[][] notableEdgePoints = null; >>> >> >> > + /** A point which is on the boundary of the polygon */ >>> >> >> > + protected GeoPoint[] edgePoints = null; >>> >> >> > + /** Tracking the maximum distance we go at any one time, so to >>> >> >> > be >>> >> >> > sure it's legal */ >>> >> >> > + protected double fullDistance = 0.0; >>> >> >> > + /** Set to true when the polygon is complete */ >>> >> >> > + protected boolean isDone = false; >>> >> >> > + >>> >> >> > + protected Membership eitherBound = new EitherBound(); >>> >> >> > + >>> >> >> > + /** >>> >> >> > + * 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. >>> >> >> > + *@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; >>> >> >> > + 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. >>> >> >> > + *@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. >>> >> >> > + *@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; >>> >> >> > + 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: {@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: {@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<>(); >>> >> >> > + 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: {@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. >>> >> >> > + *@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)); >>> >> >> > + final double distance = start.arcDistance(end); >>> >> >> > + if (distance > fullDistance) >>> >> >> > + fullDistance = distance; >>> >> >> > + final GeoPoint check = points.get(legalIndex(i + 2)); >>> >> >> > + // Here note the flip of the sense of the sided plane!! >>> >> >> > + final SidedPlane sp = new SidedPlane(check, false, start, >>> >> >> > end); >>> >> >> > + //System.out.println("Created edge "+sp+" using >>> >> >> > start="+start+" >>> >> >> > end="+end+" check="+check); >>> >> >> > + edges[i] = sp; >>> >> >> > + invertedEdges[i] = new SidedPlane(sp); >>> >> >> > + notableEdgePoints[i] = new GeoPoint[]{start, end}; >>> >> >> > + } >>> >> >> > + // In order to naively confirm that the polygon is concave, I >>> >> >> > would >>> >> >> > need to >>> >> >> > + // check every edge, and verify that every point (other than >>> >> >> > the >>> >> >> > edge endpoints) >>> >> >> > + // is within the edge's sided plane. This is an order n^2 >>> >> >> > operation. That's still >>> >> >> > + // not wrong, though, because everything else about polygons >>> >> >> > has >>> >> >> > a >>> >> >> > similar cost. >>> >> >> > + for (int edgeIndex = 0; edgeIndex < edges.length; >>> >> >> > edgeIndex++) { >>> >> >> > + final SidedPlane edge = edges[edgeIndex]; >>> >> >> > + for (int pointIndex = 0; pointIndex < points.size(); >>> >> >> > pointIndex++) { >>> >> >> > + if (pointIndex != edgeIndex && pointIndex != >>> >> >> > legalIndex(edgeIndex + 1)) { >>> >> >> > + if (edge.isWithin(points.get(pointIndex))) >>> >> >> > + throw new IllegalArgumentException("Polygon is not >>> >> >> > concave: >>> >> >> > Point " + points.get(pointIndex) + " Edge " + edge); >>> >> >> > + } >>> >> >> > + } >>> >> >> > + } >>> >> >> > + // Pick an edge point arbitrarily >>> >> >> > + edgePoints = new GeoPoint[]{points.get(0)}; >>> >> >> > + } >>> >> >> > + >>> >> >> > + /** 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(); >>> >> >> > + return index; >>> >> >> > + } >>> >> >> > + >>> >> >> > + @Override >>> >> >> > + public boolean isWithin(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; >>> >> >> > + } >>> >> >> > + } >>> >> >> > + if (isMember == false) { >>> >> >> > + return false; >>> >> >> > + } >>> >> >> > + if (holes != null) { >>> >> >> > + for (final GeoPolygon polygon : holes) { >>> >> >> > + if (polygon.isWithin(x, y, z)) { >>> >> >> > + return false; >>> >> >> > + } >>> >> >> > + } >>> >> >> > + } >>> >> >> > + return true; >>> >> >> > + } >>> >> >> > + >>> >> >> > + @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 GeoPoint[] points = >>> >> >> > this.notableEdgePoints[edgeIndex]; >>> >> >> > + if (!isInternalEdges.get(edgeIndex)) { >>> >> >> > + if (edge.intersects(planetModel, p, notablePoints, >>> >> >> > points, >>> >> >> > bounds, eitherBound)) { >>> >> >> > + //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; >>> >> >> > + } >>> >> >> > + >>> >> >> > + /** A membership implementation representing a wide bound where >>> >> >> > planes are complementary. >>> >> >> > + */ >>> >> >> > + protected class EitherBound implements Membership { >>> >> >> > + /** Constructor. >>> >> >> > + */ >>> >> >> > + public EitherBound() { >>> >> >> > + } >>> >> >> > + >>> >> >> > + @Override >>> >> >> > + public boolean isWithin(final Vector v) { >>> >> >> > + for (final SidedPlane edge : invertedEdges) { >>> >> >> > + if (!edge.isWithin(v)) { >>> >> >> > + return false; >>> >> >> > + } >>> >> >> > + } >>> >> >> > + return true; >>> >> >> > + } >>> >> >> > + >>> >> >> > + @Override >>> >> >> > + public boolean isWithin(final double x, final double y, final >>> >> >> > double z) { >>> >> >> > + for (final SidedPlane edge : invertedEdges) { >>> >> >> > + if (!edge.isWithin(x, y, z)) { >>> >> >> > + return false; >>> >> >> > + } >>> >> >> > + } >>> >> >> > + return true; >>> >> >> > + } >>> >> >> > + } >>> >> >> > + >>> >> >> > + @Override >>> >> >> > + public void getBounds(Bounds bounds) { >>> >> >> > + super.getBounds(bounds); >>> >> >> > + 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, eitherBound); >>> >> >> > + } >>> >> >> > + } >>> >> >> > + >>> >> >> > + @Override >>> >> >> > + protected double outsideDistance(final DistanceStyle >>> >> >> > distanceStyle, >>> >> >> > final double x, final double y, final double z) { >>> >> >> > + double minimumDistance = Double.MAX_VALUE; >>> >> >> > + for (final GeoPoint edgePoint : points) { >>> >> >> > + final double newDist = >>> >> >> > distanceStyle.computeDistance(edgePoint, >>> >> >> > x,y,z); >>> >> >> > + if (newDist < minimumDistance) { >>> >> >> > + minimumDistance = newDist; >>> >> >> > + } >>> >> >> > + } >>> >> >> > + for (final Plane edgePlane : edges) { >>> >> >> > + final double newDist = >>> >> >> > distanceStyle.computeDistance(planetModel, >>> >> >> > edgePlane, x, y, z, eitherBound); >>> >> >> > + if (newDist < minimumDistance) { >>> >> >> > + minimumDistance = newDist; >>> >> >> > + } >>> >> >> > + } >>> >> >> > + return minimumDistance; >>> >> >> > + } >>> >> >> > + >>> >> >> > + @Override >>> >> >> > + public boolean equals(Object o) { >>> >> >> > + if (!(o instanceof GeoConcavePolygon)) >>> >> >> > + return false; >>> >> >> > + 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 + ((holes== null)?"":", holes=" + holes) + "}"; >>> >> >> > + } >>> >> >> > +} >>> >> >> > + >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/98e04cf4/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java >>> >> >> > >>> >> >> > >>> >> >> > ---------------------------------------------------------------------- >>> >> >> > diff --git >>> >> >> > >>> >> >> > >>> >> >> > a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java >>> >> >> > >>> >> >> > >>> >> >> > b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java >>> >> >> > index fb024b6..a03c50a 100755 >>> >> >> > --- >>> >> >> > >>> >> >> > >>> >> >> > a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java >>> >> >> > +++ >>> >> >> > >>> >> >> > >>> >> >> > b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java >>> >> >> > @@ -33,6 +33,8 @@ public class GeoConvexPolygon extends >>> >> >> > GeoBasePolygon { >>> >> >> > protected final List<GeoPoint> points; >>> >> >> > /** 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 */ >>> >> >> > + protected final List<GeoPolygon> holes; >>> >> >> > >>> >> >> > /** A list of edges */ >>> >> >> > protected SidedPlane[] edges = null; >>> >> >> > @@ -44,6 +46,8 @@ public class GeoConvexPolygon extends >>> >> >> > GeoBasePolygon { >>> >> >> > protected double fullDistance = 0.0; >>> >> >> > /** Set to true when the polygon is complete */ >>> >> >> > protected boolean isDone = false; >>> >> >> > + >>> >> >> > + protected Membership eitherBound = new EitherBound(); >>> >> >> > >>> >> >> > /** >>> >> >> > * Create a convex polygon from a list of points. The first >>> >> >> > point >>> >> >> > must be on the >>> >> >> > @@ -52,8 +56,20 @@ public class GeoConvexPolygon extends >>> >> >> > GeoBasePolygon >>> >> >> > { >>> >> >> > *@param pointList is the list of points to create the polygon >>> >> >> > from. >>> >> >> > */ >>> >> >> > public GeoConvexPolygon(final PlanetModel planetModel, final >>> >> >> > List<GeoPoint> pointList) { >>> >> >> > + this(planetModel, pointList, null); >>> >> >> > + } >>> >> >> > + >>> >> >> > + /** >>> >> >> > + * Create a convex 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 complex polygon. Null == no holes. >>> >> >> > + */ >>> >> >> > + public GeoConvexPolygon(final PlanetModel planetModel, final >>> >> >> > List<GeoPoint> pointList, final List<GeoPolygon> holes) { >>> >> >> > super(planetModel); >>> >> >> > this.points = pointList; >>> >> >> > + this.holes = holes; >>> >> >> > this.isInternalEdges = new BitSet(); >>> >> >> > done(false); >>> >> >> > } >>> >> >> > @@ -66,10 +82,30 @@ public class GeoConvexPolygon extends >>> >> >> > GeoBasePolygon >>> >> >> > { >>> >> >> > *@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 GeoConvexPolygon(final PlanetModel planetModel, final >>> >> >> > List<GeoPoint> pointList, final BitSet internalEdgeFlags, >>> >> >> > - final boolean returnEdgeInternal) { >>> >> >> > + public GeoConvexPolygon(final PlanetModel planetModel, >>> >> >> > + final List<GeoPoint> pointList, >>> >> >> > + final BitSet internalEdgeFlags, >>> >> >> > + final boolean returnEdgeInternal) { >>> >> >> > + this(planetModel, pointList, null, internalEdgeFlags, >>> >> >> > returnEdgeInternal); >>> >> >> > + } >>> >> >> > + >>> >> >> > + /** >>> >> >> > + * Create a convex 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 complex 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 GeoConvexPolygon(final PlanetModel planetModel, >>> >> >> > + final List<GeoPoint> pointList, >>> >> >> > + final List<GeoPolygon> holes, >>> >> >> > + final BitSet internalEdgeFlags, >>> >> >> > + final boolean returnEdgeInternal) { >>> >> >> > super(planetModel); >>> >> >> > this.points = pointList; >>> >> >> > + this.holes = holes; >>> >> >> > this.isInternalEdges = internalEdgeFlags; >>> >> >> > done(returnEdgeInternal); >>> >> >> > } >>> >> >> > @@ -81,9 +117,27 @@ public class GeoConvexPolygon extends >>> >> >> > GeoBasePolygon >>> >> >> > { >>> >> >> > *@param startLatitude is the latitude of the first point. >>> >> >> > *@param startLongitude is the longitude of the first point. >>> >> >> > */ >>> >> >> > - public GeoConvexPolygon(final PlanetModel planetModel, final >>> >> >> > double >>> >> >> > startLatitude, final double startLongitude) { >>> >> >> > + public GeoConvexPolygon(final PlanetModel planetModel, >>> >> >> > + final double startLatitude, >>> >> >> > + final double startLongitude) { >>> >> >> > + this(planetModel, startLatitude, startLongitude, null); >>> >> >> > + } >>> >> >> > + >>> >> >> > + /** >>> >> >> > + * Create a convex 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 complex polygon. Null == no holes. >>> >> >> > + */ >>> >> >> > + public GeoConvexPolygon(final PlanetModel planetModel, >>> >> >> > + final double startLatitude, >>> >> >> > + final double startLongitude, >>> >> >> > + final List<GeoPolygon> holes) { >>> >> >> > super(planetModel); >>> >> >> > points = new ArrayList<>(); >>> >> >> > + this.holes = holes; >>> >> >> > isInternalEdges = new BitSet(); >>> >> >> > points.add(new GeoPoint(planetModel, startLatitude, >>> >> >> > startLongitude)); >>> >> >> > } >>> >> >> > @@ -138,12 +192,6 @@ public class GeoConvexPolygon extends >>> >> >> > GeoBasePolygon { >>> >> >> > edges[i] = sp; >>> >> >> > notableEdgePoints[i] = new GeoPoint[]{start, end}; >>> >> >> > } >>> >> >> > - createCenterPoint(); >>> >> >> > - } >>> >> >> > - >>> >> >> > - /** Compute a reasonable center point. >>> >> >> > - */ >>> >> >> > - protected void createCenterPoint() { >>> >> >> > // In order to naively confirm that the polygon is convex, I >>> >> >> > would >>> >> >> > need to >>> >> >> > // check every edge, and verify that every point (other than >>> >> >> > the >>> >> >> > edge endpoints) >>> >> >> > // is within the edge's sided plane. This is an order n^2 >>> >> >> > operation. That's still >>> >> >> > @@ -157,6 +205,7 @@ public class GeoConvexPolygon extends >>> >> >> > GeoBasePolygon >>> >> >> > { >>> >> >> > } >>> >> >> > } >>> >> >> > } >>> >> >> > + // Pick an edge point arbitrarily >>> >> >> > edgePoints = new GeoPoint[]{points.get(0)}; >>> >> >> > } >>> >> >> > >>> >> >> > @@ -176,6 +225,13 @@ public class GeoConvexPolygon extends >>> >> >> > GeoBasePolygon { >>> >> >> > if (!edge.isWithin(x, y, z)) >>> >> >> > return false; >>> >> >> > } >>> >> >> > + if (holes != null) { >>> >> >> > + for (final GeoPolygon polygon : holes) { >>> >> >> > + if (polygon.isWithin(x, y, z)) { >>> >> >> > + return false; >>> >> >> > + } >>> >> >> > + } >>> >> >> > + } >>> >> >> > return true; >>> >> >> > } >>> >> >> > >>> >> >> > @@ -191,26 +247,54 @@ public class GeoConvexPolygon extends >>> >> >> > GeoBasePolygon { >>> >> >> > final SidedPlane edge = edges[edgeIndex]; >>> >> >> > final GeoPoint[] points = >>> >> >> > this.notableEdgePoints[edgeIndex]; >>> >> >> > if (!isInternalEdges.get(edgeIndex)) { >>> >> >> > - //System.err.println(" non-internal edge "+edge); >>> >> >> > - // Edges flagged as 'internal only' are excluded from the >>> >> >> > matching >>> >> >> > - // Construct boundaries >>> >> >> > - final Membership[] membershipBounds = new >>> >> >> > Membership[edges.length - 1]; >>> >> >> > - int count = 0; >>> >> >> > - for (int otherIndex = 0; otherIndex < edges.length; >>> >> >> > otherIndex++) { >>> >> >> > - if (otherIndex != edgeIndex) { >>> >> >> > - membershipBounds[count++] = edges[otherIndex]; >>> >> >> > - } >>> >> >> > - } >>> >> >> > - if (edge.intersects(planetModel, p, notablePoints, >>> >> >> > points, >>> >> >> > bounds, membershipBounds)) { >>> >> >> > + if (edge.intersects(planetModel, p, notablePoints, >>> >> >> > points, >>> >> >> > bounds, eitherBound)) { >>> >> >> > //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; >>> >> >> > } >>> >> >> > >>> >> >> > + /** A membership implementation representing polygon edges that >>> >> >> > all >>> >> >> > must apply. >>> >> >> > + */ >>> >> >> > + protected class EitherBound implements Membership { >>> >> >> > + /** Constructor. >>> >> >> > + */ >>> >> >> > + public EitherBound() { >>> >> >> > + } >>> >> >> > + >>> >> >> > + @Override >>> >> >> > + public boolean isWithin(final Vector v) { >>> >> >> > + for (final SidedPlane edge : edges) { >>> >> >> > + if (!edge.isWithin(v)) { >>> >> >> > + return false; >>> >> >> > + } >>> >> >> > + } >>> >> >> > + return true; >>> >> >> > + } >>> >> >> > + >>> >> >> > + @Override >>> >> >> > + public boolean isWithin(final double x, final double y, final >>> >> >> > double z) { >>> >> >> > + for (final SidedPlane edge : edges) { >>> >> >> > + if (!edge.isWithin(x, y, z)) { >>> >> >> > + return false; >>> >> >> > + } >>> >> >> > + } >>> >> >> > + return true; >>> >> >> > + } >>> >> >> > + } >>> >> >> > + >>> >> >> > + >>> >> >> > @Override >>> >> >> > public void getBounds(Bounds bounds) { >>> >> >> > super.getBounds(bounds); >>> >> >> > @@ -221,17 +305,8 @@ public class GeoConvexPolygon extends >>> >> >> > GeoBasePolygon { >>> >> >> > } >>> >> >> > >>> >> >> > // Add planes with membership. >>> >> >> > - for (int edgeIndex = 0; edgeIndex < edges.length; >>> >> >> > edgeIndex++) { >>> >> >> > - final SidedPlane edge = edges[edgeIndex]; >>> >> >> > - // Construct boundaries >>> >> >> > - final Membership[] membershipBounds = new >>> >> >> > Membership[edges.length >>> >> >> > - 1]; >>> >> >> > - int count = 0; >>> >> >> > - for (int otherIndex = 0; otherIndex < edges.length; >>> >> >> > otherIndex++) >>> >> >> > { >>> >> >> > - if (otherIndex != edgeIndex) { >>> >> >> > - membershipBounds[count++] = edges[otherIndex]; >>> >> >> > - } >>> >> >> > - } >>> >> >> > - bounds.addPlane(planetModel, edge, membershipBounds); >>> >> >> > + for (final SidedPlane edge : edges) { >>> >> >> > + bounds.addPlane(planetModel, edge, eitherBound); >>> >> >> > } >>> >> >> > } >>> >> >> > >>> >> >> > @@ -244,16 +319,8 @@ public class GeoConvexPolygon extends >>> >> >> > GeoBasePolygon { >>> >> >> > minimumDistance = newDist; >>> >> >> > } >>> >> >> > } >>> >> >> > - for (int edgeIndex = 0; edgeIndex < edges.length; >>> >> >> > edgeIndex++) { >>> >> >> > - final Plane edgePlane = edges[edgeIndex]; >>> >> >> > - final Membership[] membershipBounds = new >>> >> >> > Membership[edges.length >>> >> >> > - 1]; >>> >> >> > - int count = 0; >>> >> >> > - for (int otherIndex = 0; otherIndex < edges.length; >>> >> >> > otherIndex++) >>> >> >> > { >>> >> >> > - if (otherIndex != edgeIndex) { >>> >> >> > - membershipBounds[count++] = edges[otherIndex]; >>> >> >> > - } >>> >> >> > - } >>> >> >> > - final double newDist = >>> >> >> > distanceStyle.computeDistance(planetModel, >>> >> >> > edgePlane, x, y, z, membershipBounds); >>> >> >> > + for (final Plane edgePlane : edges) { >>> >> >> > + final double newDist = >>> >> >> > distanceStyle.computeDistance(planetModel, >>> >> >> > edgePlane, x, y, z, eitherBound); >>> >> >> > if (newDist < minimumDistance) { >>> >> >> > minimumDistance = newDist; >>> >> >> > } >>> >> >> > @@ -270,6 +337,14 @@ public class GeoConvexPolygon extends >>> >> >> > GeoBasePolygon { >>> >> >> > 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)); >>> >> >> > } >>> >> >> > >>> >> >> > @@ -277,12 +352,15 @@ public class GeoConvexPolygon extends >>> >> >> > GeoBasePolygon { >>> >> >> > 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 "GeoConvexPolygon: {planetmodel=" + planetModel + ", >>> >> >> > points=" + points + "}"; >>> >> >> > + return "GeoConvexPolygon: {planetmodel=" + planetModel + ", >>> >> >> > points=" + points + ((holes== null)?"":", holes=" + holes) + "}"; >>> >> >> > } >>> >> >> > } >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/98e04cf4/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java >>> >> >> > >>> >> >> > >>> >> >> > ---------------------------------------------------------------------- >>> >> >> > diff --git >>> >> >> > >>> >> >> > >>> >> >> > a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java >>> >> >> > >>> >> >> > >>> >> >> > b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java >>> >> >> > index 8ee4290..f076d41 100755 >>> >> >> > --- >>> >> >> > >>> >> >> > >>> >> >> > a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java >>> >> >> > +++ >>> >> >> > >>> >> >> > >>> >> >> > b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java >>> >> >> > @@ -19,6 +19,12 @@ package org.apache.lucene.spatial3d.geom; >>> >> >> > import java.util.ArrayList; >>> >> >> > import java.util.BitSet; >>> >> >> > import java.util.List; >>> >> >> > +import java.util.Random; >>> >> >> > +import java.util.Iterator; >>> >> >> > +import java.util.Set; >>> >> >> > +import java.util.HashSet; >>> >> >> > +import java.util.Map; >>> >> >> > +import java.util.HashMap; >>> >> >> > >>> >> >> > /** >>> >> >> > * Class which constructs a GeoMembershipShape representing an >>> >> >> > arbitrary polygon. >>> >> >> > @@ -37,138 +43,619 @@ public class GeoPolygonFactory { >>> >> >> > * its neighbors determines >>> >> >> > inside/outside >>> >> >> > for the entire polygon. >>> >> >> > * @return a GeoPolygon corresponding to what was specified. >>> >> >> > */ >>> >> >> > - public static GeoPolygon makeGeoPolygon(final PlanetModel >>> >> >> > planetModel, final List<GeoPoint> pointList, final int >>> >> >> > convexPointIndex) { >>> >> >> > + public static GeoPolygon makeGeoPolygon(final PlanetModel >>> >> >> > planetModel, >>> >> >> > + final List<GeoPoint> pointList, >>> >> >> > + final int convexPointIndex) { >>> >> >> > + return makeGeoPolygon(planetModel, pointList, >>> >> >> > convexPointIndex, >>> >> >> > null); >>> >> >> > + } >>> >> >> > + >>> >> >> > + /** >>> >> >> > + * Create a GeoMembershipShape of the right kind given the >>> >> >> > specified >>> >> >> > bounds. >>> >> >> > + * >>> >> >> > + * @param pointList is a list of the GeoPoints to build >>> >> >> > an >>> >> >> > arbitrary polygon out of. >>> >> >> > + * @param convexPointIndex is the index of a single convex >>> >> >> > point >>> >> >> > whose conformation with >>> >> >> > + * its neighbors determines >>> >> >> > inside/outside >>> >> >> > for the entire polygon. >>> >> >> > + * @param holes is a list of polygons representing "holes" in >>> >> >> > the >>> >> >> > outside polygon. Null == none. >>> >> >> > + * @return a GeoPolygon corresponding to what was specified. >>> >> >> > + */ >>> >> >> > + public static GeoPolygon makeGeoPolygon(final PlanetModel >>> >> >> > planetModel, >>> >> >> > + final List<GeoPoint> pointList, >>> >> >> > + final int convexPointIndex, >>> >> >> > + final List<GeoPolygon> holes) { >>> >> >> > // The basic operation uses a set of points, two points >>> >> >> > determining >>> >> >> > one particular edge, and a sided plane >>> >> >> > // describing membership. >>> >> >> > return buildPolygonShape(planetModel, pointList, >>> >> >> > convexPointIndex, >>> >> >> > getLegalIndex(convexPointIndex + 1, pointList.size()), >>> >> >> > new >>> >> >> > SidedPlane(pointList.get(getLegalIndex(convexPointIndex >>> >> >> > - >>> >> >> > 1, pointList.size())), >>> >> >> > pointList.get(convexPointIndex), >>> >> >> > pointList.get(getLegalIndex(convexPointIndex + 1, >>> >> >> > pointList.size()))), >>> >> >> > - false); >>> >> >> > + false, >>> >> >> > + holes, >>> >> >> > + null); >>> >> >> > + } >>> >> >> > + >>> >> >> > + /** Create a GeoPolygon using the specified points and holes, >>> >> >> > using >>> >> >> > order to determine >>> >> >> > + * siding of the polygon. Much like ESRI, this method uses >>> >> >> > clockwise >>> >> >> > to indicate the space >>> >> >> > + * on the same side of the shape as being inside, and >>> >> >> > counter-clockwise to indicate the >>> >> >> > + * space on the opposite side as being inside. >>> >> >> > + * @param pointList is a list of the GeoPoints to build an >>> >> >> > arbitrary >>> >> >> > polygon out of. If points go >>> >> >> > + * clockwise from a given pole, then that pole should be >>> >> >> > within >>> >> >> > the >>> >> >> > polygon. If points go >>> >> >> > + * counter-clockwise, then that pole should be outside the >>> >> >> > polygon. >>> >> >> > + * @return a GeoPolygon corresponding to what was specified. >>> >> >> > + */ >>> >> >> > + public static GeoPolygon makeGeoPolygon(final PlanetModel >>> >> >> > planetModel, >>> >> >> > + final List<GeoPoint> pointList) { >>> >> >> > + return makeGeoPolygon(planetModel, pointList, null); >>> >> >> > + } >>> >> >> > + >>> >> >> > + /** Create a GeoPolygon using the specified points and holes, >>> >> >> > using >>> >> >> > order to determine >>> >> >> > + * siding of the polygon. Much like ESRI, this method uses >>> >> >> > clockwise >>> >> >> > to indicate the space >>> >> >> > + * on the same side of the shape as being inside, and >>> >> >> > counter-clockwise to indicate the >>> >> >> > + * space on the opposite side as being inside. >>> >> >> > + * @param pointList is a list of the GeoPoints to build an >>> >> >> > arbitrary >>> >> >> > polygon out of. If points go >>> >> >> > + * clockwise from a given pole, then that pole should be >>> >> >> > within >>> >> >> > the >>> >> >> > polygon. If points go >>> >> >> > + * counter-clockwise, then that pole should be outside the >>> >> >> > polygon. >>> >> >> > + * @param holes is a list of polygons representing "holes" in >>> >> >> > the >>> >> >> > outside polygon. Null == none. >>> >> >> > + * @return a GeoPolygon corresponding to what was specified. >>> >> >> > + */ >>> >> >> > + public static GeoPolygon makeGeoPolygon(final PlanetModel >>> >> >> > planetModel, >>> >> >> > + final List<GeoPoint> pointList, >>> >> >> > + final List<GeoPolygon> holes) { >>> >> >> > + // Create a random number generator. Effectively this >>> >> >> > furnishes >>> >> >> > us >>> >> >> > with a repeatable sequence >>> >> >> > + // of points to use for poles. >>> >> >> > + final Random generator = new Random(1234); >>> >> >> > + while (true) { >>> >> >> > + // Pick the next random pole >>> >> >> > + final double poleLat = generator.nextDouble() * Math.PI - >>> >> >> > Math.PI >>> >> >> > * 0.5; >>> >> >> > + final double poleLon = generator.nextDouble() * Math.PI * >>> >> >> > 2.0 >>> >> >> > - >>> >> >> > Math.PI; >>> >> >> > + final GeoPoint pole = new GeoPoint(planetModel, poleLat, >>> >> >> > poleLon); >>> >> >> > + // Is it inside or outside? >>> >> >> > + final Boolean isPoleInside = isInsidePolygon(pole, >>> >> >> > pointList); >>> >> >> > + if (isPoleInside != null) { >>> >> >> > + // Legal pole >>> >> >> > + return makeGeoPolygon(planetModel, pointList, holes, >>> >> >> > pole, >>> >> >> > isPoleInside); >>> >> >> > + } >>> >> >> > + // If pole choice was illegal, try another one >>> >> >> > + } >>> >> >> > + } >>> >> >> > + >>> >> >> > + /** >>> >> >> > + * Create a GeoPolygon using the specified points and holes and >>> >> >> > a >>> >> >> > test point. >>> >> >> > + * >>> >> >> > + * @param pointList is a list of the GeoPoints to build >>> >> >> > an >>> >> >> > arbitrary polygon out of. >>> >> >> > + * @param holes is a list of polygons representing "holes" in >>> >> >> > the >>> >> >> > outside polygon. Null == none. >>> >> >> > + * @param testPoint is a test point that is either known to be >>> >> >> > within >>> >> >> > the polygon area, or not. >>> >> >> > + * @param testPointInside is true if the test point is within >>> >> >> > the >>> >> >> > area, false otherwise. >>> >> >> > + * @return a GeoPolygon corresponding to what was specified. >>> >> >> > + */ >>> >> >> > + public static GeoPolygon makeGeoPolygon(final PlanetModel >>> >> >> > planetModel, >>> >> >> > + final List<GeoPoint> pointList, >>> >> >> > + final List<GeoPolygon> holes, >>> >> >> > + final GeoPoint testPoint, >>> >> >> > + final boolean testPointInside) { >>> >> >> > + // We will be trying twice to find the right GeoPolygon, >>> >> >> > using >>> >> >> > alternate siding choices for the first polygon >>> >> >> > + // side. While this looks like it might be 2x as expensive >>> >> >> > as >>> >> >> > it >>> >> >> > could be, there's really no other choice I can >>> >> >> > + // find. >>> >> >> > + final SidedPlane initialPlane = new SidedPlane(testPoint, >>> >> >> > pointList.get(0), pointList.get(1)); >>> >> >> > + // We don't know if this is the correct siding choice. We >>> >> >> > will >>> >> >> > only know as we build the complex polygon. >>> >> >> > + // So we need to be prepared to try both possibilities. >>> >> >> > + final GeoPolygon trial = buildPolygonShape(planetModel, >>> >> >> > pointList, >>> >> >> > 0, 1, initialPlane, false, holes, testPoint); >>> >> >> > + if (trial == null) { >>> >> >> > + // The testPoint was within the shape. Was that intended? >>> >> >> > + if (testPointInside) { >>> >> >> > + // Yes: build it for real >>> >> >> > + return buildPolygonShape(planetModel, pointList, 0, 1, >>> >> >> > initialPlane, false, holes, null); >>> >> >> > + } >>> >> >> > + // No: do the complement and return that. >>> >> >> > + return buildPolygonShape(planetModel, pointList, 0, 1, new >>> >> >> > SidedPlane(initialPlane), false, holes, null); >>> >> >> > + } else { >>> >> >> > + // The testPoint was outside the shape. Was that intended? >>> >> >> > + if (!testPointInside) { >>> >> >> > + // Yes: return what we just built >>> >> >> > + return trial; >>> >> >> > + } >>> >> >> > + // No: return the complement >>> >> >> > + return buildPolygonShape(planetModel, pointList, 0, 1, new >>> >> >> > SidedPlane(initialPlane), false, holes, null); >>> >> >> > + } >>> >> >> > + } >>> >> >> > + >>> >> >> > + /** For a specified point and a list of poly points, determine >>> >> >> > based >>> >> >> > on point order whether the >>> >> >> > + * point should be considered in or out of the polygon. >>> >> >> > + * @param point is the point to check. >>> >> >> > + * @param polyPoints is the list of points comprising the >>> >> >> > polygon. >>> >> >> > + * @return null if the point is illegal, otherwise false if the >>> >> >> > point >>> >> >> > is inside and true if the point is outside >>> >> >> > + * of the polygon. >>> >> >> > + */ >>> >> >> > + protected static Boolean isInsidePolygon(final GeoPoint point, >>> >> >> > final >>> >> >> > List<GeoPoint> polyPoints) { >>> >> >> > + // First, compute sine and cosine of pole point latitude and >>> >> >> > longitude >>> >> >> > + final double norm = 1.0 / point.magnitude(); >>> >> >> > + final double xyDenom = Math.sqrt(point.x * point.x + point.y >>> >> >> > * >>> >> >> > point.y); >>> >> >> > + final double sinLatitude = point.z * norm; >>> >> >> > + final double cosLatitude = xyDenom * norm; >>> >> >> > + final double sinLongitude; >>> >> >> > + final double cosLongitude; >>> >> >> > + if (Math.abs(xyDenom) < Vector.MINIMUM_RESOLUTION) { >>> >> >> > + sinLongitude = 0.0; >>> >> >> > + cosLongitude = 1.0; >>> >> >> > + } else { >>> >> >> > + final double xyNorm = 1.0 / xyDenom; >>> >> >> > + sinLongitude = point.y * xyNorm; >>> >> >> > + cosLongitude = point.x * xyNorm; >>> >> >> > + } >>> >> >> > + >>> >> >> > + // Now, compute the incremental arc distance around the >>> >> >> > points >>> >> >> > of >>> >> >> > the polygon >>> >> >> > + double arcDistance = 0.0; >>> >> >> > + Double prevAngle = null; >>> >> >> > + for (final GeoPoint polyPoint : polyPoints) { >>> >> >> > + final Double angle = computeAngle(polyPoint, sinLatitude, >>> >> >> > cosLatitude, sinLongitude, cosLongitude); >>> >> >> > + if (angle == null) { >>> >> >> > + return null; >>> >> >> > + } >>> >> >> > + System.out.println("Computed angle: "+angle); >>> >> >> > + if (prevAngle != null) { >>> >> >> > + // Figure out delta between prevAngle and current angle, >>> >> >> > and >>> >> >> > add it to arcDistance >>> >> >> > + double angleDelta = angle - prevAngle; >>> >> >> > + if (angleDelta < -Math.PI) { >>> >> >> > + angleDelta += Math.PI * 2.0; >>> >> >> > + } >>> >> >> > + if (angleDelta > Math.PI) { >>> >> >> > + angleDelta -= Math.PI * 2.0; >>> >> >> > + } >>> >> >> > + if (Math.abs(angleDelta - Math.PI) < >>> >> >> > Vector.MINIMUM_RESOLUTION) >>> >> >> > { >>> >> >> > + return null; >>> >> >> > + } >>> >> >> > + System.out.println(" angle delta = "+angleDelta); >>> >> >> > + arcDistance += angleDelta; >>> >> >> > + } >>> >> >> > + prevAngle = angle; >>> >> >> > + } >>> >> >> > + if (prevAngle != null) { >>> >> >> > + final Double lastAngle = computeAngle(polyPoints.get(0), >>> >> >> > sinLatitude, cosLatitude, sinLongitude, cosLongitude); >>> >> >> > + if (lastAngle == null) { >>> >> >> > + return null; >>> >> >> > + } >>> >> >> > + System.out.println("Computed last angle: "+lastAngle); >>> >> >> > + // Figure out delta and add it >>> >> >> > + double angleDelta = lastAngle - prevAngle; >>> >> >> > + if (angleDelta < -Math.PI) { >>> >> >> > + angleDelta += Math.PI * 2.0; >>> >> >> > + } >>> >> >> > + if (angleDelta > Math.PI) { >>> >> >> > + angleDelta -= Math.PI * 2.0; >>> >> >> > + } >>> >> >> > + if (Math.abs(angleDelta - Math.PI) < >>> >> >> > Vector.MINIMUM_RESOLUTION) { >>> >> >> > + return null; >>> >> >> > + } >>> >> >> > + System.out.println(" angle delta = "+angleDelta); >>> >> >> > + arcDistance += angleDelta; >>> >> >> > + } >>> >> >> > + // Clockwise == inside == negative >>> >> >> > + System.out.println("Arcdistance = "+arcDistance); >>> >> >> > + if (Math.abs(arcDistance) < Vector.MINIMUM_RESOLUTION) { >>> >> >> > + // No idea what direction, so try another pole. >>> >> >> > + return null; >>> >> >> > + } >>> >> >> > + return arcDistance < 0.0; >>> >> >> > + } >>> >> >> > + >>> >> >> > + protected static Double computeAngle(final GeoPoint point, >>> >> >> > + final double sinLatitude, >>> >> >> > + final double cosLatitude, >>> >> >> > + final double sinLongitude, >>> >> >> > + final double cosLongitude) { >>> >> >> > + // Coordinate rotation formula: >>> >> >> > + // x1 = x0 cos T - y0 sin T >>> >> >> > + // y1 = x0 sin T + y0 cos T >>> >> >> > + // We need to rotate the point in question into the >>> >> >> > coordinate >>> >> >> > frame specified by >>> >> >> > + // the lat and lon trig functions. >>> >> >> > + // To do this we need to do two rotations on it. First >>> >> >> > rotation >>> >> >> > is >>> >> >> > in x/y. Second rotation is in x/z. >>> >> >> > + // So: >>> >> >> > + // x1 = x0 cos az - y0 sin az >>> >> >> > + // y1 = x0 sin az + y0 cos az >>> >> >> > + // z1 = z0 >>> >> >> > + // x2 = x1 cos al - z1 sin al >>> >> >> > + // y2 = y1 >>> >> >> > + // z2 = x1 sin al + z1 cos al >>> >> >> > + >>> >> >> > + final double x1 = point.x * cosLongitude - point.y * >>> >> >> > sinLongitude; >>> >> >> > + final double y1 = point.x * sinLongitude + point.y * >>> >> >> > cosLongitude; >>> >> >> > + final double z1 = point.z; >>> >> >> > + //final double x2 = x1 * cosLatitude - z1 * sinLatitude; >>> >> >> > + final double y2 = y1; >>> >> >> > + final double z2 = x1 * sinLatitude + z1 * cosLatitude; >>> >> >> > + >>> >> >> > + // Now we should be looking down the X axis; the original >>> >> >> > point >>> >> >> > has >>> >> >> > rotated coordinates (N, 0, 0). >>> >> >> > + // So we can just compute the angle using y2 and z2. (If >>> >> >> > Math.sqrt(y2*y2 + z2 * z2) is 0.0, then the point is on the pole >>> >> >> > and >>> >> >> > we need >>> >> >> > another one). >>> >> >> > + if (Math.sqrt(y2*y2 + z2*z2) < Vector.MINIMUM_RESOLUTION) { >>> >> >> > + return null; >>> >> >> > + } >>> >> >> > + >>> >> >> > + return Math.atan2(z2, y2); >>> >> >> > } >>> >> >> > >>> >> >> > - /** Build a GeoMembershipShape given points, starting edge, and >>> >> >> > whether starting edge is internal or not. >>> >> >> > + /** Build a GeoPolygon out of one concave part and multiple >>> >> >> > convex >>> >> >> > parts given points, starting edge, and whether starting edge is >>> >> >> > internal or >>> >> >> > not. >>> >> >> > * @param pointsList is a list of the GeoPoints to build >>> >> >> > an >>> >> >> > arbitrary polygon out of. >>> >> >> > - * @param startPointIndex is one of the points constituting the >>> >> >> > starting edge. >>> >> >> > - * @param endPointIndex is another of the points constituting >>> >> >> > the >>> >> >> > starting edge. >>> >> >> > + * @param startPointIndex is the first of the points, >>> >> >> > constituting >>> >> >> > the starting edge. >>> >> >> > * @param startingEdge is the plane describing the starting >>> >> >> > edge. >>> >> >> > * @param isInternalEdge is true if the specified edge is an >>> >> >> > internal >>> >> >> > one. >>> >> >> > - * @return a GeoMembershipShape corresponding to what was >>> >> >> > specified. >>> >> >> > + * @param holes is the list of holes in the polygon, or null if >>> >> >> > none. >>> >> >> > + * @param testPoint is an (optional) test point, which will be >>> >> >> > used >>> >> >> > to determine if we are generating >>> >> >> > + * a shape with the proper sidedness. It is passed in only >>> >> >> > when >>> >> >> > the >>> >> >> > test point is supposed to be outside >>> >> >> > + * of the generated polygon. In this case, if the generated >>> >> >> > polygon >>> >> >> > is found to contain the point, the >>> >> >> > + * method exits early with a null return value. >>> >> >> > + * This only makes sense in the context of evaluating both >>> >> >> > possible >>> >> >> > choices and using logic to determine >>> >> >> > + * which result to use. If the test point is supposed to be >>> >> >> > within >>> >> >> > the shape, then it must be outside of the >>> >> >> > + * complement shape. If the test point is supposed to be >>> >> >> > outside >>> >> >> > the shape, then it must be outside of the >>> >> >> > + * original shape. Either way, we can figure out the right >>> >> >> > thing >>> >> >> > to >>> >> >> > use. >>> >> >> > + * @return a GeoMembershipShape corresponding to what was >>> >> >> > specified, >>> >> >> > or null if what was specified >>> >> >> > + * was inconsistent with what we generated. Specifically, if >>> >> >> > we >>> >> >> > specify an exterior point that is >>> >> >> > + * found in the interior of the shape we create here we return >>> >> >> > null, >>> >> >> > which is a signal that we chose >>> >> >> > + * our initial plane sidedness backwards. >>> >> >> > */ >>> >> >> > - public static GeoPolygon buildPolygonShape(final PlanetModel >>> >> >> > planetModel, final List<GeoPoint> pointsList, final int >>> >> >> > startPointIndex, >>> >> >> > final int endPointIndex, final SidedPlane startingEdge, final >>> >> >> > boolean >>> >> >> > isInternalEdge) { >>> >> >> > - // Algorithm as follows: >>> >> >> > - // Start with sided edge. Go through all points in some >>> >> >> > order. >>> >> >> > For each new point, determine if the point is within all edges >>> >> >> > considered so >>> >> >> > far. >>> >> >> > - // If not, put it into a list of points for recursion. If it >>> >> >> > is >>> >> >> > within, add new edge and keep going. >>> >> >> > - // Once we detect a point that is within, if there are points >>> >> >> > put >>> >> >> > aside for recursion, then call recursively. >>> >> >> > + public static GeoPolygon buildPolygonShape( >>> >> >> > + final PlanetModel planetModel, >>> >> >> > + final List<GeoPoint> pointsList, >>> >> >> > + final int startPointIndex, >>> >> >> > + final int endPointIndex, >>> >> >> > + final SidedPlane startingEdge, >>> >> >> > + final boolean isInternalEdge, >>> >> >> > + final List<GeoPolygon> holes, >>> >> >> > + final GeoPoint testPoint) { >>> >> >> > >>> >> >> > - // Current composite. This is what we'll actually be >>> >> >> > returning. >>> >> >> > + // It could be the case that we need a concave polygon. So >>> >> >> > we >>> >> >> > need >>> >> >> > to try and look for that case >>> >> >> > + // as part of the general code for constructing complex >>> >> >> > polygons. >>> >> >> > + >>> >> >> > + // Note that there can be only one concave polygon. >>> >> >> > + >>> >> >> > + // The code here must keep track of two lists of sided >>> >> >> > planes. >>> >> >> > The >>> >> >> > first list contains the planes consistent with >>> >> >> > + // a concave polygon. This list will grow and shrink. The >>> >> >> > second >>> >> >> > list is built starting at the current edge that >>> >> >> > + // was last consistent with the concave polygon, and contains >>> >> >> > all >>> >> >> > edges consistent with a convex polygon. >>> >> >> > + // When that sequence of edges is done, then an internal edge >>> >> >> > is >>> >> >> > created and the identified points are converted to a >>> >> >> > + // convex polygon. That internal edge is used to extend the >>> >> >> > list >>> >> >> > of edges in the concave polygon edge list. >>> >> >> > + >>> >> >> > + // The edge buffer. >>> >> >> > + final EdgeBuffer edgeBuffer = new EdgeBuffer(pointsList, >>> >> >> > startPointIndex, endPointIndex, startingEdge, isInternalEdge); >>> >> >> > + >>> >> >> > + // Current composite. This is what we'll actually be >>> >> >> > returning. >>> >> >> > This will have a number of convex polygons, and >>> >> >> > + // maybe a single concave one too. >>> >> >> > final GeoCompositePolygon rval = new GeoCompositePolygon(); >>> >> >> > >>> >> >> > - final List<GeoPoint> recursionList = new >>> >> >> > ArrayList<GeoPoint>(); >>> >> >> > - final List<GeoPoint> currentList = new ArrayList<GeoPoint>(); >>> >> >> > - final BitSet internalEdgeList = new BitSet(); >>> >> >> > - final List<SidedPlane> currentPlanes = new >>> >> >> > ArrayList<SidedPlane>(); >>> >> >> > - >>> >> >> > - // Initialize the current list and current planes >>> >> >> > - currentList.add(pointsList.get(startPointIndex)); >>> >> >> > - currentList.add(pointsList.get(endPointIndex)); >>> >> >> > - internalEdgeList.set(currentPlanes.size(), isInternalEdge); >>> >> >> > - currentPlanes.add(startingEdge); >>> >> >> > - >>> >> >> > - // Now, scan all remaining points, in order. We'll use an >>> >> >> > index >>> >> >> > and just add to it. >>> >> >> > - for (int i = 0; i < pointsList.size() - 2; i++) { >>> >> >> > - GeoPoint newPoint = pointsList.get(getLegalIndex(i + >>> >> >> > endPointIndex + 1, pointsList.size())); >>> >> >> > - if (isWithin(newPoint, currentPlanes)) { >>> >> >> > - // Construct a sided plane based on the last two points, >>> >> >> > and >>> >> >> > the previous point >>> >> >> > - SidedPlane newBoundary = new >>> >> >> > SidedPlane(currentList.get(currentList.size() - 2), newPoint, >>> >> >> > currentList.get(currentList.size() - 1)); >>> >> >> > - // Construct a sided plane based on the return trip >>> >> >> > - SidedPlane returnBoundary = new >>> >> >> > SidedPlane(currentList.get(currentList.size() - 1), >>> >> >> > currentList.get(0), >>> >> >> > newPoint); >>> >> >> > - // Verify that none of the points beyond the new point in >>> >> >> > the >>> >> >> > list are inside the polygon we'd >>> >> >> > - // be creating if we stopped making the current polygon >>> >> >> > right >>> >> >> > now. >>> >> >> > - boolean pointInside = false; >>> >> >> > - for (int j = i + 1; j < pointsList.size() - 2; j++) { >>> >> >> > - GeoPoint checkPoint = pointsList.get(getLegalIndex(j + >>> >> >> > endPointIndex + 1, pointsList.size())); >>> >> >> > - boolean isInside = true; >>> >> >> > - if (isInside && !newBoundary.isWithin(checkPoint)) >>> >> >> > - isInside = false; >>> >> >> > - if (isInside && !returnBoundary.isWithin(checkPoint)) >>> >> >> > - isInside = false; >>> >> >> > - if (isInside) { >>> >> >> > - for (SidedPlane plane : currentPlanes) { >>> >> >> > - if (!plane.isWithin(checkPoint)) { >>> >> >> > - isInside = false; >>> >> >> > + // Starting state: >>> >> >> > + // The stopping point >>> >> >> > + Edge stoppingPoint = edgeBuffer.pickOne(); >>> >> >> > + // The current edge >>> >> >> > + Edge currentEdge = stoppingPoint; >>> >> >> > + >>> >> >> > + // Progressively look for convex sections. If we find one, >>> >> >> > we >>> >> >> > emit >>> >> >> > it and replace it. >>> >> >> > + // Keep going until we have been around once and nothing >>> >> >> > needed >>> >> >> > to >>> >> >> > change, and then >>> >> >> > + // do the concave polygon, if necessary. >>> >> >> > + while (true) { >>> >> >> > + >>> >> >> > + if (currentEdge == null) { >>> >> >> > + // We're done! >>> >> >> > + break; >>> >> >> > + } >>> >> >> > + >>> >> >> > + // Find convexity around the current edge, if any >>> >> >> > + final Boolean foundIt = findConvexPolygon(planetModel, >>> >> >> > currentEdge, rval, edgeBuffer, holes, testPoint); >>> >> >> > + if (foundIt == null) { >>> >> >> > + return null; >>> >> >> > + } >>> >> >> > + >>> >> >> > + if (foundIt) { >>> >> >> > + // New start point >>> >> >> > + stoppingPoint = edgeBuffer.pickOne(); >>> >> >> > + currentEdge = stoppingPoint; >>> >> >> > + // back around >>> >> >> > + continue; >>> >> >> > + } >>> >> >> > + >>> >> >> > + // Otherwise, go on to the next >>> >> >> > + currentEdge = edgeBuffer.getNext(currentEdge); >>> >> >> > + if (currentEdge == stoppingPoint) { >>> >> >> > + break; >>> >> >> > + } >>> >> >> > + } >>> >> >> > + >>> >> >> > + // If there's anything left in the edge buffer, convert to >>> >> >> > concave >>> >> >> > polygon. >>> >> >> > + if (makeConcavePolygon(planetModel, rval, edgeBuffer, holes, >>> >> >> > testPoint) == false) { >>> >> >> > + return null; >>> >> >> > + } >>> >> >> > + >>> >> >> > + return rval; >>> >> >> > + } >>> >> >> > + >>> >> >> > + /** Look for a concave polygon in the remainder of the >>> >> >> > edgebuffer. >>> >> >> > + * By this point, if there are any edges in the edgebuffer, >>> >> >> > they >>> >> >> > represent a concave polygon. >>> >> >> > + * @param planetModel is the planet model. >>> >> >> > + * @param rval is the composite polygon we're building. >>> >> >> > + * @param edgeBuffer is the edge buffer. >>> >> >> > + * @param holes is the optional list of holes. >>> >> >> > + * @param testPoint is the optional test point. >>> >> >> > + * @return true unless the testPoint caused failure. >>> >> >> > + */ >>> >> >> > + protected static boolean makeConcavePolygon(final PlanetModel >>> >> >> > planetModel, >>> >> >> > + final GeoCompositePolygon rval, >>> >> >> > + final EdgeBuffer edgeBuffer, >>> >> >> > + final List<GeoPolygon> holes, >>> >> >> > + final GeoPoint testPoint) { >>> >> >> > + if (edgeBuffer.size() == 0) { >>> >> >> > + return true; >>> >> >> > + } >>> >> >> > + >>> >> >> > + // If there are less than three edges, something got messed >>> >> >> > up >>> >> >> > somehow. Don't know how this >>> >> >> > + // can happen but check. >>> >> >> > + if (edgeBuffer.size() < 3) { >>> >> >> > + throw new IllegalStateException("Ending edge buffer had >>> >> >> > only >>> >> >> > "+edgeBuffer.size()+" edges"); >>> >> >> > + } >>> >> >> > + >>> >> >> > + // Create the list of points >>> >> >> > + final List<GeoPoint> points = new >>> >> >> > ArrayList<GeoPoint>(edgeBuffer.size()); >>> >> >> > + final BitSet internalEdges = new BitSet(edgeBuffer.size()-1); >>> >> >> > + >>> >> >> > + Edge edge = edgeBuffer.pickOne(); >>> >> >> > + boolean isInternal = edge.isInternal; >>> >> >> > + for (int i = 0; i < edgeBuffer.size(); i++) { >>> >> >> > + points.add(edge.startPoint); >>> >> >> > + if (i < edgeBuffer.size() - 1) { >>> >> >> > + internalEdges.set(i, isInternal); >>> >> >> > + } >>> >> >> > + edge = edgeBuffer.getNext(edge); >>> >> >> > + isInternal = edge.isInternal; >>> >> >> > + } >>> >> >> > + >>> >> >> > + if (testPoint != null && holes != null && holes.size() > 0) { >>> >> >> > + // No holes, for test >>> >> >> > + final GeoPolygon testPolygon = new >>> >> >> > GeoConcavePolygon(planetModel, >>> >> >> > points, null, internalEdges, isInternal); >>> >> >> > + if (testPolygon.isWithin(testPoint)) { >>> >> >> > + return false; >>> >> >> > + } >>> >> >> > + } >>> >> >> > + >>> >> >> > + final GeoPolygon realPolygon = new >>> >> >> > GeoConcavePolygon(planetModel, >>> >> >> > points, holes, internalEdges, isInternal); >>> >> >> > + if (testPoint != null && (holes == null || holes.size() == >>> >> >> > 0)) { >>> >> >> > + if (realPolygon.isWithin(testPoint)) { >>> >> >> > + return false; >>> >> >> > + } >>> >> >> > + } >>> >> >> > + >>> >> >> > + rval.addShape(realPolygon); >>> >> >> > + return true; >>> >> >> > + } >>> >> >> > + >>> >> >> > + /** Look for a convex polygon at the specified edge. If we >>> >> >> > find >>> >> >> > it, >>> >> >> > create one and adjust the edge buffer. >>> >> >> > + * @param planetModel is the planet model. >>> >> >> > + * @param currentEdge is the current edge to use starting the >>> >> >> > search. >>> >> >> > + * @param rval is the composite polygon to build. >>> >> >> > + * @param edgeBuffer is the edge buffer. >>> >> >> > + * @param holes is the optional list of holes. >>> >> >> > + * @param testPoint is the optional test point. >>> >> >> > + * @return null if the testPoint is within any polygon >>> >> >> > detected, >>> >> >> > otherwise true if a convex polygon was created. >>> >> >> > + */ >>> >> >> > + protected static Boolean findConvexPolygon(final PlanetModel >>> >> >> > planetModel, >>> >> >> > + final Edge currentEdge, >>> >> >> > + final GeoCompositePolygon rval, >>> >> >> > + final EdgeBuffer edgeBuffer, >>> >> >> > + final List<GeoPolygon> holes, >>> >> >> > + final GeoPoint testPoint) { >>> >> >> > + >>> >> >> > + //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 (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) { >>> >> >> > + 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 (isInside) { >>> >> >> > - pointInside = true; >>> >> >> > - break; >>> >> >> > - } >>> >> >> > } >>> >> >> > - if (!pointInside) { >>> >> >> > - // Any excluded points? >>> >> >> > - boolean isInternalBoundary = recursionList.size() > 0; >>> >> >> > - if (isInternalBoundary) { >>> >> >> > - // Handle exclusion >>> >> >> > - recursionList.add(newPoint); >>> >> >> > - recursionList.add(currentList.get(currentList.size() >>> >> >> > - >>> >> >> > 1)); >>> >> >> > - if (recursionList.size() == pointsList.size()) { >>> >> >> > - // We are trying to recurse with a list the same >>> >> >> > size >>> >> >> > as >>> >> >> > the one we started with. >>> >> >> > - // Clearly, the polygon cannot be constructed >>> >> >> > - throw new IllegalArgumentException("Polygon is >>> >> >> > illegal; >>> >> >> > cannot be decomposed into convex parts"); >>> >> >> > + >>> >> >> > + 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 (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) { >>> >> >> > + 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; >>> >> >> > + } >>> >> >> > } >>> >> >> > - // We want the other side for the recursion >>> >> >> > - SidedPlane otherSideNewBoundary = new >>> >> >> > SidedPlane(newBoundary); >>> >> >> > - rval.addShape(buildPolygonShape(planetModel, >>> >> >> > recursionList, >>> >> >> > recursionList.size() - 2, recursionList.size() - 1, >>> >> >> > otherSideNewBoundary, >>> >> >> > true)); >>> >> >> > - recursionList.clear(); >>> >> >> > } >>> >> >> > - currentList.add(newPoint); >>> >> >> > - internalEdgeList.set(currentPlanes.size(), >>> >> >> > isInternalBoundary); >>> >> >> > - currentPlanes.add(newBoundary); >>> >> >> > - } else { >>> >> >> > - recursionList.add(newPoint); >>> >> >> > } >>> >> >> > - } else { >>> >> >> > - recursionList.add(newPoint); >>> >> >> > + >>> >> >> > + 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; >>> >> >> > } >>> >> >> > >>> >> >> > - boolean returnEdgeInternalBoundary = recursionList.size() > >>> >> >> > 0; >>> >> >> > - if (returnEdgeInternalBoundary) { >>> >> >> > - // The last step back to the start point had a recursion, >>> >> >> > so >>> >> >> > take >>> >> >> > care of that before we complete our work >>> >> >> > - recursionList.add(currentList.get(0)); >>> >> >> > - recursionList.add(currentList.get(currentList.size() - 1)); >>> >> >> > - if (recursionList.size() == pointsList.size()) { >>> >> >> > - // We are trying to recurse with a list the same size as >>> >> >> > the >>> >> >> > one we started with. >>> >> >> > - // Clearly, the polygon cannot be constructed >>> >> >> > - throw new IllegalArgumentException("Polygon is illegal; >>> >> >> > cannot >>> >> >> > be decomposed into convex parts"); >>> >> >> > + // 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()); >>> >> >> > + final BitSet internalEdges = new >>> >> >> > BitSet(includedEdges.size()-1); >>> >> >> > + final boolean returnIsInternal; >>> >> >> > + >>> >> >> > + if (firstEdge.startPoint == lastEdge.endPoint) { >>> >> >> > + // Degenerate case!! There is no return edge -- or rather, >>> >> >> > we >>> >> >> > already have it. >>> >> >> > + Edge edge = firstEdge; >>> >> >> > + points.add(edge.startPoint); >>> >> >> > + int i = 0; >>> >> >> > + while (true) { >>> >> >> > + if (edge == lastEdge) { >>> >> >> > + break; >>> >> >> > + } >>> >> >> > + points.add(edge.endPoint); >>> >> >> > + internalEdges.set(i++, edge.isInternal); >>> >> >> > + edge = edgeBuffer.getNext(edge); >>> >> >> > } >>> >> >> > - // Construct a sided plane based on these two points, and >>> >> >> > the >>> >> >> > previous point >>> >> >> > - SidedPlane newBoundary = new >>> >> >> > SidedPlane(currentList.get(currentList.size() - 2), >>> >> >> > currentList.get(0), >>> >> >> > currentList.get(currentList.size() - 1)); >>> >> >> > - // We want the other side for the recursion >>> >> >> > - SidedPlane otherSideNewBoundary = new >>> >> >> > SidedPlane(newBoundary); >>> >> >> > - rval.addShape(buildPolygonShape(planetModel, recursionList, >>> >> >> > recursionList.size() - 2, recursionList.size() - 1, >>> >> >> > otherSideNewBoundary, >>> >> >> > true)); >>> >> >> > - recursionList.clear(); >>> >> >> > + 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); >>> >> >> > + >>> >> >> > + // Build point list and edge list >>> >> >> > + final List<Edge> edges = new >>> >> >> > ArrayList<Edge>(includedEdges.size()); >>> >> >> > + returnIsInternal = true; >>> >> >> > + >>> >> >> > + Edge edge = firstEdge; >>> >> >> > + points.add(edge.startPoint); >>> >> >> > + int i = 0; >>> >> >> > + while (true) { >>> >> >> > + points.add(edge.endPoint); >>> >> >> > + internalEdges.set(i++, edge.isInternal); >>> >> >> > + edges.add(edge); >>> >> >> > + if (edge == lastEdge) { >>> >> >> > + break; >>> >> >> > + } >>> >> >> > + edge = edgeBuffer.getNext(edge); >>> >> >> > + } >>> >> >> > + >>> >> >> > + // Modify the edge buffer >>> >> >> > + edgeBuffer.replace(edges, returnEdge); >>> >> >> > } >>> >> >> > - // Now, add in the current shape. >>> >> >> > - rval.addShape(new GeoConvexPolygon(planetModel, currentList, >>> >> >> > internalEdgeList, returnEdgeInternalBoundary)); >>> >> >> > - //System.out.println("Done creating polygon"); >>> >> >> > - return rval; >>> >> >> > + >>> >> >> > + // Now, construct the polygon >>> >> >> > + 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; >>> >> >> > } >>> >> >> > - >>> >> >> > - /** Check if a point is within a described list of planes. >>> >> >> > - *@param newPoint is the point. >>> >> >> > - *@param currentPlanes is the list of planes. >>> >> >> > - *@return true if within. >>> >> >> > - */ >>> >> >> > - protected static boolean isWithin(final GeoPoint newPoint, >>> >> >> > final >>> >> >> > List<SidedPlane> currentPlanes) { >>> >> >> > - for (SidedPlane p : currentPlanes) { >>> >> >> > - if (!p.isWithin(newPoint)) >>> >> >> > + >>> >> >> > + protected static boolean isWithin(final GeoPoint point, final >>> >> >> > Set<Edge> edgeSet, final Edge extension, final SidedPlane >>> >> >> > returnBoundary) { >>> >> >> > + if (!extension.plane.isWithin(point)) { >>> >> >> > + return false; >>> >> >> > + } >>> >> >> > + if (returnBoundary != null && >>> >> >> > !returnBoundary.isWithin(point)) { >>> >> >> > + return false; >>> >> >> > + } >>> >> >> > + return isWithin(point, edgeSet); >>> >> >> > + } >>> >> >> > + >>> >> >> > + protected static boolean isWithin(final GeoPoint point, final >>> >> >> > Set<Edge> edgeSet) { >>> >> >> > + for (final Edge edge : edgeSet) { >>> >> >> > + if (!edge.plane.isWithin(point)) { >>> >> >> > return false; >>> >> >> > + } >>> >> >> > } >>> >> >> > return true; >>> >> >> > } >>> >> >> > - >>> >> >> > + >>> >> >> > /** Convert raw point index into valid array position. >>> >> >> > *@param index is the array index. >>> >> >> > *@param size is the array size. >>> >> >> > @@ -184,4 +671,174 @@ public class GeoPolygonFactory { >>> >> >> > return index; >>> >> >> > } >>> >> >> > >>> >> >> > + /** Class representing a single (unused) edge. >>> >> >> > + */ >>> >> >> > + protected static class Edge { >>> >> >> > + public final SidedPlane plane; >>> >> >> > + public final GeoPoint startPoint; >>> >> >> > + public final GeoPoint endPoint; >>> >> >> > + public final boolean isInternal; >>> >> >> > + >>> >> >> > + public Edge(final GeoPoint startPoint, final GeoPoint >>> >> >> > endPoint, >>> >> >> > final SidedPlane plane, final boolean isInternal) { >>> >> >> > + this.startPoint = startPoint; >>> >> >> > + this.endPoint = endPoint; >>> >> >> > + this.plane = plane; >>> >> >> > + this.isInternal = isInternal; >>> >> >> > + } >>> >> >> > + >>> >> >> > + @Override >>> >> >> > + public int hashCode() { >>> >> >> > + return System.identityHashCode(this); >>> >> >> > + } >>> >> >> > + >>> >> >> > + @Override >>> >> >> > + public boolean equals(final Object o) { >>> >> >> > + return o == this; >>> >> >> > + } >>> >> >> > + } >>> >> >> > + >>> >> >> > + /** Class representing a pool of unused edges, all linked >>> >> >> > together >>> >> >> > by >>> >> >> > vertices. >>> >> >> > + */ >>> >> >> > + protected static class EdgeBuffer { >>> >> >> > + protected final Set<Edge> edges = new HashSet<>(); >>> >> >> > + protected final Map<Edge, Edge> previousEdges = new >>> >> >> > HashMap<>(); >>> >> >> > + protected final Map<Edge, Edge> nextEdges = new HashMap<>(); >>> >> >> > + >>> >> >> > + public EdgeBuffer(final List<GeoPoint> pointList, final int >>> >> >> > startPlaneStartIndex, final int startPlaneEndIndex, final >>> >> >> > SidedPlane >>> >> >> > startPlane, final boolean startPlaneIsInternal) { >>> >> >> > + /* >>> >> >> > + System.out.println("Initial points:"); >>> >> >> > + for (final GeoPoint p : pointList) { >>> >> >> > + System.out.println(" "+p); >>> >> >> > + } >>> >> >> > + System.out.println("For start plane, the following points >>> >> >> > are >>> >> >> > in/out:"); >>> >> >> > + for (final GeoPoint p: pointList) { >>> >> >> > + System.out.println(" "+p+" is: >>> >> >> > "+(startPlane.isWithin(p)?"in":"out")); >>> >> >> > + } >>> >> >> > + */ >>> >> >> > + >>> >> >> > + final Edge startEdge = new >>> >> >> > Edge(pointList.get(startPlaneStartIndex), >>> >> >> > pointList.get(startPlaneEndIndex), >>> >> >> > startPlane, startPlaneIsInternal); >>> >> >> > + // Fill in the EdgeBuffer by walking around creating more >>> >> >> > stuff >>> >> >> > + Edge currentEdge = startEdge; >>> >> >> > + int startIndex = startPlaneStartIndex; >>> >> >> > + int endIndex = startPlaneEndIndex; >>> >> >> > + boolean isInternal = startPlaneIsInternal; >>> >> >> > + while (true) { >>> >> >> > + // Compute the next edge >>> >> >> > + startIndex = endIndex; >>> >> >> > + endIndex++; >>> >> >> > + if (endIndex >= pointList.size()) { >>> >> >> > + endIndex -= pointList.size(); >>> >> >> > + } >>> >> >> > + // Get the next point >>> >> >> > + final GeoPoint newPoint = pointList.get(endIndex); >>> >> >> > + // Build the new edge >>> >> >> > + final boolean isNewPointWithin = >>> >> >> > currentEdge.plane.isWithin(newPoint); >>> >> >> > + final SidedPlane newPlane = new >>> >> >> > SidedPlane(currentEdge.startPoint, isNewPointWithin, >>> >> >> > pointList.get(startIndex), newPoint); >>> >> >> > + /* >>> >> >> > + System.out.println("For next plane, the following points >>> >> >> > are >>> >> >> > in/out:"); >>> >> >> > + for (final GeoPoint p: pointList) { >>> >> >> > + System.out.println(" "+p+" is: >>> >> >> > "+(newPlane.isWithin(p)?"in":"out")); >>> >> >> > + } >>> >> >> > + */ >>> >> >> > + final Edge newEdge = new Edge(pointList.get(startIndex), >>> >> >> > pointList.get(endIndex), newPlane, false); >>> >> >> > + >>> >> >> > + // Link it in >>> >> >> > + previousEdges.put(newEdge, currentEdge); >>> >> >> > + nextEdges.put(currentEdge, newEdge); >>> >> >> > + edges.add(newEdge); >>> >> >> > + currentEdge = newEdge; >>> >> >> > + >>> >> >> > + if (currentEdge.endPoint == startEdge.startPoint) { >>> >> >> > + // We finish here. Link the current edge to the start >>> >> >> > edge, >>> >> >> > and exit >>> >> >> > + previousEdges.put(startEdge, currentEdge); >>> >> >> > + nextEdges.put(currentEdge, startEdge); >>> >> >> > + edges.add(startEdge); >>> >> >> > + break; >>> >> >> > + } >>> >> >> > + } >>> >> >> > + >>> >> >> > + // Verify the structure. >>> >> >> > + //verify(); >>> >> >> > + } >>> >> >> > + >>> >> >> > + /* >>> >> >> > + protected void verify() { >>> >> >> > + if (edges.size() != previousEdges.size() || edges.size() != >>> >> >> > nextEdges.size()) { >>> >> >> > + throw new IllegalStateException("broken structure"); >>> >> >> > + } >>> >> >> > + // Confirm each edge >>> >> >> > + for (final Edge e : edges) { >>> >> >> > + final Edge previousEdge = getPrevious(e); >>> >> >> > + final Edge nextEdge = getNext(e); >>> >> >> > + if (e.endPoint != nextEdge.startPoint) { >>> >> >> > + throw new IllegalStateException("broken structure"); >>> >> >> > + } >>> >> >> > + if (e.startPoint != previousEdge.endPoint) { >>> >> >> > + throw new IllegalStateException("broken structure"); >>> >> >> > + } >>> >> >> > + if (getNext(previousEdge) != e) { >>> >> >> > + throw new IllegalStateException("broken structure"); >>> >> >> > + } >>> >> >> > + if (getPrevious(nextEdge) != e) { >>> >> >> > + throw new IllegalStateException("broken structure"); >>> >> >> > + } >>> >> >> > + } >>> >> >> > + } >>> >> >> > + */ >>> >> >> > + >>> >> >> > + public Edge getPrevious(final Edge currentEdge) { >>> >> >> > + return previousEdges.get(currentEdge); >>> >> >> > + } >>> >> >> > + >>> >> >> > + public Edge getNext(final Edge currentEdge) { >>> >> >> > + return nextEdges.get(currentEdge); >>> >> >> > + } >>> >> >> > + >>> >> >> > + public void replace(final List<Edge> removeList, final Edge >>> >> >> > newEdge) { >>> >> >> > + /* >>> >> >> > + System.out.println("Replacing: "); >>> >> >> > + for (final Edge e : removeList) { >>> >> >> > + System.out.println(" "+e.startPoint+"-->"+e.endPoint); >>> >> >> > + } >>> >> >> > + System.out.println("...with: >>> >> >> > "+newEdge.startPoint+"-->"+newEdge.endPoint); >>> >> >> > + */ >>> >> >> > + final Edge previous = previousEdges.get(removeList.get(0)); >>> >> >> > + final Edge next = >>> >> >> > nextEdges.get(removeList.get(removeList.size()-1)); >>> >> >> > + edges.add(newEdge); >>> >> >> > + previousEdges.put(newEdge, previous); >>> >> >> > + nextEdges.put(previous, newEdge); >>> >> >> > + previousEdges.put(next, newEdge); >>> >> >> > + nextEdges.put(newEdge, next); >>> >> >> > + for (final Edge edge : removeList) { >>> >> >> > + edges.remove(edge); >>> >> >> > + previousEdges.remove(edge); >>> >> >> > + nextEdges.remove(edge); >>> >> >> > + } >>> >> >> > + //verify(); >>> >> >> > + } >>> >> >> > + >>> >> >> > + public void clear() { >>> >> >> > + edges.clear(); >>> >> >> > + previousEdges.clear(); >>> >> >> > + nextEdges.clear(); >>> >> >> > + } >>> >> >> > + >>> >> >> > + public int size() { >>> >> >> > + return edges.size(); >>> >> >> > + } >>> >> >> > + >>> >> >> > + public Iterator<Edge> iterator() { >>> >> >> > + return edges.iterator(); >>> >> >> > + } >>> >> >> > + >>> >> >> > + public Edge pickOne() { >>> >> >> > + final Iterator<Edge> iter = edges.iterator(); >>> >> >> > + if (iter.hasNext()) { >>> >> >> > + return iter.next(); >>> >> >> > + } >>> >> >> > + return null; >>> >> >> > + } >>> >> >> > + >>> >> >> > + } >>> >> >> > + >>> >> >> > } >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/98e04cf4/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/SidedPlane.java >>> >> >> > >>> >> >> > >>> >> >> > ---------------------------------------------------------------------- >>> >> >> > diff --git >>> >> >> > >>> >> >> > >>> >> >> > a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/SidedPlane.java >>> >> >> > >>> >> >> > >>> >> >> > b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/SidedPlane.java >>> >> >> > index e080bc0..0c19a9e 100755 >>> >> >> > --- >>> >> >> > >>> >> >> > >>> >> >> > a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/SidedPlane.java >>> >> >> > +++ >>> >> >> > >>> >> >> > >>> >> >> > b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/SidedPlane.java >>> >> >> > @@ -31,7 +31,7 @@ public class SidedPlane extends Plane implements >>> >> >> > Membership { >>> >> >> > * >>> >> >> > * @param sidedPlane is the existing plane. >>> >> >> > */ >>> >> >> > - public SidedPlane(SidedPlane sidedPlane) { >>> >> >> > + public SidedPlane(final SidedPlane sidedPlane) { >>> >> >> > super(sidedPlane, sidedPlane.D); >>> >> >> > this.sigNum = -sidedPlane.sigNum; >>> >> >> > } >>> >> >> > @@ -44,7 +44,7 @@ public class SidedPlane extends Plane implements >>> >> >> > Membership { >>> >> >> > * @param A is the first in-plane point >>> >> >> > * @param B is the second in-plane point >>> >> >> > */ >>> >> >> > - public SidedPlane(Vector p, Vector A, Vector B) { >>> >> >> > + public SidedPlane(final Vector p, final Vector A, final Vector >>> >> >> > B) >>> >> >> > { >>> >> >> > super(A, B); >>> >> >> > sigNum = Math.signum(evaluate(p)); >>> >> >> > if (sigNum == 0.0) >>> >> >> > @@ -52,6 +52,22 @@ public class SidedPlane extends Plane >>> >> >> > implements >>> >> >> > Membership { >>> >> >> > } >>> >> >> > >>> >> >> > /** >>> >> >> > + * Construct a sided plane from a pair of vectors describing >>> >> >> > points, >>> >> >> > and including >>> >> >> > + * origin, plus a point p which describes the side. >>> >> >> > + * >>> >> >> > + * @param p point to evaluate >>> >> >> > + * @param onSide is true if the point is on the correct side of >>> >> >> > the >>> >> >> > plane, false otherwise. >>> >> >> > + * @param A is the first in-plane point >>> >> >> > + * @param B is the second in-plane point >>> >> >> > + */ >>> >> >> > + public SidedPlane(final Vector p, final boolean onSide, final >>> >> >> > Vector >>> >> >> > A, final Vector B) { >>> >> >> > + super(A, B); >>> >> >> > + sigNum = >>> >> >> > onSide?Math.signum(evaluate(p)):-Math.signum(evaluate(p)); >>> >> >> > + if (sigNum == 0.0) >>> >> >> > + throw new IllegalArgumentException("Cannot determine >>> >> >> > sidedness >>> >> >> > because check point is on plane."); >>> >> >> > + } >>> >> >> > + >>> >> >> > + /** >>> >> >> > * Construct a sided plane from a point and a Z coordinate. >>> >> >> > * >>> >> >> > * @param p point to evaluate. >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/98e04cf4/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java >>> >> >> > >>> >> >> > >>> >> >> > ---------------------------------------------------------------------- >>> >> >> > diff --git >>> >> >> > >>> >> >> > >>> >> >> > a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java >>> >> >> > >>> >> >> > >>> >> >> > b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java >>> >> >> > index d9b220d..ff9bd90 100755 >>> >> >> > --- >>> >> >> > >>> >> >> > >>> >> >> > a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java >>> >> >> > +++ >>> >> >> > >>> >> >> > >>> >> >> > b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java >>> >> >> > @@ -20,6 +20,7 @@ import java.util.ArrayList; >>> >> >> > import java.util.List; >>> >> >> > >>> >> >> > import org.junit.Test; >>> >> >> > +import org.junit.Ignore; >>> >> >> > >>> >> >> > import static org.junit.Assert.assertEquals; >>> >> >> > import static org.junit.Assert.assertFalse; >>> >> >> > @@ -27,10 +28,44 @@ import static org.junit.Assert.assertTrue; >>> >> >> > >>> >> >> > public class GeoPolygonTest { >>> >> >> > >>> >> >> > + @Ignore >>> >> >> > + @Test >>> >> >> > + public void testPolygonClockwise() { >>> >> >> > + GeoPolygon c; >>> >> >> > + GeoPoint gp; >>> >> >> > + List<GeoPoint> points; >>> >> >> > + >>> >> >> > + // Points go counterclockwise, so >>> >> >> > + points = new ArrayList<GeoPoint>(); >>> >> >> > + points.add(new GeoPoint(PlanetModel.SPHERE, -0.1, -0.5)); >>> >> >> > + points.add(new GeoPoint(PlanetModel.SPHERE, 0.0, -0.6)); >>> >> >> > + points.add(new GeoPoint(PlanetModel.SPHERE, 0.1, -0.5)); >>> >> >> > + points.add(new GeoPoint(PlanetModel.SPHERE, 0.0, -0.4)); >>> >> >> > + >>> >> >> > + c = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, >>> >> >> > points); >>> >> >> > + >>> >> >> > + // Middle point should NOT be within!! >>> >> >> > + gp = new GeoPoint(PlanetModel.SPHERE, 0.0, -0.5); >>> >> >> > + assertTrue(!c.isWithin(gp)); >>> >> >> > + >>> >> >> > + // Now, go clockwise >>> >> >> > + points = new ArrayList<GeoPoint>(); >>> >> >> > + points.add(new GeoPoint(PlanetModel.SPHERE, 0.0, -0.4)); >>> >> >> > + points.add(new GeoPoint(PlanetModel.SPHERE, 0.1, -0.5)); >>> >> >> > + points.add(new GeoPoint(PlanetModel.SPHERE, 0.0, -0.6)); >>> >> >> > + points.add(new GeoPoint(PlanetModel.SPHERE, -0.1, -0.5)); >>> >> >> > + >>> >> >> > + c = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, >>> >> >> > points); >>> >> >> > + >>> >> >> > + // Middle point should be within!! >>> >> >> > + gp = new GeoPoint(PlanetModel.SPHERE, 0.0, -0.5); >>> >> >> > + assertTrue(c.isWithin(gp)); >>> >> >> > + >>> >> >> > + } >>> >> >> > >>> >> >> > @Test >>> >> >> > public void testPolygonPointWithin() { >>> >> >> > - GeoMembershipShape c; >>> >> >> > + GeoPolygon c; >>> >> >> > GeoPoint gp; >>> >> >> > List<GeoPoint> points; >>> >> >> > >>> >> >> > @@ -162,4 +197,45 @@ public class GeoPolygonTest { >>> >> >> > assertEquals(0.1, b.getMaxLatitude(), 0.000001); >>> >> >> > } >>> >> >> > >>> >> >> > + @Test >>> >> >> > + public void testPolygonBoundsCase1() { >>> >> >> > + GeoPolygon c; >>> >> >> > + LatLonBounds b; >>> >> >> > + List<GeoPoint> points; >>> >> >> > + XYZBounds xyzb; >>> >> >> > + GeoPoint point1; >>> >> >> > + GeoPoint point2; >>> >> >> > + GeoArea area; >>> >> >> > + >>> >> >> > + // Build the polygon >>> >> >> > + points = new ArrayList<>(); >>> >> >> > + points.add(new GeoPoint(PlanetModel.WGS84, >>> >> >> > 0.7769776943105245, >>> >> >> > -2.157536559188766)); >>> >> >> > + points.add(new GeoPoint(PlanetModel.WGS84, >>> >> >> > -0.9796549195552824, >>> >> >> > -0.25078026625235256)); >>> >> >> > + points.add(new GeoPoint(PlanetModel.WGS84, >>> >> >> > 0.17644522781457245, >>> >> >> > 2.4225312555674967)); >>> >> >> > + points.add(new GeoPoint(PlanetModel.WGS84, >>> >> >> > -1.4459804612164617, >>> >> >> > -1.2970934639728127)); >>> >> >> > + c = GeoPolygonFactory.makeGeoPolygon(PlanetModel.WGS84, >>> >> >> > points, >>> >> >> > 3); >>> >> >> > + System.out.println(c); >>> >> >> > + // GeoCompositeMembershipShape: {[GeoConvexPolygon: >>> >> >> > {planetmodel=PlanetModel.WGS84, points= >>> >> >> > + // [[lat=0.17644522781457245, lon=2.4225312555674967], >>> >> >> > + // [lat=-1.4459804612164617, lon=-1.2970934639728127], >>> >> >> > + // [lat=0.7769776943105245, lon=-2.157536559188766]]}, >>> >> >> > + // GeoConcavePolygon: {planetmodel=PlanetModel.WGS84, points= >>> >> >> > + // [[lat=-0.9796549195552824, lon=-0.25078026625235256], >>> >> >> > + // [lat=0.17644522781457245, lon=2.4225312555674967], >>> >> >> > + // [lat=0.7769776943105245, lon=-2.157536559188766]]}]} >>> >> >> > + point1 = new GeoPoint(PlanetModel.WGS84, -1.2013743680763862, >>> >> >> > 0.48458963747230094); >>> >> >> > + point2 = new GeoPoint(0.3189285805649921, >>> >> >> > 0.16790264636909197, >>> >> >> > -0.9308557496413026); >>> >> >> > + >>> >> >> > + assertTrue(c.isWithin(point1)); >>> >> >> > + assertTrue(c.isWithin(point2)); >>> >> >> > + >>> >> >> > + // Now try bounds >>> >> >> > + xyzb = new XYZBounds(); >>> >> >> > + c.getBounds(xyzb); >>> >> >> > + area = GeoAreaFactory.makeGeoArea(PlanetModel.WGS84, >>> >> >> > + xyzb.getMinimumX(), xyzb.getMaximumX(), xyzb.getMinimumY(), >>> >> >> > xyzb.getMaximumY(), xyzb.getMinimumZ(), xyzb.getMaximumZ()); >>> >> >> > + >>> >> >> > + assertTrue(area.isWithin(point1)); >>> >> >> > + assertTrue(area.isWithin(point2)); >>> >> >> > + } >>> >> >> > } >>> >> >> > >>> >> >> >>> >> >> >>> >> >> --------------------------------------------------------------------- >>> >> >> To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org >>> >> >> For additional commands, e-mail: dev-h...@lucene.apache.org >>> >> >> >>> >> > >>> >> >>> >> >>> >> --------------------------------------------------------------------- >>> >> To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org >>> >> For additional commands, e-mail: dev-h...@lucene.apache.org >>> >> >>> > >>> >>> --------------------------------------------------------------------- >>> To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org >>> For additional commands, e-mail: dev-h...@lucene.apache.org >>> >> > > --------------------------------------------------------------------- > To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org > For additional commands, e-mail: dev-h...@lucene.apache.org > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org
