Package org.ka2ddo.yaac.util

Class CBCAPolygon

java.lang.Object
java.awt.Polygon
org.ka2ddo.yaac.util.CBCAPolygon
All Implemented Interfaces:
Shape, Serializable
public final class CBCAPolygon extends Polygon
This implements the Cell-Based Containment Algorithm for more efficiently determining whether a point is inside a polygon with a large number of vertices.

Ref: Zalik & Kolingerova, "A cell-based point-in-polygon algorithm suitable for large sets of points", Computers & Geosciences 27 (2001) 1135-1145.

Author:
Andrew Pavlin, KA2DDO
See Also:

  • Constructor Details

    • CBCAPolygon

      public CBCAPolygon()
      Creates an empty polygon.

    • CBCAPolygon

      public CBCAPolygon(int[] xPoints, int[] yPoints, int nPoints)
      Constructs and initializes a Polygon from the specified parameters.
      Parameters:
      xPoints - an array of x coordinates
      yPoints - an array of y coordinates
      nPoints - the total number of points in the Polygon
      Throws:
      NegativeArraySizeException - if the value of nPoints is negative.
      IndexOutOfBoundsException - if nPoints is greater than the length of xPoints or the length of yPoints.
      NullPointerException - if xPoints or yPoints is null.

  • Method Details

    • reset

      public void reset()
      Resets this Polygon object to an empty polygon. The coordinate arrays and the data in them are left untouched but the number of points is reset to zero to mark the old vertex data as invalid and to start accumulating new vertex data at the beginning. All internally-cached data relating to the old vertices are discarded. Note that since the coordinate arrays from before the reset are reused, creating a new empty Polygon might be more memory efficient than resetting the current one if the number of vertices in the new polygon data is significantly smaller than the number of vertices in the data from before the reset.
      Overrides:
      reset in class Polygon

    • invalidate

      public void invalidate()
      Invalidates or flushes any internally-cached data that depends on the vertex coordinates of this Polygon. This method should be called after any direct manipulation of the coordinates in the xPoints or yPoints arrays to avoid inconsistent results from methods such as getBounds or contains that might cache data from earlier computations relating to the vertex coordinates.
      Overrides:
      invalidate in class Polygon

    • translate

      public void translate(int deltaX, int deltaY)
      Translates the vertices of the Polygon by deltaX along the x axis and by deltaY along the y axis.
      Overrides:
      translate in class Polygon
      Parameters:
      deltaX - the amount to translate along the x axis
      deltaY - the amount to translate along the y axis
      Since:
      JDK1.1

    • addPoint

      public void addPoint(int x, int y)
      Appends the specified coordinates to this Polygon.

      If an operation that calculates the bounding box of this Polygon has already been performed, such as getBounds or contains, then this method updates the bounding box.

      Overrides:
      addPoint in class Polygon
      Parameters:
      x - the specified coordinates
      y - the specified coordinates
      See Also:

    • toString

      public String toString()
      Returns a string representation of the object.
      Overrides:
      toString in class Object
      Returns:
      a string representation of the object.

    • contains

      public boolean contains(double x, double y)
      Determines if the specified coordinates are inside this Polygon. For the definition of insideness, see the class comments of Shape.

      This method is not thread-safe, as it uses pre-allocated buffer objects. Do not use one instance of CBCAPolygon in more than one thread.

      Specified by:
      contains in interface Shape
      Overrides:
      contains in class Polygon
      Parameters:
      x - the specified coordinates
      y - the specified coordinates
      Returns:
      true if the Polygon contains the specified coordinates; false otherwise.

    • doLineSegmentsIntersect

      public static boolean doLineSegmentsIntersect(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2)
      Check if two line segments intersect, according to the algorithm from "Algorithms", Cormen, Leiserson & Rivest, 1992, pp. 889-890.
      Parameters:
      ax1 - X coordinate of start of first segment
      ay1 - Y coordinate of start of first segment
      ax2 - X coordinate of end of first segment
      ay2 - Y coordinate of end of first segment
      bx1 - X coordinate of start of second segment
      by1 - Y coordinate of start of second segment
      bx2 - X coordinate of end of second segment
      by2 - Y coordinate of end of second segment
      Returns:
      boolean true if line segments intersect between their endpoints

    • createConvexBoundaryPolygon

      public static CBCAPolygon createConvexBoundaryPolygon(Point[] points)
      Find the convex hull polygon around an arbitrary unordered array of points.

      Note that the points array will be modified by this method; if the points are required for some other usage, ensure that a copy is made before passing the array to this method.

      Parameters:
      points - array of Points to bind inside the convex hull; this array will be altered by this method
      Returns:
      CBCAPolygon of a convex hull around the point set, where every vertex is a Point from the original array of Points
      Throws:
      IllegalArgumentException - if the point array does not contain enough unique vertices to create a valid polygon