Open jfirebaugh opened 8 years ago
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
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.
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.
@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.
Done in 3d55ece763c25a390b31142863b3e5dbab010fd2.
Here's an example of how this enables writing concise generic algorithms.
Here's an example of how this enables writing concise generic algorithms.
Ooooo. Nice @jfirebaugh! 🙌
@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?
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.
You can use a boost iterator_range
to model interior rings. Here's a proof of concept:
https://gist.github.com/jfirebaugh/c5e07939b6c4a5b975e20b966e371e3b
@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.
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.
@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.
@jfirebaugh The example compiles but :
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.
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
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(...); }
@jfirebaugh - https://gist.github.com/jfirebaugh/98e961c9be11990ac6aadea21bc1683e#file-boost3-cpp-L33 - unfortunately doesn't work, calling resize
might invalidate iterators.
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); }
};
mapbox::geometry::polygon<double> poly;
// .......
for (auto const& ring : poly)
{
std::cerr << ring.size() << std::endl;
}
/cc @springmeyer @jfirebaugh @mourner @flippmoke
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).
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
@flippmoke @springmeyer @jfirebaugh
mapnik-vector-tile/geometry-refactor
https://github.com/mapbox/mapnik-vector-tile/tree/geometry-refactor
polygon
currently has individualexterior_ring
andinterior_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.