我怎樣才能在一個列表

我有X點的名單中刪除太近點，y座標：我怎樣才能在一個列表

List_coord=[(462, 435), (491, 953), (617, 285),(657, 378)]

此列表lenght（這裏是4元），可以從幾百個非常大的可達35000元素。

我想在此列表中刪除太靠近閾值的點。注意：積分不會處於完全相同的位置。

我對於當前的代碼：

while iteration<5: 
    for pt in List_coord: 
    for PT in List_coord: 
     if (abs(pt[0]-PT[0])+abs(pt[1]-PT[1]))!=0 and abs(pt[0]-PT[0])<threshold and abs(pt[1]-PT[1])<threshold: 
     List_coord.remove(PT) 
    iteration=iteration+1

我可怕的代碼:)解說：

我檢查非常距離爲0，那麼就意味着我感到比較相同點
然後我檢查x和y的距離..
迭代：我需要很少的迭代來避免丟失一個刪除因爲循環內部的列表本身發生變化...

此代碼正在工作，但它是一個非常低的過程！

我相信還有另一種方法更容易，但我沒能找到，即使一些媒體鏈接回答問題，是貼近我..

注：我想避免使用額外的庫代碼如果有可能

來源

2017-09-26 bastoon

如果您先將列表排序（以第一個座標爲關鍵字），該怎麼辦？那麼你只需要比較那些第一個座標在你的閾值內的元素。 –

我需要比較兩個座標，因爲有些點可以有相同的x或非常接近的x，但不一樣的y .. – bastoon

是的，當然。但是在一個排序列表中，你只需要比較很少的元素（而不是像現在這樣做的整個列表）。 –

的Python會在這個;-)

你可能會想被稱爲四樹該解決方案有點慢，但我會先提一個簡單的方法，在情況下，它優選的。

通常的方法是對點進行分組，以便您可以輕鬆地拒絕明顯彼此遠離的點。

一種方法可能是將列表排序兩次，一次一次x。你可以證明，如果兩點太靠近，它們必須靠近一個維度或另一個維度。因此，你的內在循環可能會提前爆發。如果它看到的點與分選方向上的外點相距太遠，則可以知道該列表中的所有未來點都離得太遠。因此它不必再看。在X和Y中執行此操作，然後設置！

這種方法將傾向於由O（n log n）排序時間支配。但是，如果所有點都共享一個x值，那麼您將最終執行與您現在正在執行的O（n^2）相同的緩慢迭代操作，因爲您不會提前終止內部循環。

更可靠的解決方案是使用quadtrees。 Quadtrees旨在解決您正在查看的問題。這個想法是建立一個樹，以便您可以快速排除大量的點。我會推薦這個。

如果你的點數太多，我建議你得到一個聚類庫。有效的聚類是一項非常困難的任務，通常以C++或其他快速語言完成。

來源

2017-09-26 16:47:28

我怎樣才能在一個列表

回答

相關問題