|
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 IConvexHull
points
- 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 3public 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 |