Edit Question - KnowledgeHub

Title Body

I'm trying to implement Jarvis' algorithm for finding the convex hull of a set of points, but for some reason it doesn't work. This is my implementation: procedure TPointList.ConvexHull(aHull : TPointList); //Return the convex hull of a set of 2D points var vPointOnHull : TPoint2D; vEndpoint : TPoint2D; I : integer; begin aHull.Clear; if Count < 3 then exit; vPointOnHull := Self.LeftMostPoint; repeat aHull.Add(vPointOnHull); vEndpoint := Self.Point[0]; for I := 1 to Self.Count-1 do if Orientation(vPointOnHull,vEndpoint,Self.Point[I]) = LeftHandSide then vEndpoint := Self.Point[I]; vPointOnHull := vEndpoint; until vEndpoint = aHull.Point[0]; end; TPointList is a simple list of points. Orientation is a function from Arash Partow's library "FastGEO" The implementation is lifted more or less directly from the Wikipedia article on the algorithm What happens is that the method starts adding the same point to aHull over and over. In one test case I send in the points (200;200) (300;100) (200;50) and (100;100), and the algorithm starts by adding (100;100) to aHull which is correct, but then it starts adding (200;200) over and over again. Obviously I've done something wrong in my implementation, but for the life of me I can't see what. UPDATE: Jonathan Dursi put me on the right track. This line if Orientation(vPointOnHull,vEndpoint,Self.Point[I]) = LeftHandSide then should be replaced with this if (vPointOnHull = vEndpoint) or (Orientation(vPointOnHull,vEndpoint,Self.Point[I]) = LeftHandSide) then Works like a charm :-)

Tags (comma-separated) Cancel