hgeometry-0.11.0.0: Geometric Algorithms, Data structures, and Data types.

Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone
LanguageHaskell2010

Data.Geometry.Arrangement

Description

Data type for representing an Arrangement of lines in \(\mathbb{R}^2\).

Synopsis

Documentation

data Arrangement s l v e f r Source #

Data type representing a two dimensional planar arrangement

Instances
(Fractional r, Eq r, Eq l, Eq v, Eq e, Eq f) => Eq (Arrangement s l v e f r) Source # 
Instance details

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 # 
Instance details

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 # 
Instance details

Defined in Data.Geometry.Arrangement.Internal

type NumType (Arrangement s l v e f r) = r
type Dimension (Arrangement s l v e f r) Source # 
Instance details

Defined in Data.Geometry.Arrangement.Internal

type Dimension (Arrangement s l v e f r) = 2

inputLines :: forall s l v e f r. Lens' (Arrangement s l v e f r) (Vector ((:+) (Line 2 r) l)) Source #

subdivision :: forall s l v e f r v e f. Lens (Arrangement s l v e f r) (Arrangement s l v e f r) (PlanarSubdivision s v e f r) (PlanarSubdivision s v e f r) Source #

boundedArea :: forall s l v e f r. Lens' (Arrangement s l v e f r) (Rectangle () r) Source #

unboundedIntersections :: forall s l v e f r. Lens' (Arrangement s l v e f r) (ArrangementBoundary s l r) Source #

type ArrangementBoundary s e r = Vector (Point 2 r, VertexId' s, Maybe (Line 2 r :+ e)) 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)

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