Эффективные алгоритмы слияния полигонов

Question

У меня есть список полигонов, внутри этого списка некоторые из полигонов перекрываются или касаются других полигонов.

Моя задача - объединить все полигоны, которые перекрываются или соприкасаются друг с другом.У меня есть метод union, который делает это.

Какой самый эффективный способ сделать это?В настоящее время я могу думать о том, чтобы зациклить список многоугольников, проверить по объединенному списку, чтобы увидеть, принадлежит ли этот многоугольник как-то уже к одному из многоугольников в объединенном списке, если да, объединить их, если нет, добавить этот многоугольникдо конца объединенного списка.

Повторите вышеупомянутые шаги снова несколько раз, чтобы убедиться, что все полигоны правильно объединены.

Этот подход кажется очень не элегантным;Есть ли лучший способ сделать это?

Answer 1

Вы можете выполнить предварительные тесты с ограничивающими прямоугольниками / кружками, если он еще не является частью метода объединения, но ваша тривиальная реализация кажется подходящей для <1000 или около того polys, может быть, даже 10000 в зависимости от того, насколько они сложны.Один из способов, который вы могли бы улучшить после этого, - это хранить ваши polys в каком-то пространственном дереве, например, quad-, kd-, bsp или R-дереве.Обратите внимание, что получение данных в эти деревья обычно обходится дороже, чем операции с ними, поэтому в этом случае вам придется использовать их в своем программном обеспечении. </p>

Answer 2

Вот одна идея: выполнить сканирование, чтобы определить, какие полигоны перекрываются в любом случае, и после этого выполнить объединение.

Предполагая, что все полигоны находятся в списке ввода.

1. Для каждого полигона P_i создайте список OVERLAP полигонов, которые перекрывают P_i.

2. Возьмите Polygon P_i и любой еще существующий Polygon P_k из OVERLAP, объедините их и добавьте список OVERLAP P_k вПерекрывающийся список P_i.Удалите P_k из списка ввода и списка OVERLAP P_i.

3. Если список OVERLAP для P_i пуст, вы нашли транзитивное объединение 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' должен содержать только непересекающиеся многоугольники (или нуль, чтобы указать, что многоугольник был где-то объединен)

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)