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 分屍...


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.169.108.13
→ akasan:作 profiling 阿
→ loveme00835:最差時間複雜度是 N^2 , N=vertices + intersections
→ loveme00835:有用過較小的例子去估時間嗎?
推 bxxl:變化不同的n去看time v.s. n的曲線.
推 damody:它的方法很快了，應該不能再快了
→ damody:如果你的polygon那麼多應該要先做aabb優化才是
→ damody:總之 他提供的是比較精確的計算 粗略的計算要先自己完成

--

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 60.251.195.136
推 DJWS:會不會是因為你的polygon在xor之後產生洞？