This project is read-only.

Convex Hull of orthotope points in 5d

Mar 4, 2015 at 7:03 AM
Thank you for your nice implementation.
I've tried using MIConvexHull. However, I found a problem (not sure whether it is true).

I executed the convex hull algorithm on 2^5 points of an orthotope set of a point in 5d as follows:

0 0 0 0 0
10 0 0 0 0
0 10 0 0 0
10 10 0 0 0
0 0 10 0 0
10 0 10 0 0
0 10 10 0 0
10 10 10 0 0
0 0 0 10 0
10 0 0 10 0
0 10 0 10 0
10 10 0 10 0
0 0 10 10 0
10 0 10 10 0
0 10 10 10 0
10 10 10 10 0
0 0 0 0 10
10 0 0 0 10
0 10 0 0 10
10 10 0 0 10
0 0 10 0 10
10 0 10 0 10
0 10 10 0 10
10 10 10 0 10
0 0 0 10 10
10 0 0 10 10
0 10 0 10 10
10 10 0 10 10
0 0 10 10 10
10 0 10 10 10
0 10 10 10 10
10 10 10 10 10

6 vertices and 6 faces were given as the output. I tried printing out the normal vector of each face.
NaN NaN NaN NaN NaN ***
0.00 1.00 0.00 0.00 0.00
0.00 0.00 1.00 0.00 0.00
0.00 0.00 0.00 1.00 0.00
0.00 0.00 0.00 0.00 1.00
-0.45 -0.45 -0.45 -0.45 -0.45 ***

I doubt that why there is a face containing all NaN. Should it be (1,0,0,0,0) ?
And I can't imagine which face has the normal vector in the direction (-0.45 -0.45 -0.45 -0.45 -0.45). Did I misunderstand anything ?
Mar 4, 2015 at 10:25 AM
Hi,

Is the 4D version working as expected? If so, this is probably a bug/deficiency in the Gaussian elimination code in MathHelper.cs. For 2-4D an expanded formula is used to compute the normals, but for 5D and up involve solving a matrix. The problem is that the solver might not handle zero pivots correctly (0 at diagonal) which most likely occurs for your input data -> hence the NaN in the 1st vector. The last vector is probably caused by the NaN error introduced by the 1st one.

Anyway, I will have a look at it and see if this is really what's happening.

David
Mar 4, 2015 at 11:06 AM
Ok so the 4D version works correctly.

For the 5D version it worked when I used this config:
new ConvexHullComputationConfig 
{ 
  PointTranslationType = PointTranslationType.TranslateInternal, 
  PointTranslationGenerator = ConvexHullComputationConfig.RandomShiftByRadius() 
}
I have tried using LU solver from Math.net but it has similar issues to the I'm currently using (it doesn't do the NaN but it produces the "0.45" one).

I will to write a determinant based code for the normal computation (a generalizations of FindNormalVector4D in MathHelper.cs) but I don't know when I will get to that -- maybe soon :)
Mar 4, 2015 at 5:08 PM
Ok I think I've fixed the issue. Check the latest commit (2b75a8173e2e).
Mar 5, 2015 at 3:49 AM
Great! It works well.
I've learnt a lot from your code. Thank you very much for your work and your help.