Content deleted Content added
VonHaarberg (talk | contribs) Algorithm section split up. |
VonHaarberg (talk | contribs) Centroid computations for 2D and 3D added. |
||
Line 41:
==Integration and Centroid compuation==
Because Voronoi diagram construction algorithms can be highly non-trivial, especially for inputs of dimension higher than two, the steps of calculating this diagram and finding the exact centroids of its cells may be replaced by an approximation.
===Approximation===
A common simplification is to employ a suitable discretization of space like a fine pixel-grid, e.g. the texture [[Z-buffering|buffer]] in graphics hardware. Cells are materialized as pixels, labeled with their corresponding site-ID. A cell's new center is approximated by averaging the positions of all pixels assigned with the same label.
Alternatively, [[Monte Carlo methods]] may be used, in which random sample points are generated according to some fixed underlying probability distribution, assigned to the closest site, and averaged to approximate the centroid for each site.
===Exact computation===
Altough embedding in other spaces is also possible, this elaboration assumes [[Euclidean distance|Euclidean space]] using the [[Lp space|''L<sup>2</sup>'' norm]] and discusses the two most relevant scenarios, which are two, and respectively three dimensions.
Since a Voronoi cell is of convex shape and always encloses its site, there exist trivial decompositions into easy integratable simplices:
* In two dimensions, the edges of the polygonal cell are connected with its site, creating an umbrella-shaped set of triangles.
* In three dimensions, the cell is enclosed by several planar polygons which have to be triangulated first:
** Compute a center for the polygon face, e.g. the average of all its vertices.
** Connecting the vertices of a polygon face with its center gives a planar umbrella-shaped triangulation.
** Trivially, a set of [[Tetrahedron|tetrahedra]] is obtained by connecting triangles of the cell's hull with the cell's site.
Integration of a cell and compuation of its centroid (center of mass) is now given as a weighted combination of its simplices' [[Circumscribed circle|circumcenters]] (in the following called <math display="inline">\mathbf{c}_i</math>).
* Two dimensions:
** For a triangle the circumcircle and its center are unique and can be easily computed, e.g. using [[Circumscribed circle#Circumcenter coordinates|cartesian coordinates]].
** Weighting computes as simplex-to-cell '''area''' ratios.
* Three dimensions:
** For tetrahedra, the circumcenter is found as the intersection of three bisector planes and can be expressed as a matrix-vector product.
** Weighting computes as simplex-to-cell '''volume''' ratios.
For a 2D cell with {{math|''n''}} triangular simplices and an accumulated area <math display="inline">A_C = \sum_{i=0}^n a_i</math> (where <math display="inline">a_i</math> is the [[Triangle#Computing the area of a triangle|area of a triangle]] simplex), the new cell centroid computes as:
:<math>
C = \frac{1}{A_C}\sum_{i=0}^{n}\mathbf{c}_i a_i
</math>
Analogously, for a 3D cell with a volume of <math display="inline">V_C = \sum_{i=0}^n v_i</math> (where <math display="inline">v_i</math> is the [[Tetrahedron#Volume|volume of a tetrahedron]] simplex), the centroid computes as:
:<math>
C = \frac{1}{V_C}\sum_{i=0}^{n}\mathbf{c}_i v_i
</math>
==Convergence==
| |||