| 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
- type VoronoiDiagram point = VoronoiDiagram_ (NumType point) point
- data VoronoiDiagram_ r point
- = AllColinear !(Alternating Vector (VerticalOrLineEQ r) point)
- | ConnectedVD !(VoronoiDiagram' (MDVertex r 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
type VoronoiDiagram point = VoronoiDiagram_ (NumType point) point Source #
A Voronoi diagram
data VoronoiDiagram_ r point Source #
Constructors
| AllColinear !(Alternating Vector (VerticalOrLineEQ r) point) | |
| ConnectedVD !(VoronoiDiagram' (MDVertex r point) point) |
Instances
| (Show point, Show r, Num r, Point_ point 2 r) => Show (VoronoiDiagram_ r point) Source # | |
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope Methods showsPrec :: Int -> VoronoiDiagram_ r point -> ShowS # show :: VoronoiDiagram_ r point -> String # showList :: [VoronoiDiagram_ r point] -> ShowS # | |
| (Eq point, Eq (NumType point), Eq r) => Eq (VoronoiDiagram_ r point) Source # | |
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope Methods (==) :: VoronoiDiagram_ r point -> VoronoiDiagram_ r point -> Bool # (/=) :: VoronoiDiagram_ r point -> VoronoiDiagram_ r point -> Bool # | |
| type Dimension (VoronoiDiagram_ r point) Source # | |
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope type Dimension (VoronoiDiagram_ r point) = 2 | |
| type NumType (VoronoiDiagram_ r point) Source # | |
Defined in HGeometry.VoronoiDiagram.ViaLowerEnvelope type NumType (VoronoiDiagram_ r point) = r | |
newtype VoronoiDiagram' vertex point Source #
A connected VoronoiDiagram
Constructors
| VoronoiDiagram (MinimizationDiagram (NumType point) vertex point) |
Instances
| (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 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.