Boost geometry polygon inner representation as a STL list?

2
votes

As far as I know, boost polygon is represented as a STL vector. This is not convenient for when a new point needs to be added at a specific index of the polygon, as this is linear complexity.

Is there a way how to make boost use a list representation or otherwise solve the problem of adding a point to an index of the polygon in constant time?

1
c++boostboost-geometry
Are your polygons huge? If less than 1000 points I would ignore this vector problem, because list insert/erase typically requires memory (de)allocation, which is unbelievably slow. – Sven Nilsson
@SvenNilsson makes an excellent point, always profile your code – sehe

1 Answers

4
votes

The whole point of the Boost Geometry Design Rationale is to program to concepts, not models.

The default model of a polygon you describe indeed uses std::vector, but you can use any model - including your own types or third party types, given some adaption.

So, without further ado, use the builtin model with a list:

Live On Coliru

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <list>

int main() {
    using namespace boost::geometry;
    using Point = model::d2::point_xy<double>;
    model::polygon<Point, true, true, std::list> p;
}