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
class GeoComplexPolygon extends GeoBasePolygon
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 Classes Modifier and Type Class Description private static interface
GeoComplexPolygon.CountingEdgeIterator
Iterator execution interface, for tree traversal, plus count retrieval.private class
GeoComplexPolygon.DualCrossingEdgeIterator
Count the number of verifiable edge crossings for a dual-leg journey.private static class
GeoComplexPolygon.Edge
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
GeoComplexPolygon.EdgeIterator
Iterator execution interface, for tree traversal.private class
GeoComplexPolygon.FullLinearCrossingEdgeIterator
Count the number of verifiable edge crossings for a full 1/2 a world.private class
GeoComplexPolygon.IntersectorEdgeIterator
Assess whether edge intersects the provided plane plus bounds.private class
GeoComplexPolygon.IntersectorShapeIterator
Assess whether edge intersects the provided shape.private static class
GeoComplexPolygon.Node
An instance of this class represents a node in a tree.private class
GeoComplexPolygon.SectorLinearCrossingEdgeIterator
Count the number of verifiable edge crossings for less than 1/2 a world.private class
GeoComplexPolygon.TraversalStrategy
Strategy class for describing traversals.private static class
GeoComplexPolygon.Tree
An interface describing a tree.private static class
GeoComplexPolygon.XTree
This is the x-tree.private static class
GeoComplexPolygon.YTree
This is the y-tree.private static class
GeoComplexPolygon.ZTree
This is the z-tree.
-
Field Summary
Fields Modifier and Type Field Description private static double
DELTA_DISTANCE
This is the amount we go, roughly, in both directions, to find adjoining points to test.private GeoPoint[]
edgePoints
private static double[]
halfProportions
private static int
MAX_ITERATIONS
This is the maximum number of iterations.private static double
NEAR_EDGE_CUTOFF
private static double
OFF_PLANE_AMOUNT
This is the amount off of the envelope plane that we count as "enough" for a valid crossing assessment.private java.util.List<java.util.List<GeoPoint>>
pointsList
private GeoComplexPolygon.Edge[]
shapeStartEdges
private GeoPoint
testPoint1
private Plane
testPoint1FixedXAbovePlane
private Plane
testPoint1FixedXBelowPlane
private Plane
testPoint1FixedXPlane
private Plane
testPoint1FixedYAbovePlane
private Plane
testPoint1FixedYBelowPlane
private Plane
testPoint1FixedYPlane
private Plane
testPoint1FixedZAbovePlane
private Plane
testPoint1FixedZBelowPlane
private Plane
testPoint1FixedZPlane
private boolean
testPoint1InSet
private GeoComplexPolygon.Tree
xTree
private GeoComplexPolygon.Tree
yTree
private GeoComplexPolygon.Tree
zTree
-
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
Constructors Constructor Description GeoComplexPolygon(PlanetModel planetModel, java.io.InputStream inputStream)
Constructor for deserialization.GeoComplexPolygon(PlanetModel planetModel, java.util.List<java.util.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
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private static double
computeSquaredDistance(GeoPoint checkPoint, GeoPoint intersectionPoint)
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.boolean
equals(java.lang.Object o)
private static void
fillInEdgeDescription(java.lang.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
getBounds(Bounds bounds)
Compute bounds for the shape.GeoPoint[]
getEdgePoints()
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.private static java.util.List<java.util.List<GeoPoint>>
readPointsList(PlanetModel planetModel, java.io.InputStream inputStream)
java.lang.String
toString()
void
write(java.io.OutputStream outputStream)
Serialize to output stream.private static void
writePointsList(java.io.OutputStream outputStream, java.util.List<java.util.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 Detail
-
xTree
private final GeoComplexPolygon.Tree xTree
-
yTree
private final GeoComplexPolygon.Tree yTree
-
zTree
private final GeoComplexPolygon.Tree zTree
-
pointsList
private final java.util.List<java.util.List<GeoPoint>> pointsList
-
testPoint1InSet
private final boolean testPoint1InSet
-
testPoint1
private final GeoPoint testPoint1
-
testPoint1FixedYPlane
private final Plane testPoint1FixedYPlane
-
testPoint1FixedYAbovePlane
private final Plane testPoint1FixedYAbovePlane
-
testPoint1FixedYBelowPlane
private final Plane testPoint1FixedYBelowPlane
-
testPoint1FixedXPlane
private final Plane testPoint1FixedXPlane
-
testPoint1FixedXAbovePlane
private final Plane testPoint1FixedXAbovePlane
-
testPoint1FixedXBelowPlane
private final Plane testPoint1FixedXBelowPlane
-
testPoint1FixedZPlane
private final Plane testPoint1FixedZPlane
-
testPoint1FixedZAbovePlane
private final Plane testPoint1FixedZAbovePlane
-
testPoint1FixedZBelowPlane
private final Plane testPoint1FixedZBelowPlane
-
edgePoints
private final GeoPoint[] edgePoints
-
shapeStartEdges
private final GeoComplexPolygon.Edge[] shapeStartEdges
-
NEAR_EDGE_CUTOFF
private static final double NEAR_EDGE_CUTOFF
- See Also:
- Constant Field Values
-
halfProportions
private static final double[] halfProportions
-
DELTA_DISTANCE
private static final double DELTA_DISTANCE
This 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:
- Constant Field Values
-
MAX_ITERATIONS
private static final int MAX_ITERATIONS
This 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:
- Constant Field Values
-
OFF_PLANE_AMOUNT
private static final double OFF_PLANE_AMOUNT
This is the amount off of the envelope plane that we count as "enough" for a valid crossing assessment.- See Also:
- Constant Field Values
-
-
Constructor Detail
-
GeoComplexPolygon
public GeoComplexPolygon(PlanetModel planetModel, java.util.List<java.util.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
public GeoComplexPolygon(PlanetModel planetModel, java.io.InputStream inputStream) throws java.io.IOException
Constructor for deserialization.- Parameters:
planetModel
- is the planet model.inputStream
- is the input stream.- Throws:
java.io.IOException
-
-
Method Detail
-
readPointsList
private static java.util.List<java.util.List<GeoPoint>> readPointsList(PlanetModel planetModel, java.io.InputStream inputStream) throws java.io.IOException
- Throws:
java.io.IOException
-
write
public void write(java.io.OutputStream outputStream) throws java.io.IOException
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:
java.io.IOException
-
writePointsList
private static void writePointsList(java.io.OutputStream outputStream, java.util.List<java.util.List<GeoPoint>> pointsList) throws java.io.IOException
- Throws:
java.io.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
public GeoPoint[] 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
public boolean intersects(Plane p, GeoPoint[] notablePoints, Membership... bounds)
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
public boolean intersects(GeoShape geoShape)
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
public void getBounds(Bounds bounds)
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
protected double outsideDistance(DistanceStyle distanceStyle, double x, double y, double z)
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
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. 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
private static double computeSquaredDistance(GeoPoint checkPoint, GeoPoint intersectionPoint)
-
equals
public boolean equals(java.lang.Object o)
- Overrides:
equals
in classBasePlanetObject
-
hashCode
public int hashCode()
- Overrides:
hashCode
in classBasePlanetObject
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
fillInEdgeDescription
private static void fillInEdgeDescription(java.lang.StringBuilder description, GeoComplexPolygon.Edge startEdge)
-
-