algorithm - 如何将形状分组为多组重叠形状

Question

请注意我对解决问题的最有效方法感兴趣，而不是寻找使用特定库的建议。

我有大量(约 200,000 个)二维形状(矩形、多边形、圆形等)，我想将它们分类到重叠的组中。例如，在图片中，绿色和橙色将被标记为第 1 组，黑色、红色和蓝色将被标记为第 2 组。

Example

假设我将获得一个 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 的数量对象重叠比较(内循环)，但我仍然需要迭代其余部分以合并组。

有没有更快的？

谢谢!

Answer 1

希望这对某人有所帮助 - 这是我实际实现的(伪代码)。

tree = new spatial tree
for each shape in shapes
    set shape not in group 
    add shape to tree 

for each shape in shapes
    if shape in any group 
        skip shape

    cur_group = new group
    set shape in cur_group 

    regions = new stack
    insert bounds(shape) into regions

    while regions has items
        cur_bounds = pop(regions)

        for test_shape in find(tree, cur_bounds)
            if test_shape has group
                skip test_shape

            if overlaps(any in cur_group, test_shape)
                insert bounds(tester) into regions
                set test_shape group = cur_group