public class ConvexUtil
extends java.lang.Object
checkInvariants(List)
.Modifier and Type  Field and Description 

private static double 
EPS
Tolerance value used for dealing with floating point rounding errors.

Constructor and Description 

ConvexUtil() 
Modifier and Type  Method and Description 

static double 
angleBetweenLines(java.awt.geom.Line2D a,
java.awt.geom.Line2D b)
Computes the relative angle in counterclockwise 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 yaxis (going down along the yaxis).

static double 
angleFromVertical(java.awt.geom.Line2D line)
Computes the angle the given line makes with the
negative yaxis (going down along the yaxis).

static double 
angleFromVertical(java.awt.geom.Point2D p1,
java.awt.geom.Point2D p2)
Computes the angle the given line makes with the
negative yaxis (going down along the yaxis).

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.

private static final double EPS
public static final java.util.List<java.awt.geom.Point2D> computeConvexHull(java.util.List<java.awt.geom.Point2D> points)
points
 The points to compute the convex hull of.checkInvariants(List)
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)
first
 The first convex hull, the first point
has to be bottom leftmost and the winding
order counterclockwise.second
 The second convex hull, the first point
has to be bottom leftmost and the winding
order counterclockwise.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 counterclockwise.computeMergeLines(List, List, boolean)
,
checkInvariants(List)
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)
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 counterclockwise.second
 The second convex object, the first point
has to be bottom leftmost and the winding
order counterclockwise.computeMergeLines(List, List, boolean)
,
computeMergeBounds(List, List, Point2D[])
,
checkInvariants(List)
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)
first
 The first convex object, should have the
smallest xcoordinate of the two objects. If not
the two objects will be swapped automatically.
The winding order of the object has to be counterclockwise.second
 The second convex object, the first point
has to be bottom leftmost and the winding
order counterclockwise.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.computeMergeLines(List, List, boolean)
,
computeMergeBounds(List, List)
,
checkInvariants(List)
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)
a
to b
and one
part that is contained between the two points
going from b
to a
.hull
 The hull to split.a
 The first split point.b
 The second split point.a
to b
at index
0 and the part from b
to
a
at index 1.computeMergeBounds(List, List, Point2D[])
,
computeMergeBounds(List, List)
public static final boolean checkCollinear(int x1, int y1, int x2, int y2, int x3, int y3)
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.public static final boolean checkCollinear(java.awt.geom.Point2D p1, java.awt.geom.Point2D p2, java.awt.geom.Point2D p3)
p1
 The first point.p2
 The second point.p3
 The third point.public static final boolean checkCollinear(double x1, double y1, double x2, double y2, double x3, double y3)
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.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)
first
 The first convex hull, the first point
has to be bottom leftmost and the winding
order counterclockwise.second
 The second convex hull, the first point
has to be bottom leftmost and the winding
order counterclockwise.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.computeMergeLines(List, List, List)
,
Toussaint, Godfried T., "A simple linear algorithm for intersecting convex polygons", in The Visual Computer, vol. 1, 1985, pp. 118123,
checkInvariants(List)
public static final java.util.List<java.awt.geom.Line2D> computeSinglePointMergeLines(java.util.List<java.awt.geom.Point2D> points, java.awt.geom.Point2D point)
points
 The first convex hull, the first point
has to be bottom leftmost and the winding
order counterclockwise.point
 The point to extend the hull with.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)
first
 The first convex hull, the first point
has to be bottom leftmost and the winding
order counterclockwise.second
 The second convex hull, the first point
has to be bottom leftmost and the winding
order counterclockwise.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.computeMergeLines(List, List, boolean)
,
checkInvariants(List)
public static final boolean checkInvariants(java.util.List<java.awt.geom.Point2D> points)
The tested invariants are:
points
 The points that make up the convex object to test.public static final double angleFromVertical(java.awt.geom.Line2D line)
(0,0)(10,0)
is 90 degrees, but the
angle for the line (0,0)(10,0)
is 270 degrees.line
 The line whose angle to the vertical compute.public static final double angleFromVertical(java.awt.geom.Point2D p1, java.awt.geom.Point2D p2)
(0,0)(10,0)
is 90 degrees, but the
angle for the line (0,0)(10,0)
is 270 degrees.p1
 The start point of the given line.p2
 The end point of the given line.public static final double angleFromVertical(double x1, double y1, double x2, double y2)
(0,0)(10,0)
is 90 degrees, but the
angle for the line (0,0)(10,0)
is 270 degrees.x1
 The xcoordinate of the start point of the given line.y1
 The ycoordinate of the start point of the given line.x2
 The xcoordinate of the end point of the given line.y2
 The ycoordinate of the end point of the given line.public static final double angleBetweenLines(java.awt.geom.Line2D a, java.awt.geom.Line2D b)
a
 The first line segment (start).b
 The second line segment (end).public static final java.awt.geom.Point2D computeCentroid(java.util.List<java.awt.geom.Point2D> points)
points
 The points that make up the convex object
in (counter) clockwise order.public static final double computeArea(java.util.List<java.awt.geom.Point2D> points)
points
 The points that make up the convex object
in (counter) clockwise order.public static final boolean onLine(java.awt.geom.Point2D p, java.awt.geom.Point2D a, java.awt.geom.Point2D b)
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
.p
 The point to check.a
 The first point of the line segment.b
 The second point of the line segment.public static final double clamp(double a, double b, double val)
a
 The first bound value.b
 The second bound value.val
 The value to clamp.public static final java.awt.geom.Point2D interceptClosed(java.awt.geom.Line2D a, java.awt.geom.Line2D b)
a
 The first line segment.b
 The second line segment.null
if the given line segments do not intersect.public static final java.awt.geom.Point2D interceptOpen(java.awt.geom.Line2D a, java.awt.geom.Line2D b)
a
 The first line segment.b
 The second line segment.null
if the given line segments do not intersect.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)
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.null
if the given line segments do not intersect.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)
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.null
if the given line segments do not intersect
(meaning they run parallel).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)
checkInvariants(List)
.hull
 The convex hull to split.line
 The line to split the hull along.Line2D.relativeCCW(Point2D)
public static final boolean approxEqual(java.awt.geom.Point2D a, java.awt.geom.Point2D b)
a
 The first point.b
 The second point.public static final boolean overlapsLine(java.awt.geom.Line2D test, java.awt.geom.Line2D line)
test
 The line segment to test.line
 The line segment.