| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | GHC2024 |
HGeometry.VoronoiDiagram.ViaLowerEnvelope
Description
Compute a Voronoi Diagram of a set of points in R^2 using the lower envelope of planes in R^3.
Synopsis
- type VoronoiDiagram point vtxData = VoronoiDiagram_ (NumType point) point vtxData
- data VoronoiDiagram_ r point vtxData
- = AllColinear !(Alternating Vector (VerticalOrLineEQ r) point)
- | ConnectedVD !(VoronoiDiagram' (MDVertex r point vtxData) point)
- newtype VoronoiDiagram' vertex point = VoronoiDiagram (MinimizationDiagram (NumType point) vertex point)
- asMap :: (Point_ point 2 r, Ord point) => VoronoiDiagram' vertex point -> NEMap point (Region r vertex)
- voronoiDiagram :: (Point_ point 2 r, Functor f, Ord point, Ord r, Fractional r, Foldable1 f, Show point, Show r) => f point -> VoronoiDiagram point ()
- voronoiDiagramWith :: (Point_ point 2 r, Functor nonEmpty, Ord point, Ord r, Fractional r, Foldable1 nonEmpty) => (nonEmpty (Plane r :+ point) -> LowerEnvelope (Plane r :+ point) vtxData) -> nonEmpty point -> VoronoiDiagram point vtxData
- voronoiDiagramWith' :: (Point_ point 2 r, Ord point, Functor set, Foldable1 set, Ord r, Fractional r, Show point, Show r) => (set (Plane r :+ point) -> VertexForm Map r (Plane r :+ point)) -> set point -> VoronoiDiagram point ()
- voronoiVertices :: (Point_ point 2 r, Functor f, Ord point, Ord r, Fractional r, Foldable1 f, Show point, Show r, Ord point) => f point -> Set (Point 2 r)
- pointToPlane :: (Point_ point 2 r, Num r) => point -> Plane r
Documentation
type VoronoiDiagram point vtxData = VoronoiDiagram_ (NumType point) point vtxData Source #
A Voronoi diagram
data VoronoiDiagram_ r point vtxData Source #
Constructors
| AllColinear !(Alternating Vector (VerticalOrLineEQ r) point) | |
| ConnectedVD !(VoronoiDiagram' (MDVertex r point vtxData) point) |
Instances
| (NFData point, NFData r, NFData vtxData, NFData (NumType point)) => NFData (VoronoiDiagram_ r point vtxData) Source # | |||||
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope Methods rnf :: VoronoiDiagram_ r point vtxData -> () # | |||||
| Generic (VoronoiDiagram_ r point vtxData) Source # | |||||
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope Associated Types
Methods from :: VoronoiDiagram_ r point vtxData -> Rep (VoronoiDiagram_ r point vtxData) x # to :: Rep (VoronoiDiagram_ r point vtxData) x -> VoronoiDiagram_ r point vtxData # | |||||
| (Show point, Show r, Num r, Show vtxData, Point_ point 2 r) => Show (VoronoiDiagram_ r point vtxData) Source # | |||||
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope Methods showsPrec :: Int -> VoronoiDiagram_ r point vtxData -> ShowS # show :: VoronoiDiagram_ r point vtxData -> String # showList :: [VoronoiDiagram_ r point vtxData] -> ShowS # | |||||
| (Eq point, Eq (NumType point), Eq r, Eq vtxData) => Eq (VoronoiDiagram_ r point vtxData) Source # | |||||
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope Methods (==) :: VoronoiDiagram_ r point vtxData -> VoronoiDiagram_ r point vtxData -> Bool # (/=) :: VoronoiDiagram_ r point vtxData -> VoronoiDiagram_ r point vtxData -> Bool # | |||||
| type Rep (VoronoiDiagram_ r point vtxData) Source # | |||||
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope type Rep (VoronoiDiagram_ r point vtxData) = D1 ('MetaData "VoronoiDiagram_" "HGeometry.VoronoiDiagram.ViaLowerEnvelope" "hgeometry-1.0.0.0-inplace" 'False) (C1 ('MetaCons "AllColinear" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 (Alternating Vector (VerticalOrLineEQ r) point))) :+: C1 ('MetaCons "ConnectedVD" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 (VoronoiDiagram' (MDVertex r point vtxData) point)))) | |||||
| type Dimension (VoronoiDiagram_ r point vtxData) Source # | |||||
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope type Dimension (VoronoiDiagram_ r point vtxData) = 2 | |||||
| type NumType (VoronoiDiagram_ r point vtxData) Source # | |||||
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope type NumType (VoronoiDiagram_ r point vtxData) = r | |||||
newtype VoronoiDiagram' vertex point Source #
A connected VoronoiDiagram
Constructors
| VoronoiDiagram (MinimizationDiagram (NumType point) vertex point) |
Instances
| (NFData (NumType point), NFData vertex, NFData point) => NFData (VoronoiDiagram' vertex point) Source # | |||||
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope Methods rnf :: VoronoiDiagram' vertex point -> () # | |||||
| Generic (VoronoiDiagram' vertex point) Source # | |||||
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope Associated Types
Methods from :: VoronoiDiagram' vertex point -> Rep (VoronoiDiagram' vertex point) x # to :: Rep (VoronoiDiagram' vertex point) x -> VoronoiDiagram' vertex point # | |||||
| (Show point, Show vertex, Show (NumType point), Point_ point 2 (NumType point), Point_ vertex 2 (NumType point)) => Show (VoronoiDiagram' vertex point) Source # | |||||
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope Methods showsPrec :: Int -> VoronoiDiagram' vertex point -> ShowS # show :: VoronoiDiagram' vertex point -> String # showList :: [VoronoiDiagram' vertex point] -> ShowS # | |||||
| (Eq point, Eq vertex, Eq (NumType point)) => Eq (VoronoiDiagram' vertex point) Source # | |||||
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope Methods (==) :: VoronoiDiagram' vertex point -> VoronoiDiagram' vertex point -> Bool # (/=) :: VoronoiDiagram' vertex point -> VoronoiDiagram' vertex point -> Bool # | |||||
| type Rep (VoronoiDiagram' vertex point) Source # | |||||
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope type Rep (VoronoiDiagram' vertex point) = D1 ('MetaData "VoronoiDiagram'" "HGeometry.VoronoiDiagram.ViaLowerEnvelope" "hgeometry-1.0.0.0-inplace" 'True) (C1 ('MetaCons "VoronoiDiagram" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (MinimizationDiagram (NumType point) vertex point)))) | |||||
| type Dimension (VoronoiDiagram' vertex point) Source # | |||||
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope type Dimension (VoronoiDiagram' vertex point) = 2 | |||||
| type NumType (VoronoiDiagram' vertex point) Source # | |||||
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope type NumType (VoronoiDiagram' vertex point) = NumType point | |||||
asMap :: (Point_ point 2 r, Ord point) => VoronoiDiagram' vertex point -> NEMap point (Region r vertex) Source #
Get, for each point, its Voronoi region
voronoiDiagram :: (Point_ point 2 r, Functor f, Ord point, Ord r, Fractional r, Foldable1 f, Show point, Show r) => f point -> VoronoiDiagram point () Source #
Computes the Voronoi Diagram, by lifting the points to planes, and computing the lower envelope of these planes.
O(n^4) ( we currently use the brute force implentation...) TODO: switch to something faster
voronoiDiagramWith :: (Point_ point 2 r, Functor nonEmpty, Ord point, Ord r, Fractional r, Foldable1 nonEmpty) => (nonEmpty (Plane r :+ point) -> LowerEnvelope (Plane r :+ point) vtxData) -> nonEmpty point -> VoronoiDiagram point vtxData Source #
Given a function to compute a lower envelope; construct use it to construct the Voronoi diagram.
voronoiDiagramWith' :: (Point_ point 2 r, Ord point, Functor set, Foldable1 set, Ord r, Fractional r, Show point, Show r) => (set (Plane r :+ point) -> VertexForm Map r (Plane r :+ point)) -> set point -> VoronoiDiagram point () Source #
Given a function that can construct the vertices of the lower envelope; use it to construct the Voronoi Diagram.