用於在多邊形輪廓中排序頂點的線性時間算法

Question

我想出了一種算法，如果我的頂點索引從最低座標排序到最高，我可以讓線性時間將我的有孔多邊形變成梯形。

我得到簡單的多邊形作爲輪廓。他們有一定的秩序，可能在大多數時間被利用。

因此，給出這些條件，是否存在近似線性時間的排序算法？

Answer 1

我想你想要的答案是「不」，但我也認爲你可能要更仔細地考慮你的問題。

問題是你使用的是連續座標，所以原則上你不能使用線性排序。 （實際上，您可以使用基數類型來處理固定大小的座標，但實際上這可能比標準的O（N log N）排序慢，這是由於所涉及的開銷...）

理論規則是：無論何時你只能比較你的值的情況下，一般排序不能比O（N log N）快。

您提到了一個未指定的屬性，「可能會被大部分時間利用」。問題是O（）符號是一個漸近的，最糟糕的理論屬性，所以「大部分時間」都不會有所作爲。輸入一個特定的屬性往往能以這種方式被利用，但是：

• 的O（）加速是你的財產是什麼
• 一個更好的O（算法非常敏感的）可能是多少較慢的爲您的實際應用
• 最有效的技術，切實利用你輸入的是往往是從技術與最好的漸進性質非常不同

不幸的是，調整你的算法利用你輸入的時候，很容易錯過了一個不起眼的最壞的ca這種情況會在您釋放後很長時間內以意想不到的方式殺死您的表現。關於算法的O（）最重要的事情就是阻止它像這樣糟糕地炸燬。

請注意，爲此目的，O（N log N）是近線性，並且使用標準的，行爲良好的庫分類可能是正確的選擇。

Answer 2

線性時間運行的排序算法是計數排序，基數排序和桶排序。

維基也是有幫助的： Sorting algorithms

Answer 3

我不知道你所說的「一定的順序」和「大部分時間」的意思。對於簡單的（即非凸的）普通多邊形，恐怕可能沒有解決方案，因爲點的座標可能是任意順序的（你可以有非常奇怪的「簡單」多邊形...）

當然，如果你正在處理凸多邊形，相對於y座標的線性時間分類將變得很簡單：只需找到最低點，並在左邊和右邊平行移動......

無論如何，除非你有非常大的多邊形，否則一個很好實現的算法可能會比某些線性時間算法快或甚至更快（例如，如果線性算法的常數因子大於日誌n ... ）

Answer 4

你的問題有點含糊，但假設如下：

1. 多邊形是2D
2. 你想沿着特定軸的頂點（x或y）排序
3. 的多邊形被定義爲連接輪廓

你可以做到以下幾點：

1. 一起走頂點
2. 對於第一個頂點將其添加到範圍
3. 對於每個頂點，如果頂點是「高於」以前把它添加到當前的範圍內，否則，創建一個新的範圍與頂點在它。
4. 我們現在有排序的區間的列表，相互合併範圍：http://en.wikipedia.org/wiki/Merge_algorithm