| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
Data.Geometry
Description
Basic Geometry Types
Synopsis
- module Data.Geometry.Properties
- module Data.Geometry.Transformation
- module Data.Geometry.Point
- 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
- type family Diff (p :: Type -> Type) :: Type -> Type
- class Additive (Diff p) => Affine (p :: Type -> Type) where
- signorm :: (Metric f, Floating a) => f a -> f a
- norm :: (Metric f, Floating a) => f a -> a
- dot :: (Metric f, Num a) => f a -> f a -> a
- quadrance :: (Metric f, Num a) => f a -> a
- outer :: (Functor f, Functor g, Num a) => f a -> g a -> f (g a)
- unit :: (Additive t, Num a) => ASetter' (t a) a -> t a
- scaled :: (Traversable t, Num a) => t a -> t (t a)
- basisFor :: (Traversable t, Num a) => t b -> [t a]
- basis :: (Additive t, Traversable t, Num a) => [t a]
- (^/) :: (Functor f, Fractional a) => f a -> a -> f a
- (^*) :: (Functor f, Num a) => f a -> a -> f a
- (*^) :: (Functor f, Num a) => a -> f a -> f a
- sumV :: (Foldable f, Additive v, Num a) => f (v a) -> v a
- negated :: (Functor f, Num a) => f a -> f a
- class Functor f => Additive (f :: Type -> Type) where
- data C (n :: Nat) = C
- class (ImplicitArity (Peano d), KnownNat d) => Arity 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 :: Iso (Vector d r) (Vector d s) (VectorFamily (Peano d) r) (VectorFamily (Peano d) s)
- 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
- cons :: (Arity d, Arity (d + 1)) => r -> Vector d r -> Vector (d + 1) 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
- sameDirection :: (Eq r, Num r, Arity d) => Vector d r -> Vector d r -> Bool
- 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 :: Iso (PolyLine d1 p1 r1) (PolyLine d2 p2 r2) (LSeq 2 (Point d1 r1 :+ p1)) (LSeq 2 (Point d2 r2 :+ p2))
- fromPointsUnsafe :: [Point d r :+ p] -> PolyLine d p r
- fromPointsUnsafe' :: 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)
- edgeSegments :: Arity d => PolyLine d p r -> LSeq 1 (LineSegment d p r)
- interpolatePoly :: (RealFrac r, Arity d) => r -> PolyLine d p r -> Point d 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 :: Vertices (Point 2 r :+ p) -> SimplePolygon p r
- MultiPolygon :: SimplePolygon p r -> [SimplePolygon p r] -> MultiPolygon p r
- data PolygonType
- _SimplePolygon :: Prism' (Polygon Simple p r) (Vertices (Point 2 r :+ p))
- _MultiPolygon :: Prism' (Polygon Multi p r) (Polygon Simple p r, [Polygon Simple p r])
- outerBoundaryVector :: forall t p r. Getter (Polygon t p r) (CircularVector (Point 2 r :+ p))
- unsafeOuterBoundaryVector :: forall t p r. Lens' (Polygon t p r) (CircularVector (Point 2 r :+ p))
- outerBoundary :: forall t p r. Lens' (Polygon t p r) (SimplePolygon p r)
- polygonHoles :: forall p r. Lens' (Polygon Multi p r) [Polygon Simple p r]
- polygonHoles' :: Traversal' (Polygon t p r) [Polygon Simple p r]
- outerVertex :: Int -> Getter (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]
- size :: Polygon t p r -> Int
- polygonVertices :: Polygon t p r -> NonEmpty (Point 2 r :+ p)
- isSimple :: (Ord r, Fractional r) => Polygon p t r -> Bool
- fromCircularVector :: forall p r. (Eq r, Num r) => CircularVector (Point 2 r :+ p) -> SimplePolygon p r
- simpleFromPoints :: forall p r. (Ord r, Fractional r) => [Point 2 r :+ p] -> SimplePolygon p r
- simpleFromCircularVector :: forall p r. (Ord r, Fractional r) => CircularVector (Point 2 r :+ p) -> SimplePolygon p r
- unsafeFromPoints :: [Point 2 r :+ p] -> SimplePolygon p r
- unsafeFromCircularVector :: CircularVector (Point 2 r :+ p) -> SimplePolygon p r
- unsafeFromVector :: Vector (Point 2 r :+ p) -> SimplePolygon p r
- toVector :: Polygon t p r -> Vector (Point 2 r :+ p)
- toPoints :: Polygon t p r -> [Point 2 r :+ p]
- outerBoundaryEdges :: Polygon t p r -> CircularVector (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
- 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
- isCounterClockwise :: (Eq r, Num r) => Polygon t p r -> Bool
- toClockwiseOrder :: (Eq r, Num r) => Polygon t p r -> Polygon t p r
- toClockwiseOrder' :: (Eq r, Num r) => Polygon t p r -> Polygon t p r
- toCounterClockWiseOrder :: (Eq r, Num r) => Polygon t p r -> Polygon t p r
- toCounterClockWiseOrder' :: (Eq r, Num r) => Polygon t p r -> Polygon t p r
- reverseOuterBoundary :: Polygon t p r -> Polygon t p r
- numberVertices :: Polygon t p r -> Polygon t (SP Int p) r
- maximumVertexBy :: ((Point 2 r :+ p) -> (Point 2 r :+ p) -> Ordering) -> Polygon t p r -> Point 2 r :+ p
- minimumVertexBy :: ((Point 2 r :+ p) -> (Point 2 r :+ p) -> Ordering) -> Polygon t p r -> Point 2 r :+ p
- findRotateTo :: ((Point 2 r :+ p) -> Bool) -> SimplePolygon p r -> Maybe (SimplePolygon p r)
- rotateLeft :: Int -> SimplePolygon p r -> SimplePolygon p r
- rotateRight :: Int -> SimplePolygon 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)
- onBoundary :: (Num 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
- 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
replicate :: Vector v a => a -> v a #
Replicate value n times.
Examples:
>>>import Data.Vector.Fixed.Boxed (Vec2)>>>replicate 1 :: Vec2 IntfromList [1,1]
>>>replicate 2 :: (Double,Double,Double)(2.0,2.0,2.0)
>>>import Data.Vector.Fixed.Boxed (Vec4)>>>replicate "foo" :: Vec4 StringfromList ["foo","foo","foo","foo"]
distanceA :: (Floating a, Foldable (Diff p), Affine p) => p a -> p a -> a #
Distance between two points in an affine space
qdA :: (Affine p, Foldable (Diff p), Num a) => p a -> p a -> a #
Compute the quadrance of the difference (the square of the distance)
type family Diff (p :: Type -> Type) :: Type -> Type #
Instances
class Additive (Diff p) => Affine (p :: Type -> Type) where #
An affine space is roughly a vector space in which we have forgotten or at least pretend to have forgotten the origin.
a .+^ (b .-. a) = b@ (a .+^ u) .+^ v = a .+^ (u ^+^ v)@ (a .-. b) ^+^ v = (a .+^ v) .-. q@
Methods
(.-.) :: Num a => p a -> p a -> Diff p a infixl 6 #
Get the difference between two points as a vector offset.
(.+^) :: Num a => p a -> Diff p a -> p a infixl 6 #
Add a vector offset to a point.
(.-^) :: Num a => p a -> Diff p a -> p a infixl 6 #
Subtract a vector offset from a point.
Instances
dot :: (Metric f, Num a) => f a -> f a -> a #
Compute the inner product of two vectors or (equivalently)
convert a vector f a into a covector f a -> a.
>>>V2 1 2 `dot` V2 3 411
quadrance :: (Metric f, Num a) => f a -> a #
Compute the squared norm. The name quadrance arises from Norman J. Wildberger's rational trigonometry.
outer :: (Functor f, Functor g, Num a) => f a -> g a -> f (g a) #
Outer (tensor) product of two vectors
unit :: (Additive t, Num a) => ASetter' (t a) a -> t a #
Create a unit vector.
>>>unit _x :: V2 IntV2 1 0
scaled :: (Traversable t, Num a) => t a -> t (t a) #
Produce a diagonal (scale) matrix from a vector.
>>>scaled (V2 2 3)V2 (V2 2 0) (V2 0 3)
basisFor :: (Traversable t, Num a) => t b -> [t a] #
Produce a default basis for a vector space from which the argument is drawn.
basis :: (Additive t, Traversable t, Num a) => [t a] #
Produce a default basis for a vector space. If the dimensionality
of the vector space is not statically known, see basisFor.
(^/) :: (Functor f, Fractional a) => f a -> a -> f a infixl 7 #
Compute division by a scalar on the right.
(^*) :: (Functor f, Num a) => f a -> a -> f a infixl 7 #
Compute the right scalar product
>>>V2 3 4 ^* 2V2 6 8
(*^) :: (Functor f, Num a) => a -> f a -> f a infixl 7 #
Compute the left scalar product
>>>2 *^ V2 3 4V2 6 8
sumV :: (Foldable f, Additive v, Num a) => f (v a) -> v a #
Sum over multiple vectors
>>>sumV [V2 1 1, V2 3 4]V2 4 5
negated :: (Functor f, Num a) => f a -> f a #
Compute the negation of a vector
>>>negated (V2 2 4)V2 (-2) (-4)
class Functor f => Additive (f :: Type -> Type) where #
A vector is an additive group with additional structure.
Minimal complete definition
Nothing
Methods
The zero vector
(^+^) :: Num a => f a -> f a -> f a infixl 6 #
Compute the sum of two vectors
>>>V2 1 2 ^+^ V2 3 4V2 4 6
(^-^) :: Num a => f a -> f a -> f a infixl 6 #
Compute the difference between two vectors
>>>V2 4 5 ^-^ V2 3 1V2 1 4
lerp :: Num a => a -> f a -> f a -> f a #
Linearly interpolate between two vectors.
liftU2 :: (a -> a -> a) -> f a -> f a -> f a #
Apply a function to merge the 'non-zero' components of two vectors, unioning the rest of the values.
liftI2 :: (a -> b -> c) -> f a -> f b -> f c #
Apply a function to the components of two vectors.
- For a dense vector this is equivalent to
liftA2. - For a sparse vector this is equivalent to
intersectionWith.
Instances
| Additive [] | |
| Additive Maybe | |
| Additive Complex | |
Defined in Linear.Vector Methods (^+^) :: Num a => Complex a -> Complex a -> Complex a # (^-^) :: Num a => Complex a -> Complex a -> Complex a # lerp :: Num a => a -> Complex a -> Complex a -> Complex a # liftU2 :: (a -> a -> a) -> Complex a -> Complex a -> Complex a # liftI2 :: (a -> b -> c) -> Complex a -> Complex b -> Complex c # | |
| Additive ZipList | |
Defined in Linear.Vector Methods (^+^) :: Num a => ZipList a -> ZipList a -> ZipList a # (^-^) :: Num a => ZipList a -> ZipList a -> ZipList a # lerp :: Num a => a -> ZipList a -> ZipList a -> ZipList a # liftU2 :: (a -> a -> a) -> ZipList a -> ZipList a -> ZipList a # liftI2 :: (a -> b -> c) -> ZipList a -> ZipList b -> ZipList c # | |
| Additive Identity | |
Defined in Linear.Vector Methods (^+^) :: 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 Methods (^+^) :: Num a => Plucker a -> Plucker a -> Plucker a # (^-^) :: Num a => Plucker a -> Plucker a -> Plucker a # lerp :: Num a => a -> Plucker a -> Plucker a -> Plucker a # liftU2 :: (a -> a -> a) -> Plucker a -> Plucker a -> Plucker a # liftI2 :: (a -> b -> c) -> Plucker a -> Plucker b -> Plucker c # | |
| Additive Quaternion | |
Defined in Linear.Quaternion Methods 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 V4 | |
| Additive V3 | |
| Additive V2 | |
| Additive V1 | |
| (Eq k, Hashable k) => Additive (HashMap k) | |
Defined in Linear.Vector Methods 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 # | |
| Ord k => Additive (Map k) | |
| Additive f => Additive (Point f) | |
Defined in Linear.Affine Methods (^+^) :: Num a => Point f a -> Point f a -> Point f a # (^-^) :: Num a => Point f a -> Point f a -> Point f a # lerp :: Num a => a -> Point f a -> Point f a -> Point f a # liftU2 :: (a -> a -> a) -> Point f a -> Point f a -> Point f a # liftI2 :: (a -> b -> c) -> Point f a -> Point f b -> Point f c # | |
| Arity d => Additive (Vector d) Source # | |
Defined in Data.Geometry.Vector.VectorFixed Methods (^+^) :: 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 Methods 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 Methods (^+^) :: 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 | |
| (Additive f, Additive g) => Additive (Product f g) | |
Defined in Linear.Vector Methods zero :: Num a => Product f g a # (^+^) :: Num a => Product f g a -> Product f g a -> Product f g a # (^-^) :: Num a => Product f g a -> Product f g a -> Product f g a # lerp :: Num a => a -> Product f g a -> Product f g a -> Product f g a # liftU2 :: (a -> a -> a) -> Product f g a -> Product f g a -> Product f g a # liftI2 :: (a -> b -> c) -> Product f g a -> Product f g b -> Product f g c # | |
| (Additive f, Additive g) => Additive (Compose f g) | |
Defined in Linear.Vector Methods zero :: Num a => Compose f g a # (^+^) :: Num a => Compose f g a -> Compose f g a -> Compose f g a # (^-^) :: Num a => Compose f g a -> Compose f g a -> Compose f g a # lerp :: Num a => a -> Compose f g a -> Compose f g a -> Compose f g a # liftU2 :: (a -> a -> a) -> Compose f g a -> Compose f g a -> Compose f g a # liftI2 :: (a -> b -> c) -> Compose f g a -> Compose f g b -> Compose f g c # | |
A proxy which can be used for the coordinates.
Constructors
| C |
class (ImplicitArity (Peano d), KnownNat d) => Arity d Source #
Instances
| (ImplicitArity (Peano d), KnownNat d) => Arity d Source # | |
Defined in Data.Geometry.Vector.VectorFamily | |
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.
Constructors
| MKVector | |
Fields
| |
Instances
pattern Vector :: VectorFamilyF (Peano d) r -> Vector d r Source #
Constant sized vector with d elements.
unV :: Iso (Vector d r) (Vector d s) (VectorFamily (Peano d) r) (VectorFamily (Peano d) s) Source #
Vectors are isomorphic to a definition determined by VectorFamily.
vectorFromList :: Arity d => [r] -> Maybe (Vector d r) Source #
\( O(n) \) Convert from a list to a non-empty vector.
vectorFromListUnsafe :: Arity d => [r] -> Vector d r Source #
\( O(n) \) Convert from a list to a non-empty vector.
destruct :: (Arity d, Arity (d + 1)) => Vector (d + 1) r -> (r, Vector d r) Source #
\( O(n) \) Pop the first element off a vector.
head :: (Arity d, 1 <= d) => Vector d r -> r Source #
\( O(1) \) First element. Since arity is at least 1, this function is total.
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
cons :: (Arity d, Arity (d + 1)) => r -> Vector d r -> Vector (d + 1) r Source #
\( O(n) \) Prepend an element.
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 #
'isScalarmultipleof u v' test if v is a scalar multiple of u.
>>>Vector2 1 1 `isScalarMultipleOf` Vector2 10 10True>>>Vector3 1 1 2 `isScalarMultipleOf` Vector3 10 10 20True>>>Vector2 1 1 `isScalarMultipleOf` Vector2 10 1False>>>Vector2 1 1 `isScalarMultipleOf` Vector2 (-1) (-1)True>>>Vector2 1 1 `isScalarMultipleOf` Vector2 11.1 11.1True>>>Vector2 1 1 `isScalarMultipleOf` Vector2 11.1 11.2False>>>Vector2 2 1 `isScalarMultipleOf` Vector2 11.1 11.2False>>>Vector2 2 1 `isScalarMultipleOf` Vector2 4 2True>>>Vector2 2 1 `isScalarMultipleOf` Vector2 4 0False>>>Vector3 2 1 0 `isScalarMultipleOf` Vector3 4 0 5False>>>Vector3 0 0 0 `isScalarMultipleOf` Vector3 4 0 5True
scalarMultiple :: (Eq r, Fractional r, Arity d) => Vector d r -> Vector d r -> Maybe r Source #
scalarMultiple u v computes the scalar labmda s.t. v = lambda * u (if it exists)
sameDirection :: (Eq r, Num r, Arity d) => Vector d r -> Vector d r -> Bool Source #
Given two colinar vectors, u and v, test if they point in the same direction, i.e. iff scalarMultiple' u v == Just lambda, with lambda > 0
pre: u and v are colinear, u and v are non-zero
xComponent :: (1 <= d, Arity d) => Lens' (Vector d r) r Source #
Shorthand to access the first component
>>>Vector3 1 2 3 ^. xComponent1>>>Vector2 1 2 & xComponent .~ 10Vector2 10 2
yComponent :: (2 <= d, Arity d) => Lens' (Vector d r) r Source #
Shorthand to access the second component
>>>Vector3 1 2 3 ^. yComponent2>>>Vector2 1 2 & yComponent .~ 10Vector2 1 10
zComponent :: (3 <= d, Arity d) => Lens' (Vector d r) r Source #
Shorthand to access the third component
>>>Vector3 1 2 3 ^. zComponent3>>>Vector3 1 2 3 & zComponent .~ 10Vector3 1 2 10
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 :: Iso (PolyLine d1 p1 r1) (PolyLine d2 p2 r2) (LSeq 2 (Point d1 r1 :+ p1)) (LSeq 2 (Point d2 r2 :+ p2)) Source #
PolyLines are isomorphic to a sequence of points with at least 2 members.
fromPointsUnsafe :: [Point d r :+ p] -> PolyLine d p r Source #
pre: The input list contains at least two points
fromPointsUnsafe' :: 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.
edgeSegments :: Arity d => PolyLine d p r -> LSeq 1 (LineSegment d p r) Source #
Computes the edges, as linesegments, of an LSeq
interpolatePoly :: (RealFrac r, Arity d) => r -> PolyLine d p r -> Point d r Source #
Linearly interpolate the polyline with a value in the range \([0,n-1]\), where \(n\) is the number of vertices of the polyline.
running time: \(O(\log n)\)
>>>interpolatePoly 0.5 myPolyLinePoint2 5.0 5.0>>>interpolatePoly 1.5 myPolyLinePoint2 10.0 15.0
type SomePolygon p r = Either (Polygon Simple p r) (Polygon Multi p r) Source #
Either a simple or multipolygon
type MultiPolygon = Polygon Multi Source #
Polygon with zero or more holes.
type SimplePolygon = Polygon Simple Source #
Polygon without holes.
data Polygon (t :: PolygonType) p r where Source #
Polygons are sequences of points and may or may not contain holes.
Degenerate polygons (polygons with self-intersections or fewer than 3 points) are only possible if you use functions marked as unsafe.
Constructors
| SimplePolygon :: Vertices (Point 2 r :+ p) -> SimplePolygon p r | |
| MultiPolygon :: SimplePolygon p r -> [SimplePolygon p r] -> MultiPolygon p r |
Instances
data PolygonType Source #
We distinguish between simple polygons (without holes) and polygons with holes.
_SimplePolygon :: Prism' (Polygon Simple p r) (Vertices (Point 2 r :+ p)) Source #
Prism to test if we are a simple polygon
>>>is _SimplePolygon simplePolyTrue
_MultiPolygon :: Prism' (Polygon Multi p r) (Polygon Simple p r, [Polygon Simple p r]) Source #
Prism to test if we are a Multi polygon
>>>is _MultiPolygon multiPolyTrue
outerBoundaryVector :: forall t p r. Getter (Polygon t p r) (CircularVector (Point 2 r :+ p)) Source #
Getter access to the outer boundary vector of a polygon.
>>>toList (simpleTriangle ^. outerBoundaryVector)[Point2 0 0 :+ (),Point2 2 0 :+ (),Point2 1 1 :+ ()]
unsafeOuterBoundaryVector :: forall t p r. Lens' (Polygon t p r) (CircularVector (Point 2 r :+ p)) Source #
Unsafe lens access to the outer boundary vector of a polygon.
>>>toList (simpleTriangle ^. unsafeOuterBoundaryVector)[Point2 0 0 :+ (),Point2 2 0 :+ (),Point2 1 1 :+ ()]
>>>simpleTriangle & unsafeOuterBoundaryVector .~ CV.singleton (Point2 0 0 :+ ())SimplePolygon [Point2 0 0 :+ ()]
outerBoundary :: forall t p r. Lens' (Polygon t p r) (SimplePolygon p r) Source #
\( O(1) \) Lens access to the outer boundary of a polygon.
polygonHoles :: forall p r. Lens' (Polygon Multi p r) [Polygon Simple p r] Source #
Lens access for polygon holes.
>>>multiPoly ^. polygonHoles[SimplePolygon [Point2 0 0 :+ (),Point2 2 0 :+ (),Point2 1 1 :+ ()]]
polygonHoles' :: Traversal' (Polygon t p r) [Polygon Simple p r] Source #
\( O(1) \). Traversal lens for polygon holes. Does nothing for simple polygons.
outerVertex :: Int -> Getter (Polygon t p r) (Point 2 r :+ p) Source #
O(1) Access the i^th vertex on the outer boundary. Indices are modulo \(n\).
>>>simplePoly ^. outerVertex 0Point2 0 0 :+ ()
outerBoundaryEdge :: Int -> Polygon t p r -> LineSegment 2 p r Source #
\( O(1) \) Get the n^th edge along the outer boundary of the polygon. The edge is half open.
polygonVertices :: Polygon t p r -> NonEmpty (Point 2 r :+ p) Source #
\( O(n) \) The vertices in the polygon. No guarantees are given on the order in which they appear!
isSimple :: (Ord r, Fractional r) => Polygon p t r -> Bool Source #
\( O(n \log n) \) Check if a polygon has any holes, duplicate points, or self-intersections.
fromCircularVector :: forall p r. (Eq r, Num r) => CircularVector (Point 2 r :+ p) -> SimplePolygon p r Source #
\( O(n) \) Creates a polygon from the given vector of vertices.
The points are placed in CCW order if they are not already. Overlapping edges and repeated vertices are allowed.
simpleFromPoints :: forall p r. (Ord r, Fractional r) => [Point 2 r :+ p] -> SimplePolygon p r Source #
\( O(n \log n) \) Creates a simple polygon from the given list of vertices.
The points are placed in CCW order if they are not already. Overlapping edges and repeated vertices are not allowed and will trigger an exception.
simpleFromCircularVector :: forall p r. (Ord r, Fractional r) => CircularVector (Point 2 r :+ p) -> SimplePolygon p r Source #
\( O(n \log n) \) Creates a simple polygon from the given vector of vertices.
The points are placed in CCW order if they are not already. Overlapping edges and repeated vertices are not allowed and will trigger an exception.
unsafeFromPoints :: [Point 2 r :+ p] -> SimplePolygon p r Source #
\( O(n) \) Creates a simple polygon from the given list of vertices.
pre: the input list constains no repeated vertices.
unsafeFromCircularVector :: CircularVector (Point 2 r :+ p) -> SimplePolygon p r Source #
\( O(1) \) Creates a simple polygon from the given vector of vertices.
pre: the input list constains no repeated vertices.
unsafeFromVector :: Vector (Point 2 r :+ p) -> SimplePolygon p r Source #
\( O(1) \) Creates a simple polygon from the given vector of vertices.
pre: the input list constains no repeated vertices.
toVector :: Polygon t p r -> Vector (Point 2 r :+ p) Source #
\( O(n) \) Polygon points, from left to right.
toPoints :: Polygon t p r -> [Point 2 r :+ p] Source #
\( O(n) \) Polygon points, from left to right.
outerBoundaryEdges :: Polygon t p r -> CircularVector (LineSegment 2 p r) Source #
\( O(n) \) The edges along the outer boundary of the polygon. The edges are half open.
listEdges :: Polygon t p r -> [LineSegment 2 p r] Source #
\( O(n) \) 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.
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 (in terms of the ordering along the boundary).
>>>mapM_ print . polygonVertices $ withIncidentEdges simplePolyPoint2 0 0 :+ V2 (ClosedLineSegment (Point2 1 11 :+ ()) (Point2 0 0 :+ ())) (ClosedLineSegment (Point2 0 0 :+ ()) (Point2 10 0 :+ ())) Point2 10 0 :+ V2 (ClosedLineSegment (Point2 0 0 :+ ()) (Point2 10 0 :+ ())) (ClosedLineSegment (Point2 10 0 :+ ()) (Point2 10 10 :+ ())) Point2 10 10 :+ V2 (ClosedLineSegment (Point2 10 0 :+ ()) (Point2 10 10 :+ ())) (ClosedLineSegment (Point2 10 10 :+ ()) (Point2 5 15 :+ ())) Point2 5 15 :+ V2 (ClosedLineSegment (Point2 10 10 :+ ()) (Point2 5 15 :+ ())) (ClosedLineSegment (Point2 5 15 :+ ()) (Point2 1 11 :+ ())) Point2 1 11 :+ V2 (ClosedLineSegment (Point2 5 15 :+ ()) (Point2 1 11 :+ ())) (ClosedLineSegment (Point2 1 11 :+ ()) (Point2 0 0 :+ ()))
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 #
\( O(n) \) 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
isTriangle :: Polygon p t r -> Bool Source #
\( O(1) \) Test if the polygon is a triangle
findDiagonal :: (Ord r, Fractional r) => Polygon t p r -> LineSegment 2 p r Source #
\( O(n) \) Find a diagonal of the polygon.
pre: the polygon is given in CCW order
isCounterClockwise :: (Eq r, Num r) => Polygon t p r -> Bool Source #
\( O(n) \) Test if the outer boundary of the polygon is in clockwise or counter clockwise order.
toClockwiseOrder :: (Eq r, Num r) => Polygon t p r -> Polygon t p r Source #
\( O(n) \) Make sure that every edge has the polygon's interior on its right, by orienting the outer boundary into clockwise order, and the inner borders (i.e. any holes, if they exist) into counter-clockwise order.
toClockwiseOrder' :: (Eq r, Num r) => Polygon t p r -> Polygon t p r Source #
\( O(n) \) Orient the outer boundary into clockwise order. Leaves any holes as they are.
toCounterClockWiseOrder :: (Eq r, Num r) => Polygon t p r -> Polygon t p r Source #
\( O(n) \) Make sure that every edge has the polygon's interior on its left, by orienting the outer boundary into counter-clockwise order, and the inner borders (i.e. any holes, if they exist) into clockwise order.
toCounterClockWiseOrder' :: (Eq r, Num r) => Polygon t p r -> Polygon t p r Source #
\( O(n) \) Orient the outer boundary into counter-clockwise order. Leaves any holes as they are.
reverseOuterBoundary :: Polygon t p r -> Polygon t p r Source #
Reorient the outer boundary from clockwise order to counter-clockwise order or from counter-clockwise order to clockwise order. Leaves any holes as they are.
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 simplePolySimplePolygon [Point2 0 0 :+ SP 0 (),Point2 10 0 :+ SP 1 (),Point2 10 10 :+ SP 2 (),Point2 5 15 :+ SP 3 (),Point2 1 11 :+ SP 4 ()]
maximumVertexBy :: ((Point 2 r :+ p) -> (Point 2 r :+ p) -> Ordering) -> Polygon t p r -> Point 2 r :+ p Source #
\( O(n) \) Yield the maximum point of a polygon according to the given comparison function.
minimumVertexBy :: ((Point 2 r :+ p) -> (Point 2 r :+ p) -> Ordering) -> Polygon t p r -> Point 2 r :+ p Source #
\( O(n) \) Yield the maximum point of a polygon according to the given comparison function.
findRotateTo :: ((Point 2 r :+ p) -> Bool) -> SimplePolygon p r -> Maybe (SimplePolygon p r) Source #
Rotate to the first point that matches the given condition.
>>>toVector <$> findRotateTo (== (Point2 1 0 :+ ())) (unsafeFromPoints [Point2 0 0 :+ (), Point2 1 0 :+ (), Point2 1 1 :+ ()])Just [Point2 1 0 :+ (),Point2 1 1 :+ (),Point2 0 0 :+ ()]>>>findRotateTo (== (Point2 7 0 :+ ())) $ unsafeFromPoints [Point2 0 0 :+ (), Point2 1 0 :+ (), Point2 1 1 :+ ()]Nothing
rotateLeft :: Int -> SimplePolygon p r -> SimplePolygon p r Source #
\( O(1) \) Rotate the polygon to the left by n number of points.
rotateRight :: Int -> SimplePolygon p r -> SimplePolygon p r Source #
\( O(1) \) Rotate the polygon to the right by n number of points.
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)\)
onBoundary :: (Num r, Ord r) => Point 2 r -> Polygon t p r -> Bool Source #
\( O(n) \) Test if q lies on the boundary of the polygon.
>>>Point2 1 1 `onBoundary` simplePolyFalse>>>Point2 0 0 `onBoundary` simplePolyTrue>>>Point2 10 0 `onBoundary` simplePolyTrue>>>Point2 5 13 `onBoundary` simplePolyFalse>>>Point2 5 10 `onBoundary` simplePolyFalse>>>Point2 10 5 `onBoundary` simplePolyTrue>>>Point2 20 5 `onBoundary` simplePolyFalse
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` simplePolyInside>>>Point2 0 0 `inPolygon` simplePolyOnBoundary>>>Point2 10 0 `inPolygon` simplePolyOnBoundary>>>Point2 5 13 `inPolygon` simplePolyInside>>>Point2 5 10 `inPolygon` simplePolyInside>>>Point2 10 5 `inPolygon` simplePolyOnBoundary>>>Point2 20 5 `inPolygon` simplePolyOutside
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.
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