合并多边形的高效算法

我有一个多边形列表，在这个列表中，一些多边形重叠或触及其他多边形。合并多边形的高效算法

我的任务是合并彼此重叠或接触的所有多边形。我有一个union方法可以做到这一点。

什么是最有效的方法来做到这一点？我现在可以想到的是循环多边形列表，检查合并列表以查看该多边形是否已经属于已经合并列表中的一个多边形，如果是，将它们联合起来，如果不是，则添加该多边形到合并列表的末尾。

重复上述步骤几次，以确保所有多边形正确组合。

这种方法看起来很不雅观;有一个更好的方法吗？

来源

2010-08-02 Graviton

这里有一个想法：做一个扫描，以确定哪个多边形无论如何重叠，然后执行合并。

假设所有多边形都在输入列表中。

对于每个Polygon P_i构建一个覆盖P_i的多边形的OVERLAP。
从OVERLAP中获取Polygon P_i和任何仍存在的Polygon P_k，将它们合并，并将P_k的OVERLAP列表添加到P_i的重叠列表中。从输入列表和P_i的OVERLAP列表中删除P_k。
如果P_i的OVERLAP列表为空，则已找到P_i的传递联合。前进到输入列表中下一个剩余的多边形。

有好东西这种方法：

你只需要输入多边形（这是可能更小，更复杂，所产生的工会）的相交测试。
您可以使用空间索引来加速多边形相交检查，并且不必为合并的多边形更新它。
您可以确定哪些多边形将被合并而不实际执行联合。这意味着你可以计算出不同的合并组和手的名单在实际合并到一些专门的算法（如果有多边形合并的两组，那么您可以在并行做到这一点！）

下面是一些伪代码：

-- these are the input arrays 
var input:array[Polygon]; 
-- if Polygon #3 overlaps with #7 and #8 then overlaps[3] contains the list {7,8} 
var overlaps:array[list[integer]]; 

-- compute the overlaps 
for i=1..input.size 
    overlaps[i]=new list[integer]; 
    for k=i+1..input.size 
     if input[i] *overlaps* input[k] then 
      overlaps[i].append(k); 
     end if 
    end for 
end for 

var check:integer 

-- for all polys 
for i=1..input.size 
    -- if this poly is still in the input list (and not neutered with null) 
    if input[i] then 
     -- check all the polys that overlap with it 
     for k=1..overlaps[i].size 
      -- 'check' is a candidate 
      check=overlaps[i][k] 
      -- is this poly still in the input array? 
      if input[check] then 
       -- do the merge 
       input[i] = input[i] *union* input[check] 
       -- and delete this polygon from the input array 
       input[check]=null 
       -- and let input[i] inherits the overlapping polygons of check. 
       overlaps[i].append(overlaps[check]) 
      end if 
     end for 
    end if 
end for

后，“输入”应该只包含非重叠的多边形（或空以指示多边形已经被合并的地方）

来源

2010-08-02 10:50:14

这是什么意思**来自OVERLAP **的任何仍存在的Polygon P_k？是否有可能为此发布伪代码？ – Graviton 2010-08-02 11:17:36

cyclomatic_complexity> 10！ – 2010-08-02 11:42:14

我还没有把过多考虑到这一点，但看到如果这工作...

//let L be the list of all polygons, M be the list of all merged polygons 
//let head(L) be the first polygon in the list and tail(L) be the 
//remaining polygons other than the head polygon. 

let h = head(L) 
let t = tail(L) 

while(length(t) > 0) 
    foreach(polygon p in t) 
     if(p intersects h) 
      let h = p union h 
      t.remove(p) 
    M.append(h) 
    let h = head(t) 
    let t = tail(t)

来源

2010-08-02 10:50:46

你可以做预测试与包围盒/圈，如果它不是已经是工会法的一部分，但你简单的实现似乎罚款< 1000左右多边形，甚至10000取决于他们是多么复杂。有一种方法可以改进之后，就是将您的多边形存储在某种空间树中，如四元，kd，bsp或R树。请注意，将数据导入这些树中相对于它们的操作往往是昂贵的，因此在这种情况下，您将不得不在整个软件中使用它。

来源

2010-08-02 10:58:37

你能更明确吗？ – Graviton 2010-08-02 11:28:28

合并多边形的高效算法

回答

相关问题