poly_ops/clip.hpp

Types

template<typename Index = std::size_t>
class i_point_tracker

Point tracking common interface.

The “clipper” class stores all points in a single array. To associate extra data with each point, a second array may be created with the extra data. This interface is a set of callbacks that allows keeping an external array synchronized with clipper’s internal array.

Note that the destructor is not virtual, and is instead protected.

Subclassed by origin_point_tracker< Index >

Public Functions

virtual void new_point_between(Index a, Index b) = 0

Called when a line is split, adding a new point.

a and b are the endpoints of the line that was split. Like point_added, the index of this new point is one greater than the index of the last point added.

Parameters:

  • a – The index of the intersection point of the first line.

  • b – The index of the intersection point of the second line.

virtual void point_merge(Index from, Index to) = 0

Called when points are “merged”.

When parts of the shape are going to be truncated, this is called on the first point to be discarded as from and the point that follows it as to. If the next point is also to be discarded, this is called again with that point along with the point after that. This is repeated until the point reached is not going to be discarded, or the following point was already discarded because we’ve circled around the entire loop.

Discarded points are never referenced again.

Parameters:

  • from – The index of the point to be discarded.

  • to – The index of the point that follows from.

virtual void point_added(Index original_i) = 0

Called for every point initially added.

Every added point has an implicit index (this index is unrelated to original_i). This method is first called when point zero is added. Every subsequent call corresponds to the index that is one greater than the index of the previously added point.

original_i is the index of the input point that the added point corresponds to. The value is what the array index of the original point would be if all the input points were added, in order, to a single array. This will not necessarily be called for every point of the input; duplicate consecutive points are ignored.

Parameters:

original_i – The index of the input point that this added point corresponds to.

virtual void reset() = 0

Called by any of the “add_loops” functions to reset state.

After clipper::execute is called, the first time an “add_loops” function is called, clipper::reset and this function are automatically called.

The free functions (such as boolean_op) never call this method.

template<typename T, typename Coord, typename Index>
concept point_tracker
enum class bool_op

Given two sets of polygons, subject and clip, specifies which operation to perform.

Values:

enumerator union_

Boolean operation subject OR clip.

union operation example

enumerator intersection

Boolean operation subject AND clip.

intersection operation example

enumerator xor_

Boolean operation subject XOR clip

xor operation example

enumerator difference

Boolean operation subject AND NOT clip

difference operation example

enumerator normalize

Keep all lines but make it so all outer lines are clockwise polygons, all singly nested lines are counter-clockwise polygons, all doubly-nested lines are clockwise polygons, and so forth.

enum class bool_set

Specifies one of two sets.

The significance of these sets depends on the operation performed.

Values:

enumerator subject
enumerator clip
template<typename Coord, typename Index = std::size_t, typename Tracker = null_tracker<Coord, Index>>
class proto_loop_iterator

An opaque type that models std::forward_iterator. The iterator yields instances of point_t<Coord>.

template<typename Coord, typename Index, typename Tracker>
class temp_polygon_proxy : public std::ranges::view_interface<temp_polygon_proxy<Coord, Index, Tracker>>

A representation of a polygon with zero or more child polygons.

This class is not meant to be directly instantiated by users of this library. This class models std::ranges::forward_range and std::ranges::sized_range and yields instances of point_t<Coord>.

Public Types

using tracker_ptr = decltype(&std::declval<const Tracker&>())

Public Functions

inline temp_polygon_proxy(
const detail::loop_point<Index, Coord> *lpoints,
const detail::temp_polygon<Index> &data,
tracker_ptr tracker,
)
inline proto_loop_iterator<Coord, Index, Tracker> begin() const noexcept

Get the iterator to the first element.

inline proto_loop_iterator<Coord, Index, Tracker> end() const noexcept

Get the end iterator

inline Index size() const noexcept

Return the number of elements in this range.

inline auto inner_loops() const noexcept

Return a range representing the children of this polygon.

template<typename Coord, typename Index = std::size_t, typename Tracker = null_tracker<Coord, Index>>
using borrowed_temp_polygon_tree_range = decltype(detail::make_temp_polygon_tree_range<Index, Coord, Tracker>(std::declval<detail::loop_point<Index, Coord>*>(), std::declval<std::span<detail::temp_polygon<Index>*>>(), std::declval<Tracker>()))

An opaque type that models std::ranges::forward_range and std::ranges::sized_range.

Unlike temp_polygon_tree_range, an instance of this type does not own its data.

template<typename Coord, typename Index = std::size_t, typename Tracker = null_tracker<Coord, Index>>
using borrowed_temp_polygon_range = decltype(detail::make_temp_polygon_range<Index, Coord, Tracker>(std::declval<const std::pmr::vector<detail::loop_point<Index, Coord>>&>(), std::declval<const std::pmr::vector<detail::temp_polygon<Index>>&>(), std::declval<Tracker>()))

An opaque type that models std::ranges::forward_range and std::ranges::sized_range.

Unlike temp_polygon_range, an instance of this type does not own its data.

template<typename Coord, typename Index = std::size_t, typename Tracker = null_tracker<Coord, Index>>
using temp_polygon_tree_range = decltype(detail::make_temp_polygon_tree_range<Index, Coord, Tracker>({}, {}, {}, std::declval<Tracker>()))

An opaque type that models std::ranges::forward_range and std::ranges::sized_range.

template<typename Coord, typename Index = std::size_t, typename Tracker = null_tracker<Coord, Index>>
using temp_polygon_range = decltype(detail::make_temp_polygon_range<Index, Coord, Tracker>({}, {}, std::declval<Tracker>()))

An opaque type that models std::ranges::forward_range and std::ranges::sized_range.

template<coordinate Coord, std::integral Index = std::size_t>
class clipper

A class for performing boolean clipping operations.

An instance of clipper will reuse its allocated memory for subsequent operations, making it more efficient than calling boolean_op for performing multiple operations.

Public Functions

inline explicit clipper(std::pmr::memory_resource *_contig_mem = nullptr)
clipper(clipper &&b) = default
template<typename R>
inline void add_loops(R &&loops, bool_set cat, i_point_tracker<Index> *pt = nullptr)

Add input polygons.

The output returned by execute is invalidated.

R must satisfy point_range_or_range_range.

template<typename R>
inline void add_loops_subject(R &&loops, i_point_tracker<Index> *pt = nullptr)

Add input subject polygons.

The output returned by execute is invalidated.

R must satisfy point_range_or_range_range.

template<typename R>
inline void add_loops_clip(R &&loops, i_point_tracker<Index> *pt = nullptr)

Add input clip polygons.

The output returned by execute is invalidated.

R must satisfy point_range_or_range_range.

inline point_sink add_loop(bool_set cat, i_point_tracker<Index> *pt = nullptr)

Return a “point sink”.

This is an alternative to adding loops with ranges. The return value is a functor that allows adding one point at a time. The destructor of the return value must be called before any method of this instance of clipper is called.

The output returned by execute is invalidated.

void reset()

Discard all polygons added so far.

The output returned by execute is invalidated.

template<bool TreeOut = false, typename Tracker>
std::conditional_t<TreeOut, borrowed_temp_polygon_tree_range<Coord, Index, Tracker>, borrowed_temp_polygon_range<Coord, Index, Tracker>> execute(
bool_op op,
Tracker &&tracker,
) &

Perform a boolean operation and return the result.

After calling this function, all the input is consumed. To perform another operation, polygons must be added again.

The output of this function has references to data in this instance of clipper. The returned range is invalidated if the instance is destroyed or the next time a method of this instance is called. This means the return value cannot be fed directly back into the same instance of clipper. To keep the data, make a copy. The data is also not stored sequentially in memory.

template<bool TreeOut = false>
inline auto execute(bool_op op) &

Perform a boolean operation and return the result.

After calling this function, all the input is consumed. To perform another operation, polygons must be added again.

The output of this function has references to data in this instance of clipper. The returned range is invalidated if the instance is destroyed or the next time a method of this instance is called. This means the return value cannot be fed directly back into the same instance of clipper. To keep the data, make a copy. The data is also not stored sequentially in memory.

template<bool TreeOut = false, typename Tracker>
std::conditional_t<TreeOut, temp_polygon_tree_range<Coord, Index, Tracker>, temp_polygon_range<Coord, Index, Tracker>> execute(
bool_op op,
Tracker &&tracker,
) &&

Perform a boolean operation and return the result.

template<bool TreeOut = false>
inline auto execute(bool_op op) &&

Perform a boolean operation and return the result.

inline Index &next_orig_i() noexcept
inline Index next_orig_i() const noexcept
inline std::pmr::memory_resource *memory() const noexcept
class point_sink

Public Functions

void operator()(const point_t<Coord> &p, Index orig_i)
inline void operator()(const point_t<Coord> &p)
inline Index next_orig_i() const
inline Index &next_orig_i()
~point_sink()
template<coordinate Coord, std::integral Index, point_tracker<Coord, Index> Tracker>
class tclipper

A convenience class that combines clipper with a specific point_tracker

Public Functions

inline explicit tclipper(std::pmr::memory_resource *_contig_mem = nullptr)
inline explicit tclipper(Tracker &&tracker, std::pmr::memory_resource *_contig_mem = nullptr)
tclipper(tclipper &&b) = default
template<typename R>
inline void add_loops(R &&loops, bool_set cat)

Calls add_loops(std::forward<R>(loops),cat,tracker.callbacks())

template<typename R>
inline void add_loops_subject(R &&loops)

Calls add_loops(std::forward<R>(loops),bool_set::subject,tracker.callbacks())

template<typename R>
inline void add_loops_clip(R &&loops)

Calls add_loops(std::forward<R>(loops),bool_set::clip,tracker.callbacks())

inline clipper<Coord, Index>::point_sink add_loop(bool_set cat)

Calls base.add_loop(cat,tracker.callbacks())

inline void reset()

Calls base.reset() and ‘tracker.reset()`

template<bool TreeOut = false>
inline std::conditional_t<TreeOut, borrowed_temp_polygon_tree_range<Coord, Index, Tracker&>, borrowed_temp_polygon_range<Coord, Index, Tracker&>> execute(
bool_op op,
) &

Calls base.template execute<TreeOut,Tracker&>(op,tracker)

template<bool TreeOut = false>
inline std::conditional_t<TreeOut, temp_polygon_tree_range<Coord, Index, Tracker>, temp_polygon_range<Coord, Index, Tracker>> execute(
bool_op op,
) &&

Calls std::move(base).template execute<TreeOut,Tracker>(op,std::forward<Tracker>(tracker))

Public Members

Tracker tracker
clipper<Coord, Index> base

Functions

template<bool TreeOut, typename Coord, typename Index = std::size_t, typename Input>
auto union_op(
Input &&input,
std::pmr::memory_resource *contig_mem = nullptr,
)

Generate the union of a set of polygons.

This is equivalent to calling boolean_op with an empty range passed to clip and bool_op::union_ passed to op.

Coord must satisfy coordinate. Index must satisfy std::integral. Input must satisfy point_range_or_range_range.

template<bool TreeOut, typename Coord, typename Index = std::size_t, typename Input, typename Tracker>
std::conditional_t<TreeOut, temp_polygon_tree_range<Coord, Index, Tracker>, temp_polygon_range<Coord, Index, Tracker>> union_op(
Input &&input,
Tracker &&tracker,
std::pmr::memory_resource *contig_mem = nullptr,
)

Generate the union of a set of polygons.

This is equivalent to calling boolean_op with an empty range passed to clip and bool_op::union_ passed to op.

Coord must satisfy coordinate. Index must satisfy std::integral. Input must satisfy point_range_or_range_range. Tracker must satisfy point_tracker<Coord,Index>.

template<bool TreeOut, typename Coord, typename Index = std::size_t, typename Input>
auto normalize_op(
Input &&input,
std::pmr::memory_resource *contig_mem = nullptr,
)

“Normalize” a set of polygons.

This is equivalent to calling boolean_op with an empty range passed to clip and bool_op::normalize passed to op.

Coord must satisfy coordinate. Index must satisfy std::integral. Input must satisfy point_range_or_range_range.

template<bool TreeOut, typename Coord, typename Index = std::size_t, typename Input, typename Tracker>
std::conditional_t<TreeOut, temp_polygon_tree_range<Coord, Index, Tracker>, temp_polygon_range<Coord, Index, Tracker>> normalize_op(
Input &&input,
Tracker &&tracker,
std::pmr::memory_resource *contig_mem = nullptr,
)

“Normalize” a set of polygons.

This is equivalent to calling boolean_op with an empty range passed to clip and bool_op::normalize passed to op.

Coord must satisfy coordinate. Index must satisfy std::integral. Input must satisfy point_range_or_range_range. Tracker must satisfy point_tracker<Coord,Index>.

template<bool TreeOut, typename Coord, typename Index = std::size_t, typename SInput, typename CInput>
auto boolean_op(
SInput &&subject,
CInput &&clip,
bool_op op,
std::pmr::memory_resource *contig_mem = nullptr,
)

Perform a boolean operation on two sets of polygons.

This is equivalent to the following: 

clipper<Coord,Index> n{contig_mem};
n.add_loops(std::forward<SInput>(subject),bool_set::subject);
n.add_loops(std::forward<CInput>(clip),bool_set::clip);
RETURN_VALUE = std::move(n).execute<TreeOut>(op);
Coord must satisfy coordinate. Index must satisfy std::integral. SInput must satisfy point_range_or_range_range. CInput must satisfy point_range_or_range_range.

template<bool TreeOut, typename Coord, typename Index = std::size_t, typename SInput, typename CInput, typename Tracker>
std::conditional_t<TreeOut, temp_polygon_tree_range<Coord, Index, Tracker>, temp_polygon_range<Coord, Index, Tracker>> boolean_op(
SInput &&subject,
CInput &&clip,
bool_op op,
Tracker &&tracker,
std::pmr::memory_resource *contig_mem = nullptr,
)

Perform a boolean operation on two sets of polygons.

This is equivalent to the following: 

tclipper<Coord,Index,Tracker> n{std::forward<Tracker>(tracker),contig_mem};
n.add_loops(std::forward<SInput>(subject),bool_set::subject);
n.add_loops(std::forward<CInput>(clip),bool_set::clip);
RETURN_VALUE = std::move(n).execute<TreeOut>(op);
Coord must satisfy coordinate. Index must satisfy std::integral. SInput must satisfy point_range_or_range_range. CInput must satisfy point_range_or_range_range. Tracker must satisfy point_tracker<Coord,Index>.