ShamosHoey
class ShamosHoey(segments: Collection<Segment2<*>>, precision: DoubleEquivalence = DEFAULT_DOUBLE_EQUIVALENCE) : Algorithm<Boolean> (source)
Detects whether any pair of two-dimensional segments intersects. Only endpoint events are needed: each newly neighboring pair is tested immediately, as in the Shamos–Hoey algorithm (Algorithm 1). This takes O(n log n) time and O(n) space with the AVL order-maintenance tree under consistent geometric predicates. Near the floating-point tolerance boundary, the sweep can disagree with pairwise intersection tests (see precision tracking issue). Shared endpoints and overlaps count as intersections. Polygon simplicity, which allows only shared corners of consecutive edges, is handled separately by polygonHasSelfIntersection.
Parameters
segments
The segments to inspect.
precision
The equivalence used for geometric comparisons.
Constructors
Link copied to clipboard
constructor(segments: Collection<Segment2<*>>, precision: DoubleEquivalence = DEFAULT_DOUBLE_EQUIVALENCE)