为什么这个Jarvis'March("礼品包装算法")的实现不起作用？

Question

我正在尝试实现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;

• TPointList是一个简单的点列表.
• 定位是Arash Partow的图书馆"FastGEO"的功能
• 这个实现或多或少直接取自维基百科关于该算法的文章

会发生的是该方法开始一遍又一遍地向aHull添加相同的点.在一个测试用例中,我发送了点(200; 200)(300; 100)(200; 50)和(100; 100),算法首先将(100; 100)添加到aHull,这是正确的,但是它开始一遍又一遍地添加(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

奇迹般有效 :-)

Answer 1

(200; 200)是第0点可能不是一个小小的问题.

看起来你并没有将当前点(vPointOnHull)排除在终点(vEndPoint)之外,并且你的Orientation实现不会拒绝这种情况; 假设如果交叉积为正,则返回LHS,如果vPointOnHull == vEndPoint,则交叉积为零,因此从不LHS.因此,一旦选择了Point 0,就没有任何东西可以取代Point 0,等等.

您可以修改Orientation以在此情况下返回"Degenerate"或某些内容,并拒绝该点,或者您可以将当前点排除在永远的终点之外.请注意,您不想做明显的事情,在游进过程中从点集中过滤掉当前的CH点,因为您需要找到终点是关闭循环的第一个点.

更新:看看FastGEO的东西,可能更新Orientation不是要走的路(尽管在这个算法中需要考虑共线点的情况;如果船体上有共线点,你真的想要最接近的一个,所以你想要一个else if Orientation = Collinear then.. update vEndpoint if new point is closer句子后if语句).

最简单的可能只是添加几行来跟踪当前的指标,以便您可以轻松地测试相等性:有点像

iPointOnHull := Self.IndexOfLeftMostPoint;
vPointOnHull := Self.LeftMostPoint
...
vEndpoint := Self.Point[0];
iEndPoint := 0;
if (iPointOnHull = 0) then 
begin
    vEndPoint := Self.Point[1];
    iEndPoint := 1;
end
...
vPointOnHull := vEndPoint;
iPointOnHull := iEndPoint;