Package org.apache.lucene.spatial3d.geom
Class GeoComplexPolygon
java.lang.Object
org.apache.lucene.spatial3d.geom.BasePlanetObject
org.apache.lucene.spatial3d.geom.GeoBaseShape
org.apache.lucene.spatial3d.geom.GeoBaseMembershipShape
org.apache.lucene.spatial3d.geom.GeoBaseAreaShape
org.apache.lucene.spatial3d.geom.GeoBasePolygon
org.apache.lucene.spatial3d.geom.GeoComplexPolygon
- All Implemented Interfaces:
Bounded
,GeoArea
,GeoAreaShape
,GeoMembershipShape
,GeoOutsideDistance
,GeoPolygon
,GeoShape
,Membership
,PlanetObject
,SerializableObject
GeoComplexPolygon objects are structures designed to handle very large numbers of edges. They
perform very well in this case compared to the alternatives, which all have O(N) evaluation and
O(N^2) setup times. Complex polygons have O(N) setup times and best case O(log(N)) evaluation
times.
The tradeoff is that these objects perform object creation when evaluating intersects() and isWithin().
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static interface
Iterator execution interface, for tree traversal, plus count retrieval.private class
Count the number of verifiable edge crossings for a dual-leg journey.private static class
An instance of this class describes a single edge, and includes what is necessary to reliably determine intersection in the context of the even/odd algorithm used.private static interface
Iterator execution interface, for tree traversal.private class
Count the number of verifiable edge crossings for a full 1/2 a world.private class
Assess whether edge intersects the provided plane plus bounds.private class
Assess whether edge intersects the provided shape.private static class
An instance of this class represents a node in a tree.private class
Count the number of verifiable edge crossings for less than 1/2 a world.private class
Strategy class for describing traversals.private static class
An interface describing a tree.private static class
This is the x-tree.private static class
This is the y-tree.private static class
This is the z-tree. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate static final double
This is the amount we go, roughly, in both directions, to find adjoining points to test.private final GeoPoint[]
private static final double[]
private static final int
This is the maximum number of iterations.private static final double
private static final double
This is the amount off of the envelope plane that we count as "enough" for a valid crossing assessment.private final GeoComplexPolygon.Edge[]
private final GeoPoint
private final Plane
private final Plane
private final Plane
private final Plane
private final Plane
private final Plane
private final Plane
private final Plane
private final Plane
private final boolean
private final GeoComplexPolygon.Tree
private final GeoComplexPolygon.Tree
private final GeoComplexPolygon.Tree
Fields inherited from class org.apache.lucene.spatial3d.geom.GeoBaseAreaShape
ALL_INSIDE, NONE_INSIDE, SOME_INSIDE
Fields inherited from class org.apache.lucene.spatial3d.geom.BasePlanetObject
planetModel
-
Constructor Summary
ConstructorsConstructorDescriptionGeoComplexPolygon
(PlanetModel planetModel, InputStream inputStream) Constructor for deserialization.GeoComplexPolygon
(PlanetModel planetModel, List<List<GeoPoint>> pointsList, GeoPoint testPoint, boolean testPointInSet) Create a complex polygon from multiple lists of points, and a single point which is known to be in or out of set. -
Method Summary
Modifier and TypeMethodDescriptionprivate static double
computeSquaredDistance
(GeoPoint checkPoint, GeoPoint intersectionPoint) createLinearCrossingEdgeIterator
(GeoPoint testPoint, Plane plane, Plane abovePlane, Plane belowPlane, double thePointX, double thePointY, double thePointZ) Create a linear crossing edge iterator with the appropriate cutoff planes given the geometry.boolean
private static void
fillInEdgeDescription
(StringBuilder description, GeoComplexPolygon.Edge startEdge) private GeoPoint[]
findAdjoiningPoints
(Plane plane, GeoPoint pointOnPlane, Plane envelopePlane) Given a point on the plane and the ellipsoid, this method looks for a pair of adjoining points on either side of the plane, which are about MINIMUM_RESOLUTION away from the given point.void
Compute bounds for the shape.GeoPoint[]
Return a sample point that is on the outside edge/boundary of the shape.int
hashCode()
boolean
intersects
(GeoShape geoShape) Assess whether a shape intersects with any of the edges of this shape.boolean
intersects
(Plane p, GeoPoint[] notablePoints, Membership... bounds) Assess whether a plane, within the provided bounds, intersects with the shape's edges.private boolean
isInSet
(double x, double y, double z, GeoPoint testPoint, boolean testPointInSet, Plane testPointFixedXPlane, Plane testPointFixedXAbovePlane, Plane testPointFixedXBelowPlane, Plane testPointFixedYPlane, Plane testPointFixedYAbovePlane, Plane testPointFixedYBelowPlane, Plane testPointFixedZPlane, Plane testPointFixedZAbovePlane, Plane testPointFixedZBelowPlane) Given a test point, whether it is in set, and the associated planes, figure out if another point is in set or not.boolean
isWithin
(double x, double y, double z) Check if a point is within this shape.protected double
outsideDistance
(DistanceStyle distanceStyle, double x, double y, double z) Called by acomputeOutsideDistance
method if X/Y/Z is not within this shape.readPointsList
(PlanetModel planetModel, InputStream inputStream) toString()
void
write
(OutputStream outputStream) Serialize to output stream.private static void
writePointsList
(OutputStream outputStream, List<List<GeoPoint>> pointsList) Methods inherited from class org.apache.lucene.spatial3d.geom.GeoBaseAreaShape
getRelationship, isGeoAreaShapeInsideShape, isShapeInsideGeoAreaShape
Methods inherited from class org.apache.lucene.spatial3d.geom.GeoBaseMembershipShape
computeOutsideDistance, computeOutsideDistance, isWithin
Methods inherited from class org.apache.lucene.spatial3d.geom.BasePlanetObject
getPlanetModel
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface org.apache.lucene.spatial3d.geom.GeoArea
getRelationship
Methods inherited from interface org.apache.lucene.spatial3d.geom.GeoOutsideDistance
computeOutsideDistance, computeOutsideDistance
Methods inherited from interface org.apache.lucene.spatial3d.geom.Membership
isWithin
Methods inherited from interface org.apache.lucene.spatial3d.geom.PlanetObject
getPlanetModel
-
Field Details
-
xTree
-
yTree
-
zTree
-
pointsList
-
testPoint1InSet
private final boolean testPoint1InSet -
testPoint1
-
testPoint1FixedYPlane
-
testPoint1FixedYAbovePlane
-
testPoint1FixedYBelowPlane
-
testPoint1FixedXPlane
-
testPoint1FixedXAbovePlane
-
testPoint1FixedXBelowPlane
-
testPoint1FixedZPlane
-
testPoint1FixedZAbovePlane
-
testPoint1FixedZBelowPlane
-
edgePoints
-
shapeStartEdges
-
NEAR_EDGE_CUTOFF
private static final double NEAR_EDGE_CUTOFF- See Also:
-
halfProportions
private static final double[] halfProportions -
DELTA_DISTANCE
private static final double DELTA_DISTANCEThis is the amount we go, roughly, in both directions, to find adjoining points to test. If we go too far, we might miss a transition, but if we go too little, we might not see it either due to numerical issues.- See Also:
-
MAX_ITERATIONS
private static final int MAX_ITERATIONSThis is the maximum number of iterations. If we get this high, effectively the planes are parallel, and we treat that as a crossing.- See Also:
-
OFF_PLANE_AMOUNT
private static final double OFF_PLANE_AMOUNTThis is the amount off of the envelope plane that we count as "enough" for a valid crossing assessment.- See Also:
-
-
Constructor Details
-
GeoComplexPolygon
public GeoComplexPolygon(PlanetModel planetModel, List<List<GeoPoint>> pointsList, GeoPoint testPoint, boolean testPointInSet) Create a complex polygon from multiple lists of points, and a single point which is known to be in or out of set.- Parameters:
planetModel
- is the planet model.pointsList
- is the list of lists of edge points. The edge points describe edges, and have an implied return boundary, so that N edges require N points. These points have furthermore been filtered so that no adjacent points are identical (within the bounds of the definition used by this package). It is assumed that no edges intersect, but the structure can contain both outer rings as well as holes.testPoint
- is the point whose in/out of setness is known.testPointInSet
- is true if the test point is considered "within" the polygon.
-
GeoComplexPolygon
Constructor for deserialization.- Parameters:
planetModel
- is the planet model.inputStream
- is the input stream.- Throws:
IOException
-
-
Method Details
-
readPointsList
private static List<List<GeoPoint>> readPointsList(PlanetModel planetModel, InputStream inputStream) throws IOException - Throws:
IOException
-
write
Description copied from interface:SerializableObject
Serialize to output stream.- Specified by:
write
in interfaceSerializableObject
- Overrides:
write
in classBasePlanetObject
- Parameters:
outputStream
- is the output stream to write to.- Throws:
IOException
-
writePointsList
private static void writePointsList(OutputStream outputStream, List<List<GeoPoint>> pointsList) throws IOException - Throws:
IOException
-
isWithin
public boolean isWithin(double x, double y, double z) Description copied from interface:Membership
Check if a point is within this shape.- Parameters:
x
- is x coordinate of point to check.y
- is y coordinate of point to check.z
- is z coordinate of point to check.- Returns:
- true if the point is within this shape
-
isInSet
private boolean isInSet(double x, double y, double z, GeoPoint testPoint, boolean testPointInSet, Plane testPointFixedXPlane, Plane testPointFixedXAbovePlane, Plane testPointFixedXBelowPlane, Plane testPointFixedYPlane, Plane testPointFixedYAbovePlane, Plane testPointFixedYBelowPlane, Plane testPointFixedZPlane, Plane testPointFixedZAbovePlane, Plane testPointFixedZBelowPlane) Given a test point, whether it is in set, and the associated planes, figure out if another point is in set or not. -
getEdgePoints
Description copied from interface:GeoShape
Return a sample point that is on the outside edge/boundary of the shape.- Returns:
- samples of all edge points from distinct edge sections. Typically one point is returned, but zero or two are also possible.
-
intersects
Description copied from interface:GeoShape
Assess whether a plane, within the provided bounds, intersects with the shape's edges. Any overlap, even a single point, is considered to be an intersection. Note well that this method is allowed to return "true" if there are internal edges of a composite shape which intersect the plane. Doing this can cause getRelationship() for most GeoBBox shapes to return OVERLAPS rather than the more correct CONTAINS, but that cannot be helped for some complex shapes that are built out of overlapping parts.- Parameters:
p
- is the plane to assess for intersection with the shape's edges or bounding curves.notablePoints
- represents the intersections of the plane with the supplied bounds. These are used to disambiguate when two planes are identical and it needs to be determined whether any points exist that fulfill all the bounds.bounds
- are a set of bounds that define an area that an intersection must be within in order to qualify (provided by a GeoArea).- Returns:
- true if there's such an intersection, false if not.
-
intersects
Description copied from interface:GeoAreaShape
Assess whether a shape intersects with any of the edges of this shape. Note well that this method must return false if the shape contains or is disjoint with the given shape. It is permissible to return true if the shape is within the specified shape, if it is difficult to compute intersection with edges.- Parameters:
geoShape
- is the shape to assess for intersection with this shape's edges.- Returns:
- true if there's such an intersection, false if not.
-
getBounds
Description copied from interface:Bounded
Compute bounds for the shape.- Specified by:
getBounds
in interfaceBounded
- Overrides:
getBounds
in classGeoBaseShape
- Parameters:
bounds
- is the input bounds object. The input object will be modified.
-
outsideDistance
Description copied from class:GeoBaseMembershipShape
Called by acomputeOutsideDistance
method if X/Y/Z is not within this shape.- Specified by:
outsideDistance
in classGeoBaseMembershipShape
-
createLinearCrossingEdgeIterator
private GeoComplexPolygon.CountingEdgeIterator createLinearCrossingEdgeIterator(GeoPoint testPoint, Plane plane, Plane abovePlane, Plane belowPlane, double thePointX, double thePointY, double thePointZ) Create a linear crossing edge iterator with the appropriate cutoff planes given the geometry. -
findAdjoiningPoints
Given a point on the plane and the ellipsoid, this method looks for a pair of adjoining points on either side of the plane, which are about MINIMUM_RESOLUTION away from the given point. This only works for planes which go through the center of the world. Returns null if the planes are effectively parallel and reasonable adjoining points cannot be determined. -
computeSquaredDistance
-
equals
- Overrides:
equals
in classBasePlanetObject
-
hashCode
public int hashCode()- Overrides:
hashCode
in classBasePlanetObject
-
toString
-
fillInEdgeDescription
private static void fillInEdgeDescription(StringBuilder description, GeoComplexPolygon.Edge startEdge)
-