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

Question

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

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

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

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

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

Answer 1

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

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

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

2. Возьмите многоугольник 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 

после этого, «вход» должен содержать только непересекающиеся многоугольники (или нуль, чтобы указать, что полигон был объединен где-то)

Answer 2

Я не положить много думал в это, но видеть если это работает ...

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

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