Data.Geometry.VerticalRayShooting.PersistentSweep

Documentation

data VerticalRayShootingStructure p e r

The vertical ray shooting data structure

Constructors

VerticalRayShootingStructure r (Vector (r :+ StatusStructure p e r))

Instances

(Eq r, Eq p, Eq e) => Eq (VerticalRayShootingStructure p e r)

Defined in Data.Geometry.VerticalRayShooting.PersistentSweep

Methods

(==) :: VerticalRayShootingStructure p e r -> VerticalRayShootingStructure p e r -> Bool

(/=) :: VerticalRayShootingStructure p e r -> VerticalRayShootingStructure p e r -> Bool

(Show r, Show p, Show e) => Show (VerticalRayShootingStructure p e r)

Defined in Data.Geometry.VerticalRayShooting.PersistentSweep

Methods

showsPrec :: Int -> VerticalRayShootingStructure p e r -> ShowS

show :: VerticalRayShootingStructure p e r -> String

showList :: [VerticalRayShootingStructure p e r] -> ShowS

type StatusStructure p e r = Set (LineSegment 2 p r :+ e)

leftMost :: forall p e r. Getter (VerticalRayShootingStructure p e r) r

sweepStruct :: forall p e r. Getter (VerticalRayShootingStructure p e r) (Vector ((:+) r (StatusStructure p e r)))

Building the Data Structure

verticalRayShootingStructure :: (Ord r, Fractional r, Foldable1 t) => t (LineSegment 2 p r :+ e) -> VerticalRayShootingStructure p e r

Given a set of \(n\) interiorly pairwise disjoint *closed* segments, compute a vertical ray shooting data structure. (i.e. the endpoints of the segments may coincide).

pre: no vertical segments

running time: \(O(n\log n)\). space: \(O(n\log n)\).

Querying the Data Structure

segmentAbove :: (Ord r, Num r) => Point 2 r -> VerticalRayShootingStructure p e r -> Maybe (LineSegment 2 p r :+ e)

Find the segment vertically strictly above query point q, if it exists.

\(O(\log n)\)

segmentAboveOrOn :: (Ord r, Num r) => Point 2 r -> VerticalRayShootingStructure p e r -> Maybe (LineSegment 2 p r :+ e)

Find the segment vertically query point q, if it exists.

\(O(\log n)\)

findSlab :: Ord r => Point 2 r -> VerticalRayShootingStructure p e r -> Maybe (StatusStructure p e r)

Given a query point, find the (data structure of the) slab containing the query point

\(O(\log n)\)

lookupAbove :: (Ord r, Num r) => Point 2 r -> StatusStructure p e r -> Maybe (LineSegment 2 p r :+ e)

Finds the first segment strictly above q

\(O(\log n)\)

lookupAboveOrOn :: (Ord r, Num r) => Point 2 r -> StatusStructure p e r -> Maybe (LineSegment 2 p r :+ e)

Finds the segment containing or above the query point q

\(O(\log n)\)

searchInSlab :: Num r => (Line 2 r -> Bool) -> StatusStructure p e r -> Maybe (LineSegment 2 p r :+ e)

generic searching function