Package org.apache.lucene.spatial3d.geom
Class GeoPolygonFactory
java.lang.Object
org.apache.lucene.spatial3d.geom.GeoPolygonFactory
Class which constructs a GeoMembershipShape representing an arbitrary polygon.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static class
Class for tracking the best shape for finding a pole, and whether or not the pole must be inside or outside of the shape.private static class
Class representing a single (unused) edge.private static class
Class representing a pool of unused edges, all linked together by vertices.private static class
Class representing an iterator over an EdgeBuffer.(package private) static class
static class
Use this class to specify a polygon with associated holes.private static class
An instance of this class represents a known-good path of nodes that contains no coplanar points , no matter how assessed.private static class
Exception we throw when we can't tile a polygon due to numerical precision issues. -
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) static boolean
buildPolygonShape
(GeoCompositePolygon rval, GeoPolygonFactory.MutableBoolean seenConcave, PlanetModel planetModel, List<GeoPoint> pointsList, BitSet internalEdges, int startPointIndex, int endPointIndex, SidedPlane startingEdge, List<GeoPolygon> holes, GeoPoint testPoint) Build a GeoPolygon out of one concave part and multiple convex parts given points, starting edge, and whether starting edge is internal or not.private static Double
computeAngle
(GeoPoint point, double sinLatitude, double cosLatitude, double sinLongitude, double cosLongitude) Compute the angle for a point given rotation information.private static GeoPolygonFactory.BestShape
convertPolygon
(List<List<GeoPoint>> pointsList, GeoPolygonFactory.PolygonDescription shape, GeoPolygonFactory.BestShape testPointShape, boolean mustBeInside) Convert a polygon description to a list of shapes.filterEdges
(List<GeoPoint> noIdenticalPoints, double leniencyValue) Filter coplanar points.filterPoints
(List<? extends GeoPoint> input) Filter duplicate points.private static Boolean
findConvexPolygon
(PlanetModel planetModel, GeoPolygonFactory.Edge currentEdge, GeoCompositePolygon rval, GeoPolygonFactory.EdgeBuffer edgeBuffer, List<GeoPolygon> holes, GeoPoint testPoint) Look for a convex polygon at the specified edge.private static GeoPolygonFactory.SafePath
findSafePath
(List<GeoPoint> points, int startIndex, double leniencyValue) Iterative path search through ordered list of points.(package private) static GeoPolygon
generateGeoPolygon
(PlanetModel planetModel, List<GeoPoint> filteredPointList, List<GeoPolygon> holes, GeoPoint testPoint, boolean testPointInside) Create a GeoPolygon using the specified points and holes and a test point.private static GeoPoint
getCenterOfMass
(PlanetModel planetModel, List<GeoPoint> points) Generate a point at the center of mass of a list of points.private static int
getLegalIndex
(int index, int size) Convert raw point index into valid array position.private static Boolean
isInsidePolygon
(GeoPoint point, List<GeoPoint> polyPoints) 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.private static boolean
isWithin
(GeoPoint point, Set<GeoPolygonFactory.Edge> edgeSet) Check if a point is within a set of edges.private static boolean
isWithin
(GeoPoint point, Set<GeoPolygonFactory.Edge> edgeSet, GeoPolygonFactory.Edge extension, SidedPlane returnBoundary) Check if a point is within a set of edges.private static boolean
makeConcavePolygon
(PlanetModel planetModel, GeoCompositePolygon rval, GeoPolygonFactory.MutableBoolean seenConcave, GeoPolygonFactory.EdgeBuffer edgeBuffer, List<GeoPolygon> holes, GeoPoint testPoint) Look for a concave polygon in the remainder of the edgebuffer.static GeoPolygon
makeGeoConcavePolygon
(PlanetModel planetModel, List<GeoPoint> pointList) Create a GeoConcavePolygon using the specified points.static GeoPolygon
makeGeoConcavePolygon
(PlanetModel planetModel, List<GeoPoint> pointList, List<GeoPolygon> holes) Create a GeoConcavePolygon using the specified points and holes.static GeoPolygon
makeGeoConvexPolygon
(PlanetModel planetModel, List<GeoPoint> pointList) Create a GeoConvexPolygon using the specified points.static GeoPolygon
makeGeoConvexPolygon
(PlanetModel planetModel, List<GeoPoint> pointList, List<GeoPolygon> holes) Create a GeoConvexPolygon using the specified points and holes.static GeoPolygon
makeGeoPolygon
(PlanetModel planetModel, List<GeoPoint> pointList) Create a GeoPolygon using the specified points and holes, using order to determine siding of the polygon.static GeoPolygon
makeGeoPolygon
(PlanetModel planetModel, List<GeoPoint> pointList, List<GeoPolygon> holes) Create a GeoPolygon using the specified points and holes, using order to determine siding of the polygon.static GeoPolygon
makeGeoPolygon
(PlanetModel planetModel, List<GeoPoint> pointList, List<GeoPolygon> holes, double leniencyValue) Create a GeoPolygon using the specified points and holes, using order to determine siding of the polygon.static GeoPolygon
makeGeoPolygon
(PlanetModel planetModel, GeoPolygonFactory.PolygonDescription description) Create a GeoPolygon using the specified points and holes, using order to determine siding of the polygon.static GeoPolygon
makeGeoPolygon
(PlanetModel planetModel, GeoPolygonFactory.PolygonDescription description, double leniencyValue) Create a GeoPolygon using the specified points and holes, using order to determine siding of the polygon.static GeoPolygon
makeLargeGeoPolygon
(PlanetModel planetModel, List<GeoPolygonFactory.PolygonDescription> shapesList) Create a large GeoPolygon.private static GeoPoint
pickPole
(Random generator, PlanetModel planetModel, List<GeoPoint> points) Pick a random pole that has a good chance of being inside the polygon described by the points.
-
Field Details
-
SMALL_POLYGON_CUTOFF_EDGES
private static final int SMALL_POLYGON_CUTOFF_EDGES- See Also:
-
-
Constructor Details
-
GeoPolygonFactory
private GeoPolygonFactory()
-
-
Method Details
-
makeGeoConcavePolygon
Create a GeoConcavePolygon using the specified points. The polygon must have a maximum extent larger than PI. The siding of the polygon is chosen so that any adjacent point to a segment provides an exterior measurement and therefore, the polygon is a truly concave polygon. Note that this method should only be used when there is certainty that we are dealing with a concave polygon, e.g. the polygon has been serialized. If there is not such certainty, please refer to @makeGeoPolygon(PlanetModel, List)
.- Parameters:
pointList
- is a list of the GeoPoints to build an arbitrary polygon out of.- Returns:
- a GeoPolygon corresponding to what was specified.
-
makeGeoConvexPolygon
Create a GeoConvexPolygon using the specified points. The polygon must have a maximum extent no larger than PI. The siding of the polygon is chosen so that any adjacent point to a segment provides an interior measurement and therefore the polygon is a truly convex polygon. Note that this method should only be used when there is certainty that we are dealing with a convex polygon, e.g. the polygon has been serialized. If there is not such certainty, please refer to @makeGeoPolygon(PlanetModel, List)
.- Parameters:
pointList
- is a list of the GeoPoints to build an arbitrary polygon out of.- Returns:
- a GeoPolygon corresponding to what was specified.
-
makeGeoConcavePolygon
public static GeoPolygon makeGeoConcavePolygon(PlanetModel planetModel, List<GeoPoint> pointList, List<GeoPolygon> holes) Create a GeoConcavePolygon using the specified points and holes. The polygon must have a maximum extent larger than PI. The siding of the polygon is chosen so that any adjacent point to a segment provides an exterior measurement and therefore the polygon is a truly concave polygon. Note that this method should only be used when there is certainty that we are dealing with a concave polygon, e.g. the polygon has been serialized. If there is not such certainty, please refer tomakeGeoPolygon(PlanetModel, List, List)
.- Parameters:
pointList
- is a list of the GeoPoints to build an arbitrary polygon out of.holes
- is a list of polygons representing "holes" in the outside polygon. Holes describe the area outside each hole as being "in set". Null == none.- Returns:
- a GeoPolygon corresponding to what was specified.
-
makeGeoConvexPolygon
public static GeoPolygon makeGeoConvexPolygon(PlanetModel planetModel, List<GeoPoint> pointList, List<GeoPolygon> holes) Create a GeoConvexPolygon using the specified points and holes. The polygon must have a maximum extent no larger than PI. The siding of the polygon is chosen so that any adjacent point to a segment provides an interior measurement and therefore the polygon is a truly convex polygon. Note that this method should only be used when there is certainty that we are dealing with a convex polygon, e.g. the polygon has been serialized. If there is not such certainty, please refer tomakeGeoPolygon(PlanetModel, List, List)
.- Parameters:
pointList
- is a list of the GeoPoints to build an arbitrary polygon out of.holes
- is a list of polygons representing "holes" in the outside polygon. Holes describe the area outside each hole as being "in set". Null == none.- Returns:
- a GeoPolygon corresponding to what was specified.
-
makeGeoPolygon
public static GeoPolygon makeGeoPolygon(PlanetModel planetModel, GeoPolygonFactory.PolygonDescription description) 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.- Parameters:
description
- describes the polygon and its associated holes. 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.- Returns:
- a GeoPolygon corresponding to what was specified, or null if a valid polygon cannot be generated from this input.
-
makeGeoPolygon
public static GeoPolygon makeGeoPolygon(PlanetModel planetModel, GeoPolygonFactory.PolygonDescription description, double leniencyValue) 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.- Parameters:
description
- describes the polygon and its associated holes. 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.leniencyValue
- is the maximum distance (in units) that a point can be from the plane and still be considered as belonging to the plane. Any value greater than zero may cause some of the provided points that are in fact outside the strict definition of co-planarity, but are within this distance, to be discarded for the purposes of creating a "safe" polygon.- Returns:
- a GeoPolygon corresponding to what was specified, or null if a valid polygon cannot be generated from this input.
-
makeGeoPolygon
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.- Parameters:
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.- Returns:
- a GeoPolygon corresponding to what was specified.
-
makeGeoPolygon
public static GeoPolygon makeGeoPolygon(PlanetModel planetModel, List<GeoPoint> pointList, List<GeoPolygon> holes) 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.- Parameters:
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.holes
- is a list of polygons representing "holes" in the outside polygon. Holes describe the area outside each hole as being "in set". Null == none.- Returns:
- a GeoPolygon corresponding to what was specified, or null if a valid polygon cannot be generated from this input.
-
makeGeoPolygon
public static GeoPolygon makeGeoPolygon(PlanetModel planetModel, List<GeoPoint> pointList, List<GeoPolygon> holes, double leniencyValue) 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.- Parameters:
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.holes
- is a list of polygons representing "holes" in the outside polygon. Holes describe the area outside each hole as being "in set". Null == none.leniencyValue
- is the maximum distance (in units) that a point can be from the plane and still be considered as belonging to the plane. Any value greater than zero may cause some of the provided points that are in fact outside the strict definition of co-planarity, but are within this distance, to be discarded for the purposes of creating a "safe" polygon.- Returns:
- a GeoPolygon corresponding to what was specified, or null if a valid polygon cannot be generated from this input.
-
getCenterOfMass
Generate a point at the center of mass of a list of points. -
makeLargeGeoPolygon
public static GeoPolygon makeLargeGeoPolygon(PlanetModel planetModel, List<GeoPolygonFactory.PolygonDescription> shapesList) Create a large GeoPolygon. This is one which has more than 100 sides and/or may have resolution problems with very closely spaced points, which often occurs when the polygon was constructed to approximate curves. No tiling is done, and intersections and membership are optimized for having large numbers of sides.This method does very little checking for legality. It expects the incoming shapes to not intersect each other. The shapes can be disjoint or nested. If the shapes listed are nested, then we are describing holes. There is no limit to the depth of holes. However, if a shape is nested within another it must be explicitly described as being a child of the other shape.
Membership in any given shape is described by the clockwise/counterclockwise direction of the points. The clockwise direction indicates that a point inside is "in-set", while a counter-clockwise direction implies that a point inside is "out-of-set".
- Parameters:
planetModel
- is the planet model.shapesList
- is the list of polygons we should be making.- Returns:
- the GeoPolygon, or null if it cannot be constructed.
-
convertPolygon
private static GeoPolygonFactory.BestShape convertPolygon(List<List<GeoPoint>> pointsList, GeoPolygonFactory.PolygonDescription shape, GeoPolygonFactory.BestShape testPointShape, boolean mustBeInside) Convert a polygon description to a list of shapes. Also locate an optimal shape for evaluating a test point.- Parameters:
pointsList
- is the structure to add new polygons to.shape
- is the current polygon description.testPointShape
- is the current best choice for a low-level polygon to evaluate.- Returns:
- an updated best-choice for a test point polygon, and update the points list.
-
generateGeoPolygon
static GeoPolygon generateGeoPolygon(PlanetModel planetModel, List<GeoPoint> filteredPointList, List<GeoPolygon> holes, GeoPoint testPoint, boolean testPointInside) throws GeoPolygonFactory.TileException Create a GeoPolygon using the specified points and holes and a test point.- Parameters:
filteredPointList
- is a filtered list of the GeoPoints to build an arbitrary polygon out of.holes
- is a list of polygons representing "holes" in the outside polygon. Null == none.testPoint
- is a test point that is either known to be within the polygon area, or not.testPointInside
- is true if the test point is within the area, false otherwise.- Returns:
- a GeoPolygon corresponding to what was specified, or null if what was specified cannot be turned into a valid non-degenerate polygon.
- Throws:
GeoPolygonFactory.TileException
-
filterPoints
Filter duplicate points.- Parameters:
input
- with input list of points- Returns:
- the filtered list, or null if we can't get a legit polygon from the input.
-
filterEdges
Filter coplanar points.- Parameters:
noIdenticalPoints
- with input list of pointsleniencyValue
- is the allowed distance of a point from the plane for cleanup of overly detailed polygons- Returns:
- the filtered list, or null if we can't get a legit polygon from the input.
-
findSafePath
private static GeoPolygonFactory.SafePath findSafePath(List<GeoPoint> points, int startIndex, double leniencyValue) Iterative path search through ordered list of points. The method merges together all consecutive coplanar points and builds the plane using the first and the last point. It does not converge if the starting point is coplanar with the last and next point of the path.- Parameters:
points
- is the ordered raw list of points under consideration.startIndex
- is index of the point that starts the current path, so that we can know when we are done.leniencyValue
- is the allowed distance of a point from the plane to be considered coplanar.- Returns:
- null if the starting point is coplanar with the last and next point of the path.
-
pickPole
Pick a random pole that has a good chance of being inside the polygon described by the points.- Parameters:
generator
- is the random number generator to use.planetModel
- is the planet model to use.points
- is the list of points available.- Returns:
- the randomly-determined pole selection.
-
isInsidePolygon
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.- Parameters:
point
- is the point to check.polyPoints
- is the list of points comprising the polygon.- Returns:
- null if the point is illegal, otherwise false if the point is inside and true if the point is outside of the polygon.
-
computeAngle
private static Double computeAngle(GeoPoint point, double sinLatitude, double cosLatitude, double sinLongitude, double cosLongitude) Compute the angle for a point given rotation information.- Parameters:
point
- is the point to assesssinLatitude
- the sine of the latitudecosLatitude
- the cosine of the latitudesinLongitude
- the sine of the longitudecosLongitude
- the cosine of the longitude- Returns:
- the angle of rotation, or null if not computable
-
buildPolygonShape
static boolean buildPolygonShape(GeoCompositePolygon rval, GeoPolygonFactory.MutableBoolean seenConcave, PlanetModel planetModel, List<GeoPoint> pointsList, BitSet internalEdges, int startPointIndex, int endPointIndex, SidedPlane startingEdge, List<GeoPolygon> holes, GeoPoint testPoint) throws GeoPolygonFactory.TileException Build a GeoPolygon out of one concave part and multiple convex parts given points, starting edge, and whether starting edge is internal or not.- Parameters:
rval
- is the composite polygon to add to.seenConcave
- is true if a concave polygon has been seen in this generation yet.planetModel
- is the planet model.pointsList
- is a list of the GeoPoints to build an arbitrary polygon out of.internalEdges
- specifies which edges are internal.startPointIndex
- is the first of the points, constituting the starting edge.startingEdge
- is the plane describing the starting edge.holes
- is the list of holes in the polygon, or null if none.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.- Returns:
- false 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 false, which is a signal that we chose our initial plane sidedness backwards.
- Throws:
GeoPolygonFactory.TileException
-
makeConcavePolygon
private static boolean makeConcavePolygon(PlanetModel planetModel, GeoCompositePolygon rval, GeoPolygonFactory.MutableBoolean seenConcave, GeoPolygonFactory.EdgeBuffer edgeBuffer, List<GeoPolygon> holes, GeoPoint testPoint) throws GeoPolygonFactory.TileException 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.- Parameters:
planetModel
- is the planet model.rval
- is the composite polygon we're building.seenConcave
- is true if we've already seen a concave polygon.edgeBuffer
- is the edge buffer.holes
- is the optional list of holes.testPoint
- is the optional test point.- Returns:
- true unless the testPoint caused failure.
- Throws:
GeoPolygonFactory.TileException
-
findConvexPolygon
private static Boolean findConvexPolygon(PlanetModel planetModel, GeoPolygonFactory.Edge currentEdge, GeoCompositePolygon rval, GeoPolygonFactory.EdgeBuffer edgeBuffer, List<GeoPolygon> holes, GeoPoint testPoint) throws GeoPolygonFactory.TileException Look for a convex polygon at the specified edge. If we find it, create one and adjust the edge buffer.- Parameters:
planetModel
- is the planet model.currentEdge
- is the current edge to use starting the search.rval
- is the composite polygon to build.edgeBuffer
- is the edge buffer.holes
- is the optional list of holes.testPoint
- is the optional test point.- Returns:
- null if the testPoint is within any polygon detected, otherwise true if a convex polygon was created.
- Throws:
GeoPolygonFactory.TileException
-
isWithin
private static boolean isWithin(GeoPoint point, Set<GeoPolygonFactory.Edge> edgeSet, GeoPolygonFactory.Edge extension, SidedPlane returnBoundary) Check if a point is within a set of edges.- Parameters:
point
- is the pointedgeSet
- is the set of edgesextension
- is the new edgereturnBoundary
- is the return edge- Returns:
- true if within
-
isWithin
Check if a point is within a set of edges.- Parameters:
point
- is the pointedgeSet
- is the set of edges- Returns:
- true if within
-
getLegalIndex
private static int getLegalIndex(int index, int size) Convert raw point index into valid array position.- Parameters:
index
- is the array index.size
- is the array size.- Returns:
- an updated index.
-