org.ka2ddo.yaac.util

Class CBCAPolygon

java.lang.Object

java.awt.Polygon

org.ka2ddo.yaac.util.CBCAPolygon

All Implemented Interfaces:

java.awt.Shape, java.io.Serializable

public final class CBCAPolygon
extends java.awt.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:

Serialized Form

Field Summary

Fields inherited from class java.awt.Polygon

bounds, npoints, xpoints, ypoints

Constructor Summary

Constructors

Constructor and Description
CBCAPolygon() Creates an empty polygon.
CBCAPolygon(int[] xPoints, int[] yPoints, int nPoints) Constructs and initializes a Polygon from the specified parameters.

Method Summary

Modifier and Type	Method and Description
void	addPoint(int x, int y) Appends the specified coordinates to this Polygon.
boolean	contains(double x, double y) Determines if the specified coordinates are inside this Polygon.
static CBCAPolygon	createConvexBoundaryPolygon(java.awt.Point[] points) Find the convex hull polygon around an arbitrary unordered array of points.
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.
void	invalidate() Invalidates or flushes any internally-cached data that depends on the vertex coordinates of this Polygon.
void	reset() Resets this Polygon object to an empty polygon.
java.lang.String	toString() Returns a string representation of the object.
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.

Methods inherited from class java.awt.Polygon

contains, contains, contains, contains, contains, getBoundingBox, getBounds, getBounds2D, getPathIterator, getPathIterator, inside, intersects, intersects

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

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:

java.lang.NegativeArraySizeException - if the value of nPoints is negative.

java.lang.IndexOutOfBoundsException - if nPoints is greater than the length of xPoints or the length of yPoints.

java.lang.NullPointerException - if xPoints or yPoints is null.

Method Detail

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 java.awt.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 java.awt.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 java.awt.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 java.awt.Polygon

Parameters:

x - the specified coordinates

y - the specified coordinates

See Also:

Polygon.getBounds(), Polygon.contains(java.awt.Point)

toString

public java.lang.String toString()

Returns a string representation of the object.

Overrides:

toString in class java.lang.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 java.awt.Shape

Overrides:

contains in class java.awt.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(java.awt.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:

java.lang.IllegalArgumentException - if the point array does not contain enough unique vertices to create a valid polygon