PDA

View Full Version : convex hull (or convex-huh?)



JernejL
22-04-2006, 06:19 PM
I am in a need of 2D convex hull algorythm, i looked everywhere, the gift-wrapping looks the most appropriate for my project, but i cant figure out how to know if a point is on left side of a line (or is it a plane?), any help woud be greatly appreciated.

User137
23-04-2006, 11:16 AM
Well, you could calculate the angle between edges that are on both sides of point (vertex). If larger than 180 degrees, then non-convex, else convex.

Clootie
23-04-2006, 12:00 PM
one way is to iterate through all triangles and verify that all vertices are "beneath" it, i.e. by checking that distance from vertex to triangle's plane is always negative.

Huehnerschaender
23-04-2006, 12:47 PM
From FastGEO:



function IsPointOnRightSide(const Px,Py,x1,y1,x2,y2:TFloat):Boolean;
begin
Result &#58;= &#40;&#40;&#40;x2 - x1&#41; * &#40;py - y1&#41;&#41; < &#40;&#40;px - x1&#41; * &#40;y2 - y1&#41;&#41;&#41;;
end;




function IsPointOnLeftSide&#40;const Px,Py,x1,y1,x2,y2&#58;TFloat&#41;&#58;Boolean;
begin
Result &#58;= &#40;&#40;x2 - x1&#41; * &#40;py - y1&#41; > &#40;px - x1&#41; * &#40;y2 - y1&#41;&#41;;
end;




function Collinear&#40;const x1,y1,z1,x2,y2,z2,x3,y3,z3&#58;TFloat&#41;&#58;Boolean;
var
Dx1 &#58; TFloat;
Dx2 &#58; TFloat;
Dy1 &#58; TFloat;
Dy2 &#58; TFloat;
Dz1 &#58; TFloat;
Dz2 &#58; TFloat;
Cx &#58; TFloat;
Cy &#58; TFloat;
Cz &#58; TFloat;
begin
&#40;* Find the difference between the 2 points P2 and P3 to P1 *&#41;
Dx1 &#58;= x2 - x1;
Dy1 &#58;= y2 - y1;
Dz1 &#58;= z2 - z1;

Dx2 &#58;= x3 - x1;
Dy2 &#58;= y3 - y1;
Dz2 &#58;= z3 - z1;

&#40;* Perform a 3d cross product *&#41;
Cx &#58;= &#40;Dy1 * Dz2&#41; - &#40;Dy2 * Dz1&#41;;
Cy &#58;= &#40;Dx2 * Dz1&#41; - &#40;Dx1 * Dz2&#41;;
Cz &#58;= &#40;Dx1 * Dy2&#41; - &#40;Dx2 * Dy1&#41;;

Result &#58;= IsEqual&#40;Cx * Cx + Cy * Cy + Cz * Cz,0.0&#41;;
end;


function RobustCollinear&#40;const x1,y1,x2,y2,x3,y3&#58;TFloat; const Epsilon &#58; TFloat = Epsilon_High&#41;&#58;Boolean;
var
LeyDist1 &#58; TFloat;
LeyDist2 &#58; TFloat;
LeyDist3 &#58; TFloat;
begin
LeyDist1 &#58;= LayDistance&#40;x1,y1,x2,y2&#41;;
LeyDist2 &#58;= LayDistance&#40;x2,y2,x3,y3&#41;;
LeyDist3 &#58;= LayDistance&#40;x3,y3,x1,y1&#41;;

if LeyDist1 >= LeyDist2 then
if LeyDist1 >= LeyDist3 then
Result &#58;= IsEqual&#40;MinimumDistanceFromPointToLine&#40;x3,y3,x1,y1 ,x2,y2&#41;,0.0,Epsilon&#41;
else
Result &#58;= IsEqual&#40;MinimumDistanceFromPointToLine&#40;x2,y2,x3,y3 ,x1,y1&#41;,0.0,Epsilon&#41;
else if LeyDist2 >= LeyDist3 then
Result &#58;= IsEqual&#40;MinimumDistanceFromPointToLine&#40;x1,y1,x2,y2 ,x3,y3&#41;,0.0,Epsilon&#41;
else
Result &#58;= IsEqual&#40;MinimumDistanceFromPointToLine&#40;x2,y2,x3,y3 ,x1,y1&#41;,0.0,Epsilon&#41;;
end;


function IsPointCollinear&#40;const x1,y1,x2,y2,Px,Py&#58;TFloat; const Robust &#58; Boolean = False&#41;&#58;Boolean;
begin
&#40;*
This method will return true iff the point &#40;px,py&#41; is collinear
to points &#40;x1,y1&#41; and &#40;x2,y2&#41; and exists on the segment A&#40;x1,y1&#41;->B&#40;x2,y2&#41;
*&#41;
if &#40;&#40;&#40;x1 <= px&#41; and &#40;px <= x2&#41;&#41; or &#40;&#40;x2 <= px&#41; and &#40;px <= x1&#41;&#41;&#41; and
&#40;&#40;&#40;y1 <= py&#41; and &#40;py <= y2&#41;&#41; or &#40;&#40;y2 <= py&#41; and &#40;py <= y1&#41;&#41;&#41; then
begin
if Robust then
Result &#58;= RobustCollinear&#40;x1,y1,x2,y2,Px,Py&#41;
else
Result &#58;= Collinear&#40;x1,y1,x2,y2,Px,Py&#41;;
end
else
Result &#58;= False;
end;


Hope this helps.

JernejL
23-04-2006, 01:07 PM
Thanks, that code looks very promising :)

Huehnerschaender
23-04-2006, 01:17 PM
Seems that I forgot some function for the robust version of Collinear functions. The best way is you get your own copy of FastGEO from

http://www.partow.net/projects/fastgeo/index.html

There you find many many useful functions for geometric calculations.

Greetings,
Dirk

michalis
24-04-2006, 03:37 AM
Some time ago (in 2004) I implemented Jarvis convex hull algorithm (that's the same thing as "gift-wrapping" in 2D, AFAIK). You can grab the source code from my sources page http://www.camelot.homedns.org/~michalis/sources.php --- download "Kambi's standard units" and look inside for file units/3dgraph/convexhullunit.pas. The working demo of this is in bezier_curves program, see http://www.camelot.homedns.org/~michalis/bezier_curves.php. Feel free to use and extend this code. (it's licensed on GNU GPL)