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
