dev.roanh.convexmerger.util

Class ConvexUtil

java.lang.Object

dev.roanh.convexmerger.util.ConvexUtil

public class ConvexUtil
extends java.lang.Object

Class containing various utilities related to convex objects and hulls. General assumptions on the convex objects dealt with by this class are documented at checkInvariants(List).

Field Summary

Fields

Modifier and Type	Field and Description
private static double	EPS Tolerance value used for dealing with floating point rounding errors.

Constructor Summary

Constructors

Constructor and Description
ConvexUtil()

Method Summary

Modifier and Type	Method and Description
static double	angleBetweenLines(java.awt.geom.Line2D a, java.awt.geom.Line2D b) Computes the relative angle in counter-clockwise direction between the two given directed line segments.
static double	angleFromVertical(double x1, double y1, double x2, double y2) Computes the angle the given line makes with the negative y-axis (going down along the y-axis).
static double	angleFromVertical(java.awt.geom.Line2D line) Computes the angle the given line makes with the negative y-axis (going down along the y-axis).
static double	angleFromVertical(java.awt.geom.Point2D p1, java.awt.geom.Point2D p2) Computes the angle the given line makes with the negative y-axis (going down along the y-axis).
static boolean	approxEqual(java.awt.geom.Point2D a, java.awt.geom.Point2D b) Checks if the two given points are approximately equal.
static boolean	checkCollinear(double x1, double y1, double x2, double y2, double x3, double y3) Function to check if 3 points are collinear.
static boolean	checkCollinear(int x1, int y1, int x2, int y2, int x3, int y3) Function to check if 3 points are collinear.
static boolean	checkCollinear(java.awt.geom.Point2D p1, java.awt.geom.Point2D p2, java.awt.geom.Point2D p3) Function to check if 3 points are collinear.
static boolean	checkInvariants(java.util.List<java.awt.geom.Point2D> points) Checks if the convex object represented by the given set of points conforms to all the general invariants assumed by most algorithms in this class.
static double	clamp(double a, double b, double val) Clamps the given value to be between the given bounds.
static double	computeArea(java.util.List<java.awt.geom.Point2D> points) Computes the area of the given convex object.
static java.awt.geom.Point2D	computeCentroid(java.util.List<java.awt.geom.Point2D> points) Computes the centroid of the given convex object.
static java.util.List<java.awt.geom.Point2D>	computeConvexHull(java.util.List<java.awt.geom.Point2D> points) Computes the convex hull of the given point set using the gift wrapping algorithm.
static java.util.List<java.util.List<java.awt.geom.Point2D>>	computeMergeBounds(java.util.List<java.awt.geom.Point2D> first, java.util.List<java.awt.geom.Point2D> second) Splits the given convex objects into segments that are either on the outside or on the inside of the convex object that is created when merging them.
static java.util.List<java.util.List<java.awt.geom.Point2D>>	computeMergeBounds(java.util.List<java.awt.geom.Point2D> first, java.util.List<java.awt.geom.Point2D> second, java.awt.geom.Point2D[] mergeLines) Splits the given convex objects into segments that are either on the outside or on the inside of the convex object that is created when merging them.
static java.util.List<java.util.List<java.awt.geom.Point2D>>	computeMergeBounds(java.util.List<java.awt.geom.Point2D> hull, java.awt.geom.Point2D a, java.awt.geom.Point2D b) Splits the given hull into two parts, one part that is contained between the two points going from a to b and one part that is contained between the two points going from b to a.
static java.awt.geom.Point2D[]	computeMergeLines(java.util.List<java.awt.geom.Point2D> first, java.util.List<java.awt.geom.Point2D> second, boolean allowOverlap) Computes the two lines that would be required to combine the two given convex hulls into a single convex hull in linear time.
static java.awt.geom.Point2D[]	computeMergeLines(java.util.List<java.awt.geom.Point2D> first, java.util.List<java.awt.geom.Point2D> second, java.util.List<java.awt.geom.Point2D> hull) Computes the two lines that would be required to combine the two given convex hulls into a single convex hull using the convex hull of both objects.
static java.util.List<java.awt.geom.Line2D>	computeSinglePointMergeLines(java.util.List<java.awt.geom.Point2D> points, java.awt.geom.Point2D point) Computes the two lines that would be required to extend the given convex hull with the given point.
static java.awt.geom.Point2D	interceptClosed(java.awt.geom.Line2D a, java.awt.geom.Line2D b) Computes the intersection point of the two given closed line segments.
static java.awt.geom.Point2D	interceptClosed(java.awt.geom.Point2D a, java.awt.geom.Point2D b, java.awt.geom.Point2D c, java.awt.geom.Point2D d) Computes the intersection point of the two given closed line segments.
static java.awt.geom.Point2D	interceptOpen(java.awt.geom.Line2D a, java.awt.geom.Line2D b) Computes the intersection point of the two given infinite line segments.
static java.awt.geom.Point2D	interceptOpen(java.awt.geom.Point2D a, java.awt.geom.Point2D b, java.awt.geom.Point2D c, java.awt.geom.Point2D d) Computes the intersection point of the two given infinite line segments.
static java.util.List<java.awt.geom.Point2D>	mergeHulls(java.util.List<java.awt.geom.Point2D> first, java.util.List<java.awt.geom.Point2D> second, java.awt.geom.Point2D[] mergeLines) Merges the two given convex objects into a joint convex hull encompassing all points in both original objects.
static boolean	onLine(java.awt.geom.Point2D p, java.awt.geom.Point2D a, java.awt.geom.Point2D b) Checks if the given point p is on the closed line segment between a and b.
static boolean	overlapsLine(java.awt.geom.Line2D test, java.awt.geom.Line2D line) Checks if the given test line segment fully overlaps the given line segment.
static java.util.List<java.util.List<java.awt.geom.Point2D>>	splitHull(java.util.List<java.awt.geom.Point2D> hull, java.awt.geom.Line2D line) Splits the given convex hull into two new hulls along the given splitting line.

Methods inherited from class java.lang.Object

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

Field Detail

EPS

private static final double EPS

Tolerance value used for dealing with floating point rounding errors.

See Also:

Constant Field Values

Constructor Detail

ConvexUtil

public ConvexUtil()

Method Detail

computeConvexHull

public static final java.util.List<java.awt.geom.Point2D> computeConvexHull(java.util.List<java.awt.geom.Point2D> points)

Computes the convex hull of the given point set using the gift wrapping algorithm. The returned hull has the left most point as the first point and the winding order is counter-clockwise.

Parameters:

points - The points to compute the convex hull of.

Returns:

The convex hull for the given set of points.

See Also:

checkInvariants(List)

computeMergeLines

public static final java.awt.geom.Point2D[] computeMergeLines(java.util.List<java.awt.geom.Point2D> first,
                                                              java.util.List<java.awt.geom.Point2D> second,
                                                              java.util.List<java.awt.geom.Point2D> hull)

Computes the two lines that would be required to combine the two given convex hulls into a single convex hull using the convex hull of both objects. It is required that the left most point of the combined hull is the first point in the given hull.

Parameters:

first - The first convex hull, the first point has to be bottom leftmost and the winding order counter-clockwise.

second - The second convex hull, the first point has to be bottom leftmost and the winding order counter-clockwise.

hull - The convex hull constructed by merging the other two convex hulls, the first point has to be bottom leftmost and be an exact object reference to the first point of one of the given objects, and the winding order of points has to be counter-clockwise.

Returns:

The points for the two line segments that would be required to complete the convex hull of the two given convex hulls. The first two points make up one of the line segments and the other two the other.

See Also:

computeMergeLines(List, List, boolean), checkInvariants(List)

computeMergeBounds

public static final java.util.List<java.util.List<java.awt.geom.Point2D>> computeMergeBounds(java.util.List<java.awt.geom.Point2D> first,
                                                                                             java.util.List<java.awt.geom.Point2D> second)

Splits the given convex objects into segments that are either on the outside or on the inside of the convex object that is created when merging them.

Parameters:

first - The first convex object, should have the bottom leftmost of the two objects. If not the two objects will be swapped automatically. The winding order of the object has to be counter-clockwise.

second - The second convex object, the first point has to be bottom leftmost and the winding order counter-clockwise.

Returns:

The specific segments, index 0 has the part of the first object that would be contained inside the resulting hull, index 1 has the part of the first object that would be part of the outside of the resulting hull, index 2 has the part of the second object that would be contained inside the resulting hull, index 3 has the part of the second object that would be part of the outside of the resulting hull.

See Also:

computeMergeLines(List, List, boolean), computeMergeBounds(List, List, Point2D[]), checkInvariants(List)

computeMergeBounds

public static final java.util.List<java.util.List<java.awt.geom.Point2D>> computeMergeBounds(java.util.List<java.awt.geom.Point2D> first,
                                                                                             java.util.List<java.awt.geom.Point2D> second,
                                                                                             java.awt.geom.Point2D[] mergeLines)

Splits the given convex objects into segments that are either on the outside or on the inside of the convex object that is created when merging them.

Parameters:

first - The first convex object, should have the smallest x-coordinate of the two objects. If not the two objects will be swapped automatically. The winding order of the object has to be counter-clockwise.

second - The second convex object, the first point has to be bottom leftmost and the winding order counter-clockwise.

mergeLines - The points describing the merge lines that would be added to merge the two objects as computed by computeMergeLines(List, List, boolean). The points given here must be exact object references corresponding to points in the given objects. The first merge line has to be from the object with the bottom leftmost to the other object and the second line back from that object to the object with the bottom leftmost point.

Returns:

The specific segments, index 0 has the part of the first object that would be contained inside the resulting hull, index 1 has the part of the first object that would be part of the outside of the resulting hull, index 2 has the part of the second object that would be contained inside the resulting hull, index 3 has the part of the second object that would be part of the outside of the resulting hull.

See Also:

computeMergeLines(List, List, boolean), computeMergeBounds(List, List), checkInvariants(List)

computeMergeBounds

public static final java.util.List<java.util.List<java.awt.geom.Point2D>> computeMergeBounds(java.util.List<java.awt.geom.Point2D> hull,
                                                                                             java.awt.geom.Point2D a,
                                                                                             java.awt.geom.Point2D b)

Splits the given hull into two parts, one part that is contained between the two points going from a to b and one part that is contained between the two points going from b to a.

Parameters:

hull - The hull to split.

a - The first split point.

b - The second split point.

Returns:

The specific segments with the part from a to b at index 0 and the part from b to a at index 1.

See Also:

computeMergeBounds(List, List, Point2D[]), computeMergeBounds(List, List)

checkCollinear

public static final boolean checkCollinear(int x1,
                                           int y1,
                                           int x2,
                                           int y2,
                                           int x3,
                                           int y3)

Function to check if 3 points are collinear.

Parameters:

x1 - The x coordinate of the first point.

y1 - The y coordinate of the first point.

x2 - The x coordinate of the second point.

y2 - The y coordinate of the second point.

x3 - The x coordinate of the third point.

y3 - The y coordinate of the third point.

Returns:

True if the given points are (close to) collinear.

checkCollinear

public static final boolean checkCollinear(java.awt.geom.Point2D p1,
                                           java.awt.geom.Point2D p2,
                                           java.awt.geom.Point2D p3)

Function to check if 3 points are collinear.

Parameters:

p1 - The first point.

p2 - The second point.

p3 - The third point.

Returns:

True if the given points are (close to) collinear.

checkCollinear

public static final boolean checkCollinear(double x1,
                                           double y1,
                                           double x2,
                                           double y2,
                                           double x3,
                                           double y3)

Function to check if 3 points are collinear.

Parameters:

x1 - The x coordinate of the first point.

y1 - The y coordinate of the first point.

x2 - The x coordinate of the second point.

y2 - The y coordinate of the second point.

x3 - The x coordinate of the third point.

y3 - The y coordinate of the third point.

Returns:

True if the given points are (close to) collinear.

computeMergeLines

public static final java.awt.geom.Point2D[] computeMergeLines(java.util.List<java.awt.geom.Point2D> first,
                                                              java.util.List<java.awt.geom.Point2D> second,
                                                              boolean allowOverlap)

Computes the two lines that would be required to combine the two given convex hulls into a single convex hull in linear time. The approach used for the computation is loosely based on an algorithm proposed in a paper by Godfried Toussaint.

Parameters:

first - The first convex hull, the first point has to be bottom leftmost and the winding order counter-clockwise.

second - The second convex hull, the first point has to be bottom leftmost and the winding order counter-clockwise.

allowOverlap - When true the output lines are allowed to overlap segments from the original objects. Doing so will eliminate collinear points, but will also mean the output lines could overlap the input objects.

Returns:

The points for the two line segments that would be required to complete the convex hull of the two given convex hulls. The first two points make up in order the line going from the object containing the bottom leftmost point to the other object, and the other two points make up in order the line back from the other object to the object containing the bottom leftmost point.

See Also:

computeMergeLines(List, List, List), Toussaint, Godfried T., "A simple linear algorithm for intersecting convex polygons", in The Visual Computer, vol. 1, 1985, pp. 118-123, checkInvariants(List)

computeSinglePointMergeLines

public static final java.util.List<java.awt.geom.Line2D> computeSinglePointMergeLines(java.util.List<java.awt.geom.Point2D> points,
                                                                                      java.awt.geom.Point2D point)

Computes the two lines that would be required to extend the given convex hull with the given point.

Parameters:

points - The first convex hull, the first point has to be bottom leftmost and the winding order counter-clockwise.

point - The point to extend the hull with.

Returns:

The two resultant merge lines, both starting from the convex object and ending at the point.

mergeHulls

public static final java.util.List<java.awt.geom.Point2D> mergeHulls(java.util.List<java.awt.geom.Point2D> first,
                                                                     java.util.List<java.awt.geom.Point2D> second,
                                                                     java.awt.geom.Point2D[] mergeLines)

Merges the two given convex objects into a joint convex hull encompassing all points in both original objects. The output convex hull will not contain any collinear segments on its border, will wind counter-clockwise, and its first point will be bottom leftmost.

Parameters:

first - The first convex hull, the first point has to be bottom leftmost and the winding order counter-clockwise.

second - The second convex hull, the first point has to be bottom leftmost and the winding order counter-clockwise.

mergeLines - The points describing the merge lines that would be added to merge the two objects as computed by computeMergeLines(List, List, boolean). The points given here must be exact object references corresponding to points in the given objects. The first merge line has to be from the object with the bottom leftmost to the other object and the second line back from that object to the object with the bottom leftmost point.

Returns:

The computed joint convex hull.

See Also:

computeMergeLines(List, List, boolean), checkInvariants(List)

checkInvariants

public static final boolean checkInvariants(java.util.List<java.awt.geom.Point2D> points)

Checks if the convex object represented by the given set of points conforms to all the general invariants assumed by most algorithms in this class. More detailed information about any possible violations is printed to standard error.

The tested invariants are:

1. The object has an interior, meaning its area is non zero.
2. No sequence of 3 points on the object's boundary are collinear.
3. The first point of the object is the bottom leftmost point.
4. The object is convex.
5. The object winding order is counter-clockwise.

Parameters:

points - The points that make up the convex object to test.

Returns:

True if all invariants hold, false otherwise.

angleFromVertical

public static final double angleFromVertical(java.awt.geom.Line2D line)

Computes the angle the given line makes with the negative y-axis (going down along the y-axis). The angle is given as the number of radians traversed when rotating from the negative y-axis in counter -clockwise direction until the given line is found with the correct direction. For example the angle for the line (0,0)-(10,0) is 90 degrees, but the angle for the line (0,0)-(-10,0) is 270 degrees.

Parameters:

line - The line whose angle to the vertical compute.

Returns:

The angle of the vertical to the given line in radians, the returned angle is always a positive number.

angleFromVertical

public static final double angleFromVertical(java.awt.geom.Point2D p1,
                                             java.awt.geom.Point2D p2)

Computes the angle the given line makes with the negative y-axis (going down along the y-axis). The angle is given as the number of radians traversed when rotating from the negative y-axis in counter -clockwise direction until the given line is found with the correct direction. For example the angle for the line (0,0)-(10,0) is 90 degrees, but the angle for the line (0,0)-(-10,0) is 270 degrees.

Parameters:

p1 - The start point of the given line.

p2 - The end point of the given line.

Returns:

The angle of the vertical to the given line in radians, the returned angle is always a positive number.

angleFromVertical

public static final double angleFromVertical(double x1,
                                             double y1,
                                             double x2,
                                             double y2)

Computes the angle the given line makes with the negative y-axis (going down along the y-axis). The angle is given as the number of radians traversed when rotating from the negative y-axis in counter -clockwise direction until the given line is found with the correct direction. For example the angle for the line (0,0)-(10,0) is 90 degrees, but the angle for the line (0,0)-(-10,0) is 270 degrees.

Parameters:

x1 - The x-coordinate of the start point of the given line.

y1 - The y-coordinate of the start point of the given line.

x2 - The x-coordinate of the end point of the given line.

y2 - The y-coordinate of the end point of the given line.

Returns:

The angle of the vertical to the given line in radians, the returned angle is always a positive number.

angleBetweenLines

public static final double angleBetweenLines(java.awt.geom.Line2D a,
                                             java.awt.geom.Line2D b)

Computes the relative angle in counter-clockwise direction between the two given directed line segments.

Parameters:

a - The first line segment (start).

b - The second line segment (end).

Returns:

The relative angle between the two line segments in radians, the returned angle is always a positive number.

computeCentroid

public static final java.awt.geom.Point2D computeCentroid(java.util.List<java.awt.geom.Point2D> points)

Computes the centroid of the given convex object.

Parameters:

points - The points that make up the convex object in (counter) clockwise order.

Returns:

The centroid of the convex object.

computeArea

public static final double computeArea(java.util.List<java.awt.geom.Point2D> points)

Computes the area of the given convex object.

Parameters:

points - The points that make up the convex object in (counter) clockwise order.

Returns:

The area for the convex object.

See Also:

Shoelace formula

onLine

public static final boolean onLine(java.awt.geom.Point2D p,
                                   java.awt.geom.Point2D a,
                                   java.awt.geom.Point2D b)

Checks if the given point p is on the closed line segment between a and b. The given point is assumed to be on the infinite line segment between a and b.

Parameters:

p - The point to check.

a - The first point of the line segment.

b - The second point of the line segment.

Returns:

True if the given point is on the given line segment.

clamp

public static final double clamp(double a,
                                 double b,
                                 double val)

Clamps the given value to be between the given bounds.

Parameters:

a - The first bound value.

b - The second bound value.

val - The value to clamp.

Returns:

The clamped value.

interceptClosed

public static final java.awt.geom.Point2D interceptClosed(java.awt.geom.Line2D a,
                                                          java.awt.geom.Line2D b)

Computes the intersection point of the two given closed line segments.

Parameters:

a - The first line segment.

b - The second line segment.

Returns:

The intersection point, or null if the given line segments do not intersect.

interceptOpen

public static final java.awt.geom.Point2D interceptOpen(java.awt.geom.Line2D a,
                                                        java.awt.geom.Line2D b)

Computes the intersection point of the two given infinite line segments.

Parameters:

a - The first line segment.

b - The second line segment.

Returns:

The intersection point, or null if the given line segments do not intersect.

interceptClosed

public static final java.awt.geom.Point2D interceptClosed(java.awt.geom.Point2D a,
                                                          java.awt.geom.Point2D b,
                                                          java.awt.geom.Point2D c,
                                                          java.awt.geom.Point2D d)

Computes the intersection point of the two given closed line segments.

Parameters:

a - The first point of the first line segment.

b - The second point of the first line segment.

c - The first point of the second line segment.

d - The second point of the second line segment.

Returns:

The intersection point, or null if the given line segments do not intersect.

interceptOpen

public static final java.awt.geom.Point2D interceptOpen(java.awt.geom.Point2D a,
                                                        java.awt.geom.Point2D b,
                                                        java.awt.geom.Point2D c,
                                                        java.awt.geom.Point2D d)

Computes the intersection point of the two given infinite line segments.

Parameters:

a - The first point of the first line segment.

b - The second point of the first line segment.

c - The first point of the second line segment.

d - The second point of the second line segment.

Returns:

The intersection point, or null if the given line segments do not intersect (meaning they run parallel).

splitHull

public static final java.util.List<java.util.List<java.awt.geom.Point2D>> splitHull(java.util.List<java.awt.geom.Point2D> hull,
                                                                                    java.awt.geom.Line2D line)

Splits the given convex hull into two new hulls along the given splitting line. The given line will be treated as an infinite line segment and has to intersect the given convex hull. Geometrically the two returned convex hulls still cover the exact same area as the input convex hull. Note: input and output convex objects to this subroutine do not have to comply with the general convex object assumptions for this class as specified in checkInvariants(List).

Parameters:

hull - The convex hull to split.

line - The line to split the hull along.

Returns:

The two halves of the original now split convex hull. The first half will be entirely left to the splitting line (relative CCW of -1) and the second half will be right of the splitting line (relative CCW >= 0).

See Also:

Line2D.relativeCCW(Point2D)

approxEqual

public static final boolean approxEqual(java.awt.geom.Point2D a,
                                        java.awt.geom.Point2D b)

Checks if the two given points are approximately equal. Meaning that save for floating point rounding errors both points are in the same location.

Parameters:

a - The first point.

b - The second point.

Returns:

If both points represent the same location.

overlapsLine

public static final boolean overlapsLine(java.awt.geom.Line2D test,
                                         java.awt.geom.Line2D line)

Checks if the given test line segment fully overlaps the given line segment.

Parameters:

test - The line segment to test.

line - The line segment.

Returns:

True if the test line segment overlaps the line segment.