Efficient Algorithms to Merge Polygons

Question

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?

Answer 1

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)

Answer 2

I haven't put much thought into this but see if this works...

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

Answer 3

You can do pre-tests with bounding boxes/circles if it's not already part of the union method, but your trivial implementation seems fine for < 1000 or so polys, maybe even 10000 depending on how complex they are. One way you could improve after that it is to store your polys in some sort of spatial tree, like a quad-, kd-, bsp, or an R-tree. Note that getting the data into these trees tends to be expensive relative to the operations on them, so you would have to use it throughout your software in that case.