forward.hpp

Go to the documentation of this file.

#pragma once

 
#include <type_traits>
#include <vector>
 
namespace pgl {

struct NoLabel;

class BigInt;

template <class T>
class Rational;

template <class Vertex>
class Graph;

template <class PointType>
struct EmptyShape;

template <class Number, class Label>
struct Point;

template <class ANumber, class ALabel, class BNumber, class BLabel, class CNumber, class CLabel>
constexpr bool collinear(
    const Point<ANumber, ALabel>& a,
    const Point<BNumber, BLabel>& b,
    const Point<CNumber, CLabel>& c);

template <class PointType, class Label = NoLabel>
struct Segment;

template <class PointType, class Label = NoLabel>
struct OrientedSegment;

template <class PointType, class Label = NoLabel>
struct Line;

template <class PointType, class Label = NoLabel>
struct OrientedLine;

template <class PointType, class Label = NoLabel>
struct Ray;

template <class PointType, class Label = NoLabel>
struct Halfplane;

template <class PointType, class Label = NoLabel>
struct Rectangle;

template <class PointType, class Label = NoLabel>
struct Triangle;

template <class PointType, class Label = NoLabel>
struct Convex;

template <class PointType, class Label = NoLabel>
struct Polygon;

template <class PointType, class Label = NoLabel>
struct HalfplaneIntersection;

template <class PointType, class Label = NoLabel>
struct PolygonWithHoles;

template <class PointType, class Label = NoLabel>
struct PolygonSet;

template <class PointType, class Label = NoLabel, class Storage = std::vector<PointType>>
struct MonotoneChain;

template <class PointType, class Label = NoLabel>
struct Polyline;

template <class PointType, class Label>
struct Disk;

template <class PointType>
struct Shape;

template <class PointType = Point<Rational<BigInt>, NoLabel>, class Label = NoLabel>
class Arrangement;

template <class Number>
struct Transformation;

class Canvas;
 
namespace detail {

template <class T>
inline constexpr int shapeRank = -1;
 
template <class PointType>
inline constexpr int shapeRank<EmptyShape<PointType>> = 0;
template <class Number, class Label>
inline constexpr int shapeRank<Point<Number, Label>> = 10;
template <class PointType, class Label>
inline constexpr int shapeRank<Segment<PointType, Label>> = 20;
template <class PointType, class Label>
inline constexpr int shapeRank<OrientedSegment<PointType, Label>> = 30;
template <class PointType, class Label>
inline constexpr int shapeRank<Line<PointType, Label>> = 40;
template <class PointType, class Label>
inline constexpr int shapeRank<OrientedLine<PointType, Label>> = 50;
template <class PointType, class Label>
inline constexpr int shapeRank<Ray<PointType, Label>> = 60;
template <class PointType, class Label>
inline constexpr int shapeRank<Halfplane<PointType, Label>> = 70;
template <class PointType, class Label>
inline constexpr int shapeRank<Rectangle<PointType, Label>> = 80;
template <class PointType, class Label>
inline constexpr int shapeRank<Triangle<PointType, Label>> = 90;
template <class PointType, class Label>
inline constexpr int shapeRank<Disk<PointType, Label>> = 100;
template <class PointType, class Label>
inline constexpr int shapeRank<Convex<PointType, Label>> = 110;
template <class PointType, class Label, class Storage>
inline constexpr int shapeRank<MonotoneChain<PointType, Label, Storage>> = 115;
template <class PointType, class Label>
inline constexpr int shapeRank<Polyline<PointType, Label>> = 117;
template <class PointType, class Label>
inline constexpr int shapeRank<Polygon<PointType, Label>> = 120;
template <class PointType, class Label>
inline constexpr int shapeRank<HalfplaneIntersection<PointType, Label>> = 130;
template <class PointType, class Label>
inline constexpr int shapeRank<PolygonWithHoles<PointType, Label>> = 140;
template <class PointType, class Label>
inline constexpr int shapeRank<PolygonSet<PointType, Label>> = 150;
 
// Shape-detection traits: is_<shape>_v<T> is true when T (ignoring cv/ref) is a
// specialization of that shape. They back the public XxxConcept concepts below
// and the generic 'Shape' routing in predicates.hpp. Defined here, before any
// shape header, so every header can use any shape's concept regardless of the
// order shapes are included in pgl.hpp.
template <class T> struct is_empty_shape : std::false_type {};
template <class PointType> struct is_empty_shape<EmptyShape<PointType>> : std::true_type {};
template <class T> inline constexpr bool is_empty_shape_v = is_empty_shape<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_point : std::false_type {};
template <class Number, class Label> struct is_point<Point<Number, Label>> : std::true_type {};
template <class T> inline constexpr bool is_point_v = is_point<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_segment : std::false_type {};
template <class PointType, class Label> struct is_segment<Segment<PointType, Label>> : std::true_type {};
template <class T> inline constexpr bool is_segment_v = is_segment<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_oriented_segment : std::false_type {};
template <class PointType, class Label> struct is_oriented_segment<OrientedSegment<PointType, Label>> : std::true_type {};
template <class T> inline constexpr bool is_oriented_segment_v = is_oriented_segment<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_line : std::false_type {};
template <class PointType, class Label> struct is_line<Line<PointType, Label>> : std::true_type {};
template <class T> inline constexpr bool is_line_v = is_line<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_oriented_line : std::false_type {};
template <class PointType, class Label> struct is_oriented_line<OrientedLine<PointType, Label>> : std::true_type {};
template <class T> inline constexpr bool is_oriented_line_v = is_oriented_line<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_ray : std::false_type {};
template <class PointType, class Label> struct is_ray<Ray<PointType, Label>> : std::true_type {};
template <class T> inline constexpr bool is_ray_v = is_ray<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_halfplane : std::false_type {};
template <class PointType, class Label> struct is_halfplane<Halfplane<PointType, Label>> : std::true_type {};
template <class T> inline constexpr bool is_halfplane_v = is_halfplane<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_rectangle : std::false_type {};
template <class PointType, class Label> struct is_rectangle<Rectangle<PointType, Label>> : std::true_type {};
template <class T> inline constexpr bool is_rectangle_v = is_rectangle<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_triangle : std::false_type {};
template <class PointType, class Label> struct is_triangle<Triangle<PointType, Label>> : std::true_type {};
template <class T> inline constexpr bool is_triangle_v = is_triangle<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_convex : std::false_type {};
template <class PointType, class Label> struct is_convex<Convex<PointType, Label>> : std::true_type {};
template <class T> inline constexpr bool is_convex_v = is_convex<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_polygon : std::false_type {};
template <class PointType, class Label> struct is_polygon<Polygon<PointType, Label>> : std::true_type {};
template <class T> inline constexpr bool is_polygon_v = is_polygon<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_polygon_with_holes : std::false_type {};
template <class PointType, class Label> struct is_polygon_with_holes<PolygonWithHoles<PointType, Label>> : std::true_type {};
template <class T> inline constexpr bool is_polygon_with_holes_v = is_polygon_with_holes<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_polygon_set : std::false_type {};
template <class PointType, class Label> struct is_polygon_set<PolygonSet<PointType, Label>> : std::true_type {};
template <class T> inline constexpr bool is_polygon_set_v = is_polygon_set<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_halfplane_intersection : std::false_type {};
template <class PointType, class Label> struct is_halfplane_intersection<HalfplaneIntersection<PointType, Label>> : std::true_type {};
template <class T> inline constexpr bool is_halfplane_intersection_v = is_halfplane_intersection<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_monotone_chain : std::false_type {};
template <class PointType, class Label, class Storage> struct is_monotone_chain<MonotoneChain<PointType, Label, Storage>> : std::true_type {};
template <class T> inline constexpr bool is_monotone_chain_v = is_monotone_chain<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_polyline : std::false_type {};
template <class PointType, class Label> struct is_polyline<Polyline<PointType, Label>> : std::true_type {};
template <class T> inline constexpr bool is_polyline_v = is_polyline<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_disk : std::false_type {};
template <class PointType, class Label> struct is_disk<Disk<PointType, Label>> : std::true_type {};
template <class T> inline constexpr bool is_disk_v = is_disk<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_shape : std::false_type {};
template <class PointType> struct is_shape<Shape<PointType>> : std::true_type {};
template <class T> inline constexpr bool is_shape_v = is_shape<std::remove_cvref_t<T>>::value;
 
template <class T> struct is_transformation : std::false_type {};
template <class Number> struct is_transformation<Transformation<Number>> : std::true_type {};
template <class T> inline constexpr bool is_transformation_v = is_transformation<std::remove_cvref_t<T>>::value;
 
}  // namespace detail
 
// Public per-shape concepts: each is satisfied by any specialization of that
// shape (ignoring cv/ref). They live here so every shape and implementation
// header can constrain on them, e.g. `template<SegmentConcept S> ...`.
template <class T> concept EmptyShapeConcept = detail::is_empty_shape_v<T>;
template <class T> concept PointConcept = detail::is_point_v<T>;
template <class T> concept SegmentConcept = detail::is_segment_v<T>;
template <class T> concept OrientedSegmentConcept = detail::is_oriented_segment_v<T>;
template <class T> concept LineConcept = detail::is_line_v<T>;
template <class T> concept OrientedLineConcept = detail::is_oriented_line_v<T>;
template <class T> concept RayConcept = detail::is_ray_v<T>;
template <class T> concept HalfplaneConcept = detail::is_halfplane_v<T>;
template <class T> concept RectangleConcept = detail::is_rectangle_v<T>;
template <class T> concept TriangleConcept = detail::is_triangle_v<T>;
template <class T> concept ConvexConcept = detail::is_convex_v<T>;
template <class T> concept PolygonConcept = detail::is_polygon_v<T>;
template <class T> concept PolygonWithHolesConcept = detail::is_polygon_with_holes_v<T>;
template <class T> concept PolygonSetConcept = detail::is_polygon_set_v<T>;
template <class T> concept HalfplaneIntersectionConcept = detail::is_halfplane_intersection_v<T>;
template <class T> concept MonotoneChainConcept = detail::is_monotone_chain_v<T>;
template <class T> concept PolylineConcept = detail::is_polyline_v<T>;
template <class T> concept DiskConcept = detail::is_disk_v<T>;
template <class T> concept ShapeConcept = detail::is_shape_v<T>;
template <class T> concept TransformationConcept = detail::is_transformation_v<T>;

template <class T>
concept AnyShapeConcept =
    ShapeConcept<T> || detail::shapeRank<std::remove_cvref_t<T>> >= 0;

template <class T>
concept BoundedConvexConcept =
    PointConcept<T> || SegmentConcept<T> || OrientedSegmentConcept<T> ||
    RectangleConcept<T> || TriangleConcept<T> || ConvexConcept<T>;

template <class T>
concept UnboundedConvexConcept =
    HalfplaneConcept<T> || LineConcept<T> || OrientedLineConcept<T> ||
    RayConcept<T> || HalfplaneIntersectionConcept<T>;

template <class T>
concept BoundedPolygonalConcept =
    BoundedConvexConcept<T> || PolygonConcept<T> || PolylineConcept<T> ||
    MonotoneChainConcept<T> || PolygonWithHolesConcept<T> || PolygonSetConcept<T>;

template <class T>
concept PolygonalRegionConcept =
    RectangleConcept<T> || TriangleConcept<T> || ConvexConcept<T> ||
    PolygonConcept<T> || PolygonWithHolesConcept<T> || PolygonSetConcept<T>;
 
namespace detail {

template <class Self, class Other>
concept ClosestPairConcept =
    BoundedPolygonalConcept<Self> && BoundedPolygonalConcept<Other> &&
    requires(const Self& self, const Other& other) { self.squaredDistance(other); };

template <class Self, class Other>
concept ClosestPointsPairConcept =
    ((BoundedPolygonalConcept<Self> && (BoundedPolygonalConcept<Other> || UnboundedConvexConcept<Other>)) ||
     (UnboundedConvexConcept<Self> && BoundedPolygonalConcept<Other>)) &&
    requires(const Self& self, const Other& other) { self.squaredDistance(other); };
 
}  // namespace detail

template <class A, class B>
concept MinkowskiSummableConcept =
    (ShapeConcept<A> || detail::shapeRank<std::remove_cvref_t<A>> >= 0) &&
    (ShapeConcept<B> || detail::shapeRank<std::remove_cvref_t<B>> >= 0) &&
    (ShapeConcept<A> || ShapeConcept<B> ||
     EmptyShapeConcept<A> || EmptyShapeConcept<B> ||
     PointConcept<A> || PointConcept<B> ||
     (BoundedConvexConcept<A> && BoundedConvexConcept<B>) ||
     (HalfplaneConcept<A> && BoundedPolygonalConcept<B>) ||
     (BoundedPolygonalConcept<A> && HalfplaneConcept<B>) ||
     (UnboundedConvexConcept<A> && UnboundedConvexConcept<B>) ||
     (UnboundedConvexConcept<A> && BoundedConvexConcept<B>) ||
     (BoundedConvexConcept<A> && UnboundedConvexConcept<B>));
 
namespace detail {

template <class Other, class Predicate>
constexpr bool reduceDegenerate(const Other& other, Predicate predicate) {
    if constexpr (requires { other.getIfPoint(); }) {
        if (const auto vertex = other.getIfPoint()) {
            return predicate(*vertex);
        }
    }
    if constexpr (requires { other.getIfSegment(); }) {
        if (const auto carrier = other.getIfSegment()) {
            return predicate(*carrier);
        }
    }
    return false;
}

template <class Other, class Predicate>
constexpr bool reduceDegenerateGuarded(const Other& other, Predicate predicate) {
    return other.isDegenerate() && reduceDegenerate(other, predicate);
}

template <class TShape>
constexpr bool coversNoPoint(const TShape& shape) {
    if constexpr (requires { shape.empty(); }) {
        return shape.empty();
    } else if constexpr (requires { shape.size(); }) {
        return shape.size() == 0;
    } else {
        return false;
    }
}

template <class Other, class Predicate>
constexpr bool reduceDegenerateToPoint(const Other& other, Predicate predicate) {
    if constexpr (requires { other.getIfPoint(); }) {
        if (const auto vertex = other.getIfPoint()) {
            return predicate(*vertex);
        }
    }
    return false;
}
 
}  // namespace detail
 
}  // namespace pgl