Aleph::SweepLineSegmentIntersection Class Reference

Report all pairwise intersection points among a set of segments. More...

#include <geom_algorithms.H>

Classes
struct	Event
	Represents an event in the sweep-line algorithm. More...
struct	EventLess
	Functor wrapper for event_less (used by LineSweepFramework). More...
struct	Intersection
	A single intersection record. More...
class	StatusTree
	Sweep-line status as a balanced tree with O(log n) updates. More...

Public Member Functions
Array< Intersection >	operator() (const Array< Segment > &segments) const
	Find all pairwise segment intersection points.

Private Types
enum class	EventType { LEFT , INTERSECTION , RIGHT }
	Types of events in the Bentley-Ottmann sweep. More...

Static Private Member Functions
static Geom_Number	y_at_x (const Segment &s, const Geom_Number &x)
	Evaluate the y-coordinate of segment s at x = x.
static Segment	canonicalize (const Segment &s)
	Canonicalize a segment so its src is the "left" endpoint.
static bool	event_less (const Event &a, const Event &b)
	Ordering for events in the sweep queue.
static bool	slope_less (const Segment &a, const Segment &b)
static bool	status_less (const size_t lhs, const size_t rhs, const Geom_Number &sx, const Array< Segment > &segs)
static void	check_and_enqueue (const Array< Segment > &segs, const size_t i, const size_t j, const Geom_Number &sx, LineSweepFramework< Event, EventLess > &eq, DynSetTree< size_t, Treap_Rk > &seen_pairs, const size_t n)
	Detect an intersection and enqueue it as a future event.

Detailed Description

Report all pairwise intersection points among a set of segments.

Uses the Bentley-Ottmann sweep-line paradigm:

• An event queue processes left endpoints, right endpoints, and discovered intersection points from left to right.
• A sweep-line status keeps active segments ordered by their y-coordinate at the current sweep x.
• Only adjacent pairs in the sweep-line status are tested for intersection, bounding the total work.

Complexity

• Time: O((n + k) log n) where n = segments, k = intersections.
• Space: O(n + k)

Assumptions

• Segments must not be zero-length (src == tgt).
• Overlapping collinear segments are reported at their overlap boundary points (start and end of the shared interval).

Definition at line 5881 of file geom_algorithms.H.

Member Enumeration Documentation

EventType

enum class Aleph::SweepLineSegmentIntersection::EventType

strongprivate

Types of events in the Bentley-Ottmann sweep.

Enumerator
LEFT
INTERSECTION
RIGHT

Definition at line 5945 of file geom_algorithms.H.

Member Function Documentation

canonicalize()

static Segment Aleph::SweepLineSegmentIntersection::canonicalize ( const Segment &  s )

inlinestaticprivate

Canonicalize a segment so its src is the "left" endpoint.

This normalizes event generation:

• If x differs, the smaller-x endpoint becomes src.
• If x ties (vertical), the smaller-y endpoint becomes src.

Parameters

s	Input segment.

Returns

Segment with consistent (src,tgt) orientation.

Definition at line 5927 of file geom_algorithms.H.

References Aleph::Segment::get_src_point(), Aleph::Segment::get_tgt_point(), Aleph::Point::get_x(), and Aleph::Point::get_y().

Referenced by operator()().

check_and_enqueue()

static void Aleph::SweepLineSegmentIntersection::check_and_enqueue ( const Array< Segment > &  segs, const size_t  i, const size_t  j, const Geom_Number &  sx, LineSweepFramework< Event, EventLess > &  eq, DynSetTree< size_t, Treap_Rk > &  seen_pairs, const size_t  n  )

inlinestaticprivate

Detect an intersection and enqueue it as a future event.

Checks segments i and j for intersection. For non-parallel segments, reports the unique intersection point. For collinear overlapping segments, reports the overlap boundary points. Only intersections at x >= sx are enqueued.

Parameters

	segs	Canonicalized segment array.
	i	First segment index.
	j	Second segment index.
	sx	Current sweep x.
[in,out]	eq	Event queue.
[in,out]	seen_pairs	Set preventing duplicate pair processing.
	n	Total number of segments (used for pair-key encoding).

Definition at line 6283 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::eq(), INTERSECTION, Aleph::SegmentSegmentIntersection::OVERLAP, and Aleph::segment_segment_intersection().

Referenced by operator()().

event_less()

static bool Aleph::SweepLineSegmentIntersection::event_less ( const Event &  a, const Event &  b  )

inlinestaticprivate

Ordering for events in the sweep queue.

Sort key:

• increasing x
• then increasing y
• then event type (LEFT < INTERSECTION < RIGHT)

Definition at line 5966 of file geom_algorithms.H.

References Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::SweepLineSegmentIntersection::Event::pt, and Aleph::SweepLineSegmentIntersection::Event::type.

Referenced by Aleph::SweepLineSegmentIntersection::EventLess::operator()().

operator()()

Array< Intersection > Aleph::SweepLineSegmentIntersection::operator() ( const Array< Segment > &  segments ) const

inline

Find all pairwise segment intersection points.

Parameters

segments

Input segments.

Returns

Array of intersection records (i < j, sorted by x then y).

Exceptions

domain_error

if any segment is degenerate (zero length).

Definition at line 6332 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::and, Aleph::Array< T >::append(), canonicalize(), check_and_enqueue(), Aleph::SweepLineSegmentIntersection::StatusTree::contains(), Aleph::contains(), Aleph::divide_and_conquer_partition_dp(), Aleph::LineSweepFramework< Event, CmpEvent >::enqueue(), Aleph::eq(), Aleph::SweepLineSegmentIntersection::StatusTree::erase(), Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::SweepLineSegmentIntersection::StatusTree::insert(), LEFT, Aleph::SweepLineSegmentIntersection::Intersection::point, pred, Aleph::SweepLineSegmentIntersection::StatusTree::predecessor(), Aleph::quicksort_op(), Aleph::Array< T >::reserve(), RIGHT, seed, Aleph::SweepLineSegmentIntersection::Intersection::seg_i, Aleph::SweepLineSegmentIntersection::Intersection::seg_j, Aleph::Array< T >::size(), and Aleph::SweepLineSegmentIntersection::StatusTree::successor().

slope_less()

static bool Aleph::SweepLineSegmentIntersection::slope_less ( const Segment &  a, const Segment &  b  )

inlinestaticprivate

Definition at line 5985 of file geom_algorithms.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::Segment::get_src_point(), Aleph::Segment::get_tgt_point(), Aleph::Point::get_x(), and Aleph::Point::get_y().

Referenced by status_less().

status_less()

static bool Aleph::SweepLineSegmentIntersection::status_less ( const size_t  lhs, const size_t  rhs, const Geom_Number &  sx, const Array< Segment > &  segs  )

inlinestaticprivate

Definition at line 6004 of file geom_algorithms.H.

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

Referenced by Aleph::SweepLineSegmentIntersection::StatusTree::predecessor_for_insert(), and Aleph::SweepLineSegmentIntersection::StatusTree::successor_for_insert().

y_at_x()

static Geom_Number Aleph::SweepLineSegmentIntersection::y_at_x ( const Segment &  s, const Geom_Number &  x  )

inlinestaticprivate

Evaluate the y-coordinate of segment s at x = x.

Used to order active segments in the sweep-line status.

Parameters

s	Segment (assumed non-degenerate).
x	Sweep x coordinate.

Returns

y coordinate of the intersection of the segment with the vertical line x = x. For vertical segments, returns the midpoint y.

Definition at line 5903 of file geom_algorithms.H.

References Aleph::Segment::get_src_point(), Aleph::Segment::get_tgt_point(), Aleph::Point::get_x(), Aleph::Point::get_y(), and y1().

Referenced by status_less().

---

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

• geom_algorithms.H