Voronoi Diagram
Construction of Falloff curves Method 1:
I haven't done extensive research on this one. Although the straightforward aspects of the algorithm involve a distance metric comparison between a chosen point and all nodes. We take the minimum value to determine which voronoi cell the point occupies. An added problem, however, comes by way of creating fall off gradients relative to a given position inside such cell. One approach that I can think of involves construction of all node cell voronoi polygons. The simplest algorithm in this case, constructs the polygon by measuring the distance to all possible node cell boundaries firstly where there are two possibilities in defining such boundary:
1. The boundary is a inter nodal one.
2. The boundary is a nodal to voronoi edge boundary.
If it is case 2 then it is either horizontal or vertical line which can easily be formulated.
If it is case 1, then we can determine a point on such cell boundary line, but taking 1/2 the distance between both such nodes.
Now given a permutation test in determining the possible inter nodal configurations defining our voronoi cell boundaries, we'd need to isolate those nodes that do form the sides of the polygon versus those that don't by a set inclusion test. In this case, we know that any point on a orthogonal line relative to the polygon side, should either lay in either corresponding voronoi node cell. Thus we construct the line at a position defined 1/2 the distance between both such nodes. We compute the orthogonal direction vectors in opposite directions, and ray cast these while performing a path orthogonal test in small increments. The path orthogonal test casts a ray in the same direction as the original inter node direction vector, and chooses incrementally a neighboring point very small in distance to determine whether it lay in either voronoi cell, if it doesn't we don't discard the line, but we discard its inclusion at such point as a voronoi cell edge boundary between both such nodes. However, where such test passes indicates the edge of such voronoi cell edge boundary. The test is complete on such potential edge when at the intercept of the Voronoi system in either direction, or we could make use of any added assumptions for testing? We might be able to speed computational processes for instance, by discarding any number of nodes, for instance, that should have extremely low probability for passing such test?
Once having in theory formulated the polygons of all nodes, we can commence the procedure of fall off by relating in some way a parametric distance for all such interior points by using a distance metric which relates a relative distance boundary, for instance, we might re scale the geometry of all points on the polygon of such cell and center this a its given point of local origin (see centroid computation).
The following diagram illustrates a principle in height map scaling. Implementation from this diagram generalized would mean that all voronoi cell n-gon s need be divided in n distinct sub regions for example. Each subregion would be classed according to a scale parameter where all points falling in such sub region are re scaled by such parameter. In this case, we'd measure the point relative to its nearest cell edge distance, and then divide this distance measure by the scaling parameter which is depicted below. This would require a centroid computation.
Alternate method idea:
Involves not only determining the nearest node for voronoi cell occupancy, but also determines the second nearest node neighbor, and test eliminates that a Voronoi system edge is not occurring (that is, that the point is actually closest to the horizontal or vertical lines of the entire Voronoi system). With this test we construct as in the previous algorithm method construct a orthogonal line and test for either a two line intersection: one line determined by the node 1 and the point that occupies the node 1's cell, and the line given by the defined voronoi edge, or in local rotated coordinates where relative x is given in the positive direction to node 2 where node 1 is the point of origin, use a least distance algorithm from the point to such inter node edge boundary. Now we have a distance metric relative to the given normal of such line. If we have the assumption, that our falloff is scaled in relatively equal distance relative to such boundary, then with a supplied falloff distance parameter we can compute the relative position of such point inside such fall off interior, likely we'd want this parameterized between 0 and 1.
For a given falloff regardless we can use a curve say between 0,0 and 1,1 and given by a parametric function of t between 0 and 1.
The first method above appears at least (without testing) more computationally intensive while the second method is arguably cheaper.
Implicit assumptions are that voronoi cells are defined by linear edges, and are also given to a midpoint rule on the line defined between any two nodes and the point of intercept for such a line defining a potential edge between both such nodes. A furthered assumption is such that any line defining any edge boundary between voronoi cells is orthogonal relative to the direction vector between such node pairs. This last assumption is implicit to the consequence of the equality of any point on such line being equi distant relative to either node and because of right triangles using pythagorean theorem. Obviously if a right triangle were neither given then a distance metric between either node to such point would no longer be equidistant.
Advanced Voronoi implementation ideas:
If you want to get fancy you can use a favorite interpolating method for the polygon which smooths the cells into continuous curves. For cell approximation we can otherwise use the polygon for points being set included, but we define a falloff of the cell by the interpolated edge boundaries. In the case for method 2 above, you'd need to determine the least distance between such cell edge boundary and its interpolated curve (this would be a non linear equation)....this minimum distance problem can be solved using the distance function with the interpolated function substituted into such equation. As it turns out solving this problem also finds not only the least distance between a point and curve, but also is along the orthogonal direction to such curve at the point of intercept. However, the problem say with interpolation that exists on this is that analysis requires (as in the spline case) a routine which checks minimum distance for a family of generated curves on between a node cell edge set. The curve which returns the least distance to such point. One approximating method starts with something like a numerical test approach where a given curve in such family is honed in on by distance testing.
Also consider something like constraining a randomized path finding process along the voronoi cell boundaries so that the ridge of the voronoi cell hadn't appeared so regularly linear.
I also imagined parameterizing a point where the falloff is given by a radial relation between the node to point to edge boundary where parameter values fall between 0 and 1 for such distance which is very easy to implement.
Other alogorithmic idea could extend this by say using instead of radial parameterizing methods, elliptic ones, and so forth.
Some implementation notes:
Worked on several different approaches here. One height map generator works on the building fixed plateau heights for each cell. Very very simple. The easiest to code, and the quickest implementing real time.
Another took an algebraic solutions approach for parameterizing the distance from a voronoi cell edge. This as mentioned above. I hadn't debugged this fully.
Another approach used a vector algebra approach. Another website posted a solution to this. I can describe this however, in brief. Basically this approach utilizes several vectors in the solution process. What mathematically is desired at the end of such process is a distance from any given position relative to a closest voronoi cell edge boundary. From this distance we can parameterize our heightmap.
The vector algebra works as follows:
Let the nearest voronoi node (that our point occupies) be node 1.
Let the second nearest voronoi node be node 2.
And let N1 and N2 represent the position vectors of node 1 and 2 respectively.
The distance vector to our position is given by P.
Then we need compute the vector from N1 to N2. This is according to vector algebra
vecN1toN2 = N2-N1
and the vector from P to N2 is given by
vecPtoN2 = N2-P
Now we know (as explained above) that the midpoint of vecN1toN2 represents a position on the voronoi cell boundary edge which is also closest to P. This is very important since with this point if we can find a vector from P to such point then we can compute the projected distance from P to such voronoi cell boundary edge with a well known projection of vectors formula. This vector, however is given since we know the vector from P to N2 (given above) and since we can move from N2 to this midpoint by
- 1/2 * vecN1toN2
this is a vector 1/2 the magnitude of the vecN1toN2 and in the direction from N2 to N1.
So if we placed this vector starting at N2 it would move to N1 and land on our midpoint position.
the resultant vector
vecPtoMid = vecPtoN2-1/2*vecN1toN2
the resultant vector is a vector that goes from P to the Mid Point on the Voronoi Cell edge boundary.
Now we need a unit vector in the direction of vecN1toN2 since our projection formula requires us to have such vector in this direction in order to work. We also know this is the shortest possible distance, since the shortest distance is not only linear but a vector whose direction is orthogonal to the line that we desire to intercept. We know that vecN1toN2 is orthogonal to such line by virtue of the Voronoi diagram design and the distance metrics used in constructing such.
So the unit vector is 1/(dot product (vecN1toN2,vecN1toN2))^1/2 * vecN1toN2
noting that we are computing the magnitude of vecN1toN2 by the way and multiplying this scalar to the vector itself.
So the projection formula then is given by
|dotproduct(vecPtoMid,1/(dot product (vecN1toN2,vecN1toN2))^1/2 * vecN1toN2)|
and that is it for the distance. When you are wanting to project to the nearest point on any line from some arbitrary point separated from such line. In order to find such distance, it is important to find a vector from such point to the line. Any vector that intersects with such line will do and can be applied to the projection formulation given by dot products.
Lastly I also worked on a raytrace method, which generally is slow cumbersome, and much worse for computations.
As a mention, fall off parameterization say from [0,1] for a parameter t is a bit more tricky then I had previously considered. One being that rescaling points seem to lead to some oddness graphically speaking, for instance, if using the node and a total length from position to voronoi node cell edge radially (that is, using a bit of trig or algebra to find from say the shortest distance to such line the intercept of the lines generated from vectors vecN1toN2 with vecN1toP)...I am not certain if this were related to curve discontinuities in scaling the falloff (namely where the vornoi cell edges meet another voronoi cell edge) here left and right approach derivatives of the such edges are different which could be part of the problem here (if you used some parameteric or sampled curve that were smooth and continuous through these positions, likely this would resolve the scaling problem here, but then you'd need to contend with the problem of finding the shortest distance to a curve...which has algebraic and vector related solutions as well).
Added reads for today would include
Delaunay triangulation and algorithms for computing the Delaunay triangle circumcenter using the
circumcircle of a triangle. The link at wolfram alpha provides excellent referring information This algorithm comes by way of a
cofactors decomposition of the 4x4 determinant matrix given at the circumcircle link provided above. Basically information provided about the circle which pin points the vertices of the voronoi cell polygons is yielded from these cofactor computations. If you were asking the question on why to do this? This leads into another algorithm called
Lloyd's algorithm which in the iterative sense leads to a relaxation in the spacing between Voronoi nodes. The idea being here to reduce the number of oddly shaped and disproportionately small triangles in the diagram with more average fitting shapes (still random but containing less spatial deviation). Centrally this method likely relies upon computation of the voronoi polygon and then having computed it's
centroid, and then having in an given iterative cycle transposed the position of the node to its centroid (or retranslating the position). As one can could guess constructing the polygon is more than understanding the relevant relations from node to node in the most primitive sense.
Fortune's algorithm is also another computational method for generating the diagram, but given in a different manner. As indicated at the wikipedia link this method relies upon a 'sweep line' which forms the basis for parabolically tracing the edges of the graph. Here's another another link to an excellent article from the American Mathematical Society titled
Voronoi diagrams and a Day at the Beach that provides much further in depth explanation as to the algorithms workings.
Here's some added descriptions for thought on the Fortune Algorithm that posits some additional details outside of the highly generalized description:
In case you might have wondered at the construction of the parabolas...it appears this relies upon on old geometric construction. Namely, we use the node as a focus and the sweep line as a directrix. In this case the parabola consists of all points that are equal in distance to the node and the sweep line respectively. Thus, this equality in distances describes the set of points on the parabola. The algorithm itself is an iterated method that relies upon a dynamically changing set of points to the main sweep line iterator. As a node is added called a 'site' we track its parabola, but also check for an event called the 'circle event'. This occurs when three parabolas are parent child nested on a binary tree, or you can think of this event as graphically depicted as three parabolas stacked on one another. Where two parabolas are stacked as children on top of a base parent parabola. The algorithm also tracks the convergence point of two parabolas which is called the breakpoint. Where breakpoints are initiated and where the two parabolas intersect as the sweep line progresses determines the edge. Upon initialization of say two parabolas, for instance, with a child stack on a parent means we measure the parabola two different intersecting positions (namely where the child parabola meets the parent on both such points on the parent curve). You might find
this useful as nice reference for understanding the construction of the parabola. Thus in where ever we have incremented the sweep line and in so having verified the existence of a two parabola parent child stack we can trace the break point by use of relations given of parabolas. For instance, this equation is given by 4*p *(y-k) = (h-k)^2. where p is the distance from the point on the parabola and a point on the parabola is given by (h,k), but we also know that the distance at such a minimum point on the parabola is equal distance between the node and sweep line. Thus we have a point on the parabola determined and so to p. Thus an equation for an parabola when advancing the position of the sweep line to a node or computed circle event. For computing the circle event you can use for instance, the link above for instance, that uses cofactors computation to determine the circumcircle for the delaunay triangle, we do the precomputation for determining the position of the circle even using this algorithm, knowing the sufficiency being met for criteria existence of the circle event which is the three parabola nesting criteria. This circle event determines a vertex and thus a closure to the edge initialized from a breakpoint, all this describing the edge boundary of a voronoi cell. Thus as the sweep line is advanced to either a node or circle event, we are constantly determining new edges or closing old edges. We'd keep in mind o(n log n) computations factor being nice relative to other brute force computational methods, since the sweep line is advanced in relation to the n points plus whatever circle events that are directly perceived by the algorithm...thus avoiding for instance brute force and blind permutation testing on the set of nodes, say for delaunay triangles.
