GlobalNavigation
Class GeomUtils

java.lang.Object
  GlobalNavigation.GeomUtils

public class GeomUtils
extends java.lang.Object

Geometric utilities.

Field Summary

static java.util.Comparator<java.awt.geom.Point2D.Double>

POINT_COMPARATOR_LR Compare two points for sorting in x-increasing (then y-increasing) order.

Constructor Summary

GeomUtils()

Method Summary

static PolygonObstacle	convexHull(java.util.List<java.awt.geom.Point2D.Double> points) Compute the convex hull of a set of points.
static boolean	rightTurn(java.awt.geom.Point2D.Double p0, java.awt.geom.Point2D.Double p1, java.awt.geom.Point2D.Double p2) Check whether three ordered points make a right turn.

Methods inherited from class java.lang.Object

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

Field Detail

POINT_COMPARATOR_LR

public static final java.util.Comparator<java.awt.geom.Point2D.Double> POINT_COMPARATOR_LR

Compare two points for sorting in x-increasing (then y-increasing) order.

Constructor Detail

GeomUtils

public GeomUtils()

Method Detail

convexHull

public static PolygonObstacle convexHull(java.util.List<java.awt.geom.Point2D.Double> points)

Compute the convex hull of a set of points.

Follows de Berg, van Kreveld, Overmars, Schwarzkopf p. 6.

Parameters:

points - the set of points, not null. Will be sorted by POINT_COMPARATOR_LR and will have duplicates removed.

Returns:

the convex hull of points, which degenerates to a line segment or a point or an empty polygon if there are less than three distinct points.

rightTurn

public static boolean rightTurn(java.awt.geom.Point2D.Double p0,
                                java.awt.geom.Point2D.Double p1,
                                java.awt.geom.Point2D.Double p2)

Check whether three ordered points make a right turn.

This is equivalent to asking if p1 lies to the left of the oriented line from p0 to p2, which is equivalent to asking if the z component of the cross product of the vector from p0 to p2 with the vector from p0 to p1 is positive.

Parameters:

p0 - the first point

p1 - the second point

p2 - the third point

Returns:

true iff the ordered sequence p0, p1, p2 makes a right turn