DesignEngrLab / MIConvexHull

A .Net fast convex hull library for 2, 3, and higher dimensions.
http://designengrlab.github.io/MIConvexHull/
MIT License
338 stars 60 forks source link

Fixes #18 missing/duplicate face in 2D convex hull #20

Closed ericgarza70 closed 6 years ago

ericgarza70 commented 6 years ago

fixes #18, faces[1] was being duplicated because orderedFaceList was not initialized with the first face and the loop starts processing the second face.

MichaWiedenmann commented 6 years ago

I have had the same problem and arrived at the same conclusion: orderedFaceList must be initialized with faces[0] instead of faces[1].

In the following test case you can see that the last face is missing and the first face is duplicated:

var data = new List<double[]> { new double[] { 0, 0 }, new double[] { 1, 0 }, new double[] { 0, 1 }};
var hull = MIConvexHull.ConvexHull.Create(data);

var actual = hull.Faces.Select(f => ((f.Vertices[0].Position[0], f.Vertices[0].Position[1]), (f.Vertices[1].Position[0], f.Vertices[1].Position[1]), (f.Normal[0], f.Normal[1])));
var current = new((double, double), (double, double), (double, double))[] {
    // V[0], V[1],   Normal
    ((0, 0), (0, 1), (-1, 0)),
    ((1, 0), (0, 0), (0, -1)),
    ((0, 0), (0, 1), (-1, 0)),
    // the last line is wrong and should be instead
    // ((0, 1), (1, 0), (0.70710678118654746d, 0.70710678118654746d)),
};
MichaWiedenmann commented 6 years ago

Your fix resolves #18, you should probably put that in the body of your pull request (see Closing Issues via Pull Requests.