Polygon Sponsor
|
Voronoi Predicates
In mathematical theory predicate is an operator which returns true
or false (e.g. it may answer a question: "is it sunny today?").
Voronoi predicates contain implementation of a set of the geometric
predicates used by the Voronoi builder.
Except of those they also provide
functors that allow to compute the coordinates of the centers of the
inscribed
circles (those correspond to the Voronoi vertices) within the given
relative error precision range (64 machine epsilons). This means that
the more mantissa bits
your floating point type has the better precision of the output
geometries you'll get. This
is a very handy functionality as it allows to improve output precision
simply providing 3rd party IEEE-754 like floating-point types.
Geometric Predicates
The main issues with the implementation of any complex geometric
algorithm arise when dealing with the robustness of the geometric
predicates.
Usually this
is also the point where the commercial projects stand strong against
noncommercial implementations (it's not the case with our
implementation).
For the short example let's consider the following code snippet, that
could
be used to compute orientation of the three points:
double
cross_product(double dx1, double dy1, double dx2, double dy2) {
return dx1 * dy2 - dx2 * dy1;
}
int main() {
int v = 1 << 30; // 2 ^ 30
double result = cross_product(v, v - 1, v + 1,
v);
printf("%.3f", result);
return 0;
}
The
output of this simple program will be "0.000", while
the correct one is "1.000". In terms of the orientation test this means
that points are collinear instead of being CCW oriented. This is one of
the basic predicates used in any geometric algorithm and taking wrong
output from it may influence the further algorithm execution:
corrupting algorithm underlying structures or producing completely
invalid output. Voronoi uses
slightly more complex predicates. To insure that they are robust and
efficient the approach that combines two known techniques (lazy
arithmetic and multiple
precision computations) is used.
Lazy Arithmetic
Lazy
arithmetic is based on the usage of IEEE-754 floating-point types to
quickly evaluate the result of the expression. While this approach has
a good speed
performance it doesn't produce reliable results all the time (as in the
example above). The way to solve the issue is apart from computing
result of the expression compute the relative error of it as well. This
will
give us the range of values the evaluated result belongs to and based
on that we can
come up with two decisions: 1) output the value; 2) recompute the
expression using multiprecision type. The way relative errors are
evaluated is explained in the Voronoi
Robust FPT section.
Multiple Precision Arithmetic
In the vast majority of cases
the lazy arithmetic approach produces correct result thus further
processing is not required. In other cases the Voronoi library defined
or user
provided multiple precision types are used to produce correct result.
However even that doesn't solve all the cases. Multiprecision geometric
predicates could be divided onto two categories:
1) mathematical transformation of the predicate exists that evaluates
the exact result:
Predicate: A/B + C/D ?< 0;
After math. transform: (A*D + B*C) / (B * D) ?< 0;
Predicate: sqrt(A) ?< 1.2;
After math. transform: A ?< 1.44;
2) the correct result could be produced only by increasing
precision of the multiprecision type and with defined relative error
for the output type:
Predicate:
sqrt(A) + sqrt(B) + sqrt(C) + sqrt(D) + sqrt(E) ?< 1.2;
Imagine that value of the expression to the left is very close to 1.2;
Predicate:
sin(x) ?< 0.57;
Relative error of sin function should be known;
The Voronoi of points could be completely
implemented using predicates of the first type, however the Voronoi of
segments could not.
The predicate that doesn't fall into the first category is responsible
for comparison of the Voronoi circle events. However it appears that
properly used
this predicate can't corrupt algorithm internal structures and produces
output technically the same as produced in case this predicate fell in
the first category. The main reasons for this are: 1) algorithm
operates with integer coordinate type of the input geometries; 2)
closely
situated Voronoi vertices are considered to be the same in the output
data structure (this won't influence main targets algorithm is used
for).
|