高效的算法来合并多边形 [英] Efficient Algorithms to Merge Polygons

问题描述

我有一个多边形列表，在这个列表中，一些多边形重叠，或者触及其他多边形。

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

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

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

办法似乎很不雅;有没有更好的方法来做到这一点？

解决方案

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

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

1. 对于每个Polygon P_i构建一个覆盖P_i的Polygons OVERLAP。
   

2. 从OVERLAP中取一个Polygon P_i和任何仍存在的Polygon P_k，将它们合并并将P_k的OVERLAP列表添加到P_i的重叠列表中。从输入列表和P_i的OVERLAP列表中删除P_k。
   

3. 如果P_i的OVERLAP列表为空，则您已找到P_i的传递联合。进入输入列表中下一个剩余的Polygon。







1. 您只需要在输入多边形上进行相交测试（这可能会更小且不太复杂以至于产生的并集）。您可以使用空间索引来加速多边形相交检查，并且您不必为合并的多边形更新它。

li>


2. 您可以确定哪些多边形要合并而不实际进行联合。这意味着您可以计算不同合并组的列表，并将实际合并移交给某个专门的算法（如果有两组要合并的多边形，则可以并行执行此操作！）






以下是一些伪代码：



   - 这些是输入数组
 var input：array [Polygon]; 
  - 如果Polygon＃3与＃7和＃8重叠，则重叠[3]包含列表{7,8} 
 var overlaps：array [list [integer]]; 
 
  - 为i = 1..input.size 
计算重叠
 overlapps [i] = new list [integer]; 
 for k = i + 1..input.size 
 if input [i] * overlaps * input [k] then 
 overlaps [i] .append（k）; 
结束如果
结束为
结束为
 
 var check：整数
 
  - 所有复合
为i = 1..input.size 
  - 如果这个多边形仍然在输入列表中（并且没有用null结束）
如果输入[i]，那么
  - 检查所有重叠的多边形
 for k = 1..overlaps [i] .size 
  - 'check'is a candidate 
 check = overlaps [i] [k] 
  -  is这个聚仍然在输入数组？ 
如果输入[check]然后
  - 做合并
 input [i] = input [i] * union * input [check] 
  - 输入数组
 input [check] = null 
  - 并且让input [i]继承检查的重叠多边形。 
 overlapps [i] .append（重叠[检查]）
结束如果
结束为
结束如果
结束为
  

之后，'input'应该只包含非重叠的多边形（或者为null，表示多边形已经被合并到某处）




I have a list of polygons, inside this list, some of the polygons are overlapping, or touches other polygons.

My task is to merge all the polygons that are overlapped or touched with each other. I have a union method that does this.

What is the most efficient way to do this? What I can think of currently is to loop though the polygon list, check against the merged list to see whether this polygon is somehow belonging already to one of the polygons in the merged list, if yes, union them, if no, add this polygon to the end of the merged list.

Repeat the above steps again for a few times to make sure that all polygons are properly combined.

This approach seems very inelegant; is there a better way to do this?

解决方案

Here one idea: Do a scan to determine which Polygons overlap anyway and after that perform the merge.

Assuming all Polygons are in a input list.

1. For each Polygon P_i build a list OVERLAP of Polygons which overloap P_i.

2. Take a Polygon P_i and any still exisiting Polygon P_k from OVERLAP, union them and add the OVERLAP list of P_k to the overlap list of P_i. Remove P_k from the input list and P_i's OVERLAP list.

3. If the OVERLAP list for P_i is empty, you have found the transitive union of P_i. Advance to the next remaining Polygon in the input list.

There are nice things with this approach:

1. You need the intersection tests only on the input polygons (which are potentially smaller and less complex that the resulting union).

2. You can use a spatial index to speed up polygon intersection checks and you don't have to update it for the merged polygons.

3. You can determine which polygons are to be merged without actually doing the union. This means you can compute the list of distinct merge groups and hand over the actual merge to some specialized algorithm (If there are two groups of polygons to merge, then you can do this in parallel!)

Here's some Pseudocode:

-- 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

after that, 'input' should contain only non-overlapping polygons (or null to indicate that a polygon has been merged somewhere)

这篇关于高效的算法来合并多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！