All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class convexHull.GrahamScan

java.lang.Object
   |
   +----convexHull.GrahamScan

public class GrahamScan

extends Object

GrahamScan()

computeHull(Vector)

Compute a convex hull for a set of points using a modified Graham scan algorithm, where only LEFT TURN calculation is used.

computeStairs(Vector)

Computes the stairs of points.

leftTurn(CPoint, CPoint, CPoint)

Determines whether two oriented line segments form a left turn.

printPoints(String, Vector)

Prints out a list of points.

printPoints(Vector)

Prints out a list of points.

 public GrahamScan()

 public static Vector computeHull(Vector points)

Compute a convex hull for a set of points using a modified Graham scan algorithm, where only LEFT TURN calculation is used. LEFT TURN is calculated using ESSA algorithm which correctly determines the sign of a sum of n floating point numbers.

Parameters:

points - java.util.Vector - points for which convex hull is to be calculated

Returns:

java.util.Vector - convex hull (in counter-clockwise order)

 public static Vector computeStairs(Vector pts)

Computes the stairs of points. Each quadrant (SW,SE,NE,NW) has stairs in it. These stairs are computed and then concatenated to produce the result. The property of these stairs is that the resulting points are in counterclockwise order, and only candidates for the convex hull are stored in the set.

Parameters:

pts - java.util.Vector - set of points for which stairs are to be calculated

Returns:

java.util.Vector - the computed stairs

 public static boolean leftTurn(CPoint a,
                                CPoint b,
                                CPoint c)

Determines whether two oriented line segments form a left turn. The line segments are specified by AB, and BC.

Parameters:

a - convexHull.CPoint - point A

b - convexHull.CPoint - point B

c - convexHull.CPoint - point C

Returns:

bool - whether the line segments form a left turn

 public static void printPoints(String str,
                                Vector points)

Prints out a list of points.

Parameters:

str - string to be printed before the list

points - list of points

 public static void printPoints(Vector points)

Prints out a list of points.

Parameters:

points - list of points

All Packages  Class Hierarchy  This Package  Previous  Next  Index