Copyright	(C) Frank Staals
License	see the LICENSE file
Maintainer	Frank Staals
Safe Haskell	Safe-Inferred
Language	GHC2021

HGeometry.LineSegment.Intersection.BentleyOttmann

Description

The $O((n+k)\log n)$ time line segment intersection algorithm by Bentley and Ottmann.

Synopsis

intersections :: forall lineSegment point r f. (LineSegment_ lineSegment point, Point_ point 2 r, Eq lineSegment, Ord r, Fractional r, HasOnSegment lineSegment 2, IntersectConstraints lineSegment, Foldable f, Functor f, StartPointOf lineSegment ~ EndPointOf lineSegment) => f lineSegment -> Intersections r lineSegment
interiorIntersections :: (LineSegment_ lineSegment point, Point_ point 2 r, Eq lineSegment, Ord r, Fractional r, IntersectConstraints lineSegment, StartPointOf lineSegment ~ EndPointOf lineSegment, HasOnSegment lineSegment 2, Foldable f, Functor f) => f lineSegment -> Intersections r lineSegment
type Intersections r lineSegment = Map (Point 2 r) (Associated lineSegment)
intersectionPoints :: Intersections r lineSegment -> Set (Point 2 r)
data Associated lineSegment
startPointOf :: forall lineSegment. Lens' (Associated lineSegment) (Set (AroundStart lineSegment))
endPointOf :: forall lineSegment. Lens' (Associated lineSegment) (Set (AroundEnd lineSegment))
interiorTo :: forall lineSegment. Lens' (Associated lineSegment) (Set (AroundIntersection lineSegment))
associatedSegments :: Fold (Associated lineSegment) lineSegment
data AroundEnd a
data AroundStart a
data AroundIntersection a
isInteriorIntersection :: Associated lineSegment -> Bool
data IntersectionPoint point lineSegment
intersectionPointOf :: (LineSegment_ lineSegment point, Point_ point 2 r, Ord r, Fractional r, IntersectConstraints lineSegment) => lineSegment -> lineSegment -> Maybe (IntersectionPoint (Point 2 r) lineSegment)
intersectionPoint :: forall point lineSegment point. Lens (IntersectionPoint point lineSegment) (IntersectionPoint point lineSegment) point point
associatedSegs :: forall point lineSegment lineSegment. Lens (IntersectionPoint point lineSegment) (IntersectionPoint point lineSegment) (Associated lineSegment) (Associated lineSegment)
type IntersectConstraints lineSegment = (OrdArounds lineSegment, IsIntersectableWith lineSegment lineSegment, Intersection lineSegment lineSegment ~ Maybe (LineSegmentLineSegmentIntersection lineSegment))
type OrdArounds lineSegment = (Ord (AroundStart lineSegment), Ord (AroundIntersection lineSegment), Ord (AroundEnd lineSegment))

Documentation

intersections :: forall lineSegment point r f. (LineSegment_ lineSegment point, Point_ point 2 r, Eq lineSegment, Ord r, Fractional r, HasOnSegment lineSegment 2, IntersectConstraints lineSegment, Foldable f, Functor f, StartPointOf lineSegment ~ EndPointOf lineSegment) => f lineSegment -> Intersections r lineSegment Source #

Compute all intersections

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

interiorIntersections :: (LineSegment_ lineSegment point, Point_ point 2 r, Eq lineSegment, Ord r, Fractional r, IntersectConstraints lineSegment, StartPointOf lineSegment ~ EndPointOf lineSegment, HasOnSegment lineSegment 2, Foldable f, Functor f) => f lineSegment -> Intersections r lineSegment Source #

Computes all intersection points p s.t. p lies in the interior of at least one of the segments.

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

type Intersections r lineSegment = Map (Point 2 r) (Associated lineSegment) Source #

For each intersection point the segments intersecting there.

intersectionPoints :: Intersections r lineSegment -> Set (Point 2 r) Source #

Get the set of all intersection points

data Associated lineSegment Source #

The line segments that contain a given point p may either have p as the endpoint or have p in their interior.

if somehow the segment is degenerate, and p is both the start and end it is reported only as the start point.

Instances

Instances details

OrdArounds lineSegment => Monoid (Associated lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods mempty :: Associated lineSegment # mappend :: Associated lineSegment -> Associated lineSegment -> Associated lineSegment # mconcat :: [Associated lineSegment] -> Associated lineSegment #
OrdArounds lineSegment => Semigroup (Associated lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods (<>) :: Associated lineSegment -> Associated lineSegment -> Associated lineSegment # sconcat :: NonEmpty (Associated lineSegment) -> Associated lineSegment # stimes :: Integral b => b -> Associated lineSegment -> Associated lineSegment #
Generic (Associated lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Associated Types type Rep (Associated lineSegment) :: Type -> Type # Methods from :: Associated lineSegment -> Rep (Associated lineSegment) x # to :: Rep (Associated lineSegment) x -> Associated lineSegment #
(Read lineSegment, OrdArounds lineSegment) => Read (Associated lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods readsPrec :: Int -> ReadS (Associated lineSegment) # readList :: ReadS [Associated lineSegment] # readPrec :: ReadPrec (Associated lineSegment) # readListPrec :: ReadPrec [Associated lineSegment] #
Show lineSegment => Show (Associated lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods showsPrec :: Int -> Associated lineSegment -> ShowS # show :: Associated lineSegment -> String # showList :: [Associated lineSegment] -> ShowS #
NFData lineSegment => NFData (Associated lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods rnf :: Associated lineSegment -> () #
(Eq (AroundStart lineSegment), Eq (AroundIntersection lineSegment), Eq (AroundEnd lineSegment)) => Eq (Associated lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods (==) :: Associated lineSegment -> Associated lineSegment -> Bool # (/=) :: Associated lineSegment -> Associated lineSegment -> Bool #
type Rep (Associated lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types type Rep (Associated lineSegment) = D1 ('MetaData "Associated" "HGeometry.LineSegment.Intersection.Types" "hgeometry-1.0.0.0-inplace" 'False) (C1 ('MetaCons "Associated" 'PrefixI 'True) (S1 ('MetaSel ('Just "_startPointOf") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Set (AroundStart lineSegment))) :: (S1 ('MetaSel ('Just "_endPointOf") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Set (AroundEnd lineSegment))) :: S1 ('MetaSel ('Just "_interiorTo") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Set (AroundIntersection lineSegment))))))

startPointOf :: forall lineSegment. Lens' (Associated lineSegment) (Set (AroundStart lineSegment)) Source #

endPointOf :: forall lineSegment. Lens' (Associated lineSegment) (Set (AroundEnd lineSegment)) Source #

interiorTo :: forall lineSegment. Lens' (Associated lineSegment) (Set (AroundIntersection lineSegment)) Source #

associatedSegments :: Fold (Associated lineSegment) lineSegment Source #

Fold over the segments associated with the intersection.

data AroundEnd a Source #

Assumes that two segments have the same end point

Instances

Instances details

Functor AroundEnd Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods fmap :: (a -> b) -> AroundEnd a -> AroundEnd b # (<$) :: a -> AroundEnd b -> AroundEnd a #
Read a => Read (AroundEnd a) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods readsPrec :: Int -> ReadS (AroundEnd a) # readList :: ReadS [AroundEnd a] # readPrec :: ReadPrec (AroundEnd a) # readListPrec :: ReadPrec [AroundEnd a] #
Show a => Show (AroundEnd a) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods showsPrec :: Int -> AroundEnd a -> ShowS # show :: AroundEnd a -> String # showList :: [AroundEnd a] -> ShowS #
NFData a => NFData (AroundEnd a) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods rnf :: AroundEnd a -> () #
(Point_ point 2 r, Eq r, HasStart lineSegment point) => Eq (AroundEnd lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods (==) :: AroundEnd lineSegment -> AroundEnd lineSegment -> Bool # (/=) :: AroundEnd lineSegment -> AroundEnd lineSegment -> Bool #
(LineSegment_ lineSegment point, Point_ point 2 r, Ord r, Num r, Eq lineSegment) => Ord (AroundEnd lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods compare :: AroundEnd lineSegment -> AroundEnd lineSegment -> Ordering # (<) :: AroundEnd lineSegment -> AroundEnd lineSegment -> Bool # (<=) :: AroundEnd lineSegment -> AroundEnd lineSegment -> Bool # (>) :: AroundEnd lineSegment -> AroundEnd lineSegment -> Bool # (>=) :: AroundEnd lineSegment -> AroundEnd lineSegment -> Bool # max :: AroundEnd lineSegment -> AroundEnd lineSegment -> AroundEnd lineSegment # min :: AroundEnd lineSegment -> AroundEnd lineSegment -> AroundEnd lineSegment #
Wrapped (AroundEnd a) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Associated Types type Unwrapped (AroundEnd a) Source # Methods _Wrapped' :: Iso' (AroundEnd a) (Unwrapped (AroundEnd a)) Source #
AroundEnd a1 ~ t => Rewrapped (AroundEnd a2) t Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types
type Unwrapped (AroundEnd a) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types type Unwrapped (AroundEnd a) = a

data AroundStart a Source #

Assumes that two segments have the same start point

Instances

Instances details

Functor AroundStart Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods fmap :: (a -> b) -> AroundStart a -> AroundStart b # (<$) :: a -> AroundStart b -> AroundStart a #
Read a => Read (AroundStart a) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods readsPrec :: Int -> ReadS (AroundStart a) # readList :: ReadS [AroundStart a] # readPrec :: ReadPrec (AroundStart a) # readListPrec :: ReadPrec [AroundStart a] #
Show a => Show (AroundStart a) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods showsPrec :: Int -> AroundStart a -> ShowS # show :: AroundStart a -> String # showList :: [AroundStart a] -> ShowS #
NFData a => NFData (AroundStart a) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods rnf :: AroundStart a -> () #
(Point_ point 2 r, Eq r, HasEnd lineSegment point) => Eq (AroundStart lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods (==) :: AroundStart lineSegment -> AroundStart lineSegment -> Bool # (/=) :: AroundStart lineSegment -> AroundStart lineSegment -> Bool #
(LineSegment_ lineSegment point, Point_ point 2 r, Ord r, Num r) => Ord (AroundStart lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods compare :: AroundStart lineSegment -> AroundStart lineSegment -> Ordering # (<) :: AroundStart lineSegment -> AroundStart lineSegment -> Bool # (<=) :: AroundStart lineSegment -> AroundStart lineSegment -> Bool # (>) :: AroundStart lineSegment -> AroundStart lineSegment -> Bool # (>=) :: AroundStart lineSegment -> AroundStart lineSegment -> Bool # max :: AroundStart lineSegment -> AroundStart lineSegment -> AroundStart lineSegment # min :: AroundStart lineSegment -> AroundStart lineSegment -> AroundStart lineSegment #
Wrapped (AroundStart a) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Associated Types type Unwrapped (AroundStart a) Source # Methods _Wrapped' :: Iso' (AroundStart a) (Unwrapped (AroundStart a)) Source #
AroundStart a1 ~ t => Rewrapped (AroundStart a2) t Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types
type Unwrapped (AroundStart a) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types type Unwrapped (AroundStart a) = a

data AroundIntersection a Source #

Assumes that two segments intersect in a single point.

Instances

Instances details

Functor AroundIntersection Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods fmap :: (a -> b) -> AroundIntersection a -> AroundIntersection b # (<$) :: a -> AroundIntersection b -> AroundIntersection a #
Read a => Read (AroundIntersection a) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods readsPrec :: Int -> ReadS (AroundIntersection a) # readList :: ReadS [AroundIntersection a] # readPrec :: ReadPrec (AroundIntersection a) # readListPrec :: ReadPrec [AroundIntersection a] #
Show a => Show (AroundIntersection a) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods showsPrec :: Int -> AroundIntersection a -> ShowS # show :: AroundIntersection a -> String # showList :: [AroundIntersection a] -> ShowS #
NFData a => NFData (AroundIntersection a) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods rnf :: AroundIntersection a -> () #
Eq a => Eq (AroundIntersection a) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods (==) :: AroundIntersection a -> AroundIntersection a -> Bool # (/=) :: AroundIntersection a -> AroundIntersection a -> Bool #
(LineSegment_ lineSegment point, Point_ point 2 r, Ord r, Fractional r, Eq lineSegment, IsIntersectableWith lineSegment lineSegment, Intersection lineSegment lineSegment ~ Maybe (LineSegmentLineSegmentIntersection lineSegment)) => Ord (AroundIntersection lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods compare :: AroundIntersection lineSegment -> AroundIntersection lineSegment -> Ordering # (<) :: AroundIntersection lineSegment -> AroundIntersection lineSegment -> Bool # (<=) :: AroundIntersection lineSegment -> AroundIntersection lineSegment -> Bool # (>) :: AroundIntersection lineSegment -> AroundIntersection lineSegment -> Bool # (>=) :: AroundIntersection lineSegment -> AroundIntersection lineSegment -> Bool # max :: AroundIntersection lineSegment -> AroundIntersection lineSegment -> AroundIntersection lineSegment # min :: AroundIntersection lineSegment -> AroundIntersection lineSegment -> AroundIntersection lineSegment #
Wrapped (AroundIntersection a) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Associated Types type Unwrapped (AroundIntersection a) Source # Methods _Wrapped' :: Iso' (AroundIntersection a) (Unwrapped (AroundIntersection a)) Source #
AroundIntersection a1 ~ t => Rewrapped (AroundIntersection a2) t Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types
type Unwrapped (AroundIntersection a) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types type Unwrapped (AroundIntersection a) = a

isInteriorIntersection :: Associated lineSegment -> Bool Source #

Reports whether this associated has any interior intersections

$O(1)$

data IntersectionPoint point lineSegment Source #

An intersection point together with all segments intersecting at this point.

Instances

Instances details

Generic (IntersectionPoint point lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Associated Types type Rep (IntersectionPoint point lineSegment) :: Type -> Type # Methods from :: IntersectionPoint point lineSegment -> Rep (IntersectionPoint point lineSegment) x # to :: Rep (IntersectionPoint point lineSegment) x -> IntersectionPoint point lineSegment #
(Read lineSegment, Read point, OrdArounds lineSegment) => Read (IntersectionPoint point lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods readsPrec :: Int -> ReadS (IntersectionPoint point lineSegment) # readList :: ReadS [IntersectionPoint point lineSegment] # readPrec :: ReadPrec (IntersectionPoint point lineSegment) # readListPrec :: ReadPrec [IntersectionPoint point lineSegment] #
(Show point, Show lineSegment) => Show (IntersectionPoint point lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods showsPrec :: Int -> IntersectionPoint point lineSegment -> ShowS # show :: IntersectionPoint point lineSegment -> String # showList :: [IntersectionPoint point lineSegment] -> ShowS #
(NFData point, NFData lineSegment) => NFData (IntersectionPoint point lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods rnf :: IntersectionPoint point lineSegment -> () #
(Eq (AroundStart lineSegment), Eq (AroundIntersection lineSegment), Eq (AroundEnd lineSegment), Eq point) => Eq (IntersectionPoint point lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types Methods (==) :: IntersectionPoint point lineSegment -> IntersectionPoint point lineSegment -> Bool # (/=) :: IntersectionPoint point lineSegment -> IntersectionPoint point lineSegment -> Bool #
type Rep (IntersectionPoint point lineSegment) Source #
Instance details Defined in HGeometry.LineSegment.Intersection.Types type Rep (IntersectionPoint point lineSegment) = D1 ('MetaData "IntersectionPoint" "HGeometry.LineSegment.Intersection.Types" "hgeometry-1.0.0.0-inplace" 'False) (C1 ('MetaCons "IntersectionPoint" 'PrefixI 'True) (S1 ('MetaSel ('Just "_intersectionPoint") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 point) :*: S1 ('MetaSel ('Just "_associatedSegs") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 (Associated lineSegment))))

intersectionPointOf :: (LineSegment_ lineSegment point, Point_ point 2 r, Ord r, Fractional r, IntersectConstraints lineSegment) => lineSegment -> lineSegment -> Maybe (IntersectionPoint (Point 2 r) lineSegment) Source #

Given two segments, compute an IntersectionPoint representing their intersection (if such an intersection exists).

intersectionPoint :: forall point lineSegment point. Lens (IntersectionPoint point lineSegment) (IntersectionPoint point lineSegment) point point Source #

associatedSegs :: forall point lineSegment lineSegment. Lens (IntersectionPoint point lineSegment) (IntersectionPoint point lineSegment) (Associated lineSegment) (Associated lineSegment) Source #

type IntersectConstraints lineSegment = (OrdArounds lineSegment, IsIntersectableWith lineSegment lineSegment, Intersection lineSegment lineSegment ~ Maybe (LineSegmentLineSegmentIntersection lineSegment)) Source #

Shorthand for the more-or-less standard constraints that we need on LineSegments

type OrdArounds lineSegment = (Ord (AroundStart lineSegment), Ord (AroundIntersection lineSegment), Ord (AroundEnd lineSegment)) Source #