[問題] boost polygon library

[yu1 (～renard～)]

開發平台(Platform): (Ex: VC++, GCC, Linux, ...) 
GCC, Linux

額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 
Boost polygon library
http://www.boost.org/doc/libs/1_52_0/libs/polygon/doc/index.htm


問題(Question)：

他的Boolean function 時間複雜度是 nlogn, n為polygon所有的點數

但是我的n大約是100萬時

卻跑了半小時...


餵入的資料(Input)：

20萬個polygon, 每個polygon大約5~8個點


預期的正確結果(Expected Output)：

一般nlogn的演算法,n=100萬,

在現在一般的機器跑 應該頂多1~2 min就算多了

但是卻跑了半小時

不知道有沒有人用過這個好像比較冷門的library,

有興趣的人也歡迎討論看看~



程式碼(Code)：(請善用置底文網頁, 記得排版) 

我簡單的用他的範例提供的方法:

各input 20萬個polgon

ps ^ ps2, 光這一行就跑了半小時... // ps是boost的polygon set的 DS



--
※ 發信站: 批踢踢實業坊(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:總之 他提供的是比較精確的計算 粗略的計算要先自己完成