dune-geometry
2.4
|
![]() |
This is mainly based on Jürgen Beys http://www.igpm.rwth-aachen.de/bey/ dissertation. The relevant part is available from http://www.igpm.rwth-aachen.de/Download/reports/bey/simplex.ps.gz.
A Kuhn simplex of dimension n can be described by its size s and a permutation of the vector . To get the coordinates of the corners
of the simplex, you do as follows:
Let N(n, x) be the number of gridpoints within an n-dimensional Kuhn0 simplex of x gridunits width.
The number of points in a 0-dimensional simplex is 1, independent of its width.
N(0, x) = 1
The recursion formula is
We slice the n+1 dimensional simplex orthogonal to one of the dimensions and sum the number of points in the n dimensional subsimplices.
This formula is satisfied by the binomial coefficient
See Bronstein, Semendjajew, Musiol, Mühlig "Taschenbuch der Mathematik" (1999), Formula (1.35c)
Observations:
Let us calculate the index of vertex 9, which has the coordinates .
On to a more complicated example: vertex 6 with coordinates .
The general algorithm for n dimensions and a vertex with coordinates is as follows:
In formulas it looks like this:
Let be the index of point
in the n-dimensional Kuhn0 simplex. The coordinates measure the position of the point in gridunits and thus are integer.
Since the coordinates of a vertex within the Kuhn0 obey the relation , they cannot simply be swapped so the sum is somewhat ugly.
We don't know of a way to simply map a subelement of a Kuhn0 simplex to an index number. Luckily, the iterator interface only requires that we be able to calculate the next subelement.
Each subelement is a Kuhn (sub)simplex which triangulates a hypercube. We need to remember the vertex which is the origin of that hypercube and the index of the permutation of that identifies the Kuhn subsimplex. Now to get to the next subelement, we simply need to increment the permutation index, and if the overflows we reset it and increment the origin to the next vertex (we already know how to do that).
Some subelements generated this way are outside the refined Kuhn0 simplex, so we have to check for that, and skip them.
[NOTE: There may be some interesting stuff in http://en.wikipedia.org/wiki/Factoradic . I was not aware of it while writing this code, however.]
We need to index the n! permutations of the integers from 0 to n-1 and a way to calculate the permutation if given the index.
I'll discuss the permutation P, which operates on a vector .
P can be made up of n transpositions, . Each transposition
exchanges some arbitrary element
with the element
, where
. So we can totally describe
by the integer
. Thus we can describe P by the integer vector
, where
.
Now we need to encode the vector into a single number. To do that we view
as digit i of a number p written in a base faculty notation:
This number p is unique for each possible permutation P so we could use this as index. There is a problem though: we would like the identity permutation to have index 0. So we define the index I of the permutation slightly differently:
I can easily calculate the from I:
('/' is integer division and '' calculates the remainder).
The algorithm to transform a point from the reference simplex of dimension n to the Kuhn0 simplex (as illustrated in the image) is as follows:
The reverse (from Kuhn0 to reference) is simple as well:
For arbitrary Kuhn simplices we have to take the permutation of that simplex into account. So to map from the reference simplex of n dimensions to the Kuhn simplex with the permutation P (which is described by the vector ) we do:
And or the reverse: