为什么 Jarvis 的这个实现没有实现？ March（“礼品包装算法”）有效吗？
我正在尝试实现贾维斯算法来查找一组点的凸包，但由于某种原因它不起作用。这是我的实现：
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
Works like a charm :-)
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 :-)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
(200;200) 是点 0 可能不是巧合。
看起来您并没有将当前点 (vPointOnHull) 排除在终点 (vEndPoint) 之外，并且您的 Orientation 实现不会拒绝这种情况；如果叉积为正，则它可能会返回 LHS，并且如果 vPointOnHull == vEndPoint，则叉积为零，因此永远不会返回 LHS。因此，一旦选择了 Point 0，就不会再有任何东西可以取代 Point 0，等等。
在这种情况下，您可以修改方向以返回“退化”或其他内容，并拒绝该点，或者您可以将当前点排除在终点之外。请注意，您不想做显而易见的事情，即在行进时从点集中过滤掉当前的 CH 点，因为您需要找到结束点是关闭循环的第一个点。
更新：环顾一下 FastGEO 的东西，可能更新方向不是可行的方法（尽管应该更多地考虑该算法中的共线点情况；如果存在共线点在船体上，您确实想要首先找到最近的一个，因此您需要一个
else if Orientation = Collinear then.. update vEndpoint if new point is close子句（在 if 语句之后）。最简单的可能只是添加几行来跟踪当前的索引，这样您就可以轻松测试相等性：有点像
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 closerclause 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
循环使用以下代码行添加：
vPointOnHull仅在这些行中分配：您已经解释了
LeftMostPoint已正确添加，因此重复必须来自vEndPoint，在这些行中分配：所以我猜最后一个分配（在下面的 if 语句中）永远不会到达。
——杰罗恩
The loop adds using this line of code:
vPointOnHullis only assigned in these lines:You already explained that
LeftMostPointis added correctly, so the repeat must come fromvEndPoint, which is assigned in these lines:So I guess the last assignment (which is in the below if statement), is never reached.
--jeroen