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
