※ 引述《j100002ben (波卡Poka)》之銘言： : 標題下的很爛，可是我真的不知道要下什麼標題會比較好... : 假設有一個矩形範圍（ex: 100cm*100cm）， : 裡面有非常多（ex:100000up）個隨機位置的圓形（ex:每個皆直徑10cm）， : 每一個圓形可能會和其他圓形相交/相割， : 目標要找出矩形範圍內，最多不重疊的圓形 : 除了暴力解之外，我想不太出來我知道的演算法能夠處理這個問題 : 因為感覺像是排列組合（附帶檢查兩圓是否重疊） : 一個矩形範圍不重複排滿頂多20-30個... : 然後100000個就要檢查100000 * 99999 * ... * (100000-30)次 : 有沒有比較快速處理這種問題的方法？ : 比較是否重疊應該可以直接當成O(1)時間， : Ram夠大可以把全部的狀態放進去... : 但是比較這麼多次也是很花時間的.. : 平行運算也有想過.... : 但是也要算法可以把資料切開來「平行」才行... 反過來想...用刪去法...先將所有點列入清單內 找矩形範圍內的任一點...找出其半徑範圍x2內的點 (包含切 + 重疊) 將這些點從清單內刪除...再找這些點的半徑範圍x2內的點 遞迴方式刪除掉大部分清單內重複的點 反覆執行直到每個點都執行過上述動作 就可以確定剩下的都是獨立的 因為清單內的點越來越少, 所以速度相對應該比較快吧 目前想到比較容易寫成程式的方式是這個 -- 只有現在能做到的事很多很多 不要忽略眼前 而一昧的考慮以後的事 如果總是那樣的話 到什麼時候也不會有所作為的 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 60.248.105.226 ※ 編輯: hichcock 來自: 60.248.105.226 (06/22 11:42)