Algorithms.Geometry.LineSegmentIntersection.BentleyOttmann

Documentation

intersections :: (Ord r, Fractional r) => [LineSegment 2 p r] -> Intersections p r

Compute all intersections

\(O((n+k)\log n)\), where \(k\) is the number of intersections.

merge :: Ord r => [IntersectionPoint p r] -> Intersections p r

Group the segments with the intersection points

groupStarts :: Eq r => [Event p r] -> [Event p r]

Group the startpoints such that segments with the same start point correspond to one event.

Data type for Events

data EventType s

Type of segment

Constructors

Start !(NonEmpty s)

Intersection

End !s

Instances

Eq (EventType s)

Methods

(==) :: EventType s -> EventType s -> Bool

(/=) :: EventType s -> EventType s -> Bool

Ord (EventType s)

Methods

compare :: EventType s -> EventType s -> Ordering

(<) :: EventType s -> EventType s -> Bool

(<=) :: EventType s -> EventType s -> Bool

(>) :: EventType s -> EventType s -> Bool

(>=) :: EventType s -> EventType s -> Bool

max :: EventType s -> EventType s -> EventType s

min :: EventType s -> EventType s -> EventType s

Show s => Show (EventType s)

Methods

showsPrec :: Int -> EventType s -> ShowS

show :: EventType s -> String

showList :: [EventType s] -> ShowS

data Event p r

The actual event consists of a point and its type

Constructors

Event

Fields

• eventPoint :: !(Point 2 r)
• eventType :: !(EventType (LineSegment 2 p r))

Instances

Eq r => Eq (Event p r)

Methods

(==) :: Event p r -> Event p r -> Bool

(/=) :: Event p r -> Event p r -> Bool

Ord r => Ord (Event p r)

Methods

compare :: Event p r -> Event p r -> Ordering

(<) :: Event p r -> Event p r -> Bool

(<=) :: Event p r -> Event p r -> Bool

(>) :: Event p r -> Event p r -> Bool

(>=) :: Event p r -> Event p r -> Bool

max :: Event p r -> Event p r -> Event p r

min :: Event p r -> Event p r -> Event p r

(Show p, Show r) => Show (Event p r)

Methods

showsPrec :: Int -> Event p r -> ShowS

show :: Event p r -> String

showList :: [Event p r] -> ShowS

ordPoints :: Ord r => Point 2 r -> Point 2 r -> Ordering

An ordering that is decreasing on y, increasing on x

startSegs :: Event p r -> [LineSegment 2 p r]

Get the segments that start at the given event point

ordAtNav :: (Ord r, Fractional r) => r -> TreeNavigator r (LineSegment 2 p r)

The navigator that we use that orders the segments that intersect at a horizontal line (from left to right)

The Main Sweep

type EventQueue p r = Set (Event p r)

type StatusStructure p r = BalBST r (LineSegment 2 p r)

sweep :: (Ord r, Fractional r) => EventQueue p r -> StatusStructure p r -> [IntersectionPoint p r]

Run the sweep handling all events

handle :: (Ord r, Fractional r) => Event p r -> EventQueue p r -> StatusStructure p r -> [IntersectionPoint p r]

Handle an event point

extractContains :: (Fractional r, Ord r) => Point 2 r -> StatusStructure p r -> (StatusStructure p r, [LineSegment 2 p r], StatusStructure p r)

split the status structure, extracting the segments that contain p. the result is (before,contains,after)

toStatusStruct :: (Fractional r, Ord r) => Point 2 r -> [LineSegment 2 p r] -> StatusStructure p r

Given a point and the linesegements that contain it. Create a piece of status structure for it.

rightEndpoint :: Ord r => LineSegment 2 p r -> r

Get the right endpoint of a segment

endsAt :: Ord r => Point 2 r -> LineSegment 2 p r -> Bool

Test if a segment ends at p

Finding New events

findNewEvent :: (Ord r, Fractional r) => Point 2 r -> LineSegment 2 p r -> LineSegment 2 p r -> Maybe (Event p r)

Find all events