Re: [問題] boost polygon library 效能
※ 引述《yu1 (～renard～)》之銘言：
: 謝謝大家推文，我會嘗試分析看看時間和n的關係
: 更精確來說我的問題:
: 圖示: http://img100.imageshack.us/img100/5840/testys.png
: (抱歉想不到更好的了)
: 我有一堆polygon (由3~10個頂點組成)
: 且polygon之間不會相交
: 這一堆polygon (約20萬個)，簡稱 polygon set A，圖中的黑色
: 而這堆polygon去作一些處理後, 頂點座標會稍微移動
: 處理完的polygons，簡稱 polygone set B，圖中的紅色
: 我想要用boost polygon library 去得出 A和B的差異
: 所以就用 他library提供的function A ^ B (XOR)
: 時間複雜度應該是O(nlogn)，無intersection, n 約= 1~200萬
: 但是跑了半小時之久
: 如果我先將他們分開做 XOR會比較好嗎 (接下來還能Multi-thread)
: 但是分開又是另一種問題了，要如何確保不會將polygon 分屍...
看了你的問題以後發現如果能保證紅色範圍小於等於黑色範圍的話
根本不用用到boost polygon，感覺你的處理是細化處理，
如果你是從bitmap上抓到polygon的特徵的話，
直接把紅色的範圍減掉黑色的範圍就好，
如果得到的資料已經是polygon的外圍點集合，
可以直接把黑色當作外圍的contour，
紅色當作內圍的contour，
假設每一個黑色polygon一定大於包著紅色的polygon，
且黑色polygon之間不重疊，
紅色polygon之間不重疊，
在這一堆限制條件下，可以直接用黑色polygon 的 AABB，
找到包到的紅色polygon，
然後可以直接把黑色當作外圍的contour，
紅色當作內圍的contour。
大陸有翻譯一本real-time collision detection 的書
叫 实时碰撞检测算法技术
裡面有從2005年以前近十年的碰撞演算法發展
不過現實世界的問題可以從很多不同的觀點切入優化
就不知道適不適合你了。
--
標題 [趣事] 說服老媽進電影院看少年PI
→ milkfox:我的老虎哪有這麼可愛 老虎也要談戀愛 人X虎 11/28 10:18
→ milkfox:鄰座的怪老虎 元氣少年漂流虎 漂流床的寵物老虎 11/28 10:19
→ milkfox:少年與老虎漂流 絕園的人與虎 PSYCHO_TIGER TIGER_NOTES 11/28 10:22
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.118.175.32
討論串 (同標題文章)