Copyright | (C) Frank Staals |
---|---|
License | see the LICENSE file |
Maintainer | Frank Staals |
Safe Haskell | None |
Language | Haskell2010 |
Basic Geometry Types
Synopsis
- module Data.Geometry.Properties
- module Data.Geometry.Transformation
- module Data.Geometry.Point
- imap :: (Vector v a, Vector v b) => (Int -> a -> b) -> v a -> v b
- replicate :: Vector v a => a -> v a
- distanceA :: (Floating a, Foldable (Diff p), Affine p) => p a -> p a -> a
- qdA :: (Affine p, Foldable (Diff p), Num a) => p a -> p a -> a
- class Additive (Diff p) => Affine (p :: Type -> Type) where
- class Functor f => Additive (f :: Type -> Type) where
- dot :: (Metric f, Num a) => f a -> f a -> a
- norm :: (Metric f, Floating a) => f a -> a
- signorm :: (Metric f, Floating a) => f a -> f a
- newtype E (t :: Type -> Type) = E {
- el :: forall x. Lens' (t x) x
- (*^) :: (Functor f, Num a) => a -> f a -> f a
- (^*) :: (Functor f, Num a) => f a -> a -> f a
- (^/) :: (Functor f, Fractional a) => f a -> a -> f a
- basis :: (Additive t, Traversable t, Num a) => [t a]
- basisFor :: (Traversable t, Num a) => t b -> [t a]
- negated :: (Functor f, Num a) => f a -> f a
- outer :: (Functor f, Functor g, Num a) => f a -> g a -> f (g a)
- scaled :: (Traversable t, Num a) => t a -> t (t a)
- sumV :: (Foldable f, Additive v, Num a) => f (v a) -> v a
- unit :: (Additive t, Num a) => ASetter' (t a) a -> t a
- data C (n :: Nat) = C
- type Arity d = (ImplicitArity (Peano d), KnownNat d)
- newtype Vector (d :: Nat) (r :: *) = MKVector {
- _unV :: VectorFamily (Peano d) r
- pattern Vector4 :: r -> r -> r -> r -> Vector 4 r
- pattern Vector3 :: r -> r -> r -> Vector 3 r
- pattern Vector2 :: r -> r -> Vector 2 r
- pattern Vector1 :: r -> Vector 1 r
- pattern Vector :: VectorFamilyF (Peano d) r -> Vector d r
- unV :: Lens (Vector d r) (Vector d s) (VectorFamily (Peano d) r) (VectorFamily (Peano d) s)
- readVec :: forall d r. (Arity d, Read r) => ReadP (Vector d r)
- vectorFromList :: Arity d => [r] -> Maybe (Vector d r)
- vectorFromListUnsafe :: Arity d => [r] -> Vector d r
- destruct :: (Arity d, Arity (d + 1)) => Vector (d + 1) r -> (r, Vector d r)
- head :: (Arity d, 1 <= d) => Vector d r -> r
- element :: forall proxy i d r. (Arity d, KnownNat i, (i + 1) <= d) => proxy i -> Lens' (Vector d r) r
- element' :: forall d r. Arity d => Int -> Traversal' (Vector d r) r
- snoc :: (Arity (d + 1), Arity d) => Vector d r -> r -> Vector (d + 1) r
- init :: (Arity d, Arity (d + 1)) => Vector (d + 1) r -> Vector d r
- prefix :: forall i d r. (Arity d, Arity i, i <= d) => Vector d r -> Vector i r
- cross :: Num r => Vector 3 r -> Vector 3 r -> Vector 3 r
- isScalarMultipleOf :: (Eq r, Fractional r, Arity d) => Vector d r -> Vector d r -> Bool
- scalarMultiple :: (Eq r, Fractional r, Arity d) => Vector d r -> Vector d r -> Maybe r
- xComponent :: (1 <= d, Arity d) => Lens' (Vector d r) r
- yComponent :: (2 <= d, Arity d) => Lens' (Vector d r) r
- zComponent :: (3 <= d, Arity d) => Lens' (Vector d r) r
- module Data.Geometry.Line
- module Data.Geometry.LineSegment
- newtype PolyLine d p r = PolyLine {}
- points :: forall d p r d p r. Iso (PolyLine d p r) (PolyLine d p r) (LSeq 2 ((:+) (Point d r) p)) (LSeq 2 ((:+) (Point d r) p))
- fromPoints' :: Monoid p => [Point d r] -> PolyLine d p r
- fromLineSegment :: LineSegment d p r -> PolyLine d p r
- asLineSegment :: PolyLine d p r -> LineSegment d p r
- asLineSegment' :: PolyLine d p r -> Maybe (LineSegment d p r)
- type SomePolygon p r = Either (Polygon Simple p r) (Polygon Multi p r)
- type MultiPolygon = Polygon Multi
- type SimplePolygon = Polygon Simple
- data Polygon (t :: PolygonType) p r where
- SimplePolygon :: CSeq (Point 2 r :+ p) -> Polygon Simple p r
- MultiPolygon :: CSeq (Point 2 r :+ p) -> [Polygon Simple p r] -> Polygon Multi p r
- data PolygonType
- bitraverseVertices :: (Applicative f, Traversable t) => (p -> f q) -> (r -> f s) -> t (Point 2 r :+ p) -> f (t (Point 2 s :+ q))
- outerBoundary :: forall t p r. Lens' (Polygon t p r) (CSeq (Point 2 r :+ p))
- polygonHoles :: forall p r. Lens' (Polygon Multi p r) [Polygon Simple p r]
- outerVertex :: Int -> Lens' (Polygon t p r) (Point 2 r :+ p)
- outerBoundaryEdge :: Int -> Polygon t p r -> LineSegment 2 p r
- holeList :: Polygon t p r -> [Polygon Simple p r]
- polygonVertices :: Polygon t p r -> NonEmpty (Point 2 r :+ p)
- outerBoundaryEdges :: Polygon t p r -> CSeq (LineSegment 2 p r)
- listEdges :: Polygon t p r -> [LineSegment 2 p r]
- withIncidentEdges :: Polygon t p r -> Polygon t (Two (LineSegment 2 p r)) r
- toEdges :: CSeq (Point 2 r :+ p) -> CSeq (LineSegment 2 p r)
- onBoundary :: (Fractional r, Ord r) => Point 2 r -> Polygon t p r -> Bool
- inPolygon :: forall t p r. (Fractional r, Ord r) => Point 2 r -> Polygon t p r -> PointLocationResult
- insidePolygon :: (Fractional r, Ord r) => Point 2 r -> Polygon t p r -> Bool
- area :: Fractional r => Polygon t p r -> r
- signedArea :: Fractional r => SimplePolygon p r -> r
- centroid :: Fractional r => SimplePolygon p r -> Point 2 r
- pickPoint :: (Ord r, Fractional r) => Polygon p t r -> Point 2 r
- isTriangle :: Polygon p t r -> Bool
- findDiagonal :: (Ord r, Fractional r) => Polygon t p r -> LineSegment 2 p r
- safeMaximumOn :: Ord b => (a -> b) -> [a] -> Maybe a
- isCounterClockwise :: (Eq r, Fractional r) => Polygon t p r -> Bool
- toClockwiseOrder :: (Eq r, Fractional r) => Polygon t p r -> Polygon t p r
- toCounterClockWiseOrder :: (Eq r, Fractional r) => Polygon t p r -> Polygon t p r
- reverseOuterBoundary :: Polygon t p r -> Polygon t p r
- asSimplePolygon :: Polygon t p r -> SimplePolygon p r
- cmpExtreme :: (Num r, Ord r) => Vector 2 r -> (Point 2 r :+ p) -> (Point 2 r :+ q) -> Ordering
- extremesLinear :: (Ord r, Num r) => Vector 2 r -> Polygon t p r -> (Point 2 r :+ p, Point 2 r :+ p)
- numberVertices :: Polygon t p r -> Polygon t (SP Int p) r
- isStarShaped :: (MonadRandom m, Ord r, Fractional r) => SimplePolygon p r -> m (Maybe (Point 2 r))
Documentation
module Data.Geometry.Properties
module Data.Geometry.Transformation
module Data.Geometry.Point
class Additive (Diff p) => Affine (p :: Type -> Type) where #
Instances
Affine [] | |
Affine Maybe | |
Affine Complex | |
Affine ZipList | |
Affine Identity | |
Affine IntMap | |
Affine Vector | |
Affine Plucker | |
Affine Quaternion | |
Affine V0 | |
Affine V1 | |
Affine V2 | |
Affine V3 | |
Affine V4 | |
Ord k => Affine (Map k) | |
(Eq k, Hashable k) => Affine (HashMap k) | |
Additive f => Affine (Point f) | |
Arity d => Affine (Vector d) Source # | |
ImplicitArity d => Affine (VectorFamily d) Source # | |
Defined in Data.Geometry.Vector.VectorFamilyPeano type Diff (VectorFamily d) :: Type -> Type # (.-.) :: Num a => VectorFamily d a -> VectorFamily d a -> Diff (VectorFamily d) a # (.+^) :: Num a => VectorFamily d a -> Diff (VectorFamily d) a -> VectorFamily d a # (.-^) :: Num a => VectorFamily d a -> Diff (VectorFamily d) a -> VectorFamily d a # | |
Arity d => Affine (Vector d) Source # | |
Arity d => Affine (Point d) Source # | |
Dim n => Affine (V n) | |
Affine ((->) b :: Type -> Type) | |
class Functor f => Additive (f :: Type -> Type) where #
Nothing
(^+^) :: Num a => f a -> f a -> f a #
(^-^) :: Num a => f a -> f a -> f a #
lerp :: Num a => a -> f a -> f a -> f a #
Instances
Additive [] | |
Additive Maybe | |
Defined in Linear.Vector | |
Additive Complex | |
Defined in Linear.Vector | |
Additive ZipList | |
Defined in Linear.Vector | |
Additive Identity | |
Defined in Linear.Vector (^+^) :: Num a => Identity a -> Identity a -> Identity a # (^-^) :: Num a => Identity a -> Identity a -> Identity a # lerp :: Num a => a -> Identity a -> Identity a -> Identity a # liftU2 :: (a -> a -> a) -> Identity a -> Identity a -> Identity a # liftI2 :: (a -> b -> c) -> Identity a -> Identity b -> Identity c # | |
Additive IntMap | |
Defined in Linear.Vector | |
Additive Vector | |
Defined in Linear.Vector | |
Additive Plucker | |
Defined in Linear.Plucker | |
Additive Quaternion | |
Defined in Linear.Quaternion zero :: Num a => Quaternion a # (^+^) :: Num a => Quaternion a -> Quaternion a -> Quaternion a # (^-^) :: Num a => Quaternion a -> Quaternion a -> Quaternion a # lerp :: Num a => a -> Quaternion a -> Quaternion a -> Quaternion a # liftU2 :: (a -> a -> a) -> Quaternion a -> Quaternion a -> Quaternion a # liftI2 :: (a -> b -> c) -> Quaternion a -> Quaternion b -> Quaternion c # | |
Additive V0 | |
Additive V1 | |
Additive V2 | |
Additive V3 | |
Additive V4 | |
Ord k => Additive (Map k) | |
Defined in Linear.Vector | |
(Eq k, Hashable k) => Additive (HashMap k) | |
Defined in Linear.Vector zero :: Num a => HashMap k a # (^+^) :: Num a => HashMap k a -> HashMap k a -> HashMap k a # (^-^) :: Num a => HashMap k a -> HashMap k a -> HashMap k a # lerp :: Num a => a -> HashMap k a -> HashMap k a -> HashMap k a # liftU2 :: (a -> a -> a) -> HashMap k a -> HashMap k a -> HashMap k a # liftI2 :: (a -> b -> c) -> HashMap k a -> HashMap k b -> HashMap k c # | |
Additive f => Additive (Point f) | |
Defined in Linear.Affine | |
Arity d => Additive (Vector d) Source # | |
Defined in Data.Geometry.Vector.VectorFixed (^+^) :: Num a => Vector d a -> Vector d a -> Vector d a # (^-^) :: Num a => Vector d a -> Vector d a -> Vector d a # lerp :: Num a => a -> Vector d a -> Vector d a -> Vector d a # liftU2 :: (a -> a -> a) -> Vector d a -> Vector d a -> Vector d a # liftI2 :: (a -> b -> c) -> Vector d a -> Vector d b -> Vector d c # | |
ImplicitArity d => Additive (VectorFamily d) Source # | |
Defined in Data.Geometry.Vector.VectorFamilyPeano zero :: Num a => VectorFamily d a # (^+^) :: Num a => VectorFamily d a -> VectorFamily d a -> VectorFamily d a # (^-^) :: Num a => VectorFamily d a -> VectorFamily d a -> VectorFamily d a # lerp :: Num a => a -> VectorFamily d a -> VectorFamily d a -> VectorFamily d a # liftU2 :: (a -> a -> a) -> VectorFamily d a -> VectorFamily d a -> VectorFamily d a # liftI2 :: (a -> b -> c) -> VectorFamily d a -> VectorFamily d b -> VectorFamily d c # | |
Arity d => Additive (Vector d) Source # | |
Defined in Data.Geometry.Vector.VectorFamily (^+^) :: Num a => Vector d a -> Vector d a -> Vector d a # (^-^) :: Num a => Vector d a -> Vector d a -> Vector d a # lerp :: Num a => a -> Vector d a -> Vector d a -> Vector d a # liftU2 :: (a -> a -> a) -> Vector d a -> Vector d a -> Vector d a # liftI2 :: (a -> b -> c) -> Vector d a -> Vector d b -> Vector d c # | |
Dim n => Additive (V n) | |
Additive ((->) b :: Type -> Type) | |
Defined in Linear.Vector |
newtype E (t :: Type -> Type) #
Instances
FoldableWithIndex (E Plucker) Plucker | |
Defined in Linear.Plucker ifoldMap :: Monoid m => (E Plucker -> a -> m) -> Plucker a -> m ifolded :: IndexedFold (E Plucker) (Plucker a) a ifoldr :: (E Plucker -> a -> b -> b) -> b -> Plucker a -> b ifoldl :: (E Plucker -> b -> a -> b) -> b -> Plucker a -> b ifoldr' :: (E Plucker -> a -> b -> b) -> b -> Plucker a -> b ifoldl' :: (E Plucker -> b -> a -> b) -> b -> Plucker a -> b | |
FoldableWithIndex (E Quaternion) Quaternion | |
Defined in Linear.Quaternion ifoldMap :: Monoid m => (E Quaternion -> a -> m) -> Quaternion a -> m ifolded :: IndexedFold (E Quaternion) (Quaternion a) a ifoldr :: (E Quaternion -> a -> b -> b) -> b -> Quaternion a -> b ifoldl :: (E Quaternion -> b -> a -> b) -> b -> Quaternion a -> b ifoldr' :: (E Quaternion -> a -> b -> b) -> b -> Quaternion a -> b ifoldl' :: (E Quaternion -> b -> a -> b) -> b -> Quaternion a -> b | |
FoldableWithIndex (E V0) V0 | |
Defined in Linear.V0 | |
FoldableWithIndex (E V1) V1 | |
Defined in Linear.V1 | |
FoldableWithIndex (E V2) V2 | |
Defined in Linear.V2 | |
FoldableWithIndex (E V3) V3 | |
Defined in Linear.V3 | |
FoldableWithIndex (E V4) V4 | |
Defined in Linear.V4 | |
FunctorWithIndex (E Plucker) Plucker | |
Defined in Linear.Plucker | |
FunctorWithIndex (E Quaternion) Quaternion | |
Defined in Linear.Quaternion | |
FunctorWithIndex (E V0) V0 | |
FunctorWithIndex (E V1) V1 | |
FunctorWithIndex (E V2) V2 | |
FunctorWithIndex (E V3) V3 | |
FunctorWithIndex (E V4) V4 | |
TraversableWithIndex (E Plucker) Plucker | |
Defined in Linear.Plucker itraverse :: Applicative f => (E Plucker -> a -> f b) -> Plucker a -> f (Plucker b) itraversed :: IndexedTraversal (E Plucker) (Plucker a) (Plucker b) a b | |
TraversableWithIndex (E Quaternion) Quaternion | |
Defined in Linear.Quaternion itraverse :: Applicative f => (E Quaternion -> a -> f b) -> Quaternion a -> f (Quaternion b) itraversed :: IndexedTraversal (E Quaternion) (Quaternion a) (Quaternion b) a b | |
TraversableWithIndex (E V0) V0 | |
Defined in Linear.V0 itraverse :: Applicative f => (E V0 -> a -> f b) -> V0 a -> f (V0 b) itraversed :: IndexedTraversal (E V0) (V0 a) (V0 b) a b | |
TraversableWithIndex (E V1) V1 | |
Defined in Linear.V1 itraverse :: Applicative f => (E V1 -> a -> f b) -> V1 a -> f (V1 b) itraversed :: IndexedTraversal (E V1) (V1 a) (V1 b) a b | |
TraversableWithIndex (E V2) V2 | |
Defined in Linear.V2 itraverse :: Applicative f => (E V2 -> a -> f b) -> V2 a -> f (V2 b) itraversed :: IndexedTraversal (E V2) (V2 a) (V2 b) a b | |
TraversableWithIndex (E V3) V3 | |
Defined in Linear.V3 itraverse :: Applicative f => (E V3 -> a -> f b) -> V3 a -> f (V3 b) itraversed :: IndexedTraversal (E V3) (V3 a) (V3 b) a b | |
TraversableWithIndex (E V4) V4 | |
Defined in Linear.V4 itraverse :: Applicative f => (E V4 -> a -> f b) -> V4 a -> f (V4 b) itraversed :: IndexedTraversal (E V4) (V4 a) (V4 b) a b |
(^/) :: (Functor f, Fractional a) => f a -> a -> f a #
basis :: (Additive t, Traversable t, Num a) => [t a] #
basisFor :: (Traversable t, Num a) => t b -> [t a] #
scaled :: (Traversable t, Num a) => t a -> t (t a) #
A proxy which can be used for the coordinates.
type Arity d = (ImplicitArity (Peano d), KnownNat d) Source #
newtype Vector (d :: Nat) (r :: *) Source #
Datatype representing d dimensional vectors. The default implementation is based n VectorFixed. However, for small vectors we automatically select a more efficient representation.
MKVector | |
|
Instances
pattern Vector :: VectorFamilyF (Peano d) r -> Vector d r Source #
unV :: Lens (Vector d r) (Vector d s) (VectorFamily (Peano d) r) (VectorFamily (Peano d) s) Source #
vectorFromListUnsafe :: Arity d => [r] -> Vector d r Source #
element :: forall proxy i d r. (Arity d, KnownNat i, (i + 1) <= d) => proxy i -> Lens' (Vector d r) r Source #
Lens into the i th element
element' :: forall d r. Arity d => Int -> Traversal' (Vector d r) r Source #
Similar to element
above. Except that we don't have a static guarantee
that the index is in bounds. Hence, we can only return a Traversal
snoc :: (Arity (d + 1), Arity d) => Vector d r -> r -> Vector (d + 1) r Source #
Add an element at the back of the vector
init :: (Arity d, Arity (d + 1)) => Vector (d + 1) r -> Vector d r Source #
Get a vector of the first d - 1 elements.
prefix :: forall i d r. (Arity d, Arity i, i <= d) => Vector d r -> Vector i r Source #
Get a prefix of i elements of a vector
cross :: Num r => Vector 3 r -> Vector 3 r -> Vector 3 r Source #
Cross product of two three-dimensional vectors
isScalarMultipleOf :: (Eq r, Fractional r, Arity d) => Vector d r -> Vector d r -> Bool Source #
Test if v is a scalar multiple of u.
>>>
Vector2 1 1 `isScalarMultipleOf` Vector2 10 10
True>>>
Vector2 1 1 `isScalarMultipleOf` Vector2 10 1
False>>>
Vector2 1 1 `isScalarMultipleOf` Vector2 11.1 11.1
True>>>
Vector2 1 1 `isScalarMultipleOf` Vector2 11.1 11.2
False>>>
Vector2 2 1 `isScalarMultipleOf` Vector2 11.1 11.2
False>>>
Vector2 2 1 `isScalarMultipleOf` Vector2 4 2
True>>>
Vector2 2 1 `isScalarMultipleOf` Vector2 4 0
False
scalarMultiple :: (Eq r, Fractional r, Arity d) => Vector d r -> Vector d r -> Maybe r Source #
Get the scalar labmda s.t. v = lambda * u (if it exists)
module Data.Geometry.Line
module Data.Geometry.LineSegment
newtype PolyLine d p r Source #
A Poly line in R^d has at least 2 vertices
Instances
points :: forall d p r d p r. Iso (PolyLine d p r) (PolyLine d p r) (LSeq 2 ((:+) (Point d r) p)) (LSeq 2 ((:+) (Point d r) p)) Source #
fromPoints' :: Monoid p => [Point d r] -> PolyLine d p r Source #
pre: The input list contains at least two points. All extra vields are initialized with mempty.
fromLineSegment :: LineSegment d p r -> PolyLine d p r Source #
We consider the line-segment as closed.
asLineSegment :: PolyLine d p r -> LineSegment d p r Source #
Convert to a closed line segment by taking the first two points.
asLineSegment' :: PolyLine d p r -> Maybe (LineSegment d p r) Source #
Stricter version of asLineSegment that fails if the Polyline contains more than two points.
type SomePolygon p r = Either (Polygon Simple p r) (Polygon Multi p r) Source #
Either a simple or multipolygon
type MultiPolygon = Polygon Multi Source #
type SimplePolygon = Polygon Simple Source #
data Polygon (t :: PolygonType) p r where Source #
SimplePolygon :: CSeq (Point 2 r :+ p) -> Polygon Simple p r | |
MultiPolygon :: CSeq (Point 2 r :+ p) -> [Polygon Simple p r] -> Polygon Multi p r |
Instances
data PolygonType Source #
We distinguish between simple polygons (without holes) and Polygons with holes.
bitraverseVertices :: (Applicative f, Traversable t) => (p -> f q) -> (r -> f s) -> t (Point 2 r :+ p) -> f (t (Point 2 s :+ q)) Source #
outerBoundary :: forall t p r. Lens' (Polygon t p r) (CSeq (Point 2 r :+ p)) Source #
outerVertex :: Int -> Lens' (Polygon t p r) (Point 2 r :+ p) Source #
Access the i^th vertex on the outer boundary
outerBoundaryEdge :: Int -> Polygon t p r -> LineSegment 2 p r Source #
polygonVertices :: Polygon t p r -> NonEmpty (Point 2 r :+ p) Source #
The vertices in the polygon. No guarantees are given on the order in which they appear!
outerBoundaryEdges :: Polygon t p r -> CSeq (LineSegment 2 p r) Source #
The edges along the outer boundary of the polygon. The edges are half open.
running time: \(O(n)\)
listEdges :: Polygon t p r -> [LineSegment 2 p r] Source #
Lists all edges. The edges on the outer boundary are given before the ones on the holes. However, no other guarantees are given on the order.
running time: \(O(n)\)
withIncidentEdges :: Polygon t p r -> Polygon t (Two (LineSegment 2 p r)) r Source #
Pairs every vertex with its incident edges. The first one is its predecessor edge, the second one its successor edge.
>>>
mapM_ print . polygonVertices $ withIncidentEdges simplePoly
Point2 [0 % 1,0 % 1] :+ SP LineSegment (Closed (Point2 [1 % 1,11 % 1] :+ ())) (Closed (Point2 [0 % 1,0 % 1] :+ ())) LineSegment (Closed (Point2 [0 % 1,0 % 1] :+ ())) (Closed (Point2 [10 % 1,0 % 1] :+ ())) Point2 [10 % 1,0 % 1] :+ SP LineSegment (Closed (Point2 [0 % 1,0 % 1] :+ ())) (Closed (Point2 [10 % 1,0 % 1] :+ ())) LineSegment (Closed (Point2 [10 % 1,0 % 1] :+ ())) (Closed (Point2 [10 % 1,10 % 1] :+ ())) Point2 [10 % 1,10 % 1] :+ SP LineSegment (Closed (Point2 [10 % 1,0 % 1] :+ ())) (Closed (Point2 [10 % 1,10 % 1] :+ ())) LineSegment (Closed (Point2 [10 % 1,10 % 1] :+ ())) (Closed (Point2 [5 % 1,15 % 1] :+ ())) Point2 [5 % 1,15 % 1] :+ SP LineSegment (Closed (Point2 [10 % 1,10 % 1] :+ ())) (Closed (Point2 [5 % 1,15 % 1] :+ ())) LineSegment (Closed (Point2 [5 % 1,15 % 1] :+ ())) (Closed (Point2 [1 % 1,11 % 1] :+ ())) Point2 [1 % 1,11 % 1] :+ SP LineSegment (Closed (Point2 [5 % 1,15 % 1] :+ ())) (Closed (Point2 [1 % 1,11 % 1] :+ ())) LineSegment (Closed (Point2 [1 % 1,11 % 1] :+ ())) (Closed (Point2 [0 % 1,0 % 1] :+ ()))
toEdges :: CSeq (Point 2 r :+ p) -> CSeq (LineSegment 2 p r) Source #
Given the vertices of the polygon. Produce a list of edges. The edges are half-open.
onBoundary :: (Fractional r, Ord r) => Point 2 r -> Polygon t p r -> Bool Source #
Test if q lies on the boundary of the polygon. Running time: O(n)
>>>
point2 1 1 `onBoundary` simplePoly
False>>>
point2 0 0 `onBoundary` simplePoly
True>>>
point2 10 0 `onBoundary` simplePoly
True>>>
point2 5 13 `onBoundary` simplePoly
False>>>
point2 5 10 `onBoundary` simplePoly
False>>>
point2 10 5 `onBoundary` simplePoly
True>>>
point2 20 5 `onBoundary` simplePoly
False
TODO: testcases multipolygon
inPolygon :: forall t p r. (Fractional r, Ord r) => Point 2 r -> Polygon t p r -> PointLocationResult Source #
Check if a point lies inside a polygon, on the boundary, or outside of the polygon. Running time: O(n).
>>>
point2 1 1 `inPolygon` simplePoly
Inside>>>
point2 0 0 `inPolygon` simplePoly
OnBoundary>>>
point2 10 0 `inPolygon` simplePoly
OnBoundary>>>
point2 5 13 `inPolygon` simplePoly
Inside>>>
point2 5 10 `inPolygon` simplePoly
Inside>>>
point2 10 5 `inPolygon` simplePoly
OnBoundary>>>
point2 20 5 `inPolygon` simplePoly
Outside
TODO: Add some testcases with multiPolygons TODO: Add some more onBoundary testcases
insidePolygon :: (Fractional r, Ord r) => Point 2 r -> Polygon t p r -> Bool Source #
Test if a point lies strictly inside the polgyon.
area :: Fractional r => Polygon t p r -> r Source #
Compute the area of a polygon
signedArea :: Fractional r => SimplePolygon p r -> r Source #
Compute the signed area of a simple polygon. The the vertices are in clockwise order, the signed area will be negative, if the verices are given in counter clockwise order, the area will be positive.
centroid :: Fractional r => SimplePolygon p r -> Point 2 r Source #
Compute the centroid of a simple polygon.
pickPoint :: (Ord r, Fractional r) => Polygon p t r -> Point 2 r Source #
Pick a point that is inside the polygon.
(note: if the polygon is degenerate; i.e. has <3 vertices, we report a vertex of the polygon instead.)
pre: the polygon is given in CCW order
running time: \(O(n)\)
isTriangle :: Polygon p t r -> Bool Source #
Test if the polygon is a triangle
running time: \(O(1)\)
findDiagonal :: (Ord r, Fractional r) => Polygon t p r -> LineSegment 2 p r Source #
Find a diagonal of the polygon.
pre: the polygon is given in CCW order
running time: \(O(n)\)
safeMaximumOn :: Ord b => (a -> b) -> [a] -> Maybe a Source #
isCounterClockwise :: (Eq r, Fractional r) => Polygon t p r -> Bool Source #
Test if the outer boundary of the polygon is in clockwise or counter clockwise order.
running time: \(O(n)\)
toClockwiseOrder :: (Eq r, Fractional r) => Polygon t p r -> Polygon t p r Source #
Orient the outer boundary to clockwise order
toCounterClockWiseOrder :: (Eq r, Fractional r) => Polygon t p r -> Polygon t p r Source #
Orient the outer boundary to counter clockwise order
reverseOuterBoundary :: Polygon t p r -> Polygon t p r Source #
asSimplePolygon :: Polygon t p r -> SimplePolygon p r Source #
Convert a Polygon to a simple polygon by forgetting about any holes.
cmpExtreme :: (Num r, Ord r) => Vector 2 r -> (Point 2 r :+ p) -> (Point 2 r :+ q) -> Ordering Source #
Comparison that compares which point is larger
in the direction given by
the vector u.
extremesLinear :: (Ord r, Num r) => Vector 2 r -> Polygon t p r -> (Point 2 r :+ p, Point 2 r :+ p) Source #
Finds the extreme points, minimum and maximum, in a given direction
running time: \(O(n)\)
numberVertices :: Polygon t p r -> Polygon t (SP Int p) r Source #
assigns unique integer numbers to all vertices. Numbers start from 0, and are increasing along the outer boundary. The vertices of holes will be numbered last, in the same order.
>>>
numberVertices simplePoly
SimplePolygon CSeq [Point2 [0 % 1,0 % 1] :+ SP 0 (),Point2 [10 % 1,0 % 1] :+ SP 1 (),Point2 [10 % 1,10 % 1] :+ SP 2 (),Point2 [5 % 1,15 % 1] :+ SP 3 (),Point2 [1 % 1,11 % 1] :+ SP 4 ()]
isStarShaped :: (MonadRandom m, Ord r, Fractional r) => SimplePolygon p r -> m (Maybe (Point 2 r)) Source #
Test if a Simple polygon is star-shaped. Returns a point in the kernel (i.e. from which the entire polygon is visible), if it exists.
\(O(n)\) expected time