飛機上的最大共線點數

N點數作爲輸入。飛機上的最大共線點數

比方說(x1,y1), (x2,y2)... (xn,yn)。

是否有一個非組合的解決方案來找到最大共線點數？他們可以安排在一個奇特的數據結構，這將有助於這種計算？

2010-12-08 Rohan Monga

看看這個問題及其答案：http://stackoverflow.com/questions/4179581/what-is-the-most-efficient-algorithm-to-找到一條直線即通過模 – brainjam 2010-12-08 16:38:22

對於每個點i，找到到其他每個點j的斜率，並查找重複值。通過對斜率進行排序可以找到重複項，並且可以通過比較相鄰值來找到重複項。點i與中的每個重複項的點共線。隨時跟蹤最大集。

對於每個我，你有n-1個斜率來計算和分類和比較。因此，使用（n log n）排序，算法的複雜度爲O（n^2 log n）。

來源

2010-12-08 11:06:41

成對的點可能有相同的斜率，但是平行而不是共線。您需要查看y截距以及斜率。 – 2010-12-08 14:48:44

通讀討論這個問題here上

來源

2010-12-08 11:07:44

下面可能是解決這個問題的一種方法： 1）找出所有的斜坡選擇C（N，2）對 2）斌這些斜坡成多個水桶。 3）這些桶在找到獨立的行（因爲它們可能含有家族的平行線） 4）建立的最長線段

更具體： 1）執行（N-1）*（N-1）的計算找到這麼多的斜坡。可以使用地圖以斜坡作爲關鍵點來保存這些點。地圖中的值可以使用Set來表示。 Set可以包含一個代表兩個點的對象。是這樣的： {SLOPE1：[（P1，P2），（P1，P3），（P1，P2），（P4，P5）]} { SLOPE2：....}

2）現在在每組點中找到獨立的線。我相信在我們可以達到的每一點上迭代。例如，當訪問（p1，p2），（p1，p3），（p1，p2），（p4，p5）時，我們可以將它分成形成共線點的n個集合，例如。設置可以從： [p1，p2]開始，當我們遇到下一對（p1，p3）時，我們檢查它們中的任何一個是否已經在當前運行集合中。如果其中至少有一個是我們添加新的點到這個集合，否則創建一個新的集合。遍歷這組點中的所有點後，我們將有以下兩組，代表2個獨立的線段： [p1，p2，p3] [p4，p5] 這些的大小現在可用於建立我們找到最長的線段

複雜性明智，它應該是O（（n-1）*（n-1）+ n）〜O（n^2）。假設在Set中查找對象是O（1）

來源

2017-10-25 18:15:20 shintu

飛機上的最大共線點數

回答

相關問題