-
Notifications
You must be signed in to change notification settings - Fork 8
/
README.jmd
130 lines (88 loc) · 5.31 KB
/
README.jmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
VoronoiCells
============
[](https://github.com/robertdj/VoronoiCells.jl/actions)
[](https://codecov.io/github/JuliaGeometry/VoronoiCells.jl?branch=master)
*VoronoiCells* use the [VoronoiDelaunay](https://github.com/JuliaGeometry/VoronoiDelaunay.jl) package to compute the vertices and areas of the Voronoi cells in a tessellation.
Furthermore, *VoronoiCells* handles interaction with the specified observation rectangle.
# Installation
Switch to `Pkg` mode in Julia with `]` and run
```julia; eval = false
add VoronoiCells
```
# Usage
For specifying 2D points I use the [GeometryBasics package](https://github.com/JuliaGeometry/GeometryBasics.jl).
Using the [Plots package](https://github.com/JuliaPlots/Plots.jl) we can easily visualize Voronoi tesselations.
To make this document reproducible, I also used a random point pattern with a fixed seed.
```julia
using VoronoiCells
using GeometryBasics
using Plots
using Random
```
```julia; echo = false, results = "hidden"
pyplot()
```
First make a vector of points and a rectangle that contains the points (this README was first made when `MersenneTwister` was the default random number generator; I stick with this to make the results reproducible):
```julia
rng = Random.MersenneTwister(1337)
rect = Rectangle(Point2(0, 0), Point2(1, 1))
points = [Point2(rand(rng), rand(rng)) for _ in 1:10]
```
The main function of *VoronoiCells* is `voronoicells` that computes the cell of each generator point.
```julia
tess = voronoicells(points, rect);
```
The output `tess` is a struct.
The corners of the Voronoi cells of the `n`'th generator is available as `tess.Cells[n]`.
The corners are sorted counter-clockwise.
```julia
tess.Cells[1]
```
There is a convenience function for plotting the edges of the Voronoi cells.
The generators are not added, but here I add them separately.
```julia; label = "tesselation.png"; fig_height = 4.5; fig_width = 5
scatter(points, markersize = 6, label = "generators")
annotate!([(points[n][1] + 0.02, points[n][2] + 0.03, Plots.text(n)) for n in 1:10])
plot!(tess, legend = :topleft)
```
The function `voronoiarea` computes the area of each Voronoi cell:
```julia
voronoiarea(tess)
```
# Technical notes
My main interest is the area of the Voronoi cells and not the cells *per se*.
The current representation of a cell as its corners in a vector is by no means set in stone, so reach out if you think another representation is more suitable.
## Corners
For technical reasons the *VoronoiDelaunay* package only works with points in the rectangle [1, 2] x [1, 2] -- here referred to as the VoronoiDelaunay rectangle.
Furthermore, *VoronoiDelaunay* includes the corner points of the rectangle in the set of generators.
We can emulate the behavior in *VoronoiCells* by explicitly including the corners:
```julia
extended_points = vcat(points, VoronoiCells.corners(rect))
extended_tess = voronoicells(extended_points, rect);
```
Plotting this tesselation we see that the cells neighboring the corners are affected, namely the cells of points 1, 4, 5, 6, 9.
```julia; label = "tesselation_with_corners.png"; fig_height = 4.5; fig_width = 5
scatter(points, markersize = 6, label = "generators")
annotate!([(points[n][1] + 0.02, points[n][2] + 0.03, Plots.text(n)) for n in 1:10])
plot!(extended_tess, legend = :none)
```
*VoronoiCells* circumvents this in the following manner:
The set of transformed generators are augmented with the corners of the VoronoiDelaunay rectangle.
All points in the augmented generators are mapped to a rectangle called the computational rectangle with the following properties:
- It is a (non-empty) subset of the VoronoiDelaunay rectangle
- The Voronoi cells of the augmented generators belonging to the corners of the VoronoiDelaunay rectangle do not overlap with the computational rectangle.
This does not uniquely define a computational rectangle, but in theory any candidate will suffice.
The intersection of the computational rectangle and the Voronoi cells of the transformed generators are transformed versions of their Voronoi cells in the original rectangle.
Transforming these cells back to the original rectangle give the desired Voronoi tesselation.
Note that in order to consider point patterns in general rectangles such a mapping has to be applied anyway, so we are not introducing unnecessary computational cost.
The closer the generators are to the edges/corners of the original rectangle, the larger the computational rectangle can be.
In order to avoid additional preprocessing I use a conservative minimal rectangle with corners (1.5 + x, 15 + x), (1.5 - x, 1.5 + x), (1.5 - x, 1.5 - x), (1.5 + x, 1.5 - x) where x = 1/6.
If we can assume that all quadrants of the original rectangle contains points we can set x = 1/4.
**Reach out if this small rectangle is causing trouble.**
One extra step that *is* necessary is to figure out which Voronoi cell(s) the corners of the rectangle belongs to.
This is determined by finding the point(s) with the smallest distance to each of the corners.
# Weave
This README is generated with the [Weave package](https://github.com/JunoLab/Weave.jl) using the command
```julia; eval = false
weave("README.jmd", doctype = "github", fig_path = "doc")
```