合并多边形的高效算法

Question

我有一个多边形列表，其中一些多边形重叠或与其他多边形接触。

我的任务是合并所有相互重叠或接触的多边形。我有一个名为“union”的方法可以实现这一点。

最有效的方法是什么？目前我能想到的是循环遍历多边形列表，检查是否已经属于合并列表中的某个多边形，如果是，则将它们合并；如果没有，则将此多边形添加到合并列表的末尾。

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

这种方法似乎非常不优雅，有没有更好的方法？

- Graviton

Answer 1

这里有一个想法：进行扫描以确定哪些多边形重叠，然后执行合并操作。

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

1. 对于每个多边形 P_i，构建一个 OVERLAP 多边形列表，其中包含与 P_i 重叠的多边形。

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

3. 如果 P_i 的 OVERLAP 列表为空，则已找到 P_i 的传递联合。继续前往输入列表中的下一个剩余多边形。

这种方法有很多好处：

1. 你只需要在输入的多边形上进行交集测试（这些多边形可能比结果联合体更小、更简单）。

2. 你可以使用空间索引来加速多边形交叉检查，并且你不必为合并后的多边形更新它。

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

以下是一些伪代码：

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

之后，“input”应该只包含不重叠的多边形（或者为null，表示某个地方已经合并了一个多边形）

- Nordic Mainframe

---

“any still existing Polygon P_k from OVERLAP” 是什么意思？能否提供这方面的伪代码？ - Graviton

Answer 2

如果它还不是联合方法的一部分，你可以使用边界框/圆进行预测试，但是对于小于1000个或者更多的多边形，甚至可能是10000个，你的简单实现似乎还不错。之后，你可以通过将多边形存储在某种空间树中（如四叉树、kd树、bsp树或R树）来进一步改进。请注意，将数据放入这些树中相对于对它们的操作来说往往是昂贵的，所以在这种情况下，你必须在整个软件中使用它。

- Simon Buchan

Answer 3

我没有仔细考虑过这个问题，但看看这是否可行...

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

- Sandeep Datta