征服之前的婚姻執行問題凸包算法

我有興趣實施和學習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），這裏是步驟。

enter image description here

我明白除了每一個步驟（3）和（4）。

（3）。什麼是b？我想這沒關係。既然你已經找到了斜率m，然後繼續找到設置P的支撐線。B是你正在尋找的東西。

（4）。 P組的支持線以及如何有效地找到它？

來源

2014-10-04 jsguy

給定一個斜率和一個點，在該點存在一條具有該斜率的唯一線。讓斜率爲m，點爲（px，py）。然後求解方程中的b py = m px + b（即，b = py -m px）;該線具有方程y = m x + b。在步驟（3）和（4）中，你應該做的是計算每個點的b值，並將p_t作爲最大值b的點（通過最大x座標斷開連接）。這條線是凸包的一條支撐線，因爲它包含了一個頂點，並且在一側（在這種情況下，不在其上）有所有頂點（不正確）。

_{P.S.如果你因爲O（n log h）運行時間而感興趣，那麼請不要抱有希望;常數因素看起來很糟糕。}

來源

2014-10-05 00:44:51

征服之前的婚姻執行問題凸包算法

回答

相關問題