This project is read-only.

Triangulation Error?

May 23, 2013 at 4:44 PM
Hi everybody,

I got a very strange behavior when using the Delaunay Triangulation. With the following code
   var data = new []
    {
        new DefaultVertex() {Position = new double[]{307.2758, 679.7065}},
        new DefaultVertex() {Position = new double[]{329.4038, 952.6477}},
        new DefaultVertex() {Position = new double[]{651.7878, 630.2637}},
        new DefaultVertex() {Position = new double[]{329.4038, 307.8797}},
        new DefaultVertex() {Position = new double[]{  7.0198, 630.2637}}
    };

var test = Triangulation.CreateDelaunay<DefaultVertex, DefaultTriangulationCell<DefaultVertex>>(data);
var triangles = test.Cells.ToArray();
I only get two triangles as a result. The last Point (7.0198, 630.2637) does not appear in either of the two. Strangely, if I strip all numbers behind the decimal point for all input data, I get four triangles. Can anybody confirm that?

Thanks for any hints,

Hendrik.
May 26, 2013 at 11:31 PM
Edited May 26, 2013 at 11:57 PM
Hi Hendrik,

the problem is floating point arithmetic/degeneracy of the input data. In order to compute the triangulation, the algorithm has to compute 3D convex hull of the points lifted on a paraboloid. After the hull is computed, the triangle normal vectors are used to determine which triangles to keep and which to throw away. Now, all the points except the "middle one" seem to lie on the same circle which means when they get lifted they lie on a plane. And thanks to a "random" rounding error it might happen that the normals point to the opposite direction than one might want it to (and thus the corresponding triangles get removed). When you remove the decimal part, the points no longer lie on a circle. Actually you don't even need to change all the points, all that's required is to change the last point for example to {7.0198, 630.2647} (ie .2637 -> .2647) and you get the correct result.

One way around this problem is to introduce some randomness to the input data:
Random rnd = new Random(0); // specify the seed to keep it deterministic
double r = 0.025;

class PerturbedVertex : IVertex
{
  public double[] OriginalPosition { get; private set; }
  public double[] Position { get; private set; }
  
  public PerturbedVertex(double[] position, Random rnd, double r)
  {
    OriginalPosition = position;
    Position = new double[] { position[0] + r * rnd.NextDouble(), position[1] + r * rnd.NextDouble() };
  }
}
Hope it helps.
May 27, 2013 at 9:48 AM
Hi,

thanks for your reply. Indeed, four of the input data points lie on a circle, which is no coincidence. ;-)
Good thing is that I can control the generation of these points, so I added a slight perturbation as proposed by you and now everything seems fine.

But just to be sure: Is this just a problem with the "outer" points? Or is it a general problem which also occurs if my input data contains any points lying on a circle (which are "surrounded" by some more points)?

Cheers,

Hendrik.
May 27, 2013 at 2:46 PM
The degeneracy problems might occur even for "inner" points.

Anyway, since you are only interested in 2D triangulation, there are other libraries/algorithms that do not (should not :)) suffer from this particular problem. For example http://www.s-hull.org/ seems like a viable alternative (I tested it on your data and it did produce 4 triangles). Or just check the Wikipedia article for Delaunay Triangulation -- there are more links.