3d cube, strange CreateDelaunay behavior.

[vgdh]

I tried to do triangulation of 3d cube.

            List<IVertex> vertices = new List<IVertex>();

            vertices.Add(new Vertex(-10, -10, -10));
            vertices.Add(new Vertex(10, -10, -10));
            vertices.Add(new Vertex(-10, 10, -10));
            vertices.Add(new Vertex(10, 10, -10));

            vertices.Add(new Vertex(-10, -10, 10));
            vertices.Add(new Vertex(10, -10, 10));
            vertices.Add(new Vertex(-10, 10, 10));
            vertices.Add(new Vertex(10, 10, 10));

            var result = Triangulation.CreateDelaunay<IVertex>(vertices).Cells;

but get en exception "Failed to find initial simplex shape with non-zero volume. While data appears to be in 4 dimensions, the data is all co-planar (or collinear, co-hyperplanar) and is representable by fewer dimensions." It's pretty simple triangulation, but why it failed? When triangulating a cube, you should get 5 or 6 triangles.

Then i was changed one vertex coordinate (-10, -10, -10) to (-10, -10, -9) . And it worked, but. It get one additional squre shape cell,

But i got six triangle, and one square, i'm confused. When triangulating a cube, you should get 5 or 6 triangles.

Shape1:
10 : 10 : 10
10 : -10 : -10
10 : 10 : -10
-10 : -10 : -9
Shape2:
10 : 10 : 10
-10 : 10 : -10
-10 : 10 : 10
-10 : -10 : -9
Shape3:
10 : 10 : 10
-10 : -10 : 10
10 : -10 : 10
-10 : -10 : -9
Shape4:
-10 : -10 : -9
-10 : 10 : -10
10 : 10 : -10
10 : 10 : 10
Shape5:
-10 : -10 : -9
10 : -10 : -10
10 : -10 : 10
10 : 10 : 10
Shape6:
-10 : -10 : -9
-10 : -10 : 10
-10 : 10 : 10
10 : 10 : 10
Shape7:
10 : 10 : -10
10 : -10 : -10
-10 : 10 : -10
-10 : -10 : -9

I tried rectangular parallelepiped and get similar result

AssemblyVersion: 1.1.19.1018

[robkite]

I've run into the same issue of a ConvexHullGenerationException being thrown by the FindInitialPoints() method. It can be replicated in a simpler form as well, for example a simple 2D square will result in the same issue:

[0, 0]
[1, 0]
[1, 1]
[0, 1]

It appears this behaviour was caused by this PR: https://github.com/DesignEngrLab/MIConvexHull/pull/34

The issue exists in 1.1.19.927 onwards - 1.1.19.920 is the last version where the exception is not thrown, and the delaunay triangles are returned.

Someone will have to unravel the change to understand exactly where it is going wrong in these cases - hopefully @micampbell may be able to review this at some point if he has time.