Algorithm
Development Kit 1.0

algs.model.problems.convexhull.slowhull
Class SlowHull

java.lang.Object
  extended by algs.model.problems.convexhull.slowhull.SlowHull
All Implemented Interfaces:
IConvexHull

public class SlowHull
extends java.lang.Object
implements IConvexHull

Computes Convex Hull using a brute force approach that computes all n^3 triangles and removes points that are within a triangle.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Constructor Summary
SlowHull()
           
 
Method Summary
 IPoint[] compute(IPoint[] points)
          Use SlowHull algorithm to return the computed convex hull for the input set of points.
static double compute(IPoint[] points, int leftMostX, int i)
          Compute the angle between the vertical line based at leftMostX and the line between points[leftMostX] and points[i].
static boolean internalPoint(IPoint[] points, int m, int i, int j, int k)
          Determine if points[m] is inside triangle formed by Given line (i,j), determine which side points[m] is on.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

SlowHull

public SlowHull()
Method Detail

compute

public IPoint[] compute(IPoint[] points)
Use SlowHull algorithm to return the computed convex hull for the input set of points. Uses BruteForce approach.

Specified by:
compute in interface IConvexHull
Parameters:
points - a set of (n ≥ 3) two dimensional points.

internalPoint

public static boolean internalPoint(IPoint[] points,
                                    int m,
                                    int i,
                                    int j,
                                    int k)
Determine if points[m] is inside triangle formed by Given line (i,j), determine which side points[m] is on. Then verify that this is the case for line (j,k) and line (k,i) in that order and direction.

Here is a nifty equation, derived from the logic that a line can be computed from points (x1,y1) to (x2,y2).

                 (y2 - y1)
    0 = y - y1 - --------- (x - x1)
                 (x2 - x1)
 
If all three calculations have the same SIGN, then outside. If any deviate from the other, then INSIDE.

Note that points that are Co-linear with any of the edges are determined to be "inside"

Parameters:
points - original IPoint array into which (i,j,k) index
m - index of target point to be investigated
i - index of point 1
j - index of point 2
k - index of point 3

compute

public static double compute(IPoint[] points,
                             int leftMostX,
                             int i)
Compute the angle between the vertical line based at leftMostX and the line between points[leftMostX] and points[i]. Note that theta is the angle we are trying to compute. Since we are in control of the vertical line, we assume points[leftMostX] is the origin, thus the vertical line can be set to the vector (0,1), in otherwords, v1 = 0*i + 1*j. The other vector is then
    v2 = (points[i].getX() - points[leftMostX].getX())*i + 
           (points[i].getY() - points[leftMostX].getY())*j
 
    cos(theta) = ((Vector 1) . (Vector 2)) / (||Vector 1|| X ||Vector 2||)
 
where the . (dot) is the dot product between the vectors and ||Vector|| represents the magnitude of the vector.

If v = a*i+b*j and w = c*i+d*j, then

    dot product of v.w = ac + bd
    ||v|| is sqrt (a^2 + b^2).  
 
Once we compute cos(theta), we invoke cos[-1] to compute theta, which will be a value between 0 and pi.

Parameters:
points - points to inspect
leftMostX - index of the left-most point
i - index of target point to inspect

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.