Re: [問題] boost polygon library 效能
Hi all:
抱歉沒有定義清楚問題
紅色部份未必會比黑色的小
而且很不幸的他們會重疊 (但相同色的不會重疊)
所以現在問題縮小到: http://img525.imageshack.us/img525/1315/test2qs.png
如何將這些polygon分群
(1) 紅、黑的polygon數目可能不同 (ex:一個紅色的可能是兩個以上的polygon組成)
(2) 黑紅相疊的polygon至少要分在同群 (才能確保有XOR到)
有好的演算法可以作到這種分群嗎? (同群內的polygon越近越好，boost XOR 限制)
因為AABB algo還沒熟悉，會先study一下
謝謝!
※ 引述《damody (天亮damody)》之銘言：
: ※ 引述《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年以前近十年的碰撞演算法發展
: 不過現實世界的問題可以從很多不同的觀點切入優化
: 就不知道適不適合你了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.169.108.13
推
12/25 03:28, , 1F
12/25 03:28, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 4 篇)：