| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | GHC2024 |
HGeometry.LineSegment.Intersection.Naive
Description
Line segment intersections in \(O(n^2)\) by checking all pairs.
Synopsis
- intersections :: (Ord r, Fractional r, LineSegment_ lineSegment point, Eq lineSegment, Point_ point 2 r, IntersectConstraints seg lineSegment, LineSegment_ seg point, Foldable f) => f lineSegment -> Intersections r lineSegment
- type Intersections r lineSegment = Map (Point 2 r) (Associated lineSegment)
- data Associated lineSegment
- startPointOf :: forall lineSegment f. Functor f => (Set (AroundStart lineSegment) -> f (Set (AroundStart lineSegment))) -> Associated lineSegment -> f (Associated lineSegment)
- endPointOf :: forall lineSegment f. Functor f => (Set (AroundEnd lineSegment) -> f (Set (AroundEnd lineSegment))) -> Associated lineSegment -> f (Associated lineSegment)
- interiorTo :: forall lineSegment f. Functor f => (Set (AroundIntersection lineSegment) -> f (Set (AroundIntersection lineSegment))) -> Associated lineSegment -> f (Associated lineSegment)
- associatedSegments :: forall lineSegment f. (Contravariant f, Applicative f) => (lineSegment -> f lineSegment) -> Associated lineSegment -> f (Associated lineSegment)
- data AroundEnd a
- data AroundStart a
- data AroundIntersection a
- isInteriorIntersection :: Associated lineSegment -> Bool
- data IntersectionPoint point lineSegment
- intersectionPointOf :: (LineSegment_ lineSegment point, LineSegment_ seg point, Point_ point 2 r, Ord r, Fractional r, IntersectConstraints seg lineSegment) => lineSegment -> lineSegment -> Maybe (IntersectionPoint (Point 2 r) lineSegment)
- intersectionPoint :: forall point lineSegment point' f. Functor f => (point -> f point') -> IntersectionPoint point lineSegment -> f (IntersectionPoint point' lineSegment)
- associatedSegs :: forall point lineSegment lineSegment' f. Functor f => (Associated lineSegment -> f (Associated lineSegment')) -> IntersectionPoint point lineSegment -> f (IntersectionPoint point lineSegment')
- type IntersectConstraints seg lineSegment = (OrdArounds lineSegment, IsIntersectableWith lineSegment lineSegment, Intersection lineSegment lineSegment ~ Maybe (LineSegmentLineSegmentIntersection seg), NumType seg ~ NumType lineSegment, Dimension seg ~ Dimension lineSegment)
- type OrdArounds lineSegment = (Ord (AroundStart lineSegment), Ord (AroundEnd lineSegment))
Documentation
intersections :: (Ord r, Fractional r, LineSegment_ lineSegment point, Eq lineSegment, Point_ point 2 r, IntersectConstraints seg lineSegment, LineSegment_ seg point, Foldable f) => f lineSegment -> Intersections r lineSegment Source #
Compute all intersections (naively)
\(O(n^2)\)
type Intersections r lineSegment = Map (Point 2 r) (Associated lineSegment) Source #
For each intersection point the segments intersecting there.
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
| NFData lineSegment => NFData (Associated lineSegment) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types Methods rnf :: Associated lineSegment -> () # | |||||
| (OrdArounds lineSegment, LineSegment_ lineSegment point, Point_ point 2 r, Ord r, Fractional r, HasSupportingLine lineSegment) => Monoid (Associated lineSegment) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types Methods mempty :: Associated lineSegment # mappend :: Associated lineSegment -> Associated lineSegment -> Associated lineSegment # mconcat :: [Associated lineSegment] -> Associated lineSegment # | |||||
| (OrdArounds lineSegment, LineSegment_ lineSegment point, Point_ point 2 r, Ord r, Fractional r, HasSupportingLine lineSegment) => Semigroup (Associated lineSegment) Source # | |||||
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 # | |||||
Defined in HGeometry.LineSegment.Intersection.Types Associated Types
Methods from :: Associated lineSegment -> Rep (Associated lineSegment) x # to :: Rep (Associated lineSegment) x -> Associated lineSegment # | |||||
| Show lineSegment => Show (Associated lineSegment) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types Methods showsPrec :: Int -> Associated lineSegment -> ShowS # show :: Associated lineSegment -> String # showList :: [Associated lineSegment] -> ShowS # | |||||
| (Eq (AroundStart lineSegment), Eq (AroundIntersection lineSegment), Eq (AroundEnd lineSegment)) => Eq (Associated lineSegment) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types Methods (==) :: Associated lineSegment -> Associated lineSegment -> Bool # (/=) :: Associated lineSegment -> Associated lineSegment -> Bool # | |||||
| type Rep (Associated lineSegment) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types type Rep (Associated lineSegment) = D1 ('MetaData "Associated" "HGeometry.LineSegment.Intersection.Types" "hgeometry-1.0.0.0-inplace-lineSegmentIntersection" '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 f. Functor f => (Set (AroundStart lineSegment) -> f (Set (AroundStart lineSegment))) -> Associated lineSegment -> f (Associated lineSegment) Source #
Lens to access the segments for which this is a startPoint
endPointOf :: forall lineSegment f. Functor f => (Set (AroundEnd lineSegment) -> f (Set (AroundEnd lineSegment))) -> Associated lineSegment -> f (Associated lineSegment) Source #
Lens to access the segments for which this is an endPoint
interiorTo :: forall lineSegment f. Functor f => (Set (AroundIntersection lineSegment) -> f (Set (AroundIntersection lineSegment))) -> Associated lineSegment -> f (Associated lineSegment) Source #
Lens to access the segments for which this point lies in the interior of the segment
associatedSegments :: forall lineSegment f. (Contravariant f, Applicative f) => (lineSegment -> f lineSegment) -> Associated lineSegment -> f (Associated lineSegment) Source #
Fold over the segments associated with the intersection.
Assumes that two segments have the same end point (ordering is CCW around common endpoint) (note that we specifically mean end point; not startpoint. See AroundStart)
Instances
| Functor AroundEnd Source # | |||||
| NFData a => NFData (AroundEnd a) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types | |||||
| Generic (AroundEnd a) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types Associated Types
| |||||
| Show a => Show (AroundEnd a) Source # | |||||
| (Point_ point 2 r, Eq r, HasStart lineSegment point) => Eq (AroundEnd lineSegment) Source # | |||||
| (LineSegment_ lineSegment point, Point_ point 2 r, Ord r, Num r, Eq lineSegment) => Ord (AroundEnd lineSegment) Source # | |||||
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 # | |||||
| AroundEnd a ~ t => Rewrapped (AroundEnd a) t Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types | |||||
| type Rep (AroundEnd a) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types type Rep (AroundEnd a) = D1 ('MetaData "AroundEnd" "HGeometry.LineSegment.Intersection.Types" "hgeometry-1.0.0.0-inplace-lineSegmentIntersection" 'True) (C1 ('MetaCons "AroundEnd" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a))) | |||||
| type Unwrapped (AroundEnd a) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types | |||||
data AroundStart a Source #
A newtype helping us order segments CCW around their common start point. I.e. this assumes that two segments have the same start point.
Instances
data AroundIntersection a Source #
This type represents a line segment seg, that contains some
globally known point "p" in its interior. The Ord instance of
AroundIntersection orders segments of this type "around" p. In
particular, it orders the segments in CCW order by their starting
point (starting from the positive x-axis).
Instances
| Functor AroundIntersection Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types Methods fmap :: (a -> b) -> AroundIntersection a -> AroundIntersection b # (<$) :: a -> AroundIntersection b -> AroundIntersection a # | |||||
| NFData a => NFData (AroundIntersection a) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types Methods rnf :: AroundIntersection a -> () # | |||||
| Generic (AroundIntersection a) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types Associated Types
Methods from :: AroundIntersection a -> Rep (AroundIntersection a) x # to :: Rep (AroundIntersection a) x -> AroundIntersection a # | |||||
| Show a => Show (AroundIntersection a) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types Methods showsPrec :: Int -> AroundIntersection a -> ShowS # show :: AroundIntersection a -> String # showList :: [AroundIntersection a] -> ShowS # | |||||
| Eq a => Eq (AroundIntersection a) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types Methods (==) :: AroundIntersection a -> AroundIntersection a -> Bool # (/=) :: AroundIntersection a -> AroundIntersection a -> Bool # | |||||
| Wrapped (AroundIntersection a) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types Associated Types
Methods _Wrapped' :: Iso' (AroundIntersection a) (Unwrapped (AroundIntersection a)) Source # | |||||
| AroundIntersection a ~ t => Rewrapped (AroundIntersection a) t Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types | |||||
| type Rep (AroundIntersection a) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types type Rep (AroundIntersection a) = D1 ('MetaData "AroundIntersection" "HGeometry.LineSegment.Intersection.Types" "hgeometry-1.0.0.0-inplace-lineSegmentIntersection" 'True) (C1 ('MetaCons "AroundIntersection" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a))) | |||||
| type Unwrapped (AroundIntersection a) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types | |||||
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
| (NFData point, NFData lineSegment) => NFData (IntersectionPoint point lineSegment) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types Methods rnf :: IntersectionPoint point lineSegment -> () # | |||||
| Generic (IntersectionPoint point lineSegment) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types Associated Types
Methods from :: IntersectionPoint point lineSegment -> Rep (IntersectionPoint point lineSegment) x # to :: Rep (IntersectionPoint point lineSegment) x -> IntersectionPoint point lineSegment # | |||||
| (Show point, Show lineSegment) => Show (IntersectionPoint point lineSegment) Source # | |||||
Defined in HGeometry.LineSegment.Intersection.Types Methods showsPrec :: Int -> IntersectionPoint point lineSegment -> ShowS # show :: IntersectionPoint point lineSegment -> String # showList :: [IntersectionPoint point lineSegment] -> ShowS # | |||||
| (Eq (AroundStart lineSegment), Eq (AroundIntersection lineSegment), Eq (AroundEnd lineSegment), Eq point) => Eq (IntersectionPoint point lineSegment) Source # | |||||
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 # | |||||
Defined in HGeometry.LineSegment.Intersection.Types type Rep (IntersectionPoint point lineSegment) = D1 ('MetaData "IntersectionPoint" "HGeometry.LineSegment.Intersection.Types" "hgeometry-1.0.0.0-inplace-lineSegmentIntersection" '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, LineSegment_ seg point, Point_ point 2 r, Ord r, Fractional r, IntersectConstraints seg 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' f. Functor f => (point -> f point') -> IntersectionPoint point lineSegment -> f (IntersectionPoint point' lineSegment) Source #
Lens to access the intersectionp oint
associatedSegs :: forall point lineSegment lineSegment' f. Functor f => (Associated lineSegment -> f (Associated lineSegment')) -> IntersectionPoint point lineSegment -> f (IntersectionPoint point lineSegment') Source #
Lens to access the associated segments
type IntersectConstraints seg lineSegment = (OrdArounds lineSegment, IsIntersectableWith lineSegment lineSegment, Intersection lineSegment lineSegment ~ Maybe (LineSegmentLineSegmentIntersection seg), NumType seg ~ NumType lineSegment, Dimension seg ~ Dimension lineSegment) Source #
Shorthand for the more-or-less standard constraints that we need on LineSegments
type OrdArounds lineSegment = (Ord (AroundStart lineSegment), Ord (AroundEnd lineSegment)) Source #
Shorthand for the required Ord instances