convex hull (or convex-huh?)

[JernejL]

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]

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]

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]

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(const Px,Py,x1,y1,x2,y2:TFloat):Boolean;
begin
  Result := ((x2 - x1) * (py - y1) > (px - x1) * (y2 - y1));
end;

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

  Dx2 := x3 - x1;
  Dy2 := y3 - y1;
  Dz2 := z3 - z1;

  (* Perform a 3d cross product *)
  Cx  := (Dy1 * Dz2) - (Dy2 * Dz1);
  Cy  := (Dx2 * Dz1) - (Dx1 * Dz2);
  Cz  := (Dx1 * Dy2) - (Dx2 * Dy1);

  Result := IsEqual(Cx * Cx + Cy * Cy + Cz * Cz,0.0);
end;


function RobustCollinear(const x1,y1,x2,y2,x3,y3:TFloat; const Epsilon : TFloat = Epsilon_High):Boolean;
var
  LeyDist1 : TFloat;
  LeyDist2 : TFloat;
  LeyDist3 : TFloat;
begin
  LeyDist1 := LayDistance(x1,y1,x2,y2);
  LeyDist2 := LayDistance(x2,y2,x3,y3);
  LeyDist3 := LayDistance(x3,y3,x1,y1);

  if LeyDist1 >= LeyDist2 then
    if LeyDist1 >= LeyDist3 then
      Result := IsEqual(MinimumDistanceFromPointToLine(x3,y3,x1,y1,x2,y2),0.0,Epsilon)
    else
      Result := IsEqual(MinimumDistanceFromPointToLine(x2,y2,x3,y3,x1,y1),0.0,Epsilon)
  else if LeyDist2 >= LeyDist3 then
    Result := IsEqual(MinimumDistanceFromPointToLine(x1,y1,x2,y2,x3,y3),0.0,Epsilon)
  else
    Result := IsEqual(MinimumDistanceFromPointToLine(x2,y2,x3,y3,x1,y1),0.0,Epsilon);
end;


function IsPointCollinear(const x1,y1,x2,y2,Px,Py:TFloat; const Robust : Boolean = False):Boolean;
begin
  (*
    This method will return true iff the point (px,py) is collinear
    to points (x1,y1) and (x2,y2) and exists on the segment A(x1,y1)->B(x2,y2)
  *)
  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]

Thanks, that code looks very promising

[Huehnerschaender]

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]

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/~mich...ier_curves.php. Feel free to use and extend this code. (it's licensed on GNU GPL)