2015-11-17 142 views
0

请注意我对解决问题最有效的方法感兴趣,并且不希望使用特定库的建议。如何将几何形状组合成一组重叠形状

我有大量(〜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数对象重叠比较(内部循环),但我仍然需要重复其余部分以合并组。

有什么更快吗?

谢谢!

回答

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