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).
 
Copyright: Copyright © Andrii Sydorchuk 2010-2012.
License: Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)