arrangement.hpp File Reference

Planar subdivision induced by a set of one-dimensional shapes. More...

#include "algorithm/triangulation.hpp"
#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <map>
#include <memory>
#include <numeric>
#include <optional>
#include <random>
#include <ranges>
#include <set>
#include <span>
#include <stdexcept>
#include <type_traits>
#include <unordered_map>
#include <utility>
#include <variant>
#include <vector>

Go to the source code of this file.

Classes
class	pgl::Arrangement< PointType_, TLabel >
	The planar subdivision induced by a set of one-dimensional shapes. More...

Namespaces
namespace	pgl

Detailed Description

Planar subdivision induced by a set of one-dimensional shapes.

An pgl::Arrangement is the decomposition of the plane produced by a collection of segments, rays and lines: its finite vertices are the endpoints together with every crossing and overlap end, its edges are the pieces those vertices cut the input into, and its faces are the connected components of what is left of the plane. Every point of the plane belongs to exactly one of those cells, which is what makes an arrangement the natural back end of any operation that has to answer "the same question" on each piece of a subdivided plane — the regularized booleans, the Minkowski sums, and the connectivity tests behind separates all do exactly that.

The topology is a doubly connected edge list (DCEL). Halfedges are stored in twin-adjacent pairs, so twin(h) is h.index() ^ 1 and costs no memory access, and the whole structure is three std::uint32_t arrays (origin, next, face) beside the vertex coordinates. The three handle families are distinct types (pgl::Arrangement::VertexId, pgl::Arrangement::HalfedgeId and pgl::Arrangement::FaceId), which is what lets pgl::Arrangement::operator[] and pgl::Arrangement::witness be one name each across cell families instead of three, and what lets a caller classify cells of all three dimensions in a single generic loop.

Everything is exact: the construction uses only the library's exact predicates and constructions, and coordinates are converted to the caller's number type at extraction time through the usual ResultNumber template parameter. Because arrangement vertices are crossings, the arrangement's own point type normally has to be a rational one (pgl::EPoint is the usual choice); an integral point type is adequate exactly when every crossing is itself integral, which is what input that meets only at its endpoints guarantees, and equally what axis-parallel input does. Such an arrangement is exact throughout — construction, point location and the curve traversals alike — within the coordinate bound the exact predicates carry everywhere: two coordinate differences have to multiply inside one type promotion, which holds int coordinates safely up to 10^8. Unbounded edge ends meet at one symbolic vertex at infinity; no finite frame and no fictitious edge is introduced.