|
Algorithm Development Kit 1.0 |
||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||
java.lang.Objectalgs.model.problems.convexhull.slowhull.SlowHull
public class SlowHull
Computes Convex Hull using a brute force approach that computes all n^3 triangles and removes points that are within a triangle.
| 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 |
|---|
public SlowHull()
| Method Detail |
|---|
public IPoint[] compute(IPoint[] points)
compute in interface IConvexHullpoints - a set of (n ≥ 3) two dimensional points.
public static boolean internalPoint(IPoint[] points,
int m,
int i,
int j,
int k)
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"
points - original IPoint array into which (i,j,k) indexm - index of target point to be investigatedi - index of point 1j - index of point 2k - index of point 3
public static double compute(IPoint[] points,
int leftMostX,
int i)
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.
points - points to inspectleftMostX - index of the left-most pointi - index of target point to inspect
|
Algorithm Development Kit 1.0 | ||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||