Boost Geometry: объединение нескольких полигонов C++

У меня есть массив из нескольких полигонов Boost.Geometry, и мне нужно объединить их в один полигон. Я успешно реализовал то, что объединяет каждый последующий многоугольник с объединением двух предыдущих (просто перебирая их и объединяя другой многоугольник).

multi_polygon polygons; // an array of initial polygons
multi_polygon border;   // the unioned polygons

for (polygon p : polygons) {
    // add another polygon each iteration
    multi_polygon tmp_poly;
    union_(border, p, tmp_poly);
    border = tmp_poly;
}

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


c++ boost boost-geometry
person k-a-v    schedule 12.02.2020    source источник
comment
Возможно, реализовать лучший алгоритм для объединения всех полигонов одновременно с разверткой линии. В противном случае попробуйте сгруппировать их в двоичное дерево (объединить 1 и 2, объединить 3 и 4, объединить результаты), это может быть немного быстрее.   -  person n. 1.8e9-where's-my-share m.    schedule 27.11.2020

Ответы (2)


arrow_upward
2
arrow_downward

Это не так эффективно, как предложенный ответ, но я получил значительное ускорение, сделав это таким образом, без необходимости создавать новый алгоритм с нуля.

multi_polygon polygons; // an array of initial polygons
multi_polygon border;   // the unioned polygons
multi_polygon tmp_poly; // a temporary variable

for (const polygon &p : polygons) {
    // add another polygon each iteration
    union_(border, p, tmp_poly);
    border = tmp_poly;
    boost::geometry::clear(tmp_poly);

}
person Sebastian C    schedule 20.07.2021

arrow_upward
1
arrow_downward

Нет, assign будет только слепо добавлять полигон к мультиполигону, не объединяя их.

В настоящее время в Boost.Geometry (1.73) нет алгоритма для слияния нескольких полигонов в действительный мультиполигон.

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

  • вычислить ограничивающие рамки всех полигонов (boost::geometry::envelope())
  • поместите их (ограничивающий прямоугольник + идентификатор полигона) в R-дерево (boost::geometry::index::rtree<>)
  • объединять только те, ограничивающие рамки которых пересекаются (bgi::rtree<>::query()), сохраняя текущую объединенную часть (с bg::union_()), отслеживая идентификаторы объединенных с ней полигонов (например, с некоторыми флагами bool, хранящимися вместе с полигонами в контейнере) и итеративно расширяя ограничивающую рамку текущая часть (bg::expand())
  • поместите все непересекающиеся (не объединяемые) части в один мультиполигон
person Adam Wulkiewicz    schedule 02.07.2020