12 files changed, 515 insertions, 0 deletions
diff --git a/include/mapbox/geometry/box.hpp b/include/mapbox/geometry/box.hpp
new file mode 100644
index 0000000..bf81b70
--- /dev/null
+++ b/include/mapbox/geometry/box.hpp
@@ -0,0 +1,34 @@
+#pragma once
+
+#include <mapbox/geometry/point.hpp>
+
+namespace mapbox {
+namespace geometry {
+
+template <typename T>
+struct box
+{
+    using point_type = point<T>;
+
+    constexpr box(point_type const& min_, point_type const& max_)
+        : min(min_), max(max_)
+    {}
+
+    point_type min;
+    point_type max;
+};
+
+template <typename T>
+constexpr bool operator==(box<T> const& lhs, box<T> const& rhs)
+{
+    return lhs.min == rhs.min && lhs.max == rhs.max;
+}
+
+template <typename T>
+constexpr bool operator!=(box<T> const& lhs, box<T> const& rhs)
+{
+    return lhs.min != rhs.min || lhs.max != rhs.max;
+}
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/envelope.hpp b/include/mapbox/geometry/envelope.hpp
new file mode 100644
index 0000000..8603583
--- /dev/null
+++ b/include/mapbox/geometry/envelope.hpp
@@ -0,0 +1,33 @@
+#pragma once
+
+#include <mapbox/geometry/box.hpp>
+#include <mapbox/geometry/for_each_point.hpp>
+
+#include <limits>
+
+namespace mapbox {
+namespace geometry {
+
+template <typename G, typename T = typename G::coordinate_type>
+box<T> envelope(G const& geometry)
+{
+    using limits = std::numeric_limits<T>;
+
+    T min_t = limits::has_infinity ? -limits::infinity() : limits::min();
+    T max_t = limits::has_infinity ?  limits::infinity() : limits::max();
+
+    point<T> min(max_t, max_t);
+    point<T> max(min_t, min_t);
+
+    for_each_point(geometry, [&] (point<T> const& point) {
+        if (min.x > point.x) min.x = point.x;
+        if (min.y > point.y) min.y = point.y;
+        if (max.x < point.x) max.x = point.x;
+        if (max.y < point.y) max.y = point.y;
+    });
+
+    return box<T>(min, max);
+}
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/feature.hpp b/include/mapbox/geometry/feature.hpp
new file mode 100644
index 0000000..3bdd484
--- /dev/null
+++ b/include/mapbox/geometry/feature.hpp
@@ -0,0 +1,81 @@
+#pragma once
+
+#include <mapbox/geometry/geometry.hpp>
+
+#include <mapbox/variant.hpp>
+
+#include <cstdint>
+#include <string>
+#include <vector>
+#include <unordered_map>
+#include <experimental/optional>
+
+namespace mapbox {
+namespace geometry {
+
+struct value;
+
+struct null_value_t
+{
+    constexpr null_value_t() {}
+    constexpr null_value_t(std::nullptr_t) {}
+};
+
+constexpr bool operator==(const null_value_t&, const null_value_t&) { return true; }
+constexpr bool operator!=(const null_value_t&, const null_value_t&) { return false; }
+
+constexpr null_value_t null_value = null_value_t();
+
+// Multiple numeric types (uint64_t, int64_t, double) are present in order to support
+// the widest possible range of JSON numbers, which do not have a maximum range.
+// Implementations that produce `value`s should use that order for type preference,
+// using uint64_t for positive integers, int64_t for negative integers, and double
+// for non-integers and integers outside the range of 64 bits.
+using value_base = mapbox::util::variant<null_value_t, bool, uint64_t, int64_t, double, std::string,
+                                         mapbox::util::recursive_wrapper<std::vector<value>>,
+                                         mapbox::util::recursive_wrapper<std::unordered_map<std::string, value>>>;
+
+struct value : value_base
+{
+    using value_base::value_base;
+};
+
+using property_map = std::unordered_map<std::string, value>;
+
+// The same considerations and requirement for numeric types apply as for `value_base`.
+using identifier = mapbox::util::variant<uint64_t, int64_t, double, std::string>;
+
+template <class T>
+struct feature
+{
+    using coordinate_type = T;
+    using geometry_type = mapbox::geometry::geometry<T>; // Fully qualified to avoid GCC -fpermissive error.
+
+    geometry_type geometry;
+    property_map properties {};
+    std::experimental::optional<identifier> id {};
+};
+
+template <class T>
+constexpr bool operator==(feature<T> const& lhs, feature<T> const& rhs)
+{
+    return lhs.id == rhs.id && lhs.geometry == rhs.geometry && lhs.properties == rhs.properties;
+}
+
+template <class T>
+constexpr bool operator!=(feature<T> const& lhs, feature<T> const& rhs)
+{
+    return !(lhs == rhs);
+}
+
+template <class T, template <typename...> class Cont = std::vector>
+struct feature_collection : Cont<feature<T>>
+{
+    using coordinate_type = T;
+    using feature_type = feature<T>;
+    using container_type = Cont<feature_type>;
+    using container_type::container_type;
+};
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/for_each_point.hpp b/include/mapbox/geometry/for_each_point.hpp
new file mode 100644
index 0000000..44d6e77
--- /dev/null
+++ b/include/mapbox/geometry/for_each_point.hpp
@@ -0,0 +1,45 @@
+#pragma once
+
+#include <mapbox/geometry/geometry.hpp>
+
+namespace mapbox {
+namespace geometry {
+
+template <typename Point, typename F>
+auto for_each_point(Point&& point, F&& f)
+    -> decltype(point.x, point.y, void())
+{
+    f(std::forward<Point>(point));
+}
+
+template <typename Container, typename F>
+auto for_each_point(Container&& container, F&& f)
+    -> decltype(container.begin(), container.end(), void());
+
+template <typename...Types, typename F>
+void for_each_point(mapbox::util::variant<Types...> const& geom, F&& f)
+{
+    mapbox::util::variant<Types...>::visit(geom, [&] (auto const& g) {
+        for_each_point(g, f);
+    });
+}
+
+template <typename...Types, typename F>
+void for_each_point(mapbox::util::variant<Types...> & geom, F&& f)
+{
+    mapbox::util::variant<Types...>::visit(geom, [&] (auto & g) {
+        for_each_point(g, f);
+    });
+}
+
+template <typename Container, typename F>
+auto for_each_point(Container&& container, F&& f)
+    -> decltype(container.begin(), container.end(), void())
+{
+    for (auto& e: container) {
+        for_each_point(e, f);
+    }
+}
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/geometry.hpp b/include/mapbox/geometry/geometry.hpp
new file mode 100644
index 0000000..a3970bf
--- /dev/null
+++ b/include/mapbox/geometry/geometry.hpp
@@ -0,0 +1,53 @@
+#pragma once
+
+#include <mapbox/geometry/point.hpp>
+#include <mapbox/geometry/line_string.hpp>
+#include <mapbox/geometry/polygon.hpp>
+#include <mapbox/geometry/multi_point.hpp>
+#include <mapbox/geometry/multi_line_string.hpp>
+#include <mapbox/geometry/multi_polygon.hpp>
+
+#include <mapbox/variant.hpp>
+
+// stl
+#include <vector>
+
+namespace mapbox {
+namespace geometry {
+
+template <typename T, template <typename...> class Cont = std::vector>
+struct geometry_collection;
+
+template <typename T>
+using geometry_base = mapbox::util::variant<point<T>,
+                                            line_string<T>,
+                                            polygon<T>,
+                                            multi_point<T>,
+                                            multi_line_string<T>,
+                                            multi_polygon<T>,
+                                            geometry_collection<T>>;
+
+template <typename T>
+struct geometry : geometry_base<T>
+{
+    using coordinate_type = T;
+    using geometry_base<T>::geometry_base;
+
+    /*
+     * The default constructor would create a point geometry with default-constructed coordinates;
+     * i.e. (0, 0). Since this is not particularly useful, and could hide bugs, it is disabled.
+     */
+    geometry() = delete;
+};
+
+template <typename T, template <typename...> class Cont>
+struct geometry_collection : Cont<geometry<T>>
+{
+    using coordinate_type = T;
+    using geometry_type = geometry<T>;
+    using container_type = Cont<geometry_type>;
+    using container_type::container_type;
+};
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/line_string.hpp b/include/mapbox/geometry/line_string.hpp
new file mode 100644
index 0000000..6d811ce
--- /dev/null
+++ b/include/mapbox/geometry/line_string.hpp
@@ -0,0 +1,21 @@
+#pragma once
+
+// mapbox
+#include <mapbox/geometry/point.hpp>
+// stl
+#include <vector>
+
+namespace mapbox {
+namespace geometry {
+
+template <typename T, template <typename...> class Cont = std::vector>
+struct line_string : Cont<point<T> >
+{
+    using coordinate_type = T;
+    using point_type = point<T>;
+    using container_type = Cont<point_type>;
+    using container_type::container_type;
+};
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/multi_line_string.hpp b/include/mapbox/geometry/multi_line_string.hpp
new file mode 100644
index 0000000..07a7a1d
--- /dev/null
+++ b/include/mapbox/geometry/multi_line_string.hpp
@@ -0,0 +1,21 @@
+#pragma once
+
+// mapbox
+#include <mapbox/geometry/line_string.hpp>
+// stl
+#include <vector>
+
+namespace mapbox {
+namespace geometry {
+
+template <typename T, template <typename...> class Cont = std::vector>
+struct multi_line_string : Cont<line_string<T>>
+{
+    using coordinate_type = T;
+    using line_string_type = line_string<T>;
+    using container_type = Cont<line_string_type>;
+    using container_type::container_type;
+};
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/multi_point.hpp b/include/mapbox/geometry/multi_point.hpp
new file mode 100644
index 0000000..a3c73cf
--- /dev/null
+++ b/include/mapbox/geometry/multi_point.hpp
@@ -0,0 +1,21 @@
+#pragma once
+
+// mapbox
+#include <mapbox/geometry/point.hpp>
+// stl
+#include <vector>
+
+namespace mapbox {
+namespace geometry {
+
+template <typename T, template <typename...> class Cont = std::vector>
+struct multi_point : Cont<point<T>>
+{
+    using coordinate_type = T;
+    using point_type = point<T>;
+    using container_type = Cont<point_type>;
+    using container_type::container_type;
+};
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/multi_polygon.hpp b/include/mapbox/geometry/multi_polygon.hpp
new file mode 100644
index 0000000..ad230a0
--- /dev/null
+++ b/include/mapbox/geometry/multi_polygon.hpp
@@ -0,0 +1,21 @@
+#pragma once
+
+// mapbox
+#include <mapbox/geometry/polygon.hpp>
+// stl
+#include <vector>
+
+namespace mapbox {
+namespace geometry {
+
+template <typename T, template <typename...> class Cont = std::vector>
+struct multi_polygon : Cont<polygon<T>>
+{
+    using coordinate_type = T;
+    using polygon_type = polygon<T>;
+    using container_type = Cont<polygon_type>;
+    using container_type::container_type;
+};
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/point.hpp b/include/mapbox/geometry/point.hpp
new file mode 100644
index 0000000..0cba499
--- /dev/null
+++ b/include/mapbox/geometry/point.hpp
@@ -0,0 +1,35 @@
+#pragma once
+
+namespace mapbox {
+namespace geometry {
+
+template <typename T>
+struct point
+{
+    using coordinate_type = T;
+
+    constexpr point()
+        : x(), y()
+    {}
+    constexpr point(T x_, T y_)
+        : x(x_), y(y_)
+    {}
+
+    T x;
+    T y;
+};
+
+template <typename T>
+constexpr bool operator==(point<T> const& lhs, point<T> const& rhs)
+{
+    return lhs.x == rhs.x && lhs.y == rhs.y;
+}
+
+template <typename T>
+constexpr bool operator!=(point<T> const& lhs, point<T> const& rhs)
+{
+    return !(lhs == rhs);
+}
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/point_arithmetic.hpp b/include/mapbox/geometry/point_arithmetic.hpp
new file mode 100644
index 0000000..3940e5b
--- /dev/null
+++ b/include/mapbox/geometry/point_arithmetic.hpp
@@ -0,0 +1,119 @@
+#pragma once
+
+namespace mapbox {
+namespace geometry {
+
+template <typename T>
+constexpr point<T> operator+(point<T> const& lhs, point<T> const& rhs)
+{
+    return point<T>(lhs.x + rhs.x, lhs.y + rhs.y);
+}
+
+template <typename T>
+constexpr point<T> operator+(point<T> const& lhs, T const& rhs)
+{
+    return point<T>(lhs.x + rhs, lhs.y + rhs);
+}
+
+template <typename T>
+constexpr point<T> operator-(point<T> const& lhs, point<T> const& rhs)
+{
+    return point<T>(lhs.x - rhs.x, lhs.y - rhs.y);
+}
+
+template <typename T>
+constexpr point<T> operator-(point<T> const& lhs, T const& rhs)
+{
+    return point<T>(lhs.x - rhs, lhs.y - rhs);
+}
+
+template <typename T>
+constexpr point<T> operator*(point<T> const& lhs, point<T> const& rhs)
+{
+    return point<T>(lhs.x * rhs.x, lhs.y * rhs.y);
+}
+
+template <typename T>
+constexpr point<T> operator*(point<T> const& lhs, T const& rhs)
+{
+    return point<T>(lhs.x * rhs, lhs.y * rhs);
+}
+
+template <typename T>
+constexpr point<T> operator/(point<T> const& lhs, point<T> const& rhs)
+{
+    return point<T>(lhs.x / rhs.x, lhs.y / rhs.y);
+}
+
+template <typename T>
+constexpr point<T> operator/(point<T> const& lhs, T const& rhs)
+{
+    return point<T>(lhs.x / rhs, lhs.y / rhs);
+}
+
+template <typename T>
+constexpr point<T>& operator+=(point<T>& lhs, point<T> const& rhs)
+{
+    lhs.x += rhs.x;
+    lhs.y += rhs.y;
+    return lhs;
+}
+
+template <typename T>
+constexpr point<T>& operator+=(point<T>& lhs, T const& rhs)
+{
+    lhs.x += rhs;
+    lhs.y += rhs;
+    return lhs;
+}
+
+template <typename T>
+constexpr point<T>& operator-=(point<T>& lhs, point<T> const& rhs)
+{
+    lhs.x -= rhs.x;
+    lhs.y -= rhs.y;
+    return lhs;
+}
+
+template <typename T>
+constexpr point<T>& operator-=(point<T>& lhs, T const& rhs)
+{
+    lhs.x -= rhs;
+    lhs.y -= rhs;
+    return lhs;
+}
+
+template <typename T>
+constexpr point<T>& operator*=(point<T>& lhs, point<T> const& rhs)
+{
+    lhs.x *= rhs.x;
+    lhs.y *= rhs.y;
+    return lhs;
+}
+
+template <typename T>
+constexpr point<T>& operator*=(point<T>& lhs, T const& rhs)
+{
+    lhs.x *= rhs;
+    lhs.y *= rhs;
+    return lhs;
+}
+
+template <typename T>
+constexpr point<T>& operator/=(point<T>& lhs, point<T> const& rhs)
+{
+    lhs.x /= rhs.x;
+    lhs.y /= rhs.y;
+    return lhs;
+}
+
+template <typename T>
+constexpr point<T>& operator/=(point<T>& lhs, T const& rhs)
+{
+    lhs.x /= rhs;
+    lhs.y /= rhs;
+    return lhs;
+}
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/polygon.hpp b/include/mapbox/geometry/polygon.hpp
new file mode 100644
index 0000000..99a66aa
--- /dev/null
+++ b/include/mapbox/geometry/polygon.hpp
@@ -0,0 +1,31 @@
+#pragma once
+
+// mapbox
+#include <mapbox/geometry/point.hpp>
+
+// stl
+#include <vector>
+
+namespace mapbox {
+namespace geometry {
+
+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 : Cont<linear_ring<T>>
+{
+    using coordinate_type = T;
+    using linear_ring_type = linear_ring<T>;
+    using container_type = Cont<linear_ring_type>;
+    using container_type::container_type;
+};
+
+} // namespace geometry
+} // namespace mapbox