Я пытаюсь реализовать алгоритм Jarvis для нахождения выпуклой оболочки ряда точек, но по некоторым причинам это не работает. Это - моя реализация:
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;
То, что происходит, - то, что метод начинает добавлять ту же точку к без парусов много раз. В одном тестовом сценарии я отправляю в точках (200; 200) (300; 100) (200; 50) и (100; 100), и алгоритм запускается путем добавления (100; 100) к без парусов, который корректен, но затем это начинает добавлять (200; 200) много раз.
Очевидно, я сделал что-то не так в своей реализации, но ни за что в жизни я не вижу что.
ОБНОВЛЕНИЕ:
Jonathan Dursi поместил меня на правильном пути. Эта строка
if Orientation(vPointOnHull,vEndpoint,Self.Point[I]) = LeftHandSide then
должен быть заменен этим
if (vPointOnHull = vEndpoint) or (Orientation(vPointOnHull,vEndpoint,Self.Point[I]) = LeftHandSide) then
Работы как очарование :-)