| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Geometry.Algorithms.Delaunay
Contents
Description
Delaunay triangulation and Voronoi diagrams.
(image code)
>>>import Draw>>>import Geometry.Algorithms.Sampling>>>import Control.Monad.ST>>>import Numerics.Functions>>>import Geometry.Core as G>>>import Graphics.Rendering.Cairo as C>>>import qualified Data.Vector as V>>>import qualified System.Random.MWC as MWC>>>>>>seed = [2]>>>(width, height) = (600::Int, 600::Int)>>>:{points = runST $ do gen <- MWC.initialize (V.fromList (map fromIntegral seed)) let bb = boundingBox [zero, Vec2 (fromIntegral width) (fromIntegral height)] points <- poissonDisc gen bb 16 5 let radius = fromIntegral (min width height) / 2.5 pure (filter (\p -> normSquare (p -. boundingBoxCenter bb) <= radius^2) points) :}
>>>delaunay = delaunayTriangulation points>>>:{haddockRender "Geometry/Algorithms/Delaunay/delaunay_voronoi.svg" width height $ \_ -> do let margin = 10 bb = boundingBox [Vec2 margin margin, Vec2 (fromIntegral width - margin) (fromIntegral height - margin)] cairoScope $ do setColor (mma 1) setDash [5,5] 0 sketch (boundingBoxPolygon bb) stroke let edgeCenter (Line start end) = (start +. end) /. 2 imageSize = fromIntegral (min width height) for_ (delaunayEdges delaunay) $ \edge -> do let startRamp = imageSize * 0.4 endRamp = imageSize * 0.8 opacity = 1 - smoothstep startRamp endRamp (let Vec2 _ y = edgeCenter edge in y) setColor (mma 3 `withOpacity` opacity) sketch edge stroke for_ (clipEdgesToBox bb (voronoiEdges delaunay)) $ \edge -> do let startRamp = imageSize * 0.2 endRamp = imageSize * 0.6 opacity = smoothstep startRamp endRamp (let Vec2 _ y = edgeCenter edge in y) setColor (mma 0 `withOpacity` opacity) sketch edge stroke :} Generated file: size 729KB, crc32: 0x640a6e45
Synopsis
- delaunayTriangulation :: Sequential vector => vector Vec2 -> DelaunayTriangulation
- data DelaunayTriangulation
- delaunayTriangles :: DelaunayTriangulation -> Vector Polygon
- delaunayEdges :: DelaunayTriangulation -> Vector Line
- voronoiCorners :: DelaunayTriangulation -> Vector Vec2
- data Ray = Ray !Vec2 !Vec2
- voronoiEdges :: DelaunayTriangulation -> Vector (Either Line Ray)
- data VoronoiPolygon
- = VoronoiFinite !Polygon
- | VoronoiInfinite !Vec2 [Vec2] !Vec2
- voronoiCells :: DelaunayTriangulation -> Vector VoronoiPolygon
- delaunayHull :: DelaunayTriangulation -> Vector Vec2
- findClosestInputPoint :: DelaunayTriangulation -> Vec2 -> Int -> Int
- clipEdgesToBox :: HasBoundingBox boundingBox => boundingBox -> Vector (Either Line Ray) -> Vector Line
- clipCellsToBox :: HasBoundingBox boundingBox => boundingBox -> Vector VoronoiPolygon -> Vector Polygon
- lloydRelaxation :: (HasBoundingBox boundingBox, Sequential vector) => boundingBox -> Double -> vector Vec2 -> Vector Vec2
Core
delaunayTriangulation :: Sequential vector => vector Vec2 -> DelaunayTriangulation Source #
Create an (abstract) DelaunayTriangulation from a set of points. The
resulting data structure can be queried using various functions in this module.
Some of the accessor results are aligned, e.g. delaunayTriangles and
voronoiCorners have related \(i\)-th entries. Similarly it is possible to
annotate accessor results with arbitrary data by simply mapping over or zipping
them with the data source.
data DelaunayTriangulation Source #
Abstract data type supporting many efficient Delaunay and Voronoi properties.
Instances
| NFData DelaunayTriangulation Source # | |
Defined in Geometry.Algorithms.Delaunay.Internal.Delaunator.Api Methods rnf :: DelaunayTriangulation -> () # | |
Accessors
delaunayTriangles :: DelaunayTriangulation -> Vector Polygon Source #
All Delaunay triangles, ordered roughly from the center of the input points’ bounding box.
Note: The circumcenter of the \(i\)-th triangle is the \(i\)-th entry of
voronoiCorners. This can be used to zip them.
(image code)
>>>:{haddockRender "Geometry/Algorithms/Delaunay/triangles.svg" width height $ \_ -> do let margin = 10 bb = boundingBox [Vec2 margin margin, Vec2 (fromIntegral width - margin) (fromIntegral height - margin)] cairoScope $ do setColor (mma 0) setDash [5,5] 0 sketch (boundingBoxPolygon bb) stroke V.iforM_ (delaunayTriangles delaunay) $ \i triangle -> do setColor (mma i) sketch (growPolygon (-2) triangle) fill :} Generated file: size 48KB, crc32: 0x960a4150
delaunayEdges :: DelaunayTriangulation -> Vector Line Source #
Each (undirected) edge of the Delaunay triangulation.
(image code)
>>>:{haddockRender "Geometry/Algorithms/Delaunay/edges.svg" width height $ \_ -> do let margin = 10 bb = boundingBox [Vec2 margin margin, Vec2 (fromIntegral width - margin) (fromIntegral height - margin)] cairoScope $ do setColor (mma 0) setDash [5,5] 0 sketch (boundingBoxPolygon bb) stroke V.iforM_ (delaunayEdges delaunay) $ \i edge -> do setColor (mma i) sketch edge stroke :} Generated file: size 97KB, crc32: 0xc283d1df
voronoiCorners :: DelaunayTriangulation -> Vector Vec2 Source #
Corners of the Voronoi cells, useful for painting them in isolation.
Note: The \(i\)-th corner is the circumcenter of the \(i\)-th entry of
delaunayTriangles. This can be used to zip them.
(image code)
>>>:{haddockRender "Geometry/Algorithms/Delaunay/voronoi_corners.svg" width height $ \_ -> do let margin = 10 bb = boundingBox [Vec2 margin margin, Vec2 (fromIntegral width - margin) (fromIntegral height - margin)] cairoScope $ do setColor (mma 0) setDash [5,5] 0 sketch (boundingBoxPolygon bb) stroke for_ (clipEdgesToBox bb (voronoiEdges delaunay)) $ \edge -> do setColor (mma 0 `withOpacity` 0.2) sketch edge stroke V.iforM_ (voronoiCorners delaunay) $ \i corner -> do setColor (mma i) sketch (Circle corner 2) fill :} Generated file: size 155KB, crc32: 0xfd606083
A ray is a line that extends to infinity on one side.
voronoiEdges :: DelaunayTriangulation -> Vector (Either Line Ray) Source #
Each edge of the Voronoi diagram. The boundary edges extend to
infinity, and are provided as Rays.
clipEdgesToBox conveniently handles the case of constraining
this to a rectangular viewport.
(image code)
>>>:{haddockRender "Geometry/Algorithms/Delaunay/voronoi_edges.svg" width height $ \_ -> do let margin = 10 bb = boundingBox [Vec2 margin margin, Vec2 (fromIntegral width - margin) (fromIntegral height - margin)] cairoScope $ do setColor (mma 0) setDash [5,5] 0 sketch (boundingBoxPolygon bb) stroke V.iforM_ (clipEdgesToBox bb (voronoiEdges delaunay)) $ \i edge -> do setColor (mma i) sketch edge stroke :} Generated file: size 94KB, crc32: 0x8e95bd19
data VoronoiPolygon Source #
A Voronoi Cell can either be an ordinary (finite) polygon, or one that extends to infinity for boundary polygons.
Constructors
| VoronoiFinite !Polygon | Ordinary polygon |
| VoronoiInfinite !Vec2 [Vec2] !Vec2 | The polygon consists of a list of finite points, and extends to
infinity at the beginning/end in the direction of the first/last
argument. For example, the bottom/right quadrant (in screen coordinates)
would be |
Instances
voronoiCells :: DelaunayTriangulation -> Vector VoronoiPolygon Source #
All Voronoi polygons. The polygons at the hull can be infinite.
clipCellsToBox conveniently handles the case of constraining
this to a rectangular viewport.
Note: The cell of the \(i\)-th input point is the \(i\)-th entry of
voronoiCells. This can be used to zip them.
(image code)
>>>:{haddockRender "Geometry/Algorithms/Delaunay/voronoi_cells.svg" width height $ \_ -> do let margin = 10 bb = boundingBox [Vec2 margin margin, Vec2 (fromIntegral width - margin) (fromIntegral height - margin)] cairoScope $ do setColor (mma 0) setDash [5,5] 0 sketch (boundingBoxPolygon bb) stroke V.iforM_ (clipCellsToBox bb (voronoiCells delaunay)) $ \i polygon -> do setColor (mma i) sketch (growPolygon (-2) polygon) fill :} Generated file: size 37KB, crc32: 0x8587a040
delaunayHull :: DelaunayTriangulation -> Vector Vec2 Source #
We get the convex hull for free out of the calculation. Equivalent to
calling convexHull on the input points, but as a Vector.
(image code)
>>>:{haddockRender "Geometry/Algorithms/Delaunay/convex_hull.svg" width height $ \_ -> do let margin = 10 bb = boundingBox [Vec2 margin margin, Vec2 (fromIntegral width - margin) (fromIntegral height - margin)] cairoScope $ do setColor (mma 0) setDash [5,5] 0 sketch (boundingBoxPolygon bb) stroke sketch (Polygon (toList (delaunayHull delaunay))) setColor (mma 1) stroke for_ points $ \p -> do sketch (Circle p 2) setColor (mma 3) fill :} Generated file: size 37KB, crc32: 0x461696a3
findClosestInputPoint Source #
Arguments
| :: DelaunayTriangulation | |
| -> Vec2 | Needle |
| -> Int | Start searching at the \(i\)-th input point of
|
| -> Int | Input |
Find the index of the closest input point.
findClosestInputPoint needle starti of the closest input
point to needle, starting the search at start. start=0 searches the
entire input. points!i is the closest point’s position.
(image code)
>>>:{haddockRender "Geometry/Algorithms/Delaunay/find_triangle.svg" width height $ \_ -> do let margin = 10 bb = boundingBox [Vec2 margin margin, Vec2 (fromIntegral width - margin) (fromIntegral height - margin)] findThesePoints = runST $ do gen <- MWC.initialize (V.fromList (map (succ . fromIntegral) seed)) let margin' = 20 bb' = boundingBox [Vec2 margin' margin', Vec2 (fromIntegral width - margin') (fromIntegral height - margin')] poissonDisc gen bb' 50 4 cairoScope $ do setColor (mma 0) setDash [5,5] 0 sketch (boundingBoxPolygon bb) stroke for_ (delaunayEdges delaunay) $ \edge -> do setColor (black `withOpacity` 0.5) sketch edge stroke let foundTriangleIndices = [(p, findClosestInputPoint delaunay p 0) | p <- toList findThesePoints] for_ (zip [0..] foundTriangleIndices) $ \(i, (needle, p)) -> do let closest = points V.! p cairoScope $ do setColor (mma i) sketch (Circle closest 3) >> fill sketch (Circle needle 3) >> fill cairoScope $ do setColor black sketch (Circle closest 3) >> stroke sketch (Circle needle 3) >> stroke cairoScope $ do setColor (mma i) sketch (Line needle closest) >> stroke :} Generated file: size 181KB, crc32: 0x6d8c142f
Convenience
clipEdgesToBox :: HasBoundingBox boundingBox => boundingBox -> Vector (Either Line Ray) -> Vector Line Source #
Cut off all Rays to end at the provided BoundingBox. Convenient to take
the result of voronoiEdges and clip it to a rectangular viewport.
clipCellsToBox :: HasBoundingBox boundingBox => boundingBox -> Vector VoronoiPolygon -> Vector Polygon Source #
Cut off all infinite VoronoiCells with the provided BoundingBox. Convenient to take
the result of voronoiCells and clip it to a rectangular viewport.
This function yields incorrect results when the angle between the directions is too large, because it simply comically enlarges the »infinite« directions to finite size, closes the then finite polygon, and clips the resulting polygon. Since Voronoi cells don’t produce such wide angels for even small point sizes, this is a worthwhile tradeoff. The issue can probably be hacked around by adding another point for all corners enclosed by the direction vectors.
Arguments
| :: (HasBoundingBox boundingBox, Sequential vector) | |
| => boundingBox | |
| -> Double | Convergence factor \(\omega\). |
| -> vector Vec2 | |
| -> Vector Vec2 |
Relax the input points by moving them to(wards) their cell’s centroid, leading to a uniform distribution of points. Works well when applied multiple times.
The parameter \(\omega\) controls how far the Voronoi cell center moves towards the centroid. See here for a cool live visualization.
- \(0\) does not move the points at all.
- \(1\) moves the cell’s centers to the cell’s centroid (standard Lloyd).
- \(\sim 2\) overshoots the move towards the cell’s center, leading to faster convergence.
- \(<0\) values yield wonky-but-interesting behavior! \(\ddot\smile\)
(image code)
>>>:{haddockRender "Geometry/Algorithms/Delaunay/lloyd_relaxation.svg" width height $ \_ -> do let margin = 10 bb = boundingBox [Vec2 margin margin, Vec2 (fromIntegral width - margin) (fromIntegral height - margin)] cairoScope $ do setColor (mma 0) setDash [5,5] 0 sketch (boundingBoxPolygon bb) stroke let points' = iterate (lloydRelaxation bb 1) points !! 5 delaunay' = delaunayTriangulation points' V.iforM_ (clipCellsToBox bb (voronoiCells delaunay')) $ \i polygon -> do setColor (mma i) sketch (growPolygon (-2) polygon) fill :} Generated file: size 37KB, crc32: 0x7130f1e1