Class GeoComplexPolygon

All Implemented Interfaces:
Bounded, GeoArea, GeoAreaShape, GeoBounds, 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().

  • Field Details

    • xTree

      private final GeoComplexPolygon.Tree xTree
    • yTree

      private final GeoComplexPolygon.Tree yTree
    • zTree

      private final GeoComplexPolygon.Tree zTree
    • pointsList

      private final List<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:
    • 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:
    • 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:
    • 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:
  • 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

      public GeoComplexPolygon(PlanetModel planetModel, InputStream inputStream) throws IOException
      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

      public void write(OutputStream outputStream) throws IOException
      Description copied from interface: SerializableObject
      Serialize to output stream.
      Specified by:
      write in interface SerializableObject
      Overrides:
      write in class BasePlanetObject
      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

      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 interface Bounded
      Overrides:
      getBounds in class GeoBaseBounds
      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 a computeOutsideDistance method if X/Y/Z is not within this shape.
      Specified by:
      outsideDistance in class GeoBaseMembershipShape
    • 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(Object o)
      Overrides:
      equals in class BasePlanetObject
    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class BasePlanetObject
    • toString

      public String toString()
      Overrides:
      toString in class Object
    • fillInEdgeDescription

      private static void fillInEdgeDescription(StringBuilder description, GeoComplexPolygon.Edge startEdge)