make polygon a vector of rings

[jfirebaugh]

polygon currently has individual exterior_ring and interior_rings members.

It would be easier to work with in certain cases (notably GeoJSON serialization/deserialization) if it instead inherited from std::vector<linear_ring<T>>, where the exterior ring was element 0 and interior rings followed.

[artemp]

Having clear distinction between exterior ring and interior rings makes it easier to work when OGC geometry model is expected - WKT, WKB(postgis), boost::geometry.

Explicit is better in this case. We used to have where the exterior ring was element 0 and interior rings followed in mapnik and it was causing more issue then solving.
/cc @springmeyer @flippmoke

[jfirebaugh]

The further I get with integrating geometry.hpp and exploring how we'd write algorithms, the more I'm convinced that polygon should be a simple vector of rings. Uniformity and harmony with the other geometry.hpp types and with GeoJSON is more important than conformance with OGC in this case.

Unless there are vehement objections, I'm going to pull 6b52596ec0efd0c5b6530782a79175428bce01f2 into the next release.

[springmeyer]

Good to know your experience here @jfirebaugh. I've found this design without limitations myself, but I'm open to considering the merits of this. However I do cringe as it would require large updates to mapnik-vector-tile if we adapted to the latest geometry (https://github.com/mapbox/mapnik-vector-tile/search?utf8=%E2%9C%93&q=interior_rings) and the distinction has felt very useful.

[jfirebaugh]

@springmeyer: from what I can see it will make mapnik code much shorter and simpler too. Every place that the same algorithm is repeated for exterior_ring and then interior_rings becomes a simple single loop. Here, here, here, here, here, here. In fact I found only a single place where exterior and interior rings were treated differently. All other uses will benefit from keeping all rings in a single vector.

[jfirebaugh]

Done in 3d55ece.

Here's an example of how this enables writing concise generic algorithms.

[springmeyer]

Here's an example of how this enables writing concise generic algorithms.

Ooooo. Nice @jfirebaugh! 🙌

[springmeyer]

@jfirebaugh - one thought: In Mapnik, for best performance with polygons with lots of holes, we only use the exterior ring to determine the envelope: https://github.com/mapnik/mapnik/blob/d97583b53e134ca916aebbf9abbc4e8a5851d41f/include/mapnik/geometry_envelope_impl.hpp#L80-L95. How about specializing on multipolygon to avoid those extra loops?

[flippmoke]

After thinking about this for some time I am not convinced this is the best decision. @artemp is right in that it is very hard to adapt this to something like boost. For example look at the code where I am trying to adapt boost geometry to geometry.hpp:

template <typename CoordinateType>
struct exterior_ring<mapbox::geometry::polygon<CoordinateType> >
{
    static mapbox::geometry::linear_ring<CoordinateType> & get(mapbox::geometry::polygon<CoordinateType> & p)
    {
        return p.exterior_ring;
    }

    static mapbox::geometry::linear_ring<CoordinateType> const& get(mapbox::geometry::polygon<CoordinateType> const& p)
    {
        return p.exterior_ring;
    }
};

template <typename CoordinateType>
struct interior_rings<mapbox::geometry::polygon<CoordinateType> >
{
    using holes_type = typename mapbox::geometry::polygon<CoordinateType>::rings_container;
    static holes_type&  get(mapbox::geometry::polygon<CoordinateType> & p)
    {
        return p.interior_rings;
    }

    static holes_type const& get(mapbox::geometry::polygon<CoordinateType> const& p)
    {
        return p.interior_rings;
    }
};

The problems here is that I am not able to provide easily a reference of a std::vector that is a portion of a std::vector for interior rings and what am I supposed to do if there is no first ring in the vector or linear rings? Again, this is passed as a reference, so even if I made a temporary empty linear ring it would go out of scope.

[jfirebaugh]

You can use a boost iterator_range to model interior rings. Here's a proof of concept:

https://gist.github.com/jfirebaugh/c5e07939b6c4a5b975e20b966e371e3b

[artemp]

@jfirebaugh - iterator_range doesn't cut it unfortunately. Mutating algorithms e.g clipping needs to be able to resize/reserve internally

boost::geometry::intersection(bbox, polygon, result);

error: no member named 'resize' in 'boost::iterator_range<std::__1::__wrap_iter<mapbox::geometry::linear_ring<double, std::vector> *> >'
                interior_rings(destination).resize(

FYI, https://gist.github.com/jfirebaugh/c5e07939b6c4a5b975e20b966e371e3b - calling is_valid on empty polygon throws `out-of-range' exception which is wrong too.

[mourner]

It seems that this will be inconvenient either way, especially when trying to work with boost geometry, but I'm still in favour of vector of rings — doing otherwise will make a lot of geojson-vt-cpp/geojson-cpp code much more verbose and complicated.

[jfirebaugh]

@artemp This example compiles for me with Boost 1.61.0. In any case, these are proofs of concept -- whether or not it works for all boost geometry algorithms without additional wrappers or trait definitions, I think it's clear that the current definition of polygon does not preclude the use of boost, despite the fact that one of the reasons we started geometry.hpp was explicitly to avoid using boost geometry!

There is zero doubt in my mind that the current design of polygon is the correct one, and I suspect that once you start to write or rewrite algorithms using it, you will come to appreciate the advantages of a uniform container structure for line strings, polygons, rings, and multi-geometries.

[artemp]

@jfirebaugh The example compiles but :

• If you change mapbox::geometry::polygon<double> result; to be

container<mapbox::geometry::polygon<double>> result;

which is what you'd expect as result from intersection, it fails to compile.

• There's also subtle issue with boost::geometry::polygon concepts expecting exterior_ring to be initialised e.g return p.at(0); <-- with current vector of rings polygon this statement throws.

/cc @springmeyer @jfirebaugh @flippmoke @mourner

[jfirebaugh]

I opened a ticket regarding the resize issue. My guess is it is an undocumented requirement and we will need add resize to the wrapper type. Here's an example that does compile.

Regarding at(0), I think this should be handled by making validity checks where necessary prior to calling boost algorithms. This can be a simple if (polygon.empty() || !boost::geometry::is_valid(polygon)) { throw std::runtime_error(...); }

[artemp]

@jfirebaugh - https://gist.github.com/jfirebaugh/98e961c9be11990ac6aadea21bc1683e#file-boost3-cpp-L33 - unfortunately doesn't work, calling resize might invalidate iterators.

[artemp]

It would be easier to work with in certain cases (notably GeoJSON serialization/deserialization) if it instead inherited from std::vector<linear_ring>, where the exterior ring was element 0 and interior rings followed.

The desired interface is easily achieved by implementing "rings iterator" e.g

namespace mapbox { namespace geometry {

template <typename T>
struct point
{
    using coordinate_type = T;
    point()
        : x(), y()
    {}
    point(T x_, T y_)
        : x(x_), y(y_)
    {}
    T x;
    T y;
};

template <typename T>
bool operator==(point<T> const& lhs, point<T> const& rhs)
{
    return lhs.x == rhs.x && lhs.y == rhs.y;
}

template <typename T>
bool operator!=(point<T> const& lhs, point<T> const& rhs)
{
    return lhs.x != rhs.x || lhs.y != rhs.y;
}

template <typename T, template <typename...> class Cont = std::vector>
struct linear_ring : Cont<point<T>>
{
    using coordinate_type = T;
    using point_type = point<T>;
    using container_type = Cont<point_type>;
    using container_type::container_type;
};

template <typename T, template <typename...> class Cont = std::vector>
struct polygon
{
    using coordinate_type = T;
    using linear_ring_type = linear_ring<T>;
    using container_type = Cont<linear_ring_type>;
    linear_ring_type exterior_ring;
    container_type interior_rings;

    class rings_iterator : public boost::iterator_facade<rings_iterator,
                                                         linear_ring_type const,
                                                         boost::forward_traversal_tag>
    {
    public:
        using value_type = linear_ring_type;
        rings_iterator(std::size_t end)
            : poly_(nullptr), pos_(end) {}
        rings_iterator(polygon const& poly)
            : poly_(&poly), pos_(0) {}
    private:
        friend class boost::iterator_core_access;
        void increment() { ++pos_;}
        void decrement() {} // no-op
        void advance(typename boost::iterator_difference<rings_iterator>::type) {} // no-op
        bool equal( rings_iterator const& other) const
        {
            return (pos_ == other.pos_);
        }
        value_type const& dereference() const
        {
            if (pos_ == 0) return poly_->exterior_ring;
            else return poly_->interior_rings.at(pos_ - 1);
        }
        polygon const* poly_;
        std::size_t pos_;
    };

    rings_iterator begin() { return rings_iterator(*this); }
    rings_iterator end() { return rings_iterator(interior_rings.size() + 1); }
}; 

Usage

 mapbox::geometry::polygon<double> poly;
 // .......
for (auto const& ring : poly)
{
    std::cerr << ring.size() << std::endl;
}

/cc @springmeyer @jfirebaugh @mourner @flippmoke

[jfirebaugh]

calling resize might invalidate iterators

True. I think this goes back to the boost issue I filed. If resize is a requirement on the result of interior_rings(), boost needs to define its invalidation semantics, or guarantee that after resize (or any other operation which might invalidate the range) interior_rings() is always called again to obtain a fresh range (as appears to in fact be the case).

[artemp]

https://github.com/mapnik/mapnik/blob/geometry-refactor/include/mapnik/geometry/polygon.hpp
^ this is what I had to implement in order to adapt to boost.geometry properly. As I mentioned above, using iterator range doesn't fulfil requirements for mutating algorithm. I'll need to investigate implications for mapnik in terms of memory usage and performance before deciding about merging into mapnik/master. On the brighter side - all tests are passing in mapnik now.

I have to say, I'm still totally unconvinced that not having explicit exterior ring in Polygon is a good model - on the contrary, while it makes mapping into GeoJSON easier it doesn't fit well into geometry concepts on the whole (beyond a simple data format). I'm worried that this might become a rather short-sighted solution, but hey, you've been warned :)

/cc @springmeyer @jfirebaugh @flippmoke

[artemp]

@flippmoke @springmeyer @jfirebaugh
mapnik-vector-tile/geometry-refactor https://github.com/mapbox/mapnik-vector-tile/tree/geometry-refactor