| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| 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
- 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)
- type VertexForm r plane = Map (Point 3 r) (Definers plane)
- data Definers plane
- fromCCWList :: [plane] -> Definers plane
- definers :: (Plane_ plane r, Ord r, Fractional r) => Three plane -> Maybe (Point 3 r, Definers plane)
- fromVertexForm :: (Plane_ plane r, Ord plane, Ord r, Fractional r) => VertexForm r plane -> MinimizationDiagram r plane
- mergeDefiners :: (Plane_ plane r, Eq plane, Ord r, Fractional r) => Point 3 r -> Definers plane -> Definers plane -> 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
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
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
| |
Instances
| Functor (Region r) Source # | |
| Foldable (Region r) Source # | |
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 # elem :: Eq a => a -> Region r a -> Bool # maximum :: Ord a => Region r a -> a # minimum :: Ord a => Region r a -> a # | |
| Traversable (Region r) Source # | |
Defined in HGeometry.Plane.LowerEnvelope.Connected.Type | |
| (Show point, Show r) => Show (Region r point) Source # | |
| (Eq point, Eq r) => Eq (Region r point) Source # | |
| type Dimension (Region r point) Source # | |
Defined in HGeometry.Plane.LowerEnvelope.Connected.Type type Dimension (Region r point) = Dimension point | |
| type NumType (Region r point) Source # | |
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
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.
in CCW order, starting with the plane that is minimal at the vertical up direction from their common vertex.
Instances
| Functor Definers Source # | |
| Foldable Definers Source # | |
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 # elem :: Eq a => a -> Definers a -> Bool # maximum :: Ord a => Definers a -> a # minimum :: Ord a => Definers a -> a # | |
| Show plane => Show (Definers plane) Source # | |
| Eq plane => Eq (Definers plane) Source # | |
| Ord plane => Ord (Definers plane) Source # | |
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 # | |
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 :: (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
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.
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.
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.