CODEWITHSUNDEEP
c++boostboost-geometry
k-a-v
k-a-v

Reputation: 347

Boost Geometry: Union multiple polygons C++

I have an array of several Boost.Geometry polygons, and I need to union them into a single polygon. I have successfully implemented something that merges each successive polygon with the union of the previous two (just looping through them and unioning another polygon). 

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

However, this takes quite a long time to execute. I heard mention in a video that the assign function could be used for this, but it was not detailed how, and I couldn't find anything else about this. How can I speed up this process?

Upvotes: 2

Views: 4405

Answers (2)

scastro
scastro

Reputation: 31

This is not as efficient as the proposed answer, but I got some significant speedups from doing it this way without having to create a new algorithm from scratch.

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

}

Upvotes: 2

Adam Wulkiewicz
Adam Wulkiewicz

Reputation: 2098

No, assign would only blindly add a polygon to a multi-polygon without merging them.

Currently in Boost.Geometry (1.73) there is no algorithm for merging multiple polygons into a valid multi-polygon.

You could however speed up your algorithm. It makes sense only to merge polygons that are intersecting. Everything else that is not intersecting could simply be added to the resulting multi-polygon. So you could:

  • calculate bounding boxes of all polygons (boost::geometry::envelope())
  • put them (bounding box + id of a polygon) in the R-tree (boost::geometry::index::rtree<>)
  • merge only those which bounding boxes intersect (bgi::rtree<>::query()), keeping the currently merged part (with bg::union_()), tracking ids of polygons merged with it (e.g. with some bool flags stored together with polygons in a container) and iteratively expanding the bounding box of a current part (bg::expand())
  • put all of the non-intersecting (non-mergeable) parts in a single multi-polygon

Upvotes: 3

Related Questions