维基百科的文章解除或多或少直接
- 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
什么情况是，该方法开始添加相同点处于下风一遍又一遍。在一种测试情况下，我发送在点（200; 200）（300; 100），（200; 50）和（100; 100），并且所述算法开始，加入（100; 100）到下风这是正确的，但随后它开始增加（200，200）。一遍又一遍
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.
更新：
乔纳森Dursi把我在正确的轨道。此行
Jonathan Dursi put me on the right track. This line
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 :-)
推荐答案
这可能不是一个conicidence是（200，200）。为一点0
It's probably not a conicidence that (200;200) is point 0.
看起来你不是被终点（vEndPoint），以及实现取向不会拒绝这种情况下，不包括当前点（vPointOnHull）; presumably它返回LHS如果叉积为正，而如果vPointOnHull == vEndPoint，交叉积为零，所以从来LHS。所以从来都没有取代点0点后选择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.
您可以修改方向返回退化什么在这种情况下，也拒绝了一点，或者你可以从以往任何时候都终点排除当前点。需要注意的是，你不想做明显的事情，过滤掉电流CH点从点同时通过设置进发，因为你需要找到结束点是第一点，收循环。
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.
更新：环顾了一下在FastGEO的东西，很可能更新方向是不是要走的路（虽然有点更多的思考应该进入直排点情况下，这个算法，如果有在船体上的共线点，你真的想最近的一个第一，所以你想一个否则，如果方向=共线然后..更新vEndpoint如果新点接近条款如果语句后）。
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).
最简单的可能只是添加几行保持当前indicies的曲目，所以你可以很容易地进行平等的测试：东西有点像
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;
这篇关于为什么不这样执行贾维斯'三月（QUOT;礼品包装算法＆QUOT;）工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
