pgl Namespace Reference

Namespaces
namespace	pdfgen

Classes
class	Arrangement
	The planar subdivision induced by a set of one-dimensional shapes. More...
class	BigInt
	Arbitrary precision signed integer. More...
class	BitMatrix
	A bit per cell of a rectangular window of the integer grid. More...
class	Canvas
	Stores drawable objects and exports them as an SVG image. More...
struct	CanvasCommand
	Deferred style update applied to the current canvas style. More...
struct	CanvasStyle
	SVG style captured for each inserted element. More...
struct	Convex
	Closed convex polygon stored by its vertices. More...
struct	Disk
	Closed Euclidean disk stored by boundary points plus optional disk label. More...
struct	DivisionResult
	Default result type for an operation that may require division. More...
struct	EmptyShape
	The empty set of points in the plane. More...
class	Graph
	Undirected simple graph stored as adjacency sets. More...
struct	Halfplane
	Closed half-plane defined by an oriented boundary line. More...
struct	HalfplaneIntersection
	Intersection of closed half-planes; convex but possibly unbounded or empty. More...
class	IntervalTree
	Mutable interval tree over the projection of bounded shapes. More...
struct	is_int128
struct	is_int128< pgl::int128 >
struct	is_Rational
struct	is_Rational< Rational< T > >
struct	Line
	Unoriented infinite line. More...
struct	MonotoneChain
	Weakly x-monotone polyline stored by lexicographically sorted vertices. More...
struct	NoLabel
	Sentinel type used when a point carries no extra label. More...
struct	OrientedLine
	Directed infinite line with left/right side semantics plus optional line label. More...
struct	OrientedSegment
	Directed segment preserving source-to-target order plus optional segment label. More...
struct	Point
	Two-dimensional point with optional label payload. More...
struct	Polygon
	Closed simple polygon stored by its vertices. More...
struct	PolygonSet
	Set of closed regions with pairwise disjoint interiors. More...
struct	PolygonWithHoles
	Closed region bounded by one outer simple polygon minus disjoint polygonal holes. More...
struct	Polyline
	Open polygonal chain stored in traversal order; may self-intersect. More...
class	Rational
	Exact rational number class template. More...
struct	rational_int
	The integer type a Rational stores its parts in; any other type is its own answer. More...
struct	rational_int< Rational< Int > >
struct	Ray
	Half-infinite line starting from one source point plus optional ray label. More...
struct	Rectangle
	Axis-aligned rectangle stored by minimum and maximum corners. More...
struct	Segment
	Unoriented closed segment between two endpoints plus optional segment label. More...
struct	select_int_ge
struct	select_int_ge< 128 >
struct	select_int_ge< 16 >
struct	select_int_ge< 32 >
struct	select_int_ge< 64 >
struct	select_int_ge< 8 >
struct	Shape
	Runtime variant wrapper over the supported primitive shapes. More...
class	ShapeTree
	Static shape tree of bounded shapes. More...
struct	SweepContact
	Both boundariesCross and boundariesMeet, from one sweep. More...
struct	to_integer_with_digits
struct	Transformation
	Affine transformation stored as a 2x3 matrix. More...
struct	Triangle
	Closed triangle stored by three vertices. More...
struct	Triangulation
	Triangulation whose connectivity may change and whose vertex set may grow. More...

Concepts
concept	AnyShapeConcept
	Any concrete geometry type or the runtime Shape wrapper.
concept	BoundedConvexConcept
	Bounded convex primitives.
concept	BoundedPolygonalConcept
	Bounded polygonal primitives, convex or not.
concept	ConvexConcept
concept	DiskConcept
concept	EmptyShapeConcept
concept	HalfplaneConcept
concept	HalfplaneIntersectionConcept
concept	LineConcept
concept	MinkowskiSummableConcept
	Shape pairs whose Minkowski sum Pangolin can represent.
concept	MonotoneChainConcept
concept	NumericType
concept	OrientedLineConcept
concept	OrientedSegmentConcept
concept	PointConcept
concept	PolygonalRegionConcept
	Bounded polygonal regions: exactly the shapes a PolygonSet can always represent.
concept	PolygonConcept
concept	PolygonSetConcept
concept	PolygonWithHolesConcept
concept	PolylineConcept
concept	RationalConcept
concept	RayConcept
concept	RectangleConcept
concept	SegmentConcept
concept	ShapeConcept
concept	TransformationConcept
concept	TriangleConcept
concept	UnboundedConvexConcept
	Unbounded convex polyhedral primitives.

Typedefs
using	int128
	Signed 128-bit integer.
template<class T>
using	rational_int_t = typename rational_int<T>::type
template<class T>
using	grid_number_t
	The integer type a coordinate rasterizes onto by default.
template<typename T>
using	to_integer_with_digits_t = typename to_integer_with_digits<T>::type
using	ERational = Rational<BigInt>
	Exact, overflow-free result used when integral coordinates require fractions.
template<class Number>
using	division_result_t = typename DivisionResult<Number>::type
	Convenience alias for DivisionResult.
using	ETransformation = Transformation<ERational>
using	EPoint = Point<ERational>
using	EEmptyShape = EmptyShape<EPoint>
using	ESegment = Segment<EPoint>
using	EOrientedSegment = OrientedSegment<EPoint>
using	ELine = Line<EPoint>
using	EOrientedLine = OrientedLine<EPoint>
using	ERay = Ray<EPoint>
using	EHalfplane = Halfplane<EPoint>
using	ERectangle = Rectangle<EPoint>
using	ETriangle = Triangle<EPoint>
using	EDisk = Disk<EPoint>
using	EConvex = Convex<EPoint>
using	EPolygon = Polygon<EPoint>
using	EMonotoneChain = MonotoneChain<EPoint>
using	EPolyline = Polyline<EPoint>
using	EHalfplaneIntersection = HalfplaneIntersection<EPoint>
using	EPolygonWithHoles = PolygonWithHoles<EPoint>
using	EPolygonSet = PolygonSet<EPoint>
using	EShape = Shape<EPoint>
template<class PointType = Point<>, class Label = NoLabel>
using	MonotoneChainView = MonotoneChain<PointType, Label, std::span<const PointType>>
	A non-owning MonotoneChain that views an external, already canonical (sorted, duplicate-free) contiguous range of vertices.

Enumerations
enum class	GridAdjacency { edge , vertex }
	Which grid cells count as neighbors. More...
enum class	ProjectionAxis { x , y }
	Axis used to project a shape's bounding box into an interval. More...
enum class	BoundaryContact { Disjoint , Touching , Crossing }
	How two edge sets meet, as classified by redBlueSweep. More...
enum class	CanvasProperty {   stroke , fill , fillOpacity , strokeOpacity ,   strokeWidth , pointRadius }
	Names the style property targeted by a canvas command. More...

Functions
template<class PointType>
BitMatrix< PointType >	operator+ (const PointType &vector, const BitMatrix< PointType > &matrix)
	Returns the same cells translated by a vector.
template<class PointType>
	BitMatrix (PointType, int, int) -> BitMatrix< PointType >
template<class PointType, class LabelType>
	BitMatrix (const Rectangle< PointType, LabelType > &) -> BitMatrix< PointType >
template<class PointType, class LabelType>
	BitMatrix (const PolygonWithHoles< PointType, LabelType > &) -> BitMatrix< PointType >
template<class PointType, class LabelType>
	BitMatrix (const Polygon< PointType, LabelType > &) -> BitMatrix< PointType >
template<class PointType, class LabelType>
	BitMatrix (const PolygonSet< PointType, LabelType > &) -> BitMatrix< PointType >
template<std::ranges::input_range Range> requires (detail::is_point_v<std::remove_cvref_t<std::ranges::range_value_t<Range>>> && !AnyShapeConcept<std::remove_cvref_t <Range>> && !detail::is_bit_matrix_v<std::remove_cvref_t<Range>>)
	BitMatrix (Range &&) -> BitMatrix< std::remove_cvref_t< std::ranges::range_value_t< Range > > >
template<class PointType, class ShapeType>
BitMatrix< PointType >	outerRaster (const ShapeType &shape, const Rectangle< PointType > &window)
	Rasterizes a shape into the cells it meets: its outer approximation.
template<class PointType, class ShapeType>
BitMatrix< PointType >	innerRaster (const ShapeType &shape, const Rectangle< PointType > &window)
	Rasterizes a shape into the cells it covers: its inner approximation.
template<class PointType = Point<int>, class ShapeType> requires std::signed_integral< std::remove_cvref_t<decltype(std::declval<const ShapeType&>().bbox().min().x())>>
BitMatrix< PointType >	outerRaster (const ShapeType &shape)
	Rasterizes a bounded shape over its own bounding box.
template<class PointType = Point<int>, class ShapeType> requires std::signed_integral< std::remove_cvref_t<decltype(std::declval<const ShapeType&>().bbox().min().x())>>
BitMatrix< PointType >	innerRaster (const ShapeType &shape)
	Rasterizes a bounded shape over its own bounding box.
template<class Container>
Segment< detail::closest_pair_input_point_t< Container > >	closestPair (const Container &input)
	Computes a closest pair of points by divide and conquer.
template<class Container>
auto	grahamScan (const Container &points_)
	Computes the convex hull of a point container using Graham's scan.
template<class Container>
auto	grahamScanExtended (const Container &points_)
	Computes the convex hull of a point container using Graham's scan.
template<class Container>
auto	convexHull (const Container &points_)
	Computes the convex hull of a point container.
template<class Container>
auto	convexHullExtended (const Container &points_)
	Computes the convex hull of a point container.
template<class Rational = pgl::Rational<pgl::BigInt>, class Container>
auto	findIntersections (const Container &segments)
	Finds all intersecting segment pairs with Bentley-Ottmann.
template<class Rational = pgl::Rational<pgl::BigInt>, class Container>
auto	findCrossings (const Container &segments)
	Finds all proper crossing segment pairs with Bentley-Ottmann.
template<class Rational = pgl::Rational<pgl::BigInt>, class Container>
bool	detectIntersections (const Container &segments)
	Detects whether any two segments intersect.
template<class Rational = pgl::Rational<pgl::BigInt>, class Container>
bool	detectCrossings (const Container &segments)
	Detects whether any two segments properly cross.
template<class Rational = pgl::Rational<pgl::BigInt>, class Container>
auto	bruteForceCrossings (const Container &segments)
	Finds all crossing segment pairs by brute force.
template<class Rational = pgl::Rational<pgl::BigInt>, class Container>
auto	bruteForceIntersections (const Container &segments)
	Finds all intersecting segment pairs by brute force.
template<class Container>
	IntervalTree (const Container &) -> IntervalTree< typename Container::value_type >
template<class Container, class UniformRandomBitGenerator>
detail::min_disk_result_t< Container >	smallestEnclosingDisk (const Container &input, UniformRandomBitGenerator &&generator)
	Computes the smallest closed disk containing a set of points.
template<class Container>
detail::min_disk_result_t< Container >	smallestEnclosingDisk (const Container &input)
	Computes the smallest closed disk containing a set of points.
template<class T = int>
std::vector< Polygon< Point< T > > >	polyominoes (std::size_t size)
	Enumerates the free polyominoes of a given size as polygons.
template<class T = int>
std::vector< Polygon< Point< T > > >	polyominoes (std::size_t n1, std::size_t n2)
	Enumerates the free polyominoes of every size in [n1, n2].
template<class T = int>
std::vector< Polygon< Point< T > > >	polyominoesUpTo (std::size_t n)
	Enumerates the free polyominoes of every size from 1 to n.
template<class T = int>
std::vector< PolygonWithHoles< Point< T > > >	polyominoRegions (std::size_t size)
	Enumerates the free polyominoes of a given size as regions.
template<class T = int>
std::vector< PolygonWithHoles< Point< T > > >	polyominoRegions (std::size_t n1, std::size_t n2)
	Enumerates the free polyominoes of every size in [n1, n2] as regions.
template<class T = int>
std::vector< PolygonWithHoles< Point< T > > >	polyominoRegionsUpTo (std::size_t n)
	Enumerates the free polyominoes of every size from 1 to n as regions.
template<class RedRange, class BlueRange>
BoundaryContact	redBlueSweep (const RedRange &red, const BlueRange &blue)
	Classifies how two edge sets meet, in one combined left-to-right sweep.
template<class RedRange, class BlueRange>
bool	boundariesCross (const RedRange &red, const BlueRange &blue)
	True exactly when some red edge properly crosses some blue edge.
template<class RedRange, class BlueRange>
bool	boundariesMeet (const RedRange &red, const BlueRange &blue)
	True exactly when some red edge meets some blue edge, crossing or not.
template<class RedRange, class BlueRange>
SweepContact	boundaryContactBits (const RedRange &red, const BlueRange &blue)
template<class RedShape, class BlueShape>
constexpr bool	preferSweep (const RedShape &red, const BlueShape &blue)
	Whether red against blue is a job for redBlueSweep rather than for a pairwise test of their monotone boundary chains.
template<PolygonConcept OuterPolygon, PolygonConcept InnerPolygon>
bool	sweepContains (const OuterPolygon &outer, const InnerPolygon &inner)
	Sweep-based counterpart of Polygon::contains(Polygon).
template<class Container>
	ShapeTree (const Container &) -> ShapeTree< typename Container::value_type >
template<class Container>
	ShapeTree (const Container &, std::size_t) -> ShapeTree< typename Container::value_type >
template<class Container, class WeightFn>
	ShapeTree (const Container &, std::size_t, WeightFn) -> ShapeTree< typename Container::value_type, WeightFn >
template<class Container, class WeightFn> requires (!std::is_integral_v<WeightFn>)
	ShapeTree (const Container &, WeightFn) -> ShapeTree< typename Container::value_type, WeightFn >
template<class Number, class Label, class CenterNumber, class CenterLabel>
void	sortAround (std::vector< Point< Number, Label > > &points, const Point< CenterNumber, CenterLabel > &p)
	Sorts points counterclockwise around a center point.
template<class Number, class Label>
void	hilbertSort (std::vector< Point< Number, Label > > &points)
	Sorts points along a Hilbert space-filling curve.
template<class TriangleRange> requires TriangleConcept<typename TriangleRange::value_type>
	Triangulation (const TriangleRange &) -> Triangulation< typename TriangleRange::value_type >
template<class SegmentRange> requires SegmentConcept<typename SegmentRange::value_type>
	Triangulation (const SegmentRange &) -> Triangulation< Triangle< typename SegmentRange::value_type::PointType >, typename SegmentRange::value_type >
template<class PointRange> requires PointConcept<typename PointRange::value_type>
	Triangulation (const PointRange &) -> Triangulation< Triangle< Point< typename PointRange::value_type::NumberType > > >
template<class PointRange, class SegmentRange> requires PointConcept<typename PointRange::value_type> && SegmentConcept<typename SegmentRange::value_type>
	Triangulation (const PointRange &, const SegmentRange &) -> Triangulation< Triangle< Point< typename PointRange::value_type::NumberType > >, Segment< Point< typename PointRange::value_type::NumberType >, typename SegmentRange::value_type::LabelType > >
template<class PointType>
	Triangulation (const Polygon< PointType > &) -> Triangulation< Triangle< PointType > >
template<class PolyPoint, class PointRange> requires PointConcept<typename PointRange::value_type>
	Triangulation (const Polygon< PolyPoint > &, const PointRange &) -> Triangulation< Triangle< PolyPoint > >
template<class PolyPoint, class SegmentRange> requires SegmentConcept<typename SegmentRange::value_type>
	Triangulation (const Polygon< PolyPoint > &, const SegmentRange &) -> Triangulation< Triangle< PolyPoint >, Segment< PolyPoint, typename SegmentRange::value_type::LabelType > >
template<class PolyPoint, class PointRange, class SegmentRange> requires PointConcept<typename PointRange::value_type> && SegmentConcept<typename SegmentRange::value_type>
	Triangulation (const Polygon< PolyPoint > &, const PointRange &, const SegmentRange &) -> Triangulation< Triangle< PolyPoint >, Segment< PolyPoint, typename SegmentRange::value_type::LabelType > >
template<class RegionPoint>
	Triangulation (const PolygonWithHoles< RegionPoint > &) -> Triangulation< Triangle< RegionPoint > >
template<class RegionPoint, class PointRange> requires PointConcept<typename PointRange::value_type>
	Triangulation (const PolygonWithHoles< RegionPoint > &, const PointRange &) -> Triangulation< Triangle< RegionPoint > >
template<class RegionPoint, class SegmentRange> requires SegmentConcept<typename SegmentRange::value_type>
	Triangulation (const PolygonWithHoles< RegionPoint > &, const SegmentRange &) -> Triangulation< Triangle< RegionPoint >, Segment< RegionPoint, typename SegmentRange::value_type::LabelType > >
template<class RegionPoint, class PointRange, class SegmentRange> requires PointConcept<typename PointRange::value_type> && SegmentConcept<typename SegmentRange::value_type>
	Triangulation (const PolygonWithHoles< RegionPoint > &, const PointRange &, const SegmentRange &) -> Triangulation< Triangle< RegionPoint >, Segment< RegionPoint, typename SegmentRange::value_type::LabelType > >
template<class SetPoint>
	Triangulation (const PolygonSet< SetPoint > &) -> Triangulation< Triangle< SetPoint > >
template<class SetPoint, class PointRange> requires PointConcept<typename PointRange::value_type>
	Triangulation (const PolygonSet< SetPoint > &, const PointRange &) -> Triangulation< Triangle< SetPoint > >
template<class SetPoint, class SegmentRange> requires SegmentConcept<typename SegmentRange::value_type>
	Triangulation (const PolygonSet< SetPoint > &, const SegmentRange &) -> Triangulation< Triangle< SetPoint >, Segment< SetPoint, typename SegmentRange::value_type::LabelType > >
template<class SetPoint, class PointRange, class SegmentRange> requires PointConcept<typename PointRange::value_type> && SegmentConcept<typename SegmentRange::value_type>
	Triangulation (const PolygonSet< SetPoint > &, const PointRange &, const SegmentRange &) -> Triangulation< Triangle< SetPoint >, Segment< SetPoint, typename SegmentRange::value_type::LabelType > >
template<class Rational = pgl::Rational<pgl::BigInt>, class Container>
auto	xyCrossings (const Container &segments)
	Finds all crossing segment pairs with a bounding-box sweep.
template<class Rational = pgl::Rational<pgl::BigInt>, class Container>
auto	xyIntersections (const Container &segments)
	Finds all intersecting segment pairs with a bounding-box sweep.
BigInt	abs (const BigInt &v)
	Free-function absolute value, matching the integer helpers.
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)
	Tests whether three points are collinear.
constexpr int	round_up_bits (int bits)
template<class Number, class ShapeT> requires (detail::shapeRank<ShapeT> >= 0 && !RectangleConcept<ShapeT> && !DiskConcept<ShapeT>)
constexpr auto	operator* (const Transformation< Number > &transformation, const ShapeT &shape)
	Applies a transformation to any supported shape.
template<class Number, ShapeConcept ShapeT>
constexpr auto	operator* (const Transformation< Number > &transformation, const ShapeT &shape)
	Applies a transformation to the polymorphic Shape wrapper.
template<class ResultPoint, class ShapeRange>
PolygonSet< ResultPoint >	regularizedUnionOf (const ShapeRange &shapes, bool simpleBoundaries=false)
	The regularized union of arbitrarily many shapes, as a set of regions.
template<class Number, class Label>
std::ostream &	operator<< (std::ostream &stream, const Point< Number, Label > &point)
	Streams a point as (x,y) or label:(x,y).
template<class PointType, class LabelType>
std::ostream &	operator<< (std::ostream &stream, const Segment< PointType, LabelType > &segment)
	Streams a segment as p--q, or label:{p--q} when it carries a label.
template<class PointType, class LabelType>
std::ostream &	operator<< (std::ostream &stream, const OrientedSegment< PointType, LabelType > &segment)
	Streams an oriented segment as p->q, or label:{p->q} when it carries a label.
template<class PointType, class LabelType>
std::ostream &	operator<< (std::ostream &stream, const Line< PointType, LabelType > &line)
	Streams a line as -p--q-.
template<class PointType, class LabelType>
std::ostream &	operator<< (std::ostream &stream, const OrientedLine< PointType, LabelType > &line)
	Streams an oriented line as -p--q->.
template<class PointType, class LabelType>
std::ostream &	operator<< (std::ostream &stream, const Ray< PointType, LabelType > &ray)
	Streams a ray as p--q->.
template<class PointType, class LabelType>
std::ostream &	operator<< (std::ostream &stream, const Rectangle< PointType, LabelType > &rectangle)
	Streams a rectangle as [min,max], or as [] when it is empty.
template<class PointType, class LabelType>
std::ostream &	operator<< (std::ostream &stream, const Triangle< PointType, LabelType > &triangle)
	Streams a triangle as <abc>.
template<class PointType, class LabelType>
std::ostream &	operator<< (std::ostream &stream, const Halfplane< PointType, LabelType > &halfplane)
	Streams a half-plane as ^-p--q-^.
template<class PointType, class LabelType>
std::ostream &	operator<< (std::ostream &stream, const Disk< PointType, LabelType > &disk)
	Streams a disk as ((p1)(p2)(p3)).
template<class PointType, class LabelType>
std::ostream &	operator<< (std::ostream &stream, const Convex< PointType, LabelType > &convex)
	Streams a Convex as Convex[(P1),(P2),(P3),(Pn)...].
template<class PointType, class LabelType>
std::ostream &	operator<< (std::ostream &stream, const Polygon< PointType, LabelType > &polygon)
	Streams a Polygon as Polygon[(P1),(P2),(P3),(Pn)...].
template<class PointType, class LabelType>
std::ostream &	operator<< (std::ostream &stream, const PolygonWithHoles< PointType, LabelType > &region)
	Streams a region as PolygonWithHoles[outer,holes...].
template<class PointType, class LabelType>
std::ostream &	operator<< (std::ostream &stream, const PolygonSet< PointType, LabelType > &set)
	Streams a set as PolygonSet[components...].
template<class PointType, class LabelType, class Storage>
std::ostream &	operator<< (std::ostream &stream, const MonotoneChain< PointType, LabelType, Storage > &chain)
	Streams a MonotoneChain as MonotoneChain[(P1),(P2),(P3),...].
template<class PointType, class LabelType>
std::ostream &	operator<< (std::ostream &stream, const Polyline< PointType, LabelType > &polyline)
	Streams a Polyline as Polyline[(P1),(P2),(P3),...].
template<class PointType, class LabelType>
std::ostream &	operator<< (std::ostream &stream, const HalfplaneIntersection< PointType, LabelType > &region)
	Streams a HalfplaneIntersection as HalfplaneIntersection[h1,h2,...].
template<class LeftNumber, class LeftLabel, class RightNumber, class RightLabel>
constexpr auto	operator* (const Point< LeftNumber, LeftLabel > &left, const Point< RightNumber, RightLabel > &right)
	Returns the dot product of two points.
template<class A, class B> requires MinkowskiSummableConcept<A, B>
constexpr auto	operator+ (const A &a, const B &b)
	Returns the Minkowski sum a ⊕ b, the same as a.minkowskiSum(b).
template<class ANumber, class ALabel, class BNumber, class BLabel, class CNumber, class CLabel>
constexpr auto	orientationDeterminant (const Point< ANumber, ALabel > &a, const Point< BNumber, BLabel > &b, const Point< CNumber, CLabel > &c)
	Returns the signed orientation determinant of three points.
template<class ANumber, class ALabel, class BNumber, class BLabel, class CNumber, class CLabel>
constexpr std::partial_ordering	orientationSign (const Point< ANumber, ALabel > &a, const Point< BNumber, BLabel > &b, const Point< CNumber, CLabel > &c)
	Classifies the orientation of three points.
template<class UNumber, class ULabel, class VNumber, class VLabel>
constexpr std::partial_ordering	crossSign (const Point< UNumber, ULabel > &u, const Point< VNumber, VLabel > &v)
	Classifies the turn from one vector to another.
template<class ANumber, class ALabel, class BNumber, class BLabel, class PNumber, class PLabel, class QNumber, class QLabel>
constexpr std::partial_ordering	crossSign (const Point< ANumber, ALabel > &a, const Point< BNumber, BLabel > &b, const Point< PNumber, PLabel > &p, const Point< QNumber, QLabel > &q)
	Classifies the turn from the direction a -> b to the direction p -> q.
template<class ANumber, class ALabel, class BNumber, class BLabel>
constexpr bool	sameDirection (const Point< ANumber, ALabel > &a1, const Point< ANumber, ALabel > &a2, const Point< BNumber, BLabel > &b1, const Point< BNumber, BLabel > &b2)
	Tests whether the directions a1 -> a2 and b1 -> b2 are parallel.
template<class ANumber, class ALabel, class BNumber, class BLabel>
constexpr std::partial_ordering	dotSign (const Point< ANumber, ALabel > &a, const Point< BNumber, BLabel > &b)
	Tells if the angle between two vectors is acute, right, or obtuse.
template<class ANumber, class ALabel, class BNumber, class BLabel, class PNumber, class PLabel, class QNumber, class QLabel>
constexpr std::partial_ordering	dotSign (const Point< ANumber, ALabel > &a, const Point< BNumber, BLabel > &b, const Point< PNumber, PLabel > &p, const Point< QNumber, QLabel > &q)
	Tells if the angle between the directions a -> b and p -> q is acute, right, or obtuse.
template<class ANumber, class ALabel, class BNumber, class BLabel, class CNumber, class CLabel, class DNumber, class DLabel>
constexpr auto	inCircleDeterminant (const Point< ANumber, ALabel > &a, const Point< BNumber, BLabel > &b, const Point< CNumber, CLabel > &c, const Point< DNumber, DLabel > &d)
	Returns the signed in-circle determinant of a query point.
template<class ANumber, class ALabel, class BNumber, class BLabel, class CNumber, class CLabel, class DNumber, class DLabel>
constexpr std::partial_ordering	inCircleSign (const Point< ANumber, ALabel > &a, const Point< BNumber, BLabel > &b, const Point< CNumber, CLabel > &c, const Point< DNumber, DLabel > &d)
	Classifies a point with respect to the circumcircle of three others.
template<class LeftNumber, class LeftLabel, class RightNumber, class RightLabel>
constexpr auto	operator- (const Point< LeftNumber, LeftLabel > &left, const Point< RightNumber, RightLabel > &right)
	Translates a point by the opposite of another point.
template<class Number, class Label, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Point< Number, Label > &point, const Scalar &scalar)
	Scales a point by a scalar.
template<class Scalar, class Number, class Label> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const Point< Number, Label > &point)
	Scales a point by a scalar written on the left.
template<class Number, class Label, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const Point< Number, Label > &point, const Scalar &scalar)
	Divides both coordinates by a scalar.
template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const Segment< PointType, LabelType > &segment, const Point< TranslationNumber, TranslationLabel > &translation)
	Translates a segment by the opposite of a point.
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Segment< PointType, LabelType > &segment, const Scalar &scalar)
	Scales a segment by a scalar.
template<class Scalar, class PointType, class LabelType> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const Segment< PointType, LabelType > &segment)
	Scales a segment by a scalar written on the left.
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const Segment< PointType, LabelType > &segment, const Scalar &scalar)
	Divides both endpoints by a scalar.
template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const OrientedSegment< PointType, LabelType > &segment, const Point< TranslationNumber, TranslationLabel > &translation)
	Translates an oriented segment by the opposite of a point.
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const OrientedSegment< PointType, LabelType > &segment, const Scalar &scalar)
	Scales an oriented segment by a scalar.
template<class Scalar, class PointType, class LabelType> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const OrientedSegment< PointType, LabelType > &segment)
	Scales an oriented segment by a scalar written on the left.
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const OrientedSegment< PointType, LabelType > &segment, const Scalar &scalar)
	Divides both endpoints by a scalar.
template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const Line< PointType, LabelType > &line, const Point< TranslationNumber, TranslationLabel > &translation)
	Translates a line by the opposite of a point.
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Line< PointType, LabelType > &line, const Scalar &scalar)
	Scales a line by a scalar.
template<class Scalar, class PointType, class LabelType> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const Line< PointType, LabelType > &line)
	Scales a line by a scalar written on the left.
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const Line< PointType, LabelType > &line, const Scalar &scalar)
	Divides both defining points by a scalar.
template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const OrientedLine< PointType, LabelType > &line, const Point< TranslationNumber, TranslationLabel > &translation)
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const OrientedLine< PointType, LabelType > &line, const Scalar &scalar)
template<class Scalar, class PointType, class LabelType> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const OrientedLine< PointType, LabelType > &line)
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const OrientedLine< PointType, LabelType > &line, const Scalar &scalar)
template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const Ray< PointType, LabelType > &ray, const Point< TranslationNumber, TranslationLabel > &translation)
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Ray< PointType, LabelType > &ray, const Scalar &scalar)
template<class Scalar, class PointType, class LabelType> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const Ray< PointType, LabelType > &ray)
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const Ray< PointType, LabelType > &ray, const Scalar &scalar)
template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const Rectangle< PointType, LabelType > &rectangle, const Point< TranslationNumber, TranslationLabel > &translation)
	Translates a rectangle by the opposite of a point.
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Rectangle< PointType, LabelType > &rectangle, const Scalar &scalar)
	Scales a rectangle by a scalar.
template<class Scalar, class PointType, class LabelType> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const Rectangle< PointType, LabelType > &rectangle)
	Scales a rectangle by a scalar written on the left.
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const Rectangle< PointType, LabelType > &rectangle, const Scalar &scalar)
	Divides both rectangle corners by a scalar.
template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const Triangle< PointType, LabelType > &triangle, const Point< TranslationNumber, TranslationLabel > &translation)
	Returns a copy of a triangle translated by the opposite point.
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Triangle< PointType, LabelType > &triangle, const Scalar &scalar)
	Returns a scaled copy of a triangle.
template<class Scalar, class PointType, class LabelType> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const Triangle< PointType, LabelType > &triangle)
	Returns a scaled copy of a triangle with the scalar on the left.
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const Triangle< PointType, LabelType > &triangle, const Scalar &scalar)
	Returns a copy of a triangle divided by a scalar.
template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const Halfplane< PointType, LabelType > &halfplane, const Point< TranslationNumber, TranslationLabel > &translation)
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Halfplane< PointType, LabelType > &halfplane, const Scalar &scalar)
template<class Scalar, class PointType, class LabelType> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const Halfplane< PointType, LabelType > &halfplane)
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const Halfplane< PointType, LabelType > &halfplane, const Scalar &scalar)
	Convex () -> Convex< Point<>, NoLabel >
template<std::ranges::input_range Range> requires detail::is_point_v<std::ranges::range_value_t<Range>>
	Convex (Range &&) -> Convex< std::remove_cvref_t< std::ranges::range_value_t< Range > >, NoLabel >
template<class Number> requires (!detail::is_point_v<Number>)
	Convex (std::initializer_list< Number >) -> Convex< Point< Number >, NoLabel >
template<class Number> requires (!detail::is_point_v<Number>)
	Convex (std::initializer_list< Number >, bool) -> Convex< Point< Number >, NoLabel >
template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const Convex< PointType, LabelType > &convex, const Point< TranslationNumber, TranslationLabel > &translation)
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Convex< PointType, LabelType > &convex, const Scalar &scalar)
template<class Scalar, class PointType, class LabelType> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const Convex< PointType, LabelType > &convex)
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const Convex< PointType, LabelType > &convex, const Scalar &scalar)
	Disk () -> Disk< Point<>, NoLabel >
	Deduces a default disk with Point<> boundary points and no label.
template<class PointType>
	Disk (PointType, typename PointType::NumberType) -> Disk< PointType, NoLabel >
	Deduces a disk from a center point and a radius.
template<PointConcept PointType>
	Disk (PointType, PointType, PointType) -> Disk< PointType, NoLabel >
	Deduces a disk from three boundary points.
template<class Number>
	Disk (Number, Number, Number) -> Disk< Point< Number >, NoLabel >
	Deduces a disk from center coordinates and a radius.
template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const Disk< PointType, LabelType > &disk, const Point< TranslationNumber, TranslationLabel > &translation)
	Returns a copy of disk translated by translation.
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Disk< PointType, LabelType > &disk, const Scalar &scalar)
	Returns a copy of disk with every boundary point scaled by scalar.
template<class Scalar, class PointType, class LabelType> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const Disk< PointType, LabelType > &disk)
	Returns a copy of disk with every boundary point scaled by scalar.
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const Disk< PointType, LabelType > &disk, const Scalar &scalar)
	Returns a copy of disk with every boundary point divided by scalar.
template<class PointType, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const EmptyShape< PointType > &, const Point< TranslationNumber, TranslationLabel > &)
	Translates the empty shape by a negated point; a no-op.
template<class PointType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const EmptyShape< PointType > &, const Scalar &)
	Scales the empty shape around the origin; a no-op.
template<class Scalar, class PointType> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const EmptyShape< PointType > &empty)
	Scales the empty shape around the origin; a no-op.
template<class PointType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const EmptyShape< PointType > &, const Scalar &)
	Divides the empty shape around the origin; a no-op.
template<class PointType>
std::ostream &	operator<< (std::ostream &stream, const EmptyShape< PointType > &)
	Streams the empty shape.
	Halfplane () -> Halfplane< Point<>, NoLabel >
template<class PointType>
	Halfplane (PointType, PointType) -> Halfplane< PointType, NoLabel >
template<class PointType, class A>
	Halfplane (PointType, PointType, A) -> Halfplane< PointType, std::decay_t< A > >
template<class Number>
	Halfplane (Number, Number, Number, Number) -> Halfplane< Point< Number >, NoLabel >
	HalfplaneIntersection () -> HalfplaneIntersection< Point<>, NoLabel >
template<HalfplaneConcept H>
	HalfplaneIntersection (const H &) -> HalfplaneIntersection< typename H::PointType, NoLabel >
template<std::ranges::input_range Range> requires detail::is_halfplane_v<std::ranges::range_value_t<Range>>
	HalfplaneIntersection (Range &&) -> HalfplaneIntersection< typename std::remove_cvref_t< std::ranges::range_value_t< Range > >::PointType, NoLabel >
template<std::ranges::input_range Range> requires detail::is_halfplane_v<std::ranges::range_value_t<Range>>
	HalfplaneIntersection (Range &&, bool) -> HalfplaneIntersection< typename std::remove_cvref_t< std::ranges::range_value_t< Range > >::PointType, NoLabel >
template<RectangleConcept R>
	HalfplaneIntersection (const R &) -> HalfplaneIntersection< typename R::PointType, NoLabel >
template<TriangleConcept T>
	HalfplaneIntersection (const T &) -> HalfplaneIntersection< typename T::PointType, NoLabel >
template<ConvexConcept C>
	HalfplaneIntersection (const C &) -> HalfplaneIntersection< typename C::PointType, NoLabel >
template<PointConcept P>
	HalfplaneIntersection (const P &) -> HalfplaneIntersection< Point< typename P::NumberType, typename P::LabelType >, NoLabel >
template<SegmentConcept S>
	HalfplaneIntersection (const S &) -> HalfplaneIntersection< typename S::PointType, NoLabel >
template<LineConcept L>
	HalfplaneIntersection (const L &) -> HalfplaneIntersection< typename L::PointType, NoLabel >
template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const HalfplaneIntersection< PointType, LabelType > &region, const Point< TranslationNumber, TranslationLabel > &translation)
	Translates a region by a negated point.
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const HalfplaneIntersection< PointType, LabelType > &region, const Scalar &scalar)
	Scales a region around the origin.
template<class Scalar, class PointType, class LabelType> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const HalfplaneIntersection< PointType, LabelType > &region)
	Scales a region around the origin.
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const HalfplaneIntersection< PointType, LabelType > &region, const Scalar &scalar)
	Divides a region around the origin.
	Line () -> Line< Point<>, NoLabel >
template<class PointType>
	Line (PointType, PointType) -> Line< PointType, NoLabel >
template<class PointType, class A>
	Line (PointType, PointType, A) -> Line< PointType, std::decay_t< A > >
template<class Number>
	Line (Number, Number, Number, Number) -> Line< Point< Number >, NoLabel >
	MonotoneChain () -> MonotoneChain< Point<>, NoLabel >
template<std::ranges::input_range Range> requires detail::is_point_v<std::ranges::range_value_t<Range>>
	MonotoneChain (Range &&) -> MonotoneChain< std::remove_cvref_t< std::ranges::range_value_t< Range > >, NoLabel >
template<std::ranges::input_range Range> requires detail::is_point_v<std::ranges::range_value_t<Range>>
	MonotoneChain (Range &&, bool) -> MonotoneChain< std::remove_cvref_t< std::ranges::range_value_t< Range > >, NoLabel >
template<class Number> requires (!detail::is_point_v<Number>)
	MonotoneChain (std::initializer_list< Number >) -> MonotoneChain< Point< Number >, NoLabel >
template<class Number> requires (!detail::is_point_v<Number>)
	MonotoneChain (std::initializer_list< Number >, bool) -> MonotoneChain< Point< Number >, NoLabel >
template<class PointType, class LabelType, class Storage, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const MonotoneChain< PointType, LabelType, Storage > &chain, const Point< TranslationNumber, TranslationLabel > &translation)
template<class PointType, class LabelType, class Storage, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const MonotoneChain< PointType, LabelType, Storage > &chain, const Scalar &scalar)
template<class Scalar, class PointType, class LabelType, class Storage> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const MonotoneChain< PointType, LabelType, Storage > &chain)
template<class PointType, class LabelType, class Storage, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const MonotoneChain< PointType, LabelType, Storage > &chain, const Scalar &scalar)
	OrientedLine () -> OrientedLine< Point<>, NoLabel >
template<class PointType>
	OrientedLine (PointType, PointType) -> OrientedLine< PointType, NoLabel >
template<class PointType, class A>
	OrientedLine (PointType, PointType, A) -> OrientedLine< PointType, std::decay_t< A > >
template<class Number>
	OrientedLine (Number, Number, Number, Number) -> OrientedLine< Point< Number >, NoLabel >
	OrientedSegment () -> OrientedSegment< Point<>, NoLabel >
template<class PointType>
	OrientedSegment (PointType, PointType) -> OrientedSegment< PointType, NoLabel >
template<class PointType, class A>
	OrientedSegment (PointType, PointType, A) -> OrientedSegment< PointType, std::decay_t< A > >
template<class Number>
	OrientedSegment (Number, Number, Number, Number) -> OrientedSegment< Point< Number >, NoLabel >
	Point () -> Point< int >
template<class Number>
	Point (Number, Number) -> Point< Number >
template<class Number, class Label>
	Point (Number, Number, Label) -> Point< Number, std::decay_t< Label > >
	Polygon () -> Polygon< Point<>, NoLabel >
template<std::ranges::input_range Range> requires detail::is_point_v<std::ranges::range_value_t<Range>>
	Polygon (Range &&) -> Polygon< std::remove_cvref_t< std::ranges::range_value_t< Range > >, NoLabel >
template<class Number> requires (!detail::is_point_v<Number>)
	Polygon (std::initializer_list< Number >) -> Polygon< Point< Number >, NoLabel >
template<class Number> requires (!detail::is_point_v<Number>)
	Polygon (std::initializer_list< Number >, bool) -> Polygon< Point< Number >, NoLabel >
template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const Polygon< PointType, LabelType > &polygon, const Point< TranslationNumber, TranslationLabel > &translation)
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Polygon< PointType, LabelType > &polygon, const Scalar &scalar)
template<class Scalar, class PointType, class LabelType> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const Polygon< PointType, LabelType > &polygon)
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const Polygon< PointType, LabelType > &polygon, const Scalar &scalar)
	PolygonSet () -> PolygonSet< Point<>, NoLabel >
template<PolygonWithHolesConcept Component>
	PolygonSet (Component &&) -> PolygonSet< typename std::remove_cvref_t< Component >::PointType, NoLabel >
template<std::ranges::input_range ComponentRange> requires detail::is_polygon_with_holes_v<std::ranges::range_value_t<ComponentRange>>
	PolygonSet (ComponentRange &&) -> PolygonSet< typename std::ranges::range_value_t< ComponentRange >::PointType, NoLabel >
template<std::ranges::input_range ComponentRange> requires detail::is_polygon_with_holes_v<std::ranges::range_value_t<ComponentRange>>
	PolygonSet (ComponentRange &&, bool) -> PolygonSet< typename std::ranges::range_value_t< ComponentRange >::PointType, NoLabel >
template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const PolygonSet< PointType, LabelType > &set, const Point< TranslationNumber, TranslationLabel > &translation)
	Returns a copy of a set translated by the opposite point.
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const PolygonSet< PointType, LabelType > &set, const Scalar &scalar)
template<class Scalar, class PointType, class LabelType> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const PolygonSet< PointType, LabelType > &set)
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const PolygonSet< PointType, LabelType > &set, const Scalar &scalar)
	PolygonWithHoles () -> PolygonWithHoles< Point<>, NoLabel >
template<PolygonConcept OuterPolygon>
	PolygonWithHoles (OuterPolygon &&) -> PolygonWithHoles< typename std::remove_cvref_t< OuterPolygon >::PointType, NoLabel >
template<PolygonConcept OuterPolygon>
	PolygonWithHoles (OuterPolygon &&, bool) -> PolygonWithHoles< typename std::remove_cvref_t< OuterPolygon >::PointType, NoLabel >
template<PolygonConcept OuterPolygon, std::ranges::input_range HoleRange> requires detail::is_polygon_v<std::ranges::range_value_t<HoleRange>>
	PolygonWithHoles (OuterPolygon &&, HoleRange &&) -> PolygonWithHoles< typename std::remove_cvref_t< OuterPolygon >::PointType, NoLabel >
template<PolygonConcept OuterPolygon, std::ranges::input_range HoleRange> requires detail::is_polygon_v<std::ranges::range_value_t<HoleRange>>
	PolygonWithHoles (OuterPolygon &&, HoleRange &&, bool) -> PolygonWithHoles< typename std::remove_cvref_t< OuterPolygon >::PointType, NoLabel >
template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const PolygonWithHoles< PointType, LabelType > &region, const Point< TranslationNumber, TranslationLabel > &translation)
	Returns a copy of a region translated by the opposite point.
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const PolygonWithHoles< PointType, LabelType > &region, const Scalar &scalar)
template<class Scalar, class PointType, class LabelType> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const PolygonWithHoles< PointType, LabelType > &region)
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const PolygonWithHoles< PointType, LabelType > &region, const Scalar &scalar)
	Polyline () -> Polyline< Point<>, NoLabel >
template<std::ranges::input_range Range> requires detail::is_point_v<std::ranges::range_value_t<Range>>
	Polyline (Range &&) -> Polyline< std::remove_cvref_t< std::ranges::range_value_t< Range > >, NoLabel >
template<class Number> requires (!detail::is_point_v<Number>)
	Polyline (std::initializer_list< Number >) -> Polyline< Point< Number >, NoLabel >
template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const Polyline< PointType, LabelType > &polyline, const Point< TranslationNumber, TranslationLabel > &translation)
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Polyline< PointType, LabelType > &polyline, const Scalar &scalar)
template<class Scalar, class PointType, class LabelType> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const Polyline< PointType, LabelType > &polyline)
template<class PointType, class LabelType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const Polyline< PointType, LabelType > &polyline, const Scalar &scalar)
	Ray () -> Ray< Point<>, NoLabel >
template<class PointType>
	Ray (PointType, PointType) -> Ray< PointType, NoLabel >
template<class PointType, class A>
	Ray (PointType, PointType, A) -> Ray< PointType, std::decay_t< A > >
template<class Number>
	Ray (Number, Number, Number, Number) -> Ray< Point< Number >, NoLabel >
	Rectangle () -> Rectangle< Point<>, NoLabel >
template<class PointType>
	Rectangle (PointType, PointType) -> Rectangle< PointType, NoLabel >
template<class Number>
	Rectangle (Number, Number, Number, Number) -> Rectangle< Point< Number >, NoLabel >
template<std::ranges::input_range Range> requires detail::is_point_v<std::ranges::range_value_t<Range>>
	Rectangle (Range &&) -> Rectangle< std::remove_cvref_t< std::ranges::range_value_t< Range > >, NoLabel >
	Segment () -> Segment< Point<>, NoLabel >
template<class PointType>
	Segment (PointType, PointType) -> Segment< PointType, NoLabel >
template<class PointType, class A>
	Segment (PointType, PointType, A) -> Segment< PointType, std::decay_t< A > >
template<class Number>
	Segment (Number, Number, Number, Number) -> Segment< Point< Number >, NoLabel >
template<class T, class... Ts>
	Shape (const std::variant< T, Ts... > &) -> Shape< detail::shape_point_type_t< T > >
template<class T, class... Ts>
	Shape (const std::optional< std::variant< T, Ts... > > &) -> Shape< detail::shape_point_type_t< T > >
template<class PointType, class TranslationNumber, class TranslationLabel>
constexpr auto	operator- (const Shape< PointType > &shape, const Point< TranslationNumber, TranslationLabel > &translation)
	Translates a shape by a negated point.
template<class PointType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Shape< PointType > &shape, const Scalar &scalar)
	Scales a shape around the origin.
template<class Scalar, class PointType> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator* (const Scalar &scalar, const Shape< PointType > &shape)
	Scales a shape around the origin.
template<class PointType, class Scalar> requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
constexpr auto	operator/ (const Shape< PointType > &shape, const Scalar &scalar)
	Divides a shape around the origin.
template<class PointType>
std::ostream &	operator<< (std::ostream &stream, const Shape< PointType > &shape)
	Streams the currently stored alternative.
	Triangle () -> Triangle< Point<>, NoLabel >
template<class PointType>
	Triangle (PointType, PointType, PointType) -> Triangle< PointType, NoLabel >
template<class PointType, class A>
	Triangle (PointType, PointType, PointType, A) -> Triangle< PointType, std::decay_t< A > >
template<class Number>
	Triangle (Number, Number, Number, Number, Number, Number) -> Triangle< Point< Number >, NoLabel >
CanvasCommand	stroke (std::string value)
	Creates a command that changes the current stroke color.
CanvasCommand	fill (std::string value)
	Creates a command that changes the current fill color.
CanvasCommand	fillOpacity (std::string value)
	Creates a command that changes the current fill opacity.
CanvasCommand	strokeOpacity (std::string value)
	Creates a command that changes the current stroke opacity.
CanvasCommand	strokeWidth (std::string value)
	Creates a command that changes the current stroke width.
CanvasCommand	pointRadius (std::string value)
	Creates a command that changes the current point radius.
Rational deduction guides
Explicit guides that pin class template argument deduction so it is consistent across compilers. The numerator constructor deliberately makes Int non-deducible (see its comment), so CTAD for a bare, non-built-in integer numerator such as pgl::BigInt is supplied here instead: as an explicit guide, its constraint is honored even by compilers (clang 18) that mishandle constraints on the guides synthesized from constrained constructors. Floating-point and built-in integer arguments are excluded so they continue to deduce the default Rational<int64_t> via the other constructors' guides.
template<class T> requires (!pgl::detail::extended_integral<T> && !std::floating_point<T> && !RationalConcept<T>)
	Rational (T) -> Rational< T >

Variables
template<class T>
constexpr bool	is_Rational_v = is_Rational<T>::value

Typedef Documentation

division_result_t

template<class Number>

using pgl::division_result_t = typename DivisionResult<Number>::type

Convenience alias for DivisionResult.

EConvex

using pgl::EConvex = Convex<EPoint>

EDisk

using pgl::EDisk = Disk<EPoint>

EEmptyShape

using pgl::EEmptyShape = EmptyShape<EPoint>

EHalfplane

using pgl::EHalfplane = Halfplane<EPoint>

EHalfplaneIntersection

using pgl::EHalfplaneIntersection = HalfplaneIntersection<EPoint>

ELine

using pgl::ELine = Line<EPoint>

EMonotoneChain

using pgl::EMonotoneChain = MonotoneChain<EPoint>

EOrientedLine

using pgl::EOrientedLine = OrientedLine<EPoint>

EOrientedSegment

using pgl::EOrientedSegment = OrientedSegment<EPoint>

EPoint

using pgl::EPoint = Point<ERational>

EPolygon

using pgl::EPolygon = Polygon<EPoint>

EPolygonSet

using pgl::EPolygonSet = PolygonSet<EPoint>

EPolygonWithHoles

using pgl::EPolygonWithHoles = PolygonWithHoles<EPoint>

EPolyline

using pgl::EPolyline = Polyline<EPoint>

ERational

using pgl::ERational = Rational<BigInt>

Exact, overflow-free result used when integral coordinates require fractions.

ERay

using pgl::ERay = Ray<EPoint>

ERectangle

using pgl::ERectangle = Rectangle<EPoint>

ESegment

using pgl::ESegment = Segment<EPoint>

EShape

using pgl::EShape = Shape<EPoint>

ETransformation

using pgl::ETransformation = Transformation<ERational>

ETriangle

using pgl::ETriangle = Triangle<EPoint>

grid_number_t

template<class T>

using pgl::grid_number_t

Initial value:

std::conditional_t<std::signed_integral<rational_int_t<T>>,
                                        rational_int_t<T>, std::int64_t>

The integer type a coordinate rasterizes onto by default.

A grid cell is an integer position, so a shape can only be rasterized over a signed integer coordinate type. One that already is stays itself, so an integer shape rasterizes with no conversion at all, and a Rational collapses to the integer it is built on, which every whole fraction fits. Anything else – a floating-point coordinate, a Rational over a BigInt – goes to int64_t, wide enough for every whole number a double can name; the value is checked against its range rather than wrapped into it.

int128

using pgl::int128

Initial value:

boost::multiprecision::number<boost::multiprecision::cpp_int_backend<
   127, 127, boost::multiprecision::signed_magnitude, boost::multiprecision::unchecked, void>>

Signed 128-bit integer.

Aliases the native __int128_t extension when the compiler provides it (recent g++ and clang++). On toolchains without it (e.g. MSVC) it falls back to Boost.Multiprecision's fixed-width 128-bit integer; Boost is only included in that fallback case.

MonotoneChainView

template<class PointType = Point<>, class Label = NoLabel>

using pgl::MonotoneChainView = MonotoneChain<PointType, Label, std::span<const PointType>>

A non-owning MonotoneChain that views an external, already canonical (sorted, duplicate-free) contiguous range of vertices.

MonotoneChainView shares every read-only operation with the owning chain — it is just MonotoneChain instantiated over a std::span — but the caller owns the underlying storage and is responsible for keeping it alive and canonical for the view's lifetime. Mutating operations (insert, in-place scaling/rotation, operator*=, …) are not available; transformations that return a chain yield an owning MonotoneChain instead.

rational_int_t

template<class T>

using pgl::rational_int_t = typename rational_int<T>::type

to_integer_with_digits_t

template<typename T>

using pgl::to_integer_with_digits_t = typename to_integer_with_digits<T>::type

Enumeration Type Documentation

BoundaryContact

enum class pgl::BoundaryContact

strong

How two edge sets meet, as classified by redBlueSweep.

The three states are deliberately asymmetric in strength, because the sweep stops at the first crossing it sees rather than enumerating everything:

• BoundaryContact::Disjoint is a complete claim: no red edge meets any blue edge, anywhere.
• BoundaryContact::Crossing is a verified claim: a concrete pair was checked with Segment::crosses and does properly cross.
• BoundaryContact::Touching means the boundaries do meet and no crossing pair was found — which is not quite the same as there being none, since the search for one stops early in a few degenerate corners (see redBlueSweep). A caller that needs certainty either way must treat it as "meets, crossing status unknown" and settle the question by other means; a caller that only wants to skip work when the boundaries are clear of each other can rely on BoundaryContact::Disjoint.

Enumerator
Disjoint	No red edge meets any blue edge.
Touching	The two edge sets meet; no crossing pair was found.
Crossing	A red edge properly crosses a blue edge.

CanvasProperty

enum class pgl::CanvasProperty

strong

Names the style property targeted by a canvas command.

Enumerator
stroke
fill
fillOpacity
strokeOpacity
strokeWidth
pointRadius

GridAdjacency

enum class pgl::GridAdjacency

strong

Which grid cells count as neighbors.

edge is 4-adjacency (cells sharing a side), vertex is 8-adjacency (cells sharing a side or only a corner).

Enumerator
edge
vertex

ProjectionAxis

enum class pgl::ProjectionAxis

strong

Axis used to project a shape's bounding box into an interval.

Enumerator
x
y

Function Documentation

abs()

BigInt pgl::abs ( const BigInt & v )

inline

Free-function absolute value, matching the integer helpers.

BitMatrix() [1/6]

template<class PointType, class LabelType>

pgl::BitMatrix

(

const Polygon< PointType, LabelType > &

)

-> BitMatrix< PointType >

BitMatrix() [2/6]

template<class PointType, class LabelType>

pgl::BitMatrix

(

const PolygonSet< PointType, LabelType > &

)

-> BitMatrix< PointType >

BitMatrix() [3/6]

template<class PointType, class LabelType>

pgl::BitMatrix

(

const PolygonWithHoles< PointType, LabelType > &

)

-> BitMatrix< PointType >

BitMatrix() [4/6]

template<class PointType, class LabelType>

pgl::BitMatrix

(

const Rectangle< PointType, LabelType > &

)

-> BitMatrix< PointType >

BitMatrix() [5/6]

template<class PointType>

pgl::BitMatrix	(	PointType	,
		int	,
		int	) -> BitMatrix< PointType >

BitMatrix() [6/6]

template<std::ranges::input_range Range>
requires (detail::is_point_v<std::remove_cvref_t<std::ranges::range_value_t<Range>>> && !AnyShapeConcept<std::remove_cvref_t
<Range>> && !detail::is_bit_matrix_v<std::remove_cvref_t<Range>>)

pgl::BitMatrix

(

Range &&

)

-> BitMatrix< std::remove_cvref_t< std::ranges::range_value_t< Range > > >

boundariesCross()

template<class RedRange, class BlueRange>

bool pgl::boundariesCross	(	const RedRange &	red,
		const BlueRange &	blue )

True exactly when some red edge properly crosses some blue edge.

A bool-returning shorthand for redBlueSweep(red, blue) == BoundaryContact::Crossing, for callers that only need that one bit and would otherwise have to name BoundaryContact themselves. Naming it from a call site defined earlier in the include order than this header — such as PolygonWithHoles::areaContains in implementation/contains.hpp — would require the enum to already be visible there, which the library's layering does not guarantee; a dependent call to this function, by contrast, is resolved by argument-dependent lookup at instantiation time, so it works regardless of physical include order as long as this header is reachable by then (which the umbrella pgl.hpp guarantees).

boundariesMeet()

template<class RedRange, class BlueRange>

bool pgl::boundariesMeet	(	const RedRange &	red,
		const BlueRange &	blue )

True exactly when some red edge meets some blue edge, crossing or not.

A bool-returning shorthand for redBlueSweep(red, blue) != BoundaryContact::Disjoint; see boundariesCross for why this exists as a dependent-call wrapper rather than a direct comparison at the call site.

boundaryContactBits()

template<class RedRange, class BlueRange>

SweepContact pgl::boundaryContactBits	(	const RedRange &	red,
		const BlueRange &	blue )

bruteForceCrossings()

template<class Rational = pgl::Rational<pgl::BigInt>, class Container>

auto pgl::bruteForceCrossings

(

const Container &

segments

)

Finds all crossing segment pairs by brute force.

Checks every unordered pair in quadratic time.

Template Parameters

Rational	Unused template parameter kept for API symmetry.
Container	Container of segment-like values.

Parameters

segments

Input segment container.

Returns

Vector of crossing segment pairs.

bruteForceIntersections()

template<class Rational = pgl::Rational<pgl::BigInt>, class Container>

auto pgl::bruteForceIntersections

(

const Container &

segments

)

Finds all intersecting segment pairs by brute force.

Checks every unordered pair in quadratic time.

Template Parameters

Rational	Unused template parameter kept for API symmetry.
Container	Container of segment-like values.

Parameters

segments

Input segment container.

Returns

Vector of intersecting segment pairs.

closestPair()

template<class Container>

Segment< detail::closest_pair_input_point_t< Container > > pgl::closestPair ( const Container & input )

nodiscard

Computes a closest pair of points by divide and conquer.

The points are sorted by abscissa and split in half by a vertical line. Each half is solved recursively, and only the points lying within the better of the two half-solutions of the split line can still form a closer pair; sorting that strip by ordinate and scanning it settles them in linear time.

The recursion stops and tries every pair once a range gets small enough that brute force is the cheaper of the two; where that is depends on the coordinate type, see detail::closestPairBruteForceThreshold.

Only squared distances are compared, in the promoted coordinate type, so the result is exact for integer coordinates. Ties are broken arbitrarily. The returned segment keeps the input point type, labels included, and orders its endpoints like any other Segment.

Template Parameters

Container

Container of pgl points.

Parameters

input

Input points; they are copied and the container is not modified.

Precondition

input holds at least two points; fewer is undefined behavior.

Returns

Segment joining two points at minimum distance from each other.

@complexity O(n log n) time on inputs whose strips stay short, which is the ordinary case; O(n log^2 n) worst case, approached when the points are so clustered along one line that the strip keeps holding a constant fraction of the range. O(n) additional space.

collinear()

template<class ANumber, class ALabel, class BNumber, class BLabel, class CNumber, class CLabel>

bool pgl::collinear ( const Point< ANumber, ALabel > & a, const Point< BNumber, BLabel > & b, const Point< CNumber, CLabel > & c )

constexpr

Tests whether three points are collinear.

Parameters

a	First point.
b	Second point.
c	Third point.

Returns

true if the points lie on a common line.

Parameters

a	First point.
b	Second point.
c	Third point.

Returns

true if the orientation determinant vanishes.

Convex() [1/4]

pgl::Convex

(

)

-> Convex< Point<>, NoLabel >

Convex() [2/4]

template<std::ranges::input_range Range>
requires detail::is_point_v<std::ranges::range_value_t<Range>>

pgl::Convex

(

Range &&

)

-> Convex< std::remove_cvref_t< std::ranges::range_value_t< Range > >, NoLabel >

Convex() [3/4]

template<class Number>
requires (!detail::is_point_v<Number>)

pgl::Convex

(

std::initializer_list< Number >

)

-> Convex< Point< Number >, NoLabel >

Convex() [4/4]

template<class Number>
requires (!detail::is_point_v<Number>)

pgl::Convex	(	std::initializer_list< Number >	,
		bool	) -> Convex< Point< Number >, NoLabel >

convexHull()

template<class Container>

auto pgl::convexHull

(

const Container &

points_

)

Computes the convex hull of a point container.

Collinear points on hull edges are discarded, so the returned hull contains only the extreme vertices. convexHullExtended keeps them.

Template Parameters

Container

Container whose value type is a pgl point type.

Parameters

points_

Input points.

Returns

Hull vertices in boundary order.

convexHullExtended()

template<class Container>

auto pgl::convexHullExtended

(

const Container &

points_

)

Computes the convex hull of a point container.

Collinear points on hull edges are kept, so the returned hull holds every input point on its boundary. convexHull returns the vertices alone.

Template Parameters

Container

Container whose value type is a pgl point type.

Parameters

points_

Input points.

Returns

Hull points in boundary order.

crossSign() [1/2]

template<class ANumber, class ALabel, class BNumber, class BLabel, class PNumber, class PLabel, class QNumber, class QLabel>

std::partial_ordering pgl::crossSign ( const Point< ANumber, ALabel > & a, const Point< BNumber, BLabel > & b, const Point< PNumber, PLabel > & p, const Point< QNumber, QLabel > & q )

constexpr

Classifies the turn from the direction a -> b to the direction p -> q.

The sign of (b - a) x (q - p), formed with a single promotion so that a caller holding two directions as four points never has to build — and possibly overflow — the difference vectors itself.

Parameters

a	Tail of the first direction.
b	Head of the first direction.
p	Tail of the second direction.
q	Head of the second direction.

Returns

Cross-product sign of the two directions.

crossSign() [2/2]

template<class UNumber, class ULabel, class VNumber, class VLabel>

std::partial_ordering pgl::crossSign ( const Point< UNumber, ULabel > & u, const Point< VNumber, VLabel > & v )

constexpr

Classifies the turn from one vector to another.

The sign of the 2D cross product u x v: positive when v lies counterclockwise from u within half a turn, negative when it lies clockwise, and equivalence when the two are parallel or one is zero. This is orientationSign in vector form — orientationSign(a, b, c) is crossSign(b - a, c - a) — and is what the many call sites that already hold directions rather than point triples need.

Parameters

u	First vector.
v	Second vector.

Returns

Cross-product sign of (u, v).

detectCrossings()

template<class Rational = pgl::Rational<pgl::BigInt>, class Container>

bool pgl::detectCrossings

(

const Container &

segments

)

Detects whether any two segments properly cross.

Runs in O(n log n) in the positive or negative detection mode used here.

Template Parameters

Rational	Exact rational type used internally by the sweep line.
Container	Container of segment-like values.

Parameters

segments

Input segment container.

Returns

true if at least one crossing pair exists.

Warning

Needs rational numbers, preferably with unbonded size

detectIntersections()

template<class Rational = pgl::Rational<pgl::BigInt>, class Container>

bool pgl::detectIntersections

(

const Container &

segments

)

Detects whether any two segments intersect.

Runs in O(n log n) in the positive or negative detection mode used here.

Template Parameters

Rational	Exact rational type used internally by the sweep line.
Container	Container of segment-like values.

Parameters

segments

Input segment container.

Returns

true if at least one intersecting pair exists.

Warning

Needs rational numbers, preferably with unbonded size

Disk() [1/4]

pgl::Disk

(

)

-> Disk< Point<>, NoLabel >

Deduces a default disk with Point<> boundary points and no label.

Disk() [2/4]

template<class Number>

pgl::Disk	(	Number	,
		Number	,
		Number	) -> Disk< Point< Number >, NoLabel >

Deduces a disk from center coordinates and a radius.

Disk() [3/4]

template<PointConcept PointType>

pgl::Disk	(	PointType	,
		PointType	,
		PointType	) -> Disk< PointType, NoLabel >

Deduces a disk from three boundary points.

Disk() [4/4]

template<class PointType>

pgl::Disk	(	PointType	,
		typename PointType::NumberType	) -> Disk< PointType, NoLabel >

Deduces a disk from a center point and a radius.

dotSign() [1/2]

template<class ANumber, class ALabel, class BNumber, class BLabel>

std::partial_ordering pgl::dotSign ( const Point< ANumber, ALabel > & a, const Point< BNumber, BLabel > & b )

constexpr

Tells if the angle between two vectors is acute, right, or obtuse.

Parameters

a	First vector.
b	Second vector.

Returns

Negative for obtuse angle, positive for acute angle, and equivalence for right angle.

dotSign() [2/2]

template<class ANumber, class ALabel, class BNumber, class BLabel, class PNumber, class PLabel, class QNumber, class QLabel>

std::partial_ordering pgl::dotSign ( const Point< ANumber, ALabel > & a, const Point< BNumber, BLabel > & b, const Point< PNumber, PLabel > & p, const Point< QNumber, QLabel > & q )

constexpr

Tells if the angle between the directions a -> b and p -> q is acute, right, or obtuse.

The sign of (b - a) . (q - p), formed with a single promotion. Ordering points along a direction is the common use: t comes before u along d exactly when dotSign(t, u, tail, head) > 0 for a direction tail -> head.

Parameters

a	Tail of the first direction.
b	Head of the first direction.
p	Tail of the second direction.
q	Head of the second direction.

Returns

Negative for obtuse, positive for acute, equivalence for right.

fill()

CanvasCommand pgl::fill ( std::string value )

inline

Creates a command that changes the current fill color.

fillOpacity()

CanvasCommand pgl::fillOpacity ( std::string value )

inline

Creates a command that changes the current fill opacity.

findCrossings()

template<class Rational = pgl::Rational<pgl::BigInt>, class Container>

auto pgl::findCrossings

(

const Container &

segments

)

Finds all proper crossing segment pairs with Bentley-Ottmann.

Runs in O((n + k) log n) where n is the number of input segments and k is the number of reported crossing pairs.

Template Parameters

Rational	Exact rational type used internally by the sweep line.
Container	Container of segment-like values.

Parameters

segments

Input segment container.

Returns

Vector of crossing segment pairs.

Warning

Needs rational numbers, preferably with unbonded size

findIntersections()

template<class Rational = pgl::Rational<pgl::BigInt>, class Container>

auto pgl::findIntersections

(

const Container &

segments

)

Finds all intersecting segment pairs with Bentley-Ottmann.

Runs in O((n + k) log n) where n is the number of input segments and k is the number of reported pairs.

Template Parameters

Rational	Exact rational type used internally by the sweep line.
Container	Container of segment-like values.

Parameters

segments

Input segment container.

Returns

Vector of intersecting segment pairs.

Warning

Needs rational numbers, preferably with unbonded size

grahamScan()

template<class Container>

auto pgl::grahamScan

(

const Container &

points_

)

Computes the convex hull of a point container using Graham's scan.

Collinear points on hull edges are discarded, so the returned hull contains only the extreme vertices.

Template Parameters

Container

Container whose value type is a pgl point type.

Parameters

points_

Input points.

Returns

Hull vertices in boundary order.

grahamScanExtended()

template<class Container>

auto pgl::grahamScanExtended

(

const Container &

points_

)

Computes the convex hull of a point container using Graham's scan.

Collinear points on hull edges are kept, so the returned hull holds every input point on its boundary, not only the extreme vertices.

Template Parameters

Container

Container whose value type is a pgl point type.

Parameters

points_

Input points.

Returns

Hull points in boundary order.

Halfplane() [1/4]

pgl::Halfplane

(

)

-> Halfplane< Point<>, NoLabel >

Halfplane() [2/4]

template<class Number>

pgl::Halfplane	(	Number	,
		Number	,
		Number	,
		Number	) -> Halfplane< Point< Number >, NoLabel >

Halfplane() [3/4]

template<class PointType>

pgl::Halfplane	(	PointType	,
		PointType	) -> Halfplane< PointType, NoLabel >

Halfplane() [4/4]

template<class PointType, class A>

pgl::Halfplane	(	PointType	,
		PointType	,
		A	) -> Halfplane< PointType, std::decay_t< A > >

HalfplaneIntersection() [1/10]

pgl::HalfplaneIntersection

(

)

-> HalfplaneIntersection< Point<>, NoLabel >

HalfplaneIntersection() [2/10]

template<ConvexConcept C>

pgl::HalfplaneIntersection

(

const C &

)

-> HalfplaneIntersection< typename C::PointType, NoLabel >

HalfplaneIntersection() [3/10]

template<HalfplaneConcept H>

pgl::HalfplaneIntersection

(

const H &

)

-> HalfplaneIntersection< typename H::PointType, NoLabel >

HalfplaneIntersection() [4/10]

template<LineConcept L>

pgl::HalfplaneIntersection

(

const L &

)

-> HalfplaneIntersection< typename L::PointType, NoLabel >

HalfplaneIntersection() [5/10]

template<PointConcept P>

pgl::HalfplaneIntersection

(

const P &

)

-> HalfplaneIntersection< Point< typename P::NumberType, typename P::LabelType >, NoLabel >

HalfplaneIntersection() [6/10]

template<RectangleConcept R>

pgl::HalfplaneIntersection

(

const R &

)

-> HalfplaneIntersection< typename R::PointType, NoLabel >

HalfplaneIntersection() [7/10]

template<SegmentConcept S>

pgl::HalfplaneIntersection

(

const S &

)

-> HalfplaneIntersection< typename S::PointType, NoLabel >

HalfplaneIntersection() [8/10]

template<TriangleConcept T>

pgl::HalfplaneIntersection

(

const T &

)

-> HalfplaneIntersection< typename T::PointType, NoLabel >

HalfplaneIntersection() [9/10]

template<std::ranges::input_range Range>
requires detail::is_halfplane_v<std::ranges::range_value_t<Range>>

pgl::HalfplaneIntersection

(

Range &&

)

-> HalfplaneIntersection< typename std::remove_cvref_t< std::ranges::range_value_t< Range > >::PointType, NoLabel >

HalfplaneIntersection() [10/10]

template<std::ranges::input_range Range>
requires detail::is_halfplane_v<std::ranges::range_value_t<Range>>

pgl::HalfplaneIntersection	(	Range &&	,
		bool	) -> HalfplaneIntersection< typename std::remove_cvref_t< std::ranges::range_value_t< Range > >::PointType, NoLabel >

hilbertSort()

template<class Number, class Label>

void pgl::hilbertSort

(

std::vector< Point< Number, Label > > &

points

)

Sorts points along a Hilbert space-filling curve.

Reorders points in place so that points close together in the plane are close together in the sequence. This spatial coherence makes the order a useful preprocessing step for incremental algorithms — for example, inserting points in Hilbert order keeps each point-location walk short.

The order is produced by the median policy: the set is recursively split into four quadrants by nested medians, following the Hilbert curve's recursive structure. Only coordinate comparisons are used, so the result is exact for integer coordinates and well defined for any numeric type.

Template Parameters

Number	Coordinate type of the points.
Label	Label type of the points.

Parameters

points

Points to reorder in place.

inCircleDeterminant()

template<class ANumber, class ALabel, class BNumber, class BLabel, class CNumber, class CLabel, class DNumber, class DLabel>

auto pgl::inCircleDeterminant ( const Point< ANumber, ALabel > & a, const Point< BNumber, BLabel > & b, const Point< CNumber, CLabel > & c, const Point< DNumber, DLabel > & d )

constexpr

Returns the signed in-circle determinant of a query point.

Points a, b, and c define the circumcircle; the returned value is the 3x3 determinant whose rows are (p - d) augmented with |p - d|^2 for p in {a, b, c}. It equals -2 * signedArea(a,b,c) * power(d), where power(d) = |d - center|^2 - radius^2, so its sign classifies d against the circle (like inCircleSign) while its magnitude is the exact, scaled power of d — the basis for division-free circle/segment predicates.

Parameters

a	First circle point.
b	Second circle point.
c	Third circle point.
d	Query point.

Returns

The in-circle determinant in a promoted coordinate type.

inCircleSign()

template<class ANumber, class ALabel, class BNumber, class BLabel, class CNumber, class CLabel, class DNumber, class DLabel>

std::partial_ordering pgl::inCircleSign ( const Point< ANumber, ALabel > & a, const Point< BNumber, BLabel > & b, const Point< CNumber, CLabel > & c, const Point< DNumber, DLabel > & d )

constexpr

Classifies a point with respect to the circumcircle of three others.

Points a, b, and c define the circumcircle. The sign convention assumes counterclockwise orientation of (a,b,c) and flips when that orientation is reversed.

Parameters

a	First circle point.
b	Second circle point.
c	Third circle point.
d	Query point.

Returns

For counterclockwise (a,b,c): greater inside, equivalent on the boundary, less outside. The order is reversed for clockwise (a,b,c).

innerRaster() [1/2]

template<class PointType = Point<int>, class ShapeType>
requires std::signed_integral< std::remove_cvref_t<decltype(std::declval<const ShapeType&>().bbox().min().x())>>

BitMatrix< PointType > pgl::innerRaster

(

const ShapeType &

shape

)

Rasterizes a bounded shape over its own bounding box.

Template Parameters

PointType

Cell type of the result; Point<int> unless given.

Parameters

shape

Bounded shape with integer coordinates.

innerRaster() [2/2]

template<class PointType, class ShapeType>

BitMatrix< PointType > pgl::innerRaster	(	const ShapeType &	shape,
		const Rectangle< PointType > &	window )

Rasterizes a shape into the cells it covers: its inner approximation.

A cell is set when the shape contains the whole of it, so the result is covered by the shape. Costs one exact predicate per cell of window.

Template Parameters

PointType

Cell type of the result, deduced from window.

Parameters

shape	Shape to rasterize.
window	Window of the result, read as BitMatrix::BitMatrix(const RectangleType&) reads it.

IntervalTree()

template<class Container>

pgl::IntervalTree

(

const Container &

)

-> IntervalTree< typename Container::value_type >

Line() [1/4]

pgl::Line

(

)

-> Line< Point<>, NoLabel >

Line() [2/4]

template<class Number>

pgl::Line	(	Number	,
		Number	,
		Number	,
		Number	) -> Line< Point< Number >, NoLabel >

Line() [3/4]

template<class PointType>

pgl::Line	(	PointType	,
		PointType	) -> Line< PointType, NoLabel >

Line() [4/4]

template<class PointType, class A>

pgl::Line	(	PointType	,
		PointType	,
		A	) -> Line< PointType, std::decay_t< A > >

MonotoneChain() [1/5]

pgl::MonotoneChain

(

)

-> MonotoneChain< Point<>, NoLabel >

MonotoneChain() [2/5]

template<std::ranges::input_range Range>
requires detail::is_point_v<std::ranges::range_value_t<Range>>

pgl::MonotoneChain

(

Range &&

)

-> MonotoneChain< std::remove_cvref_t< std::ranges::range_value_t< Range > >, NoLabel >

MonotoneChain() [3/5]

template<std::ranges::input_range Range>
requires detail::is_point_v<std::ranges::range_value_t<Range>>

pgl::MonotoneChain	(	Range &&	,
		bool	) -> MonotoneChain< std::remove_cvref_t< std::ranges::range_value_t< Range > >, NoLabel >

MonotoneChain() [4/5]

template<class Number>
requires (!detail::is_point_v<Number>)

pgl::MonotoneChain

(

std::initializer_list< Number >

)

-> MonotoneChain< Point< Number >, NoLabel >

MonotoneChain() [5/5]

template<class Number>
requires (!detail::is_point_v<Number>)

pgl::MonotoneChain	(	std::initializer_list< Number >	,
		bool	) -> MonotoneChain< Point< Number >, NoLabel >

operator*() [1/41]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Convex< PointType, LabelType > & convex, const Scalar & scalar )

constexpr

operator*() [2/41]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Disk< PointType, LabelType > & disk, const Scalar & scalar )

constexpr

Returns a copy of disk with every boundary point scaled by scalar.

operator*() [3/41]

template<class PointType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const EmptyShape< PointType > & , const Scalar &  )

constexpr

Scales the empty shape around the origin; a no-op.

The empty set has no points to scale, so it is returned unchanged, over the promoted point type to mirror the coordinate promotion of the other shapes' scaling.

Returns

The empty shape over the promoted point type.

operator*() [4/41]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Halfplane< PointType, LabelType > & halfplane, const Scalar & scalar )

constexpr

operator*() [5/41]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const HalfplaneIntersection< PointType, LabelType > & region, const Scalar & scalar )

constexpr

Scales a region around the origin.

The coordinate type is promoted to match the scalar, mirroring the other shapes' free scaling operators.

operator*() [6/41]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Line< PointType, LabelType > & line, const Scalar & scalar )

constexpr

Scales a line by a scalar.

Template Parameters

PointType	Defining point type of the line.
Scalar	Scalar type.

Parameters

line	Line to scale.
scalar	Scale factor.

Returns

Scaled line.

operator*() [7/41]

template<class PointType, class LabelType, class Storage, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const MonotoneChain< PointType, LabelType, Storage > & chain, const Scalar & scalar )

constexpr

operator*() [8/41]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const OrientedLine< PointType, LabelType > & line, const Scalar & scalar )

constexpr

operator*() [9/41]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const OrientedSegment< PointType, LabelType > & segment, const Scalar & scalar )

constexpr

Scales an oriented segment by a scalar.

Template Parameters

Number	Coordinate type of the segment endpoints.
Label	Label type of the segment endpoints.
Scalar	Scalar type.

Parameters

segment	Oriented segment to scale.
scalar	Scale factor.

Returns

Scaled oriented segment.

operator*() [10/41]

template<class LeftNumber, class LeftLabel, class RightNumber, class RightLabel>

auto pgl::operator* ( const Point< LeftNumber, LeftLabel > & left, const Point< RightNumber, RightLabel > & right )

nodiscardconstexpr

Returns the dot product of two points.

Template Parameters

LeftNumber	Coordinate type of the left operand.
LeftLabel	Label type of the left operand.
RightNumber	Coordinate type of the right operand.
RightLabel	Label type of the right operand.

Parameters

left	Left point.
right	Right point.

Returns

Dot product.

operator*() [11/41]

template<class Number, class Label, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Point< Number, Label > & point, const Scalar & scalar )

nodiscardconstexpr

Scales a point by a scalar.

Template Parameters

Number	Coordinate type of the point.
Label	Label type of the point.
Scalar	Scalar type.

Parameters

point	Point to scale.
scalar	Scale factor.

Returns

Scaled point.

operator*() [12/41]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Polygon< PointType, LabelType > & polygon, const Scalar & scalar )

constexpr

operator*() [13/41]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const PolygonSet< PointType, LabelType > & set, const Scalar & scalar )

constexpr

operator*() [14/41]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const PolygonWithHoles< PointType, LabelType > & region, const Scalar & scalar )

constexpr

operator*() [15/41]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Polyline< PointType, LabelType > & polyline, const Scalar & scalar )

constexpr

operator*() [16/41]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Ray< PointType, LabelType > & ray, const Scalar & scalar )

constexpr

operator*() [17/41]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Rectangle< PointType, LabelType > & rectangle, const Scalar & scalar )

constexpr

Scales a rectangle by a scalar.

Template Parameters

NumberType	Coordinate type of the rectangle corners.
Label	Label type of the rectangle corners.
Scalar	Scalar type.

Parameters

rectangle	Rectangle to scale.
scalar	Scale factor.

Returns

Scaled rectangle.

operator*() [18/41]

template<class Scalar, class PointType, class LabelType>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const Convex< PointType, LabelType > & convex )

constexpr

operator*() [19/41]

template<class Scalar, class PointType, class LabelType>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const Disk< PointType, LabelType > & disk )

constexpr

Returns a copy of disk with every boundary point scaled by scalar.

operator*() [20/41]

template<class Scalar, class PointType>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const EmptyShape< PointType > & empty )

constexpr

Scales the empty shape around the origin; a no-op.

The empty set has no points to scale, so it is returned unchanged, over the promoted point type to mirror the coordinate promotion of the other shapes' scaling.

Returns

The empty shape over the promoted point type.

operator*() [21/41]

template<class Scalar, class PointType, class LabelType>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const Halfplane< PointType, LabelType > & halfplane )

constexpr

operator*() [22/41]

template<class Scalar, class PointType, class LabelType>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const HalfplaneIntersection< PointType, LabelType > & region )

constexpr

Scales a region around the origin.

The coordinate type is promoted to match the scalar, mirroring the other shapes' free scaling operators.

operator*() [23/41]

template<class Scalar, class PointType, class LabelType>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const Line< PointType, LabelType > & line )

constexpr

Scales a line by a scalar written on the left.

Template Parameters

Scalar	Scalar type.
PointType	Defining point type of the line.

Parameters

scalar	Scale factor.
line	Line to scale.

Returns

Scaled line.

operator*() [24/41]

template<class Scalar, class PointType, class LabelType, class Storage>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const MonotoneChain< PointType, LabelType, Storage > & chain )

constexpr

operator*() [25/41]

template<class Scalar, class PointType, class LabelType>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const OrientedLine< PointType, LabelType > & line )

constexpr

operator*() [26/41]

template<class Scalar, class PointType, class LabelType>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const OrientedSegment< PointType, LabelType > & segment )

constexpr

Scales an oriented segment by a scalar written on the left.

Template Parameters

Scalar	Scalar type.
Number	Coordinate type of the segment endpoints.
Label	Label type of the segment endpoints.

Parameters

scalar	Scale factor.
segment	Oriented segment to scale.

Returns

Scaled oriented segment.

operator*() [27/41]

template<class Scalar, class Number, class Label>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const Point< Number, Label > & point )

nodiscardconstexpr

Scales a point by a scalar written on the left.

Template Parameters

Scalar	Scalar type.
Number	Coordinate type of the point.
Label	Label type of the point.

Parameters

scalar	Scale factor.
point	Point to scale.

Returns

Scaled point.

operator*() [28/41]

template<class Scalar, class PointType, class LabelType>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const Polygon< PointType, LabelType > & polygon )

constexpr

operator*() [29/41]

template<class Scalar, class PointType, class LabelType>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const PolygonSet< PointType, LabelType > & set )

constexpr

operator*() [30/41]

template<class Scalar, class PointType, class LabelType>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const PolygonWithHoles< PointType, LabelType > & region )

constexpr

operator*() [31/41]

template<class Scalar, class PointType, class LabelType>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const Polyline< PointType, LabelType > & polyline )

constexpr

operator*() [32/41]

template<class Scalar, class PointType, class LabelType>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const Ray< PointType, LabelType > & ray )

constexpr

operator*() [33/41]

template<class Scalar, class PointType, class LabelType>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const Rectangle< PointType, LabelType > & rectangle )

constexpr

Scales a rectangle by a scalar written on the left.

Template Parameters

Scalar	Scalar type.
NumberType	Coordinate type of the rectangle corners.
Label	Label type of the rectangle corners.

Parameters

scalar	Scale factor.
rectangle	Rectangle to scale.

Returns

Scaled rectangle.

operator*() [34/41]

template<class Scalar, class PointType, class LabelType>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const Segment< PointType, LabelType > & segment )

constexpr

Scales a segment by a scalar written on the left.

Template Parameters

Scalar	Scalar type.
Number	Coordinate type of the segment endpoints.
Label	Label type of the segment endpoints.

Parameters

scalar	Scale factor.
segment	Segment to scale.

Returns

Scaled segment.

operator*() [35/41]

template<class Scalar, class PointType>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const Shape< PointType > & shape )

constexpr

Scales a shape around the origin.

Visits the stored alternative and scales it, re-wrapping the result. The coordinate type is promoted to match the scalar, mirroring the per-shape scaling operators.

Parameters

shape	Shape to scale.
scalar	Scaling factor.

Returns

Scaled shape over the promoted point type.

operator*() [36/41]

template<class Scalar, class PointType, class LabelType>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Scalar & scalar, const Triangle< PointType, LabelType > & triangle )

constexpr

Returns a scaled copy of a triangle with the scalar on the left.

operator*() [37/41]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Segment< PointType, LabelType > & segment, const Scalar & scalar )

constexpr

Scales a segment by a scalar.

Template Parameters

Number	Coordinate type of the segment endpoints.
Label	Label type of the segment endpoints.
Scalar	Scalar type.

Parameters

segment	Segment to scale.
scalar	Scale factor.

Returns

Scaled segment.

operator*() [38/41]

template<class PointType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Shape< PointType > & shape, const Scalar & scalar )

constexpr

Scales a shape around the origin.

Visits the stored alternative and scales it, re-wrapping the result. The coordinate type is promoted to match the scalar, mirroring the per-shape scaling operators.

Parameters

shape	Shape to scale.
scalar	Scaling factor.

Returns

Scaled shape over the promoted point type.

operator*() [39/41]

template<class Number, ShapeConcept ShapeT>

auto pgl::operator* ( const Transformation< Number > & transformation, const ShapeT & shape )

nodiscardconstexpr

Applies a transformation to the polymorphic Shape wrapper.

Exceptions

std::logic_error

if the wrapped alternative is Rectangle or Disk.

operator*() [40/41]

template<class Number, class ShapeT>
requires (detail::shapeRank<ShapeT> >= 0 && !RectangleConcept<ShapeT> && !DiskConcept<ShapeT>)

auto pgl::operator* ( const Transformation< Number > & transformation, const ShapeT & shape )

nodiscardconstexpr

Applies a transformation to any supported shape.

Defined for every shape except Rectangle and Disk: a general affine map turns a rectangle into a parallelogram and a disk into an ellipse, and neither class can represent that, so no overload is provided for them.

Template Parameters

Number	Entry type of transformation.
ShapeT	Shape type; must not be Rectangle or Disk.

Parameters

transformation	Transformation to apply.
shape	Shape to transform.

Returns

The transformed shape, with a coordinate type promoted via std::common_type_t<Number, ShapeT::NumberType>.

operator*() [41/41]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator* ( const Triangle< PointType, LabelType > & triangle, const Scalar & scalar )

constexpr

Returns a scaled copy of a triangle.

operator+() [1/2]

template<class A, class B>
requires MinkowskiSummableConcept<A, B>

auto pgl::operator+ ( const A & a, const B & b )

nodiscardconstexpr

Returns the Minkowski sum a ⊕ b, the same as a.minkowskiSum(b).

Summing a shape with a Point is a translation, which is the reading this operator has always had; the remaining supported pairs (MinkowskiSummableConcept) extend it to the operation + denotes for point sets.

operator+() [2/2]

template<class PointType>

BitMatrix< PointType > pgl::operator+	(	const PointType &	vector,
		const BitMatrix< PointType > &	matrix )

Returns the same cells translated by a vector.

operator-() [1/19]

template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const Convex< PointType, LabelType > & convex, const Point< TranslationNumber, TranslationLabel > & translation )

constexpr

operator-() [2/19]

template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const Disk< PointType, LabelType > & disk, const Point< TranslationNumber, TranslationLabel > & translation )

constexpr

Returns a copy of disk translated by translation.

Returns a copy of disk translated by translation.

Returns a copy of disk translated by -translation.

operator-() [3/19]

template<class PointType, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const EmptyShape< PointType > & , const Point< TranslationNumber, TranslationLabel > &  )

constexpr

Translates the empty shape by a negated point; a no-op.

The empty set has no points to move, so it is returned unchanged, over the promoted point type to mirror the coordinate promotion of the other shapes' translation.

Returns

The empty shape over the promoted point type.

operator-() [4/19]

template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const Halfplane< PointType, LabelType > & halfplane, const Point< TranslationNumber, TranslationLabel > & translation )

constexpr

operator-() [5/19]

template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const HalfplaneIntersection< PointType, LabelType > & region, const Point< TranslationNumber, TranslationLabel > & translation )

constexpr

Translates a region by a negated point.

operator-() [6/19]

template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const Line< PointType, LabelType > & line, const Point< TranslationNumber, TranslationLabel > & translation )

constexpr

Translates a line by the opposite of a point.

Template Parameters

PointType	Defining point type of the line.
TranslationNumber	Coordinate type of the translation point.
TranslationLabel	Label type of the translation point.

Parameters

line	Line to translate.
translation	Translation vector to subtract.

Returns

Translated line.

operator-() [7/19]

template<class PointType, class LabelType, class Storage, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const MonotoneChain< PointType, LabelType, Storage > & chain, const Point< TranslationNumber, TranslationLabel > & translation )

constexpr

operator-() [8/19]

template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const OrientedLine< PointType, LabelType > & line, const Point< TranslationNumber, TranslationLabel > & translation )

constexpr

operator-() [9/19]

template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const OrientedSegment< PointType, LabelType > & segment, const Point< TranslationNumber, TranslationLabel > & translation )

constexpr

Translates an oriented segment by the opposite of a point.

Template Parameters

Number	Coordinate type of the segment endpoints.
Label	Label type of the segment endpoints.
TranslationNumber	Coordinate type of the translation point.
TranslationLabel	Label type of the translation point.

Parameters

segment	Oriented segment to translate.
translation	Translation vector to subtract.

Returns

Translated oriented segment.

operator-() [10/19]

template<class LeftNumber, class LeftLabel, class RightNumber, class RightLabel>

auto pgl::operator- ( const Point< LeftNumber, LeftLabel > & left, const Point< RightNumber, RightLabel > & right )

nodiscardconstexpr

Translates a point by the opposite of another point.

Template Parameters

LeftNumber	Coordinate type of the left operand.
LeftLabel	Label type of the left operand.
RightNumber	Coordinate type of the right operand.
RightLabel	Label type of the right operand.

Parameters

left	Point to translate.
right	Vector to subtract.

Returns

Translated point.

operator-() [11/19]

template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const Polygon< PointType, LabelType > & polygon, const Point< TranslationNumber, TranslationLabel > & translation )

constexpr

operator-() [12/19]

template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const PolygonSet< PointType, LabelType > & set, const Point< TranslationNumber, TranslationLabel > & translation )

constexpr

Returns a copy of a set translated by the opposite point.

operator-() [13/19]

template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const PolygonWithHoles< PointType, LabelType > & region, const Point< TranslationNumber, TranslationLabel > & translation )

constexpr

Returns a copy of a region translated by the opposite point.

operator-() [14/19]

template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const Polyline< PointType, LabelType > & polyline, const Point< TranslationNumber, TranslationLabel > & translation )

constexpr

operator-() [15/19]

template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const Ray< PointType, LabelType > & ray, const Point< TranslationNumber, TranslationLabel > & translation )

constexpr

operator-() [16/19]

template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const Rectangle< PointType, LabelType > & rectangle, const Point< TranslationNumber, TranslationLabel > & translation )

constexpr

Translates a rectangle by the opposite of a point.

Template Parameters

NumberType	Coordinate type of the rectangle corners.
Label	Label type of the rectangle corners.
TranslationNumber	Coordinate type of the translation point.
TranslationLabel	Label type of the translation point.

Parameters

rectangle	Rectangle to translate.
translation	Translation vector to subtract.

Returns

Translated rectangle.

operator-() [17/19]

template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const Segment< PointType, LabelType > & segment, const Point< TranslationNumber, TranslationLabel > & translation )

constexpr

Translates a segment by the opposite of a point.

Template Parameters

Number	Coordinate type of the segment endpoints.
Label	Label type of the segment endpoints.
TranslationNumber	Coordinate type of the translation point.
TranslationLabel	Label type of the translation point.

Parameters

segment	Segment to translate.
translation	Translation vector to subtract.

Returns

Translated segment.

operator-() [18/19]

template<class PointType, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const Shape< PointType > & shape, const Point< TranslationNumber, TranslationLabel > & translation )

constexpr

Translates a shape by a negated point.

Visits the stored alternative and translates it, re-wrapping the result. The coordinate type is promoted to match the translation, mirroring the per-shape translation operators.

Parameters

shape	Shape to translate.
translation	Translation vector.

Returns

Translated shape over the promoted point type.

operator-() [19/19]

template<class PointType, class LabelType, class TranslationNumber, class TranslationLabel>

auto pgl::operator- ( const Triangle< PointType, LabelType > & triangle, const Point< TranslationNumber, TranslationLabel > & translation )

constexpr

Returns a copy of a triangle translated by the opposite point.

operator/() [1/19]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const Convex< PointType, LabelType > & convex, const Scalar & scalar )

constexpr

operator/() [2/19]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const Disk< PointType, LabelType > & disk, const Scalar & scalar )

constexpr

Returns a copy of disk with every boundary point divided by scalar.

operator/() [3/19]

template<class PointType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const EmptyShape< PointType > & , const Scalar &  )

constexpr

Divides the empty shape around the origin; a no-op.

The empty set has no points to scale, so it is returned unchanged, over the promoted point type to mirror the coordinate promotion of the other shapes' scaling.

Returns

The empty shape over the promoted point type.

operator/() [4/19]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const Halfplane< PointType, LabelType > & halfplane, const Scalar & scalar )

constexpr

operator/() [5/19]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const HalfplaneIntersection< PointType, LabelType > & region, const Scalar & scalar )

constexpr

Divides a region around the origin.

Warning

Divides coordinates, so the result is generally inexact for integer coordinate types.

operator/() [6/19]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const Line< PointType, LabelType > & line, const Scalar & scalar )

constexpr

Divides both defining points by a scalar.

Template Parameters

PointType	Defining point type of the line.
Scalar	Scalar type.

Parameters

line	Line to divide.
scalar	Divisor.

Returns

Scaled line.

operator/() [7/19]

template<class PointType, class LabelType, class Storage, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const MonotoneChain< PointType, LabelType, Storage > & chain, const Scalar & scalar )

constexpr

operator/() [8/19]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const OrientedLine< PointType, LabelType > & line, const Scalar & scalar )

constexpr

operator/() [9/19]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const OrientedSegment< PointType, LabelType > & segment, const Scalar & scalar )

constexpr

Divides both endpoints by a scalar.

Template Parameters

Number	Coordinate type of the segment endpoints.
Label	Label type of the segment endpoints.
Scalar	Scalar type.

Parameters

segment	Oriented segment to divide.
scalar	Divisor.

Returns

Scaled oriented segment.

operator/() [10/19]

template<class Number, class Label, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const Point< Number, Label > & point, const Scalar & scalar )

nodiscardconstexpr

Divides both coordinates by a scalar.

Template Parameters

Number	Coordinate type of the point.
Label	Label type of the point.
Scalar	Scalar type.

Parameters

point	Point to divide.
scalar	Divisor.

Returns

Scaled point.

operator/() [11/19]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const Polygon< PointType, LabelType > & polygon, const Scalar & scalar )

constexpr

operator/() [12/19]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const PolygonSet< PointType, LabelType > & set, const Scalar & scalar )

constexpr

operator/() [13/19]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const PolygonWithHoles< PointType, LabelType > & region, const Scalar & scalar )

constexpr

operator/() [14/19]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const Polyline< PointType, LabelType > & polyline, const Scalar & scalar )

constexpr

operator/() [15/19]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const Ray< PointType, LabelType > & ray, const Scalar & scalar )

constexpr

operator/() [16/19]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const Rectangle< PointType, LabelType > & rectangle, const Scalar & scalar )

constexpr

Divides both rectangle corners by a scalar.

Template Parameters

NumberType	Coordinate type of the rectangle corners.
Label	Label type of the rectangle corners.
Scalar	Scalar type.

Parameters

rectangle	Rectangle to divide.
scalar	Divisor.

Returns

Scaled rectangle.

operator/() [17/19]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const Segment< PointType, LabelType > & segment, const Scalar & scalar )

constexpr

Divides both endpoints by a scalar.

Template Parameters

Number	Coordinate type of the segment endpoints.
Label	Label type of the segment endpoints.
Scalar	Scalar type.

Parameters

segment	Segment to divide.
scalar	Divisor.

Returns

Scaled segment.

operator/() [18/19]

template<class PointType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const Shape< PointType > & shape, const Scalar & scalar )

constexpr

Divides a shape around the origin.

Visits the stored alternative and divides it, re-wrapping the result. The coordinate type is promoted to match the scalar, mirroring the per-shape scaling operators.

Parameters

shape	Shape to scale.
scalar	Scaling factor.

Returns

Scaled shape over the promoted point type.

operator/() [19/19]

template<class PointType, class LabelType, class Scalar>
requires (!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)

auto pgl::operator/ ( const Triangle< PointType, LabelType > & triangle, const Scalar & scalar )

constexpr

Returns a copy of a triangle divided by a scalar.

operator<<() [1/19]

template<class PointType, class LabelType>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const Convex< PointType, LabelType > &	convex )

Streams a Convex as Convex[(P1),(P2),(P3),(Pn)...].

Parameters

stream	Output stream.
convex	Convex to print.

Returns

The output stream.

operator<<() [2/19]

template<class PointType, class LabelType>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const Disk< PointType, LabelType > &	disk )

Streams a disk as ((p1)(p2)(p3)).

Writes disk to stream as Disk(a b c).

Parameters

stream	Output stream.
disk	Disk to print.

Returns

The output stream.

operator<<() [3/19]

template<class PointType>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const EmptyShape< PointType > &	)

Streams the empty shape.

Parameters

stream

Output stream.

Returns

The output stream.

operator<<() [4/19]

template<class PointType, class LabelType>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const Halfplane< PointType, LabelType > &	halfplane )

Streams a half-plane as ^-p--q-^.

Parameters

stream	Output stream.
halfplane	Half-plane to print.

Returns

The output stream.

operator<<() [5/19]

template<class PointType, class LabelType>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const HalfplaneIntersection< PointType, LabelType > &	region )

Streams a HalfplaneIntersection as HalfplaneIntersection[h1,h2,...].

The empty region prints as HalfplaneIntersection[empty] and the whole plane as HalfplaneIntersection[plane].

Parameters

stream	Output stream.
region	Region to print.

Returns

The same stream.

operator<<() [6/19]

template<class PointType, class LabelType>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const Line< PointType, LabelType > &	line )

Streams a line as -p--q-.

Parameters

stream	Output stream.
line	Line to print.

Returns

The output stream.

Template Parameters

PointType

Defining point type of the line.

Parameters

stream	Output stream.
line	Line to print.

Returns

The output stream.

operator<<() [7/19]

template<class PointType, class LabelType, class Storage>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const MonotoneChain< PointType, LabelType, Storage > &	chain )

Streams a MonotoneChain as MonotoneChain[(P1),(P2),(P3),...].

Parameters

stream	Output stream.
chain	Chain to print.

Returns

The output stream.

operator<<() [8/19]

template<class PointType, class LabelType>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const OrientedLine< PointType, LabelType > &	line )

Streams an oriented line as -p--q->.

Parameters

stream	Output stream.
line	Oriented line to print.

Returns

The output stream.

operator<<() [9/19]

template<class PointType, class LabelType>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const OrientedSegment< PointType, LabelType > &	segment )

Streams an oriented segment as p->q, or label:{p->q} when it carries a label.

Streams an oriented segment as p->q.

Uses source()/target() (not min()/max()): the orientation is part of the value.

Parameters

stream	Output stream.
segment	Oriented segment to print.

Returns

The output stream.

Template Parameters

Number	Coordinate type of the segment endpoints.
Label	Label type of the segment endpoints.

Parameters

stream	Output stream.
segment	Oriented segment to print.

Returns

The output stream.

operator<<() [10/19]

template<class Number, class Label>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const Point< Number, Label > &	point )

Streams a point as (x,y) or label:(x,y).

Parameters

stream	Output stream.
point	Point to print.

Returns

The output stream.

Template Parameters

Number	Coordinate type of the point.
Label	Label type of the point.

Parameters

stream	Output stream.
point	Point to print.

Returns

The output stream.

operator<<() [11/19]

template<class PointType, class LabelType>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const Polygon< PointType, LabelType > &	polygon )

Streams a Polygon as Polygon[(P1),(P2),(P3),(Pn)...].

Parameters

stream	Output stream.
polygon	Polygon to print.

Returns

The output stream.

operator<<() [12/19]

template<class PointType, class LabelType>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const PolygonSet< PointType, LabelType > &	set )

Streams a set as PolygonSet[components...].

Every component prints as an ordinary region, in the set's canonical order.

Parameters

stream	Output stream.
set	Set to print.

Returns

The output stream.

operator<<() [13/19]

template<class PointType, class LabelType>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const PolygonWithHoles< PointType, LabelType > &	region )

Streams a region as PolygonWithHoles[outer,holes...].

The outer boundary and every hole print as ordinary polygons, so the holes are distinguished by position rather than by orientation — matching the storage, which keeps every ring counterclockwise.

Parameters

stream	Output stream.
region	Region to print.

Returns

The output stream.

operator<<() [14/19]

template<class PointType, class LabelType>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const Polyline< PointType, LabelType > &	polyline )

Streams a Polyline as Polyline[(P1),(P2),(P3),...].

Parameters

stream	Output stream.
polyline	Polyline to print.

Returns

The output stream.

operator<<() [15/19]

template<class PointType, class LabelType>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const Ray< PointType, LabelType > &	ray )

Streams a ray as p--q->.

Parameters

stream	Output stream.
ray	Ray to print.

Returns

The output stream.

operator<<() [16/19]

template<class PointType, class LabelType>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const Rectangle< PointType, LabelType > &	rectangle )

Streams a rectangle as [min,max], or as [] when it is empty.

Streams a rectangle as [min,max].

Parameters

stream	Output stream.
rectangle	Rectangle to print.

Returns

The output stream.

Template Parameters

NumberType	Coordinate type of the rectangle corners.
Label	Label type of the rectangle corners.

Parameters

stream	Output stream.
rectangle	Rectangle to print.

Returns

The output stream.

operator<<() [17/19]

template<class PointType, class LabelType>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const Segment< PointType, LabelType > &	segment )

Streams a segment as p--q, or label:{p--q} when it carries a label.

Streams a segment as p--q.

Parameters

stream	Output stream.
segment	Segment to print.

Returns

The output stream.

Template Parameters

Number	Coordinate type of the segment endpoints.
Label	Label type of the segment endpoints.

Parameters

stream	Output stream.
segment	Segment to print.

Returns

The output stream.

operator<<() [18/19]

template<class PointType>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const Shape< PointType > &	shape )

Streams the currently stored alternative.

Template Parameters

PointType

Shared point type.

Parameters

stream	Output stream.
shape	Shape wrapper to print.

Returns

The output stream.

operator<<() [19/19]

template<class PointType, class LabelType>

std::ostream & pgl::operator<<	(	std::ostream &	stream,
		const Triangle< PointType, LabelType > &	triangle )

Streams a triangle as <abc>.

Streams a triangle as <abc> using canonical vertex order.

Parameters

stream	Output stream.
triangle	Triangle to print.

Returns

The output stream.

orientationDeterminant()

template<class ANumber, class ALabel, class BNumber, class BLabel, class CNumber, class CLabel>

auto pgl::orientationDeterminant ( const Point< ANumber, ALabel > & a, const Point< BNumber, BLabel > & b, const Point< CNumber, CLabel > & c )

constexpr

Returns the signed orientation determinant of three points.

Parameters

a	First point.
b	Second point.
c	Third point.

Returns

Determinant of vectors ab and ac.

orientationSign()

template<class ANumber, class ALabel, class BNumber, class BLabel, class CNumber, class CLabel>

std::partial_ordering pgl::orientationSign ( const Point< ANumber, ALabel > & a, const Point< BNumber, BLabel > & b, const Point< CNumber, CLabel > & c )

constexpr

Classifies the orientation of three points.

Returns negative for clockwise order, positive for counterclockwise order, and equivalence when the points are collinear.

Parameters

a	First point.
b	Second point.
c	Third point.

Returns

Orientation sign of (a,b,c).

OrientedLine() [1/4]

pgl::OrientedLine

(

)

-> OrientedLine< Point<>, NoLabel >

OrientedLine() [2/4]

template<class Number>

pgl::OrientedLine	(	Number	,
		Number	,
		Number	,
		Number	) -> OrientedLine< Point< Number >, NoLabel >

OrientedLine() [3/4]

template<class PointType>

pgl::OrientedLine	(	PointType	,
		PointType	) -> OrientedLine< PointType, NoLabel >

OrientedLine() [4/4]

template<class PointType, class A>

pgl::OrientedLine	(	PointType	,
		PointType	,
		A	) -> OrientedLine< PointType, std::decay_t< A > >

OrientedSegment() [1/4]

pgl::OrientedSegment

(

)

-> OrientedSegment< Point<>, NoLabel >

OrientedSegment() [2/4]

template<class Number>

pgl::OrientedSegment	(	Number	,
		Number	,
		Number	,
		Number	) -> OrientedSegment< Point< Number >, NoLabel >

OrientedSegment() [3/4]

template<class PointType>

pgl::OrientedSegment	(	PointType	,
		PointType	) -> OrientedSegment< PointType, NoLabel >

OrientedSegment() [4/4]

template<class PointType, class A>

pgl::OrientedSegment	(	PointType	,
		PointType	,
		A	) -> OrientedSegment< PointType, std::decay_t< A > >

outerRaster() [1/2]

template<class PointType = Point<int>, class ShapeType>
requires std::signed_integral< std::remove_cvref_t<decltype(std::declval<const ShapeType&>().bbox().min().x())>>

BitMatrix< PointType > pgl::outerRaster

(

const ShapeType &

shape

)

Rasterizes a bounded shape over its own bounding box.

Template Parameters

PointType

Cell type of the result; Point<int> unless given.

Parameters

shape

Bounded shape with integer coordinates.

outerRaster() [2/2]

template<class PointType, class ShapeType>

BitMatrix< PointType > pgl::outerRaster	(	const ShapeType &	shape,
		const Rectangle< PointType > &	window )

Rasterizes a shape into the cells it meets: its outer approximation.

A cell is set when the shape intersects it, boundary included, so the result covers the shape. Costs one exact predicate per cell of window, and works for every shape; BitMatrix::BitMatrix(const PolygonWithHoles<PointType, TLabel>&) is the cheap path for a rectilinear region.

Template Parameters

PointType

Cell type of the result, deduced from window.

Parameters

shape	Shape to rasterize.
window	Window of the result, read as BitMatrix::BitMatrix(const RectangleType&) reads it.

Point() [1/3]

pgl::Point

(

)

-> Point< int >

Point() [2/3]

template<class Number>

pgl::Point	(	Number	,
		Number	) -> Point< Number >

Point() [3/3]

template<class Number, class Label>

pgl::Point	(	Number	,
		Number	,
		Label	) -> Point< Number, std::decay_t< Label > >

pointRadius()

CanvasCommand pgl::pointRadius ( std::string value )

inline

Creates a command that changes the current point radius.

Polygon() [1/4]

pgl::Polygon

(

)

-> Polygon< Point<>, NoLabel >

Polygon() [2/4]

template<std::ranges::input_range Range>
requires detail::is_point_v<std::ranges::range_value_t<Range>>

pgl::Polygon

(

Range &&

)

-> Polygon< std::remove_cvref_t< std::ranges::range_value_t< Range > >, NoLabel >

Polygon() [3/4]

template<class Number>
requires (!detail::is_point_v<Number>)

pgl::Polygon

(

std::initializer_list< Number >

)

-> Polygon< Point< Number >, NoLabel >

Polygon() [4/4]

template<class Number>
requires (!detail::is_point_v<Number>)

pgl::Polygon	(	std::initializer_list< Number >	,
		bool	) -> Polygon< Point< Number >, NoLabel >

PolygonSet() [1/4]

pgl::PolygonSet

(

)

-> PolygonSet< Point<>, NoLabel >

PolygonSet() [2/4]

template<PolygonWithHolesConcept Component>

pgl::PolygonSet

(

Component &&

)

-> PolygonSet< typename std::remove_cvref_t< Component >::PointType, NoLabel >

PolygonSet() [3/4]

template<std::ranges::input_range ComponentRange>
requires detail::is_polygon_with_holes_v<std::ranges::range_value_t<ComponentRange>>

pgl::PolygonSet

(

ComponentRange &&

)

-> PolygonSet< typename std::ranges::range_value_t< ComponentRange >::PointType, NoLabel >

PolygonSet() [4/4]

template<std::ranges::input_range ComponentRange>
requires detail::is_polygon_with_holes_v<std::ranges::range_value_t<ComponentRange>>

pgl::PolygonSet	(	ComponentRange &&	,
		bool	) -> PolygonSet< typename std::ranges::range_value_t< ComponentRange >::PointType, NoLabel >

PolygonWithHoles() [1/5]

pgl::PolygonWithHoles

(

)

-> PolygonWithHoles< Point<>, NoLabel >

PolygonWithHoles() [2/5]

template<PolygonConcept OuterPolygon>

pgl::PolygonWithHoles

(

OuterPolygon &&

)

-> PolygonWithHoles< typename std::remove_cvref_t< OuterPolygon >::PointType, NoLabel >

PolygonWithHoles() [3/5]

template<PolygonConcept OuterPolygon>

pgl::PolygonWithHoles	(	OuterPolygon &&	,
		bool	) -> PolygonWithHoles< typename std::remove_cvref_t< OuterPolygon >::PointType, NoLabel >

PolygonWithHoles() [4/5]

template<PolygonConcept OuterPolygon, std::ranges::input_range HoleRange>
requires detail::is_polygon_v<std::ranges::range_value_t<HoleRange>>

pgl::PolygonWithHoles	(	OuterPolygon &&	,
		HoleRange &&	) -> PolygonWithHoles< typename std::remove_cvref_t< OuterPolygon >::PointType, NoLabel >

PolygonWithHoles() [5/5]

template<PolygonConcept OuterPolygon, std::ranges::input_range HoleRange>
requires detail::is_polygon_v<std::ranges::range_value_t<HoleRange>>

pgl::PolygonWithHoles	(	OuterPolygon &&	,
		HoleRange &&	,
		bool	) -> PolygonWithHoles< typename std::remove_cvref_t< OuterPolygon >::PointType, NoLabel >

Polyline() [1/3]

pgl::Polyline

(

)

-> Polyline< Point<>, NoLabel >

Polyline() [2/3]

template<std::ranges::input_range Range>
requires detail::is_point_v<std::ranges::range_value_t<Range>>

pgl::Polyline

(

Range &&

)

-> Polyline< std::remove_cvref_t< std::ranges::range_value_t< Range > >, NoLabel >

Polyline() [3/3]

template<class Number>
requires (!detail::is_point_v<Number>)

pgl::Polyline

(

std::initializer_list< Number >

)

-> Polyline< Point< Number >, NoLabel >

polyominoes() [1/2]

template<class T = int>

std::vector< Polygon< Point< T > > > pgl::polyominoes	(	std::size_t	n1,
		std::size_t	n2 )

Enumerates the free polyominoes of every size in [n1, n2].

Concatenates polyominoes for each size from n1 to n2 inclusive, smallest first. An empty range (n1 > n2) yields no polyominoes.

Template Parameters

T	Coordinate type of the returned points (defaults to int).

Parameters

n1	Smallest size to include.
n2	Largest size to include.

Returns

The hole-free free polyominoes of every size in the range.

polyominoes() [2/2]

template<class T = int>

std::vector< Polygon< Point< T > > > pgl::polyominoes

(

std::size_t

size

)

Enumerates the free polyominoes of a given size as polygons.

Returns one Polygon<Point<T>> per free polyomino of size cells, i.e. counted up to translation, rotation and reflection (5 for size 4, 12 for size 5, and so on). Each polygon traces the polyomino's boundary with small non-negative integer coordinates, normalized like any other Polygon (counterclockwise, lexicographically smallest vertex first).

Polyominoes that enclose a hole (possible from seven cells onward) are omitted: their boundary is not a simple polygon, which Polygon cannot represent. Use polyominoRegions to get every polyomino, holes and all.

Template Parameters

T	Coordinate type of the returned points (defaults to int).

Parameters

size	Number of cells in each polyomino; 0 yields no polyominoes.

Returns

The hole-free free polyominoes of size cells, in a deterministic order.

polyominoesUpTo()

template<class T = int>

std::vector< Polygon< Point< T > > > pgl::polyominoesUpTo

(

std::size_t

n

)

Enumerates the free polyominoes of every size from 1 to n.

Convenience for polyominoes(std::size_t, std::size_t) with a lower bound of one, smallest first.

Template Parameters

T	Coordinate type of the returned points (defaults to int).

Parameters

n	Largest size to include.

Returns

The hole-free free polyominoes of every size up to n.

polyominoRegions() [1/2]

template<class T = int>

std::vector< PolygonWithHoles< Point< T > > > pgl::polyominoRegions	(	std::size_t	n1,
		std::size_t	n2 )

Enumerates the free polyominoes of every size in [n1, n2] as regions.

Concatenates polyominoRegions for each size from n1 to n2 inclusive, smallest first. An empty range (n1 > n2) yields no polyominoes.

Template Parameters

T	Coordinate type of the returned points (defaults to int).

Parameters

n1	Smallest size to include.
n2	Largest size to include.

Returns

The free polyominoes of every size in the range, holes included.

polyominoRegions() [2/2]

template<class T = int>

std::vector< PolygonWithHoles< Point< T > > > pgl::polyominoRegions

(

std::size_t

size

)

Enumerates the free polyominoes of a given size as regions.

Like polyominoes, but returning a PolygonWithHoles<Point<T>> per free polyomino and omitting none of them: a region represents an enclosed hole, so the holed polyominoes — which appear from seven cells on and are a growing fraction of the answer — are kept. The count is therefore the full free polyomino sequence (108 for size seven, where polyominoes returns 107).

Each region has small non-negative integer coordinates and canonical rings. Its area is the cell count, and its holes may touch the outer boundary at a point: two diagonally opposite cells of a polyomino can pinch a hole shut against the outside, which PolygonWithHoles::isValid accepts.

Template Parameters

T	Coordinate type of the returned points (defaults to int).

Parameters

size	Number of cells in each polyomino; 0 yields no polyominoes.

Returns

The free polyominoes of size cells, in a deterministic order.

polyominoRegionsUpTo()

template<class T = int>

std::vector< PolygonWithHoles< Point< T > > > pgl::polyominoRegionsUpTo

(

std::size_t

n

)

Enumerates the free polyominoes of every size from 1 to n as regions.

Convenience for polyominoRegions(std::size_t, std::size_t) with a lower bound of one, smallest first.

Template Parameters

T	Coordinate type of the returned points (defaults to int).

Parameters

n	Largest size to include.

Returns

The free polyominoes of every size up to n, holes included.

Rational()

template<class T>
requires (!pgl::detail::extended_integral<T> && !std::floating_point<T> && !RationalConcept<T>)

pgl::Rational

(

T

)

-> Rational< T >

Ray() [1/4]

pgl::Ray

(

)

-> Ray< Point<>, NoLabel >

Ray() [2/4]

template<class Number>

pgl::Ray	(	Number	,
		Number	,
		Number	,
		Number	) -> Ray< Point< Number >, NoLabel >

Ray() [3/4]

template<class PointType>

pgl::Ray	(	PointType	,
		PointType	) -> Ray< PointType, NoLabel >

Ray() [4/4]

template<class PointType, class A>

pgl::Ray	(	PointType	,
		PointType	,
		A	) -> Ray< PointType, std::decay_t< A > >

Rectangle() [1/4]

pgl::Rectangle

(

)

-> Rectangle< Point<>, NoLabel >

Rectangle() [2/4]

template<class Number>

pgl::Rectangle	(	Number	,
		Number	,
		Number	,
		Number	) -> Rectangle< Point< Number >, NoLabel >

Rectangle() [3/4]

template<class PointType>

pgl::Rectangle	(	PointType	,
		PointType	) -> Rectangle< PointType, NoLabel >

Rectangle() [4/4]

template<std::ranges::input_range Range>
requires detail::is_point_v<std::ranges::range_value_t<Range>>

pgl::Rectangle

(

Range &&

)

-> Rectangle< std::remove_cvref_t< std::ranges::range_value_t< Range > >, NoLabel >

redBlueSweep()

template<class RedRange, class BlueRange>

BoundaryContact pgl::redBlueSweep	(	const RedRange &	red,
		const BlueRange &	blue )

Classifies how two edge sets meet, in one combined left-to-right sweep.

red and blue are ranges of segment-like values — the edges of two polygon boundaries, say, from Polygon::edgesView. Neither set may properly cross itself: that is the simple-polygon contract, and it is what lets the sweep test red against blue only, and ignore how tangled either boundary is on its own.

The sweep keeps the edges crossing the sweep line in a height-ordered status structure and tests a pair the moment the two become neighbours in it. Every pair that ever meets becomes adjacent first (or shares an endpoint, which the event stream reports directly), so a BoundaryContact::Disjoint answer is exhaustive. It stops at the first verified crossing — one that Segment::crosses confirms — and merely records that the boundaries touch otherwise, so touchings never enlarge the event queue and cannot slow it down.

Every decision goes through orientationSign on the original coordinates, so nothing is evaluated in floating point that was not already, and the sweep needs neither y-at-x interpolation nor rational arithmetic.

Complexity: O((n + m) log(n + m)) for n red and m blue edges, whatever the shape of either boundary and however many touchings there are.

Parameters

red	First edge set.
blue	Second edge set.

Returns

BoundaryContact::Disjoint, BoundaryContact::Touching or BoundaryContact::Crossing; see BoundaryContact for how far each of the three can be trusted.

regularizedUnionOf()

template<class ResultPoint, class ShapeRange>

PolygonSet< ResultPoint > pgl::regularizedUnionOf	(	const ShapeRange &	shapes,
		bool	simpleBoundaries = false )

The regularized union of arbitrarily many shapes, as a set of regions.

One arrangement over all their boundaries settles the whole union, where folding regularizedUnion over the range would build one per step and re-triangulate everything accumulated so far. That is what makes it the right back end for a construction whose natural form is a union of many pieces — the Minkowski sum of two non-convex shapes is one.

Parameters

shapes

The pieces to unite.

simpleBoundaries

Set when no two boundary edges of the same piece overlap, which lets regularizedUnionByCoverage classify the faces instead of the witness scan below. A Convex is such a piece by construction and never has to say so, as are a Triangle and a Rectangle; a Polygon is one whenever it meets its own simplicity precondition, and a PolygonWithHoles is one exactly when it carries no slit — which is why this is the caller's to assert and not a property read off the type.

Returns

The pieces of the union, in canonical order.

round_up_bits()

int pgl::round_up_bits ( int bits )

constexpr

sameDirection()

template<class ANumber, class ALabel, class BNumber, class BLabel>

bool pgl::sameDirection ( const Point< ANumber, ALabel > & a1, const Point< ANumber, ALabel > & a2, const Point< BNumber, BLabel > & b1, const Point< BNumber, BLabel > & b2 )

constexpr

Tests whether the directions a1 -> a2 and b1 -> b2 are parallel.

Compares the 2D cross product of the two direction vectors against zero, so it reports true for parallel and anti-parallel directions alike (and when either direction is degenerate). The two endpoints of each direction must share a point type; the two directions may use different point types.

Parameters

a1	Tail of the first direction.
a2	Head of the first direction.
b1	Tail of the second direction.
b2	Head of the second direction.

Returns

true if the two direction vectors are parallel.

Segment() [1/4]

pgl::Segment

(

)

-> Segment< Point<>, NoLabel >

Segment() [2/4]

template<class Number>

pgl::Segment	(	Number	,
		Number	,
		Number	,
		Number	) -> Segment< Point< Number >, NoLabel >

Segment() [3/4]

template<class PointType>

pgl::Segment	(	PointType	,
		PointType	) -> Segment< PointType, NoLabel >

Segment() [4/4]

template<class PointType, class A>

pgl::Segment	(	PointType	,
		PointType	,
		A	) -> Segment< PointType, std::decay_t< A > >

Shape() [1/2]

template<class T, class... Ts>

pgl::Shape

(

const std::optional< std::variant< T, Ts... > > &

)

-> Shape< detail::shape_point_type_t< T > >

Shape() [2/2]

template<class T, class... Ts>

pgl::Shape

(

const std::variant< T, Ts... > &

)

-> Shape< detail::shape_point_type_t< T > >

ShapeTree() [1/4]

template<class Container>

pgl::ShapeTree

(

const Container &

)

-> ShapeTree< typename Container::value_type >

ShapeTree() [2/4]

template<class Container>

pgl::ShapeTree	(	const Container &	,
		std::size_t	) -> ShapeTree< typename Container::value_type >

ShapeTree() [3/4]

template<class Container, class WeightFn>

pgl::ShapeTree	(	const Container &	,
		std::size_t	,
		WeightFn	) -> ShapeTree< typename Container::value_type, WeightFn >

ShapeTree() [4/4]

template<class Container, class WeightFn>
requires (!std::is_integral_v<WeightFn>)

pgl::ShapeTree	(	const Container &	,
		WeightFn	) -> ShapeTree< typename Container::value_type, WeightFn >

smallestEnclosingDisk() [1/2]

template<class Container>

detail::min_disk_result_t< Container > pgl::smallestEnclosingDisk ( const Container & input )

nodiscard

Computes the smallest closed disk containing a set of points.

This overload supplies the generator for the randomized incremental order, from a fixed seed, so the same input always yields the same disk. See the generator-taking overload for result and complexity details.

Warning

Constructing a disk from two support points divides coordinates by

1. If an integral coordinate type is used, all input coordinates should be even; otherwise integer division can truncate the result.

smallestEnclosingDisk() [2/2]

template<class Container, class UniformRandomBitGenerator>

detail::min_disk_result_t< Container > pgl::smallestEnclosingDisk ( const Container & input, UniformRandomBitGenerator && generator )

nodiscard

Computes the smallest closed disk containing a set of points.

The points are shuffled and processed by the randomized incremental algorithm. Whenever a point lies outside the current disk, that point must lie on the boundary of the new minimum disk; the two nested scans apply the same observation to the remaining one or two boundary points. A disk in the plane has at most three support points, so this yields expected linear time.

The returned disk retains the input coordinate number type. Point labels are not copied to the constructed disk's boundary points.

Warning

Constructing a disk from two support points divides coordinates by

1. If an integral coordinate type is used, all input coordinates should be even; otherwise integer division can truncate the result.

Template Parameters

Container	Container of pgl points.
UniformRandomBitGenerator	Random-bit generator accepted by std::shuffle.

Parameters

input	Input points; they are copied and the container is not modified.
generator	Generator used to randomize the incremental order.

Precondition

input is not empty.

Returns

The unique smallest enclosing disk.

@complexity Expected O(n) time and O(n) additional space.

sortAround()

template<class Number, class Label, class CenterNumber, class CenterLabel>

void pgl::sortAround	(	std::vector< Point< Number, Label > > &	points,
		const Point< CenterNumber, CenterLabel > &	p )

Sorts points counterclockwise around a center point.

The angular order starts from the lexicographically smallest point in points (its direction from p defines angle zero) and proceeds counterclockwise around p. Points that share an angular direction are tied; the tie is broken by putting the points that are farther from p first. With this convention, connecting the sorted points in order traces a simple, star-shaped polygon whose kernel contains p. Points equal to p have no direction to sort by and end up last.

The comparison relies only on the exact orientationSign predicate and squared distances, so it stays exact for integer coordinates.

The points are first split by the horizontal line through p, which costs two coordinate comparisons each. Each part then spans half a turn, where the orientation sign alone already orders the directions, so the sort spends one orientation predicate per comparison instead of the three that comparing angles measured from the reference direction would take.

Template Parameters

Number	Coordinate type of the points being sorted.
Label	Label type of the points being sorted.
CenterNumber	Coordinate type of the center point.
CenterLabel	Label type of the center point.

Parameters

points	Points to reorder in place.
p	Center the points are sorted around.

stroke()

CanvasCommand pgl::stroke ( std::string value )

inline

Creates a command that changes the current stroke color.

strokeOpacity()

CanvasCommand pgl::strokeOpacity ( std::string value )

inline

Creates a command that changes the current stroke opacity.

strokeWidth()

CanvasCommand pgl::strokeWidth ( std::string value )

inline

Creates a command that changes the current stroke width.

sweepContains()

template<PolygonConcept OuterPolygon, PolygonConcept InnerPolygon>

bool pgl::sweepContains	(	const OuterPolygon &	outer,
		const InnerPolygon &	inner )

Sweep-based counterpart of Polygon::contains(Polygon).

Same answer as Polygon::contains for two simple polygons, reached by the same three-step argument — a point of inner inside outer, no crossing of the boundaries, and an edge-by-edge check only when they touch — but with the middle step done by redBlueSweep instead of by testing the polygons' lexicographically monotone chains against each other pairwise. The chain test is the faster of the two whenever both boundaries decompose into few chains, which is the near-convex case; its cost is the product of the two chain counts, so a comb, a star or any boundary that reverses direction at most vertices drives it to O(n·m), where the sweep stays at O((n + m) log(n + m)).

The two are kept side by side deliberately: this one is the scalable implementation, Polygon::contains the one tuned for the common shapes.

Parameters

outer	Candidate container.
inner	Candidate containee.

Returns

true when outer contains every point of inner, boundary included.

Triangle() [1/4]

pgl::Triangle

(

)

-> Triangle< Point<>, NoLabel >

Triangle() [2/4]

template<class Number>

pgl::Triangle	(	Number	,
		Number	,
		Number	,
		Number	,
		Number	,
		Number	) -> Triangle< Point< Number >, NoLabel >

Triangle() [3/4]

template<class PointType>

pgl::Triangle	(	PointType	,
		PointType	,
		PointType	) -> Triangle< PointType, NoLabel >

Triangle() [4/4]

template<class PointType, class A>

pgl::Triangle	(	PointType	,
		PointType	,
		PointType	,
		A	) -> Triangle< PointType, std::decay_t< A > >

Triangulation() [1/16]

template<class PointRange>
requires PointConcept<typename PointRange::value_type>

pgl::Triangulation

(

const PointRange &

)

-> Triangulation< Triangle< Point< typename PointRange::value_type::NumberType > > >

Triangulation() [2/16]

template<class PointRange, class SegmentRange>
requires PointConcept<typename PointRange::value_type> && SegmentConcept<typename SegmentRange::value_type>

pgl::Triangulation	(	const PointRange &	,
		const SegmentRange &	) -> Triangulation< Triangle< Point< typename PointRange::value_type::NumberType > >, Segment< Point< typename PointRange::value_type::NumberType >, typename SegmentRange::value_type::LabelType > >

Triangulation() [3/16]

template<class PointType>

pgl::Triangulation

(

const Polygon< PointType > &

)

-> Triangulation< Triangle< PointType > >

Triangulation() [4/16]

template<class PolyPoint, class PointRange>
requires PointConcept<typename PointRange::value_type>

pgl::Triangulation	(	const Polygon< PolyPoint > &	,
		const PointRange &	) -> Triangulation< Triangle< PolyPoint > >

Triangulation() [5/16]

template<class PolyPoint, class PointRange, class SegmentRange>
requires PointConcept<typename PointRange::value_type> && SegmentConcept<typename SegmentRange::value_type>

pgl::Triangulation	(	const Polygon< PolyPoint > &	,
		const PointRange &	,
		const SegmentRange &	) -> Triangulation< Triangle< PolyPoint >, Segment< PolyPoint, typename SegmentRange::value_type::LabelType > >

Triangulation() [6/16]

template<class PolyPoint, class SegmentRange>
requires SegmentConcept<typename SegmentRange::value_type>

pgl::Triangulation	(	const Polygon< PolyPoint > &	,
		const SegmentRange &	) -> Triangulation< Triangle< PolyPoint >, Segment< PolyPoint, typename SegmentRange::value_type::LabelType > >

Triangulation() [7/16]

template<class SetPoint>

pgl::Triangulation

(

const PolygonSet< SetPoint > &

)

-> Triangulation< Triangle< SetPoint > >

Triangulation() [8/16]

template<class SetPoint, class PointRange>
requires PointConcept<typename PointRange::value_type>

pgl::Triangulation	(	const PolygonSet< SetPoint > &	,
		const PointRange &	) -> Triangulation< Triangle< SetPoint > >

Triangulation() [9/16]

template<class SetPoint, class PointRange, class SegmentRange>
requires PointConcept<typename PointRange::value_type> && SegmentConcept<typename SegmentRange::value_type>

pgl::Triangulation	(	const PolygonSet< SetPoint > &	,
		const PointRange &	,
		const SegmentRange &	) -> Triangulation< Triangle< SetPoint >, Segment< SetPoint, typename SegmentRange::value_type::LabelType > >

Triangulation() [10/16]

template<class SetPoint, class SegmentRange>
requires SegmentConcept<typename SegmentRange::value_type>

pgl::Triangulation	(	const PolygonSet< SetPoint > &	,
		const SegmentRange &	) -> Triangulation< Triangle< SetPoint >, Segment< SetPoint, typename SegmentRange::value_type::LabelType > >

Triangulation() [11/16]

template<class RegionPoint>

pgl::Triangulation

(

const PolygonWithHoles< RegionPoint > &

)

-> Triangulation< Triangle< RegionPoint > >

Triangulation() [12/16]

template<class RegionPoint, class PointRange>
requires PointConcept<typename PointRange::value_type>

pgl::Triangulation	(	const PolygonWithHoles< RegionPoint > &	,
		const PointRange &	) -> Triangulation< Triangle< RegionPoint > >

Triangulation() [13/16]

template<class RegionPoint, class PointRange, class SegmentRange>
requires PointConcept<typename PointRange::value_type> && SegmentConcept<typename SegmentRange::value_type>

pgl::Triangulation	(	const PolygonWithHoles< RegionPoint > &	,
		const PointRange &	,
		const SegmentRange &	) -> Triangulation< Triangle< RegionPoint >, Segment< RegionPoint, typename SegmentRange::value_type::LabelType > >

Triangulation() [14/16]

template<class RegionPoint, class SegmentRange>
requires SegmentConcept<typename SegmentRange::value_type>

pgl::Triangulation	(	const PolygonWithHoles< RegionPoint > &	,
		const SegmentRange &	) -> Triangulation< Triangle< RegionPoint >, Segment< RegionPoint, typename SegmentRange::value_type::LabelType > >

Triangulation() [15/16]

template<class SegmentRange>
requires SegmentConcept<typename SegmentRange::value_type>

pgl::Triangulation

(

const SegmentRange &

)

-> Triangulation< Triangle< typename SegmentRange::value_type::PointType >, typename SegmentRange::value_type >

Triangulation() [16/16]

template<class TriangleRange>
requires TriangleConcept<typename TriangleRange::value_type>

pgl::Triangulation

(

const TriangleRange &

)

-> Triangulation< typename TriangleRange::value_type >

xyCrossings()

template<class Rational = pgl::Rational<pgl::BigInt>, class Container>

auto pgl::xyCrossings

(

const Container &

segments

)

Finds all crossing segment pairs with a bounding-box sweep.

Reports the same pairs as bruteForceCrossings, in the order the sweep meets them rather than in input order, by testing only the pairs whose bounding boxes overlap. Takes O((n + k) log n) time for n segments and k bounding-box-overlapping pairs, so it is the faster of the two whenever the boxes are not almost all overlapping, and it needs no exact arithmetic: unlike findCrossings it accepts floating-point coordinates.

Template Parameters

Rational	Unused template parameter kept for API symmetry.
Container	Container of segment-like values.

Parameters

segments

Input segment container.

Returns

Vector of crossing segment pairs.

xyIntersections()

template<class Rational = pgl::Rational<pgl::BigInt>, class Container>

auto pgl::xyIntersections

(

const Container &

segments

)

Finds all intersecting segment pairs with a bounding-box sweep.

Reports the same pairs as bruteForceIntersections, in the order the sweep meets them rather than in input order, by testing only the pairs whose bounding boxes overlap. Takes O((n + k) log n) time for n segments and k bounding-box-overlapping pairs, so it is the faster of the two whenever the boxes are not almost all overlapping, and it needs no exact arithmetic: unlike findIntersections it accepts floating-point coordinates.

Template Parameters

Rational	Unused template parameter kept for API symmetry.
Container	Container of segment-like values.

Parameters

segments

Input segment container.

Returns

Vector of intersecting segment pairs.

Variable Documentation

is_Rational_v

template<class T>

bool pgl::is_Rational_v = is_Rational<T>::value

inlineconstexpr