| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
Data.Geometry.Arrangement.Internal
Description
Data type for representing an Arrangement of lines in \(\mathbb{R}^2\).
Synopsis
- type ArrangementBoundary s e r = Vector (Point 2 r, VertexId' s, Maybe (Line 2 r :+ e))
- data Arrangement s l v e f r = Arrangement {
- _inputLines :: Vector (Line 2 r :+ l)
- _subdivision :: PlanarSubdivision s v e f r
- _boundedArea :: Rectangle () r
- _unboundedIntersections :: ArrangementBoundary s l r
- unboundedIntersections :: forall k (s :: k) l v e f r. Lens' (Arrangement (s :: k) l v e f r) (ArrangementBoundary s l r)
- subdivision :: forall k (s :: k) l v e f r v e f. Lens (Arrangement (s :: k) l v e f r) (Arrangement (s :: k) l v e f r) (PlanarSubdivision s v e f r) (PlanarSubdivision s v e f r)
- inputLines :: forall k (s :: k) l v e f r. Lens' (Arrangement (s :: k) l v e f r) (Vector ((:+) (Line 2 r) l))
- boundedArea :: forall k (s :: k) l v e f r. Lens' (Arrangement (s :: k) l v e f r) (Rectangle () r)
- constructArrangement :: (Ord r, Fractional r) => proxy s -> [Line 2 r :+ l] -> Arrangement s l () (Maybe l) () r
- constructArrangementInBox :: (Ord r, Fractional r) => proxy s -> Rectangle () r -> [Line 2 r :+ l] -> Arrangement s l () (Maybe l) () r
- constructArrangementInBox' :: (Ord r, Fractional r) => proxy s -> Rectangle () r -> [Line 2 r :+ l] -> Arrangement s l () (Maybe l) () r
- computeSegsAndParts :: forall r l. (Ord r, Fractional r) => Rectangle () r -> [Line 2 r :+ l] -> ([LineSegment 2 () r :+ Maybe l], [(Point 2 r, Maybe (Line 2 r :+ l))])
- perLine :: forall r l. (Ord r, Fractional r) => Rectangle () r -> (Line 2 r :+ l) -> [Line 2 r :+ l] -> [LineSegment 2 () r :+ l]
- intersectionPoint :: forall r l. (Ord r, Fractional r) => (Line 2 r :+ l) -> (Line 2 r :+ l) -> Maybe (Point 2 r)
- toSegments :: Ord r => [Point 2 r] -> [LineSegment 2 () r]
- makeBoundingBox :: (Ord r, Fractional r) => [Line 2 r :+ l] -> Rectangle () r
- intersections :: (Ord r, Fractional r) => [Line 2 r :+ l] -> [Point 2 r]
- sideIntersections :: (Ord r, Fractional r) => [Line 2 r :+ l] -> LineSegment 2 q r -> [(Point 2 r, Line 2 r :+ l)]
- unBoundedParts :: (Ord r, Fractional r) => Rectangle () r -> [Line 2 r :+ l] -> [(Point 2 r, Maybe (Line 2 r :+ l))]
- link :: Eq r => [(Point 2 r, a)] -> PlanarSubdivision s v (Maybe e) f r -> Vector (Point 2 r, VertexId' s, a)
- makePairs :: [a] -> [(a, [a])]
- allPairs :: [a] -> [(a, a)]
- alignWith :: (a -> b -> Bool) -> CSeq a -> CSeq b -> Maybe (CSeq (a, b))
- traverseLine :: (Ord r, Fractional r) => Line 2 r -> Arrangement s l v (Maybe e) f r -> [Dart s]
- findStart :: forall s l v e f r. (Ord r, Fractional r) => Line 2 r -> Arrangement s l v (Maybe e) f r -> Maybe (Dart s)
- findStartVertex :: (Ord r, Fractional r) => Point 2 r -> Arrangement s l v e f r -> Maybe (Point 2 r, VertexId' s, Maybe (Line 2 r :+ l))
- findStartDart :: PlanarSubdivision s v (Maybe e) f r -> VertexId' s -> Maybe (Dart s)
- follow :: (Ord r, Num r) => Arrangement s l v e f r -> Dart s -> Maybe (Dart s)
Documentation
data Arrangement s l v e f r Source #
Data type representing a two dimensional planar arrangement
Constructors
| Arrangement | |
Fields
| |
Instances
| (Fractional r, Eq r, Eq l, Eq v, Eq e, Eq f) => Eq (Arrangement s l v e f r) Source # | |
Defined in Data.Geometry.Arrangement.Internal Methods (==) :: Arrangement s l v e f r -> Arrangement s l v e f r -> Bool # (/=) :: Arrangement s l v e f r -> Arrangement s l v e f r -> Bool # | |
| (Show r, Show l, Show v, Show e, Show f) => Show (Arrangement s l v e f r) Source # | |
Defined in Data.Geometry.Arrangement.Internal Methods showsPrec :: Int -> Arrangement s l v e f r -> ShowS # show :: Arrangement s l v e f r -> String # showList :: [Arrangement s l v e f r] -> ShowS # | |
| type NumType (Arrangement s l v e f r) Source # | |
Defined in Data.Geometry.Arrangement.Internal | |
| type Dimension (Arrangement s l v e f r) Source # | |
Defined in Data.Geometry.Arrangement.Internal | |
unboundedIntersections :: forall k (s :: k) l v e f r. Lens' (Arrangement (s :: k) l v e f r) (ArrangementBoundary s l r) Source #
subdivision :: forall k (s :: k) l v e f r v e f. Lens (Arrangement (s :: k) l v e f r) (Arrangement (s :: k) l v e f r) (PlanarSubdivision s v e f r) (PlanarSubdivision s v e f r) Source #
inputLines :: forall k (s :: k) l v e f r. Lens' (Arrangement (s :: k) l v e f r) (Vector ((:+) (Line 2 r) l)) Source #
boundedArea :: forall k (s :: k) l v e f r. Lens' (Arrangement (s :: k) l v e f r) (Rectangle () r) Source #
constructArrangement :: (Ord r, Fractional r) => proxy s -> [Line 2 r :+ l] -> Arrangement s l () (Maybe l) () r Source #
Builds an arrangement of \(n\) lines
running time: \(O(n^2\log n\)
constructArrangementInBox :: (Ord r, Fractional r) => proxy s -> Rectangle () r -> [Line 2 r :+ l] -> Arrangement s l () (Maybe l) () r Source #
Constructs the arrangemnet inside the box. note that the resulting box may be larger than the given box to make sure that all vertices of the arrangement actually fit.
running time: \(O(n^2\log n\)
constructArrangementInBox' :: (Ord r, Fractional r) => proxy s -> Rectangle () r -> [Line 2 r :+ l] -> Arrangement s l () (Maybe l) () r Source #
Constructs the arrangemnet inside the box. (for parts to be useful, it is assumed this boxfits at least the boundingbox of the intersections in the Arrangement)
computeSegsAndParts :: forall r l. (Ord r, Fractional r) => Rectangle () r -> [Line 2 r :+ l] -> ([LineSegment 2 () r :+ Maybe l], [(Point 2 r, Maybe (Line 2 r :+ l))]) Source #
perLine :: forall r l. (Ord r, Fractional r) => Rectangle () r -> (Line 2 r :+ l) -> [Line 2 r :+ l] -> [LineSegment 2 () r :+ l] Source #
intersectionPoint :: forall r l. (Ord r, Fractional r) => (Line 2 r :+ l) -> (Line 2 r :+ l) -> Maybe (Point 2 r) Source #
toSegments :: Ord r => [Point 2 r] -> [LineSegment 2 () r] Source #
makeBoundingBox :: (Ord r, Fractional r) => [Line 2 r :+ l] -> Rectangle () r Source #
Constructs a boundingbox containing all intersections
running time: \(O(n^2)\), where \(n\) is the number of input lines
intersections :: (Ord r, Fractional r) => [Line 2 r :+ l] -> [Point 2 r] Source #
Computes all intersections
sideIntersections :: (Ord r, Fractional r) => [Line 2 r :+ l] -> LineSegment 2 q r -> [(Point 2 r, Line 2 r :+ l)] Source #
Computes the intersections with a particular side
unBoundedParts :: (Ord r, Fractional r) => Rectangle () r -> [Line 2 r :+ l] -> [(Point 2 r, Maybe (Line 2 r :+ l))] Source #
Constructs the unbounded intersections. Reported in clockwise direction.
link :: Eq r => [(Point 2 r, a)] -> PlanarSubdivision s v (Maybe e) f r -> Vector (Point 2 r, VertexId' s, a) Source #
Links the vertices of the outer boundary with those in the subdivision
alignWith :: (a -> b -> Bool) -> CSeq a -> CSeq b -> Maybe (CSeq (a, b)) Source #
Given a predicate that tests if two elements of a CSeq match, find a rotation of the seqs such at they match.
Running time: \(O(n)\)
traverseLine :: (Ord r, Fractional r) => Line 2 r -> Arrangement s l v (Maybe e) f r -> [Dart s] Source #
Given an Arrangement and a line in the arrangement, follow the line through he arrangement.
findStart :: forall s l v e f r. (Ord r, Fractional r) => Line 2 r -> Arrangement s l v (Maybe e) f r -> Maybe (Dart s) Source #
Find the starting point of the line the arrangement
findStartVertex :: (Ord r, Fractional r) => Point 2 r -> Arrangement s l v e f r -> Maybe (Point 2 r, VertexId' s, Maybe (Line 2 r :+ l)) Source #
Given a point on the boundary of the boundedArea box; find the vertex this point corresponds to.
running time: \(O(\log n)\)
basically; maps every point to a tuple of the point and the side the point occurs on. We then binary search to find the point we are looking for.
findStartDart :: PlanarSubdivision s v (Maybe e) f r -> VertexId' s -> Maybe (Dart s) Source #
Find the starting dart of the given vertex v. Reports a dart s.t. tailOf d = v
running me: \(O(k)\) where \(k\) is the degree of the vertex
follow :: (Ord r, Num r) => Arrangement s l v e f r -> Dart s -> Maybe (Dart s) Source #
Given a dart d that incoming to v (headOf d == v), find the outgoing dart colinear with the incoming one. Again reports dart d' s.t. tailOf d' = v
running time: \(O(k)\), where k is the degree of the vertex d points to