请注意我对解决问题最有效的方法感兴趣,并且不希望使用特定库的建议。如何将几何形状组合成一组重叠形状
我有大量(〜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
数对象重叠比较(内部循环),但我仍然需要重复其余部分以合并组。
有什么更快吗?
谢谢!