Copyright | (C) Frank Staals |
---|---|
License | see the LICENSE file |
Maintainer | Frank Staals |
Safe Haskell | Safe-Inferred |
Language | GHC2021 |
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 lineSegment, Foldable f) => f lineSegment -> Intersections r lineSegment
- type Intersections r lineSegment = Map (Point 2 r) (Associated lineSegment)
- data Associated lineSegment
- startPointOf :: Lens' (Associated lineSegment) (Set (AroundStart lineSegment))
- endPointOf :: Lens' (Associated lineSegment) (Set (AroundEnd lineSegment))
- interiorTo :: 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 :: Lens (IntersectionPoint point lineSegment) (IntersectionPoint point' lineSegment) point point'
- associatedSegs :: 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 :: (Ord r, Fractional r, LineSegment_ lineSegment point, Eq lineSegment, Point_ point 2 r, IntersectConstraints lineSegment, 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
startPointOf :: Lens' (Associated lineSegment) (Set (AroundStart lineSegment)) Source #
Lens to access the segments for which this is a startPoint
endPointOf :: Lens' (Associated lineSegment) (Set (AroundEnd lineSegment)) Source #
Lens to access the segments for which this is an endPoint
interiorTo :: Lens' (Associated lineSegment) (Set (AroundIntersection lineSegment)) Source #
Lens to access the segments for which this point lies in the interior of the segment
associatedSegments :: Fold (Associated lineSegment) lineSegment Source #
Fold over the segments associated with the intersection.
Assumes that two segments have the same end point
Instances
data AroundStart a Source #
Assumes that two segments have the same start point
Instances
data AroundIntersection a Source #
Assumes that two segments intersect in a single point.
Instances
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
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 :: Lens (IntersectionPoint point lineSegment) (IntersectionPoint point' lineSegment) point point' Source #
Lens to access the intersectionp oint
associatedSegs :: Lens (IntersectionPoint point lineSegment) (IntersectionPoint point lineSegment') (Associated lineSegment) (Associated lineSegment') Source #
Lens to access the associated segments
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 #