| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | Safe-Inferred |
| Language | GHC2021 |
HGeometry.VerticalRayShooting.PersistentSweep
Description
Synopsis
- type VerticalRayShootingStructure lineSegment = VerticalRayShootingStructure' (NumType lineSegment) lineSegment
- type StatusStructure lineSegment = Set lineSegment
- verticalRayShootingStructure :: (LineSegment_ lineSegment point, Point_ point 2 r, Ord r, Fractional r, Foldable1 f) => f lineSegment -> VerticalRayShootingStructure lineSegment
- segmentAbove :: (LineSegment_ lineSegment point, Point_ point 2 r, Point_ queryPoint 2 r, Ord r, Num r, HasSupportingLine lineSegment) => queryPoint -> VerticalRayShootingStructure lineSegment -> Maybe lineSegment
- segmentAboveOrOn :: (LineSegment_ lineSegment point, Point_ point 2 r, Point_ queryPoint 2 r, Ord r, Num r, HasSupportingLine lineSegment) => queryPoint -> VerticalRayShootingStructure lineSegment -> Maybe lineSegment
- findSlab :: (LineSegment_ lineSegment point, Point_ point 2 r, Point_ queryPoint 2 r, Ord r, Num r, HasSupportingLine lineSegment) => queryPoint -> VerticalRayShootingStructure lineSegment -> Maybe (StatusStructure lineSegment)
- lookupAbove :: (LineSegment_ lineSegment point, Point_ point 2 r, Point_ queryPoint 2 r, Ord r, Num r, HasSupportingLine lineSegment) => queryPoint -> StatusStructure lineSegment -> Maybe lineSegment
- lookupAboveOrOn :: (LineSegment_ lineSegment point, Point_ point 2 r, Point_ queryPoint 2 r, Ord r, Num r, HasSupportingLine lineSegment) => queryPoint -> StatusStructure lineSegment -> Maybe lineSegment
- searchInSlab :: (LineSegment_ lineSegment point, Point_ point 2 r, HasSupportingLine lineSegment, Num r) => (LinePV 2 r -> Bool) -> StatusStructure lineSegment -> Maybe lineSegment
Documentation
type VerticalRayShootingStructure lineSegment = VerticalRayShootingStructure' (NumType lineSegment) lineSegment Source #
The vertical ray shooting data structure
type StatusStructure lineSegment = Set lineSegment Source #
The status structure
Building the Data Structure
verticalRayShootingStructure :: (LineSegment_ lineSegment point, Point_ point 2 r, Ord r, Fractional r, Foldable1 f) => f lineSegment -> VerticalRayShootingStructure lineSegment Source #
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 :: (LineSegment_ lineSegment point, Point_ point 2 r, Point_ queryPoint 2 r, Ord r, Num r, HasSupportingLine lineSegment) => queryPoint -> VerticalRayShootingStructure lineSegment -> Maybe lineSegment Source #
Find the segment vertically strictly above query point q, if it exists.
\(O(\log n)\)
segmentAboveOrOn :: (LineSegment_ lineSegment point, Point_ point 2 r, Point_ queryPoint 2 r, Ord r, Num r, HasSupportingLine lineSegment) => queryPoint -> VerticalRayShootingStructure lineSegment -> Maybe lineSegment Source #
Find the segment vertically query point q, if it exists.
\(O(\log n)\)
findSlab :: (LineSegment_ lineSegment point, Point_ point 2 r, Point_ queryPoint 2 r, Ord r, Num r, HasSupportingLine lineSegment) => queryPoint -> VerticalRayShootingStructure lineSegment -> Maybe (StatusStructure lineSegment) Source #
Given a query point, find the (data structure of the) slab containing the query point
\(O(\log n)\)
lookupAbove :: (LineSegment_ lineSegment point, Point_ point 2 r, Point_ queryPoint 2 r, Ord r, Num r, HasSupportingLine lineSegment) => queryPoint -> StatusStructure lineSegment -> Maybe lineSegment Source #
Finds the first segment strictly above q
\(O(\log n)\)
lookupAboveOrOn :: (LineSegment_ lineSegment point, Point_ point 2 r, Point_ queryPoint 2 r, Ord r, Num r, HasSupportingLine lineSegment) => queryPoint -> StatusStructure lineSegment -> Maybe lineSegment Source #
Finds the segment containing or above the query point q
\(O(\log n)\)
searchInSlab :: (LineSegment_ lineSegment point, Point_ point 2 r, HasSupportingLine lineSegment, Num r) => (LinePV 2 r -> Bool) -> StatusStructure lineSegment -> Maybe lineSegment Source #
generic searching function