請注意我對解決問題最有效的方法感興趣,並且不希望使用特定庫的建議。如何將幾何形狀組合成一組重疊形狀
我有大量(〜200,000)的二維形狀(矩形,多邊形,圓形等),我想排序成重疊組。例如,在畫面中,綠色和橙色將被標記爲1組,黑色,紅色和藍色將被標記爲組2
比方說,我會給出一個list<Shape>
。緩慢的解決辦法是:
(我沒有運行此代碼 - 只是舉個例子算法)
// Everything initialized with groupid = 0
int groupid = 1;
for (int i = 0; i < shapes.size(); ++i)
{
if (shapes[i].groupid)
{
// The shape hasn't been assigned a group yet
// so assign it now
shapes[i].groupid = groupid;
++groupid;
}
// As we compare shapes, we may find that a shape overlaps with something
// that was already assigned a group. This keeps track of groups that
// should be merged.
set<int> mergingGroups = set<int>();
// Compare to all other shapes
for (int j = i + 1; j < shapes.size(); ++j)
{
// If this is one of the groups that we are merging, then
// we don't need to check overlap, just merge them
if (shapes[j].groupid && mergingGroups.contains(shapes[j].groupid))
{
shapes[j].groupid = shapes[i].groupid;
}
// Otherwise, if they overlap, then mark them as the same group
else if (shapes[i].overlaps(shapes[j]))
{
if (shapes[j].groupid >= 0)
{
// Already have a group assigned
mergingGroups.insert(shapes[j].groupid;
}
// Mark them as part of the same group
shapes[j].groupid = shapes[i].groupid
}
}
}
更快的解決辦法是把對象變成一個空間樹,以減少j
數對象重疊比較(內部循環),但我仍然需要重複其餘部分以合併組。
有什麼更快嗎?
謝謝!