| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | GHC2021 |
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
- data VoronoiDiagram point
- = AllColinear !(Alternating Vector (VerticalOrLineEQ (NumType point)) point)
- | ConnectedVD !(VoronoiDiagram' (Point 2 (NumType point)) 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)) -> nonEmpty 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
data VoronoiDiagram point Source #
A Voronoi diagram
Constructors
| AllColinear !(Alternating Vector (VerticalOrLineEQ (NumType point)) point) | |
| ConnectedVD !(VoronoiDiagram' (Point 2 (NumType point)) point) |
Instances
| (Show point, Show (NumType point)) => Show (VoronoiDiagram point) Source # | |
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope Methods showsPrec :: Int -> VoronoiDiagram point -> ShowS # show :: VoronoiDiagram point -> String # showList :: [VoronoiDiagram point] -> ShowS # | |
| (Eq point, Eq (NumType point)) => Eq (VoronoiDiagram point) Source # | |
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope Methods (==) :: VoronoiDiagram point -> VoronoiDiagram point -> Bool # (/=) :: VoronoiDiagram point -> VoronoiDiagram point -> Bool # | |
| type Dimension (VoronoiDiagram point) Source # | |
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope type Dimension (VoronoiDiagram point) = 2 | |
| type NumType (VoronoiDiagram point) Source # | |
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope type NumType (VoronoiDiagram point) = NumType point | |
newtype VoronoiDiagram' vertex point Source #
A connected VoronoiDiagram
Constructors
| VoronoiDiagram (MinimizationDiagram (NumType point) vertex point) |
Instances
| (Show point, Show vertex, Show (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 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)) -> nonEmpty point -> VoronoiDiagram point Source #
Given a function to compute a lower envelope; construct use it to construct the Voronoi diagram.
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) Source #
Compute the vertices of the Voronoi diagram
pointToPlane :: (Point_ point 2 r, Num r) => point -> Plane r Source #
lifts the point to a plane; so that the lower envelope corresponds to the VD