[問題] boost polygon library 效能

看板C_and_CPP作者yu1 (～renard～)時間11年前 (2012/12/23 13:38)推噓2(2推 0噓 5→)

留言7則, 4人參與討論串1/4 (看更多)

開發平台(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

12/23 16:32, , 1^F

12/23 16:32, 1^F

→

loveme00835

12/23 16:52, , 2^F

12/23 16:52, 2^F

→

loveme00835

12/23 16:53, , 3^F

12/23 16:53, 3^F