Aleph::SegmentArrangement Class Reference

Compute the full planar subdivision induced by a set of segments. More...

#include <geom_algorithms.H>

Collaboration diagram for Aleph::SegmentArrangement:

Classes
struct	ArrEdge
	Represents an edge in the planar subdivision. More...
struct	ArrFace
	Represents a face (region) in the planar subdivision. More...
struct	HalfEdge
	Internal half-edge structure used for face traversal. More...
struct	Result
	The complete result of the segment arrangement computation. More...

Public Member Functions
Result	operator() (const Array< Segment > &segments) const
	Compute the arrangement of a set of segments.

Static Private Member Functions
static bool	pt_less (const Point &a, const Point &b)
	Lexicographic point comparison.
static size_t	find_vertex (const Array< Point > &verts, const Point &p)
	Find the index of point p in a sorted vertex array (binary search).
static int	angle_quad (const Geom_Number &dx, const Geom_Number &dy)
	Angular quadrant of direction (dx, dy).
static bool	angle_lt (const Geom_Number &dx1, const Geom_Number &dy1, const Geom_Number &dx2, const Geom_Number &dy2)
	Compare two directions from the same origin by angle (exact).

Static Private Attributes
static constexpr size_t	NONE = ~static_cast<size_t>(0)

Detailed Description

Compute the full planar subdivision induced by a set of segments.

Given n segments, produces:

• Vertices: segment endpoints + intersection points (deduplicated).
• Edges: sub-segments between consecutive vertices along each segment.
• Faces: connected regions of the plane (including the unbounded face).

Complexity

For n segments with k intersections:

• Time: O((n + k) log(n + k))
• Space: O(n + k)

Example

Array<Segment> segs;
segs.append(Segment(Point(0,0), Point(2,2)));
segs.append(Segment(Point(0,2), Point(2,0)));
SegmentArrangement arr;
auto res = arr(segs);
// res.vertices / res.edges / res.faces describe the subdivision.

Definition at line 10359 of file geom_algorithms.H.

Member Function Documentation

angle_lt()

static bool Aleph::SegmentArrangement::angle_lt ( const Geom_Number &  dx1, const Geom_Number &  dy1, const Geom_Number &  dx2, const Geom_Number &  dy2  )

inlinestaticprivate

Compare two directions from the same origin by angle (exact).

Returns true if (dx1,dy1) has a smaller CCW angle than (dx2,dy2).

Definition at line 10428 of file geom_algorithms.H.

References angle_quad(), and Aleph::divide_and_conquer_partition_dp().

angle_quad()

static int Aleph::SegmentArrangement::angle_quad ( const Geom_Number &  dx, const Geom_Number &  dy  )

inlinestaticprivate

Angular quadrant of direction (dx, dy).

Definition at line 10417 of file geom_algorithms.H.

References Aleph::and, and Aleph::divide_and_conquer_partition_dp().

Referenced by angle_lt().

find_vertex()

static size_t Aleph::SegmentArrangement::find_vertex ( const Array< Point > &  verts, const Point &  p  )

inlinestaticprivate

Find the index of point p in a sorted vertex array (binary search).

Definition at line 10402 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), NONE, and pt_less().

Referenced by operator()().

operator()()

Result Aleph::SegmentArrangement::operator() ( const Array< Segment > &  segments ) const

inline

Compute the arrangement of a set of segments.

Parameters

segments

Input segments (non-degenerate).

Returns

Vertices, edges, and faces of the planar subdivision.

Definition at line 10461 of file geom_algorithms.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), find_vertex(), Aleph::Point::get_x(), NONE, pt_less(), Aleph::quicksort_op(), Aleph::Array< T >::reserve(), Aleph::Array< T >::size(), Aleph::SegmentArrangement::ArrFace::unbounded, and Aleph::vertical.

pt_less()

static bool Aleph::SegmentArrangement::pt_less ( const Point &  a, const Point &  b  )

inlinestaticprivate

Lexicographic point comparison.

Definition at line 10395 of file geom_algorithms.H.

References Aleph::Point::get_x(), and Aleph::Point::get_y().

Referenced by find_vertex(), and operator()().

Member Data Documentation

NONE

constexpr size_t Aleph::SegmentArrangement::NONE = ~static_cast<size_t>(0)

staticconstexprprivate

Definition at line 10392 of file geom_algorithms.H.

Referenced by find_vertex(), and operator()().

---

The documentation for this class was generated from the following file:

• geom_algorithms.H