來自兩組的最接近的一對點，每組一個

我有兩組點，A和B，並且我試圖找到最接近的一對點，其中從每組取一點。也就是說，如果你要使用兩點畫線，我想要兩點讓我畫兩條線之間的最短線段。來自兩組的最接近的一對點，每組一個

環顧四周，幾乎所有的事情似乎都是在尋找1組中最接近的點。雖然我確實找到了一個解決方案，推薦voronoi tesselation開始，這似乎有點像矯枉過正，但我只是在尋找比O（n^2）更好的東西。

如果有幫助，這兩套我比較表格行，雖然他們不一定是直的，我正在用C＃寫這篇文章。

謝謝。

2014-01-21 djcmm476

http://en.wikipedia.org/wiki/Closest_pair_of_points_problem –

但是，這隻適用於一組要點... – djcmm476

想想你的句子_「哪裏有一點從每個集合中拿走」_所以我們得到什麼？一套新的C（A1，B1）或我想念你嗎？ – WiiMaxx

應該可以通過處理所有的點並用額外的位標記它們來適應經典的D算法（如維基百科鏈接中所述）。

合併步驟需要修改，以便僅與每組中的成員接受候選左右對。這樣，遞歸函數將返回最接近的A-B對。 O（N.Log（N））行爲應該保留。

如果你提到的「線條」有一個已知方程，以便可以快速評估點/線距離（甚至線/線交點），那麼可能會有更快的解決方案。

2014-01-21 11:50:37

這很有道理。我不太清楚如何在C＃中標記它們，但不添加一些預算法工作，你有什麼建議嗎？ – djcmm476

對不起，我看不到你的觀點。你可以在你的點結構中添加一個布爾變量，或者維護一個單獨的布爾列表，並與點列表相對應。不涉及處理。 –

您能否詳細說明如何在N log N中執行此操作？如果A的所有點緊密聚集在（0,0）附近，並且B的所有點緊密聚集在（100,100）附近，我不知道該怎麼辦：我認爲如果是這種情況，那麼「劃分」將最終將來自集合A的所有點集合在一起，並集合在一起，因此合併不會很快。 – Irvan

回答