Support for multiple dimensions

[artemp]

Currently only 2D planar geometries are considered. Having looked at geojson-vt-cpp made me realise that sooner or later we'll want to use extra dimensions. In GIS world while not proper 3D - concept of 2.5D is widely used. Even notorious ESRI shapefiles have support for it:).

What do people think ?

/cc @kkaefer @jfirebaugh @springmeyer @flippmoke @jakepruitt @mapsam @BergWerkGIS

[springmeyer]

Capturing voice @artemp this morning on this:

• I'm 👍 on providing a point 3d type as long as it is zero cost. It would be zero cost if it:
  • Does not impact compile times for usage of just the normal point (2d type)
  • Does not impact compiled binary size (won't, a non-issue since we'll stay header only).
• Once done the idea is geojson-vt-cpp would use it immediately

[jfirebaugh]

So, something like:

namespace mapbox { namespace geometry {

template <typename P, template <typename...> class Cont>
struct line_string : Cont<P> { ... };

namespace 2d {
   template <class T> struct point { ... };

   template <class T, template <typename...> class Cont = std::vector>
   using line_string = mapbox::geometry::line_string<point<T>, Cont>;
}

namespace 3d {
   template <class T> struct point { ... };

   template <class T, template <typename...> class Cont = std::vector>
   using line_string = mapbox::geometry::line_string<point<T>, Cont>;
}

}}

[artemp]

@jfirebaugh not quite, here is what I have in mind
(don't be afraid of some similarities to boost::geometry::model this is a LEGO approach )

• Pure data-structure based geometry framework

namespace geometry {

// Base pure data-structures, no methods
struct empty {};

template <typename T, int dim>
struct point {}; //

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

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

template <typename T>
struct point<T,4>
{
    using value_type = T;
    value_type x;
    value_type y;
    value_type z;
    value_type m;
    point() {}
    point(value_type x_, value_type y_, value_type z_, value_type m_)
        : x(x_), y(y_), z(z_), m(m_)  {}
};

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

// TODO: add remaining types
} // geometry

• Client code geometry definitions + interface

Library should provide reference definitions for the most common use case e.g : 2D/double
Plus basic interface see #7 for reasoning

namespace client {

// Define my geometry types add useful methods
struct point : geometry::point<double, 2>
{
    using base_type = geometry::point<double,2>;
    point() {}
    point(double x_, double y_)
        : base_type(x_, y_) {}
};

struct line_string : geometry::line_string<geometry::point<float, 3>>
{
    using point_type = geometry::point<float, 3>;
    void add_point(float x, float y, float z)
    {
        geometry::line_string<point_type>::emplace_back(x, y, z);
    }
    std::size_t num_points() const
    {
        return geometry::line_string<point_type>::size();
    }
};
using geometry = mapbox::util::variant<geometry::empty, 
                                       point, // 2D double
                                       line_string>; // 3D float
} // client definitions

• Use it

struct printer
{
    void operator()(client::point const& pt) const
    {
        std::cerr << "Point " << sizeof(pt) << std::endl;
        std::cerr << "x=" << pt.x << ", y=" << pt.y << std::endl;
    }
    void operator()(client::line_string const& line) const
    {
        std::cerr << "LineString " << sizeof(line) << std::endl;
        for (auto const& pt : line)
        {
            std::cerr << "x=" << pt.x << ", y=" << pt.y << " z=" << pt.z << std::endl;
        }
    }
    template <typename T>
    void operator() (T const& g) const
    {
        std::cerr << "Not implemented" << std::endl;
    }
};

int main()
{
    std::cerr << "Geometry base" << std::endl;

    std::vector<client::geometry> v;

    client::point pt(100,200); // 2D point double
    v.push_back(std::move(pt));

    client::line_string line; // 3D line float
    line.add_point(100, 200, 1.0);
    line.add_point(200, 100, 0.5);
    line.add_point(100, 100, 1.0);
    v.push_back(std::move(line));

    for (auto const& geom : v)
    {
        mapbox::util::apply_visitor(printer(), geom);
    }

    return 0;
}

The above addresses both support for multiple dimensions and keeping base geometry bare-bones data.
ref #7

It's also flexible to allow mixing value_types and dimensions which can be useful in some cases.
/cc @springmeyer @jfirebaugh @daniel-j-h @danpat @flippmoke @kkaefer

[jfirebaugh]

Hmm, I think we're getting ahead of ourselves. The goal was to create a set of simple, concrete types that could be shared across Mapbox projects. A solution that involves client namespaces and deep inheritance trees feels like we're getting into over-complicated "what if" territory.

It looks to me like geojson-vt-cpp uses a z coordinate not as a geometric coordinate but as an expedient place to stash some temporary data for the simplification algorithm. It could use a custom type which composes the geometry.hpp point and the third value (looks like it should be called tolerance or something like that).

[artemp]

This is not "what if" :) We're already using double,int,float,int64 geometries in a few places (cc/ @flippmoke ) and support for extra dimensions would be super useful in simplification, 2.5D (elevation) just to mention two. The main point with the above approach is that it's possible to instantiate concrete types using 2D points and double coordinates types which fits "simple, concrete types that could be shared across Mapbox projects" requirement.

The 'client' namespace is the way to split creation/accessor interface which is what #7 is about, no? It doesn't have to be 'client' and we can omit it from the first draft. But I think it can be useful, also it's optional (separate header).

/cc @jfirebaugh @springmeyer @flippmoke @mourner

[mourner]

It looks to me like geojson-vt-cpp uses a z coordinate not as a geometric coordinate but as an expedient place to stash some temporary data for the simplification algorithm. It could use a custom type which composes the geometry.hpp point and the third value (looks like it should be called tolerance or something like that).

The current Projected* classes that have the third coord are intended to be internal, but having this in geometry.hpp would certainly cut down on amount of boilerplate because I need to mirror GeoJSON feature representations that have that tolerance along with each coordinate.

[jfirebaugh]

Hmm. I'm still skeptical. I don't get the "point" of a client namespace and inheriting client::line_string from geometry::line_string (which itself inherits from the container type). How is this better than the simpler interface I proposed in #9 (comment)?

[artemp]

@jfirebaugh - I think I'm not explaining well. I'll try again :)

Everything in client namespace is for demonstration purposes and not necessarily part of the geometry.hpp. It shows how to add creating/mutating methods specific to the client code. Just replace client with mapnik for example. The main objects are pure data structures.

[jfirebaugh]

Ah, I understand now. In that case, I think the proposals are pretty much the same, except that I'm including predefined 2d and 3d namespaces (actually I guess they'd need to be d2 and d3) that contain an appropriate series of concrete, pure data structure definitions for point, line_string, ..., geometry types of that dimensionality. I think that's essential -- the core use case for this library.

[artemp]

@jfirebaugh - having separate d2/d3 namespaces will just duplicate code and make it less generic. Please, take a look again

namespace geometry {

template <typename T, int dim>
struct point {}; //

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

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

template <typename T>
struct point<T,4>
{
    using value_type = T;
    value_type x;
    value_type y;
    value_type z;
    value_type m;
    point() {}
    point(value_type x_, value_type y_, value_type z_, value_type m_)
        : x(x_), y(y_), z(z_), m(m_)  {}
};

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

// TODO: add remaining types
} // geometry

It solves nicely multi-dimensions without re-definitions^. Of course we can still have actual types instantiated in separate namespaces if needed.

[jfirebaugh]

@artemp I think we largely agree but are missing each other. Maybe some concrete code will help. Here's what I propose. This keeps existing line_string, multi_point, ..., geometry types effectively the same but typedefs them to more generic line_string_t, multi_point_t, ... geometry_t types that are templated on a Point type. This keeps the API the same for common 2d usage, but provides a way to use non-standard point types (3d points or points that carry auxiliary data) fairly easily:

struct MyPoint { double x; double y; uint64_t extra; };
using geometry = mapbox::geometry::geometry_t<MyPoint>;
using line_string = geometry::line_string_type;
using polygon = geometry::polygon_type;
using multi_point = geometry::multi_point_type;
using multi_line_string = geometry::multi_line_string_type;
using multi_polygon = geometry::multi_polygon_type;

cc @mourner