the algorithm i used come's from this page :
http://www.cse.yorku.ca/~aaw/Hang/qu...Algorithm.html
in pseudo code :
Code:
Input = a set S of n points
Assume that there are at least 2 points in the input set S of points
QuickHull (S)
{
// Find convex hull from the set S of n points
Convex Hull := {}
Find left and right most points, say A & B, and add A & B to convex hull
Segment AB divides the remaining (n-2) points into 2 groups S1 and S2
where S1 are points in S that are on the right side of the oriented line from A to B,
and S2 are points in S that are on the right side of the oriented line from B to A
FindHull (S1, A, B)
FindHull (S2, B, A)
}
FindHull (Sk, P, Q)
{
// Find points on convex hull from the set Sk of points
// that are on the right side of the oriented line from P to Q
If Sk has no point,
then return.
From the given set of points in Sk, find farthest point, say C, from segment PQ
Add point C to convex hull at the location between P and Q
Three points P, Q, and C partition the remaining points of Sk into 3 subsets: S0, S1, and S2
where S0 are points inside triangle PCQ, S1are points on the right side of the oriented
line from P to C, and S2 are points on the right side of the oriented line from C to Q.
FindHull(S1, P, C)
FindHull(S2, C, Q)
}
Output = convex hull
the result is not convex
Bookmarks