为什么Jarvis'March（“礼品包装算法”）的这种实现不起作用？ [英] Why doesn't this implementation of Jarvis' March ("Gift wrapping algorithm") work?

问题描述

我正在尝试实现Jarvis算法来找到一组点的凸包，但由于某种原因，它不起作用。这是我的实现：

  procedure TPointList.ConvexHull（aHull：TPointList）; //返回一组2D点的凸包
 var 
 vPointOnHull：TPoint2D; 
 vEndpoint：TPoint2D; 
 I：integer; 
 begin 
 aHull.Clear; 
如果Count< 3然后退出; 
 
 vPointOnHull：= Self.LeftMostPoint; 
重复
 aHull.Add（vPointOnHull）; 
 vEndpoint：= Self.Point [0]; 
 
对于I：= 1到Self.Count-1 do 
如果Orientation（vPointOnHull，vEndpoint，Self.Point [I]）= LeftHandSide然后
 vEndpoint：= Self。点[I] 
 
 vPointOnHull：= vEndpoint; 
，直到vEndpoint = aHull.Point [0]; 
结束
  

• TPointList是一个简单的点列表。


• 方向是Arash Partow的图书馆FastGEO的一个功能。


• 这个实现或多或少直接从关于算法的维基百科文章

发生什么是该方法开始向aHull添加相同的点一遍又一遍。在一个测试用例中，我发送点（200; 200）（300; 100）（200; 50）和（100; 100），并且算法开始于将（100; 100）加到一个正确的它开始一遍又一遍地添加（200; 200）。

显然，我在执行过程中做错了，但对于我的生活我看不到什么。

更新：

Jonathan Dursi把我放在正确的轨道上。如果Orientation（vPointOnHull，vEndpoint，Self.Point [I]）= LeftHandSide然后

  c $ c> 

应该替换为这个

  if（vPointOnHull = vEndpoint）或（Orientation（vPointOnHull，vEndpoint，Self.Point [I]）= LeftHandSide）然后
  

像一个魅力一样工作： - ）

解决方案

（200; 200） 0。

看起来你没有排除当前点（vPointOnHull）作为终点（vEndPoint），而您的Orientation实现不会拒绝案件;如果交叉产品为正，则可能返回LHS，如果vPointOnHull == vEndPoint，则交叉产品为零，所以从不LHS。所以当点0被选择时，没有任何东西替代点0。

您可以修改方向返回退化或者在这种情况下的某种东西，也可以拒绝该点，或者您可以排除当前点从不是终点。请注意，您不想做明显的事情，因为您需要发现终点是关闭循环的第一个点，因此过滤当前行中的当前CH点。

更新：看看FastGEO的东西，可能更新Orientation不是要走的路（尽管更多的想法应该进入colinear点数在这个算法中;如果船体上有共线点，那么你真的需要最接近的一个，所以你想要一个 else if Orientation = Collinear then .. update vEndpoint if new point near code>子句之后的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; 
  

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 :-)

解决方案

It's probably not a conicidence that (200;200) is point 0.

It looks like you're not excluding the current point (vPointOnHull) from being the end point (vEndPoint), and your implementation of Orientation doesn't reject that case; presumably it returns LHS if the cross-product is positive, and if vPointOnHull == vEndPoint, the cross product is zero, so never LHS. So nothing ever replaces Point 0 once Point 0 is selected, et voila.

You could modify Orientation to return "Degenerate" or something in that case, and also reject the point, or you could exclude the current point from ever being the end point. Note that you don't want to do the obvious thing, filter out current CH points from the point set while marching through, because you need to find that the end point is the first point to close the loop.

Update: Looking around a bit at the FastGEO stuff, probably updating Orientation isn't the way to go (although a bit more thought should go into the colinear points case in this algorithm; if there are collinear points on the hull, you really want the closest one first, so you'd like an else if Orientation = Collinear then.. update vEndpoint if new point is closer clause after that if statement).

Easiest might just be to add a couple lines keeping track of the current indicies so you can easily test for equality: something a bit like

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;

这篇关于为什么Jarvis'March（“礼品包装算法”）的这种实现不起作用？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！