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 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.
|
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 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.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 counter-clockwise.second
- The second convex object, the first point
has to be bottom leftmost and the winding
order counter-clockwise.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 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.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 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.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)
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 counter-clockwise.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 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.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 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.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.