booleans.hpp File Reference

Regularized boolean operations on closed polygonal regions. More...

#include "algorithm/arrangement.hpp"
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <cstddef>
#include <limits>
#include <map>
#include <numeric>
#include <ranges>
#include <type_traits>
#include <variant>
#include <vector>

Go to the source code of this file.

Namespaces
namespace	pgl

Functions
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.

Detailed Description

Regularized boolean operations on closed polygonal regions.

The four operations — difference A ∖ B, union A ∪ B, intersection A ∩ B and symmetric difference A △ B — are one algorithm run with four per-cell tests. The difference came first, and it is the one whose result genuinely needs PolygonWithHoles for the simplest of inputs: removing a polygon from the middle of another one leaves a region with a hole, which no other shape can express.

The other three need a region too, though it takes a holed operand to see it:

• a union closes a hole into being whenever the operands wrap round between them, as a U united with the bar that caps it;
• an intersection keeps the holes of a holed operand, so it needs a region whenever one of its operands is one. That does not contradict Polygon::intersection(const OtherPolygon&) const returning plain polygons: the argument that no component of A ∩ B has a hole assumes both operands have a connected complement, which every shape in the library satisfies except a region with holes;
• a symmetric difference is the union of two differences, and inherits holes from both.

What is computed is the regularized result, closure of the operation on the open interiors: closure(A° ∖ B), closure(A° ∪ B°), closure(A° ∩ B°) and closure((A° ∖ B) ∪ (B° ∖ A)). Lower-dimensional leftovers — a stretch of boundary the operands share without either covering it, an isolated contact point, a slit — have nowhere to go in a set of regions and are dropped. That is the usual convention for boolean operations on solids.

The engine is the cell decomposition of detail::cellSeparates seen from the other side: the pgl::Arrangement of both boundaries cuts the plane into faces on which membership in A and in B is constant, one witness point per face decides whether it survives, and the boundary of the union of the surviving faces is read straight off the arrangement — a halfedge is on it exactly when the face to its left is kept and the face across it is not. Only the per-cell test tells the four operations apart. Everything is exact — the arrangement is built over rationals — and the result is converted to the requested coordinate type only at the very end, so an integral answer comes back integral however the intermediate crossings looked.