samepointset.hpp File Reference

Exact equality of the point sets represented by arbitrary shapes. More...

#include "implementation/predicates.hpp"
#include <algorithm>
#include <compare>
#include <concepts>
#include <cstddef>
#include <optional>
#include <ranges>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>

Go to the source code of this file.

Namespaces
namespace	pgl

Detailed Description

Exact equality of the point sets represented by arbitrary shapes.

A.samePointSet(B) asks whether A and B cover the same points, so it agrees with A.contains(B) && B.contains(A) — but it is almost never worth computing that way. Every pair of shape kinds gets its own definition here, each written around three observations:

• Most pairs cannot agree at all. A defined line is unbounded and a segment is not; a disk with area has a curved boundary and a convex polygon does not; a rectangle with area has four corners and a triangle three. Such a pair is false in O(1) once each operand that has collapsed below its natural dimension is reduced onto the point or segment it covers, which is the only way the two can meet.
• Shapes are stored canonically. A Segment orders its endpoints, a Rectangle its corners, and Rectangle, Triangle, Convex and Polygon all present their ring counterclockwise from its lexicographically smallest vertex — a vertex that is a function of the point set alone, never of how the shape was built. A cached bounding box and that one vertex settle two independently built rings in O(1), which is what makes the expected cost of this predicate constant rather than linear. Rings that agree on both are compared vertex for vertex, and only rings that disagree there are walked corner by corner, skipping the vertices that merely subdivide a straight edge — the one freedom two equal rings have left.
• No definition sums an area. Twice the area of a ring overflows an integral coordinate type long before its vertices do, and it costs a full pass over a shape whose first vertex would have answered the question. Degeneracy is therefore read off isPoint / isSegment, which stop at the first vertex that proves the shape has area.

The one shared step is the empty set, in pgl::detail::samePointSetAny: an operand covering no point equals exactly the operands covering no point, whatever the two kinds are. Every definition below may assume both operands are non-empty.