c++ - 在实践中，通过使用两个切线合并两个凸包的算法如何工作？

我试图在C++中实现分而治之的算法，即从一组二维点中查找凸包。为简单起见，我们假定所有点都用整数描述。

该算法最重要的部分是合并您根据先前的递归调用计算出的两个凸包。此部分涉及找到两个凸包的上下切线，然后进行合并。

合并是微不足道的，如果您找到了描述切线的四个点，则不在这四个点定义的多边形内的点将成为新凸包的一部分。

但是，我不知道如何找到这四个要点。

这是大多数源(此源于http://www.cs.wustl.edu/~pless/506/l3.html)建议的伪代码，用于查找凸包HA和凸包HB的下切线。

Finding the Lower Tangent
LowerTangent(HA ; HB ) :
(1) Let a be the rightmost point of HA .
(2) Let b be the leftmost point of HB .
(3) While ab is not a lower tangent for HA and HB do
(a) While ab is not a lower tangent to HA do a = a - 1 (move a clockwise).
(b) While ab is not a lower tangent to HB do b = b + 1 (move b counterCW).
(4) Return ab.

(1)，(2)

这些点最初是按x坐标排序的，因此可以在O(1)中找到HA的最右点和HB的最左点。

a = HA[HA.size-1]
b = HB[0]

现在我无法理解下一步。

选择了这个ab线段后，我们如何检查ab是否不是较低的切线，以便我们可以输入第一个while循环还是不输入？

然后，如何按照顺时针方向将a点移动到a-1？这些点按其x坐标排序，仅执行a = a-1将导致错误的结果。

谢谢!

最佳答案

您的引用仅简要说明:



并且似乎没有提供更多细节。我找到了this reference，它进一步介绍了如何找到较低的切线，包括一些示例代码。

另外请注意，您不应为此目的对X坐标进行排序。该算法依赖于点以其正常连续顺序定义了多边形。按X排序只能帮助您找到初始点。

该引用的下切线算法的伪代码为:

idx1 = (Rightmost point index of Poly1)
idx2 = (Leftmost point index of Poly2)

while (TRUE)
    while (isLeft(Poly1[idx2], Poly2[idx1], Poly2[idx1+1]) <= 0)
        ++idx1;
    end while

    while (isLeft(Poly2[idx1], Poly1[idx2], Poly1[idx2-1]) >= 0)
        --idx2;
        done = FALSE;
    end while
end while

// idx1/idx2 are now the two indices that form the lower tangent

来自相同引用的isLeft()代码为:

float isLeft (Point P0, Point P1, Point P2)
{
    return (P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y);
}

关于c++ - 在实践中，通过使用两个切线合并两个凸包的算法如何工作？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25825970/