Copyright	(C) Frank Staals
License	see the LICENSE file
Maintainer	Frank Staals
Safe Haskell	Safe-Inferred
Language	GHC2021

HGeometry.Plane.LowerEnvelope.Connected

Description

A Representation of the Lower envelope of planes as a bunch of convex regions

Synopsis

data MinimizationDiagram r plane
asMap :: MinimizationDiagram r plane -> Map plane (Region r (Point 2 r))
data Region r point
- = Bounded (CircularList point)
- | Unbounded (Vector 2 r) (NonEmpty point) (Vector 2 r)
type CircularList a = [a]
intersectionPoint :: (Plane_ plane r, Ord r, Fractional r) => Three plane -> Maybe (Point 3 r)
intersectionLine :: (Plane_ plane r, Fractional r, Eq r) => plane -> plane -> Maybe (VerticalOrLineEQ r)
intersectionVector :: (Plane_ plane r, Ord r, Fractional r) => plane -> plane -> Maybe (Vector 2 r)
fromVertexForm :: (Plane_ plane r, Ord plane, Ord r, Fractional r) => VertexForm r plane -> MinimizationDiagram r plane
data Definers plane
fromCCWList :: [plane] -> Definers plane
definers :: forall plane r. (Plane_ plane r, Ord r, Fractional r) => Three plane -> Maybe (Point 3 r, Definers plane)
mergeDefiners :: (Plane_ plane r, Eq plane, Ord r, Fractional r) => Point 3 r -> Definers plane -> Definers plane -> Definers plane
type VertexForm r plane = Map (Point 3 r) (Definers plane)
bruteForceLowerEnvelope :: (Plane_ plane r, Ord plane, Ord r, Fractional r, Foldable set) => set plane -> MinimizationDiagram r plane
computeVertexForm :: (Plane_ plane r, Ord plane, Ord r, Fractional r, Foldable set) => set plane -> VertexForm r plane

Documentation

data MinimizationDiagram r plane Source #

A minimization daigram just maps every plane on the lower envelope to the region above which it is minimal. Every plane has at most one such a region.

Instances

Instances details

CFunctor (MinimizationDiagram r) Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.Type Methods cmap :: (Dom (MinimizationDiagram r) a, Dom (MinimizationDiagram r) b) => (a -> b) -> MinimizationDiagram r a -> MinimizationDiagram r b Source # (<$:) :: (Dom (MinimizationDiagram r) a, Dom (MinimizationDiagram r) b) => a -> MinimizationDiagram r b -> MinimizationDiagram r a Source #
Constrained (MinimizationDiagram r) Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.Type Associated Types type Dom (MinimizationDiagram r) a Source #
(Show plane, Show r) => Show (MinimizationDiagram r plane) Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.Type Methods showsPrec :: Int -> MinimizationDiagram r plane -> ShowS # show :: MinimizationDiagram r plane -> String # showList :: [MinimizationDiagram r plane] -> ShowS #
(Eq plane, Eq r) => Eq (MinimizationDiagram r plane) Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.Type Methods (==) :: MinimizationDiagram r plane -> MinimizationDiagram r plane -> Bool # (/=) :: MinimizationDiagram r plane -> MinimizationDiagram r plane -> Bool #
type Dom (MinimizationDiagram r) plane Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.Type type Dom (MinimizationDiagram r) plane = (Ord plane, NumType plane ~ r)
type Dimension (MinimizationDiagram r plane) Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.Type type Dimension (MinimizationDiagram r plane) = 2
type NumType (MinimizationDiagram r plane) Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.Type type NumType (MinimizationDiagram r plane) = r

asMap :: MinimizationDiagram r plane -> Map plane (Region r (Point 2 r)) Source #

Get the underlying Map that relates every plane in the envelope to its projected region

data Region r point Source #

A region in the minimization diagram. The boundary is given in CCW order; i.e. the region is to the left of the boundary.

Constructors

Bounded (CircularList point)
Unbounded
Fields (Vector 2 r) vector indicating the direction of the unbounded edge incident to the first vertex. Note that this vector thus points INTO vertex v. (NonEmpty point) the vertices in CCW order, (Vector 2 r) the vector indicating the direction of the unbounded edge incident to the last vertex. The vector points away from the vertex (i.e. towards +infty).

Instances

Instances details

Foldable (Region r) Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.Type Methods fold :: Monoid m => Region r m -> m # foldMap :: Monoid m => (a -> m) -> Region r a -> m # foldMap' :: Monoid m => (a -> m) -> Region r a -> m # foldr :: (a -> b -> b) -> b -> Region r a -> b # foldr' :: (a -> b -> b) -> b -> Region r a -> b # foldl :: (b -> a -> b) -> b -> Region r a -> b # foldl' :: (b -> a -> b) -> b -> Region r a -> b # foldr1 :: (a -> a -> a) -> Region r a -> a # foldl1 :: (a -> a -> a) -> Region r a -> a # toList :: Region r a -> [a] # null :: Region r a -> Bool # length :: Region r a -> Int # elem :: Eq a => a -> Region r a -> Bool # maximum :: Ord a => Region r a -> a # minimum :: Ord a => Region r a -> a # sum :: Num a => Region r a -> a # product :: Num a => Region r a -> a #
Traversable (Region r) Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.Type Methods traverse :: Applicative f => (a -> f b) -> Region r a -> f (Region r b) # sequenceA :: Applicative f => Region r (f a) -> f (Region r a) # mapM :: Monad m => (a -> m b) -> Region r a -> m (Region r b) # sequence :: Monad m => Region r (m a) -> m (Region r a) #
Functor (Region r) Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.Type Methods fmap :: (a -> b) -> Region r a -> Region r b # (<$) :: a -> Region r b -> Region r a #
(Show point, Show r) => Show (Region r point) Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.Type Methods showsPrec :: Int -> Region r point -> ShowS # show :: Region r point -> String # showList :: [Region r point] -> ShowS #
(Eq point, Eq r) => Eq (Region r point) Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.Type Methods (==) :: Region r point -> Region r point -> Bool # (/=) :: Region r point -> Region r point -> Bool #
type Dimension (Region r point) Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.Type type Dimension (Region r point) = Dimension point
type NumType (Region r point) Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.Type type NumType (Region r point) = r

type CircularList a = [a] Source #

bounded regions are really circular lists, but we just represent them as lists for now.

intersectionPoint :: (Plane_ plane r, Ord r, Fractional r) => Three plane -> Maybe (Point 3 r) Source #

Computes there the three planes intersect

intersectionLine :: (Plane_ plane r, Fractional r, Eq r) => plane -> plane -> Maybe (VerticalOrLineEQ r) Source #

Given two planes, computes the line in which they intersect.

intersectionVector :: (Plane_ plane r, Ord r, Fractional r) => plane -> plane -> Maybe (Vector 2 r) Source #

Computes the direction vector v of the directed line l in which the two planes h and h' intersect, and so that h will be to the left of the directed line

fromVertexForm :: (Plane_ plane r, Ord plane, Ord r, Fractional r) => VertexForm r plane -> MinimizationDiagram r plane Source #

Given the vertices of the lower envelope; compute the minimization diagram.

$O(h\log h)$ assuming that the input is degenerate.

data Definers plane Source #

in CCW order, starting with the plane that is minimal at the vertical up direction from their common vertex.

Instances

Instances details

Foldable Definers Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.VertexForm Methods fold :: Monoid m => Definers m -> m # foldMap :: Monoid m => (a -> m) -> Definers a -> m # foldMap' :: Monoid m => (a -> m) -> Definers a -> m # foldr :: (a -> b -> b) -> b -> Definers a -> b # foldr' :: (a -> b -> b) -> b -> Definers a -> b # foldl :: (b -> a -> b) -> b -> Definers a -> b # foldl' :: (b -> a -> b) -> b -> Definers a -> b # foldr1 :: (a -> a -> a) -> Definers a -> a # foldl1 :: (a -> a -> a) -> Definers a -> a # toList :: Definers a -> [a] # null :: Definers a -> Bool # length :: Definers a -> Int # elem :: Eq a => a -> Definers a -> Bool # maximum :: Ord a => Definers a -> a # minimum :: Ord a => Definers a -> a # sum :: Num a => Definers a -> a # product :: Num a => Definers a -> a #
Functor Definers Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.VertexForm Methods fmap :: (a -> b) -> Definers a -> Definers b # (<$) :: a -> Definers b -> Definers a #
Show plane => Show (Definers plane) Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.VertexForm Methods showsPrec :: Int -> Definers plane -> ShowS # show :: Definers plane -> String # showList :: [Definers plane] -> ShowS #
Eq plane => Eq (Definers plane) Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.VertexForm Methods (==) :: Definers plane -> Definers plane -> Bool # (/=) :: Definers plane -> Definers plane -> Bool #
Ord plane => Ord (Definers plane) Source #
Instance details Defined in HGeometry.Plane.LowerEnvelope.Connected.VertexForm Methods compare :: Definers plane -> Definers plane -> Ordering # (<) :: Definers plane -> Definers plane -> Bool # (<=) :: Definers plane -> Definers plane -> Bool # (>) :: Definers plane -> Definers plane -> Bool # (>=) :: Definers plane -> Definers plane -> Bool # max :: Definers plane -> Definers plane -> Definers plane # min :: Definers plane -> Definers plane -> Definers plane #

fromCCWList :: [plane] -> Definers plane Source #

Given the planes in order, starting with the one that is closest in the up direction, construct the Definers.

definers :: forall plane r. (Plane_ plane r, Ord r, Fractional r) => Three plane -> Maybe (Point 3 r, Definers plane) Source #

Smart constructor for creating the definers of three planes

mergeDefiners :: (Plane_ plane r, Eq plane, Ord r, Fractional r) => Point 3 r -> Definers plane -> Definers plane -> Definers plane Source #

Merge two lists of definers.

O(n^2), since we are using incremental insertion.

type VertexForm r plane = Map (Point 3 r) (Definers plane) Source #

The vertices of a lower envelope is just a Map with every vertex its definers, i.e. the planes that define the vertex in CCW order around it.

bruteForceLowerEnvelope :: (Plane_ plane r, Ord plane, Ord r, Fractional r, Foldable set) => set plane -> MinimizationDiagram r plane Source #

Computes the lower envelope in O(n^4) time.

computeVertexForm :: (Plane_ plane r, Ord plane, Ord r, Fractional r, Foldable set) => set plane -> VertexForm r plane Source #

Computes the vertices of the lower envelope

O(n^4) time.