c++ - 婚前征服凸包算法的实现问题

Question

我有兴趣实现和研究 Kirkpatrick–Seidel algorithm .这是找到一组点的凸包的分而治之的方法。我只关心二维情况。

我发现了一份关于这个问题的有趣讲义 here :

算法的大致步骤如下:

  INPUT: A set P of points on the plane.
  OUTPUT: The set of points that define the convex hull.
  1. Calculate median x-coordinate M of P. 
  2. Find the bridge segment that crosses the line x = M using the 
     Prune and Search Technique.
  3. Trim the set based on this segment
  4. Split P to sets PL, PR and recursively apply the above steps to find
     the remaining segments
  5. The above steps must be run twice, once for the upper hall and once
     for the lower hall. Once you find both, you have the convex hull.

(1) 可以在 O(N) 中找到。这非常简单，尤其是在 C++ 中，您可以只使用 nth_element带有指定的比较器

(3) 也可以在 O(N) 中找到。如果您找到的线段由点定义 p1和 p2那么你只需要忽略每个点 p其中 p1.x <= p.x <= p2.x

(4) 只是(3)

的直接结果

(5) 对您刚刚找到的两个子集进行两次递归调用

为了实现O(nlogn)这种分而治之算法的复杂性。我们还需要步骤(2) 来获取O(n) .

根据讲义，这一步可以用线性规划来解决，因为我们是在平面上工作，所以可以达到线性时间。

现在，讲义将更详细地解释 (2) 部分，这是步骤。

我理解除 (3) 和 (4) 之外的所有步骤。

(3)。什么是 b ？我想没关系。既然你已经找到斜坡 m然后继续寻找集合 P 的支撑线。B 是您正在寻找的东西。

(4)。集合P的支撑线是什么，如何高效找到它？

Answer 1

给定一个斜率和一个点，存在一条通过该点的斜率的唯一直线。设斜率为 m，点为 (px, py)。然后求解方程中的b py = m px + b(即b = py - m px)；这条线有等式 y = m x + b。您在步骤 (3) 和 (4) 中应该做的是为每个点计算 b 并将 p_t 设为具有最大 b 的点(通过最大 x 坐标打破平局)。这条线是凸包的支撑线，因为它包含一个顶点，并且所有顶点(不正确地)都在一侧(在本例中，不在它上面)。

_{附言如果您因为 O(n log h) 运行时间而感兴趣，那么请不要抱太大希望；常数因子看起来很糟糕。}