ConvexHull seems to need ordered vertices.

Oct 26, 2015 at 10:03 AM
Hi All,

We would like to use your amazing library in our project, but when I use the convex hull algorithm with the following array of vertices (data1), the result is not what we expected (see attached image1).
 var data1 = new[]
            {
                new DefaultVertex() {Position = new double[] {6.12462612219888, -2.82012708039241, 54.7593677198152}},
                new DefaultVertex() {Position = new double[] {2.50985487378094, 1.89445238269812, 28.8316930270887}},
                new DefaultVertex() {Position = new double[] {3.93876828779782, -4.98474478287388, 56.9239854222967}},
                new DefaultVertex() {Position = new double[] {-8.7022901886211, -9.20874348983484, 39.9348888996217}},
                new DefaultVertex() {Position = new double[] {1.75291045339676, -7.14936248535535, 59.0886031247781}},
                new DefaultVertex() {Position = new double[] {-19.9144352510231, -20.3119393623678, 51.0380847721547}},
                new DefaultVertex() {Position = new double[] {4.81414216559895, -8.69499738277009, 60.6342380221929}},
                new DefaultVertex() {Position = new double[] {-4.21214506240203, -28.2401231676396, 58.9662685774264}},
                new DefaultVertex() {Position = new double[] {7.87537387780114, -10.2406322801848, 62.1798729196076}},
                new DefaultVertex() {Position = new double[] {11.4901451262191, -36.1683069729113, 66.8944523826982}},
                new DefaultVertex() {Position = new double[] {10.0612317122022, -8.07601457770335, 60.0152552171261}},
                new DefaultVertex() {Position = new double[] {22.7022901886211, -25.0651111003783, 55.7912565101652}},
                new DefaultVertex() {Position = new double[] {12.2470895466033, -5.91139687522187, 57.8506375146446}},
                new DefaultVertex() {Position = new double[] {33.9144352510232, -13.9619152278454, 44.6880606376322}},
                new DefaultVertex() {Position = new double[] {9.18585783440108, -4.36576197780714, 56.3050026172299}},
                new DefaultVertex() {Position = new double[] {18.2121450624021, -6.03373142257363, 36.7598768323604}},

            };

            ConvexHull<DefaultVertex, DefaultConvexFace<DefaultVertex>> ch = ConvexHull.Create<DefaultVertex>(data1);
But if we order the array in this way(ordered by z values), the result is correct (see data2 and attached image2).
 var data2 = new[]
            {
                new DefaultVertex() {Position = new double[] {2.50985487378094, 1.89445238269812, 28.8316930270887}},
                new DefaultVertex() {Position = new double[] {18.2121450624021, -6.03373142257363, 36.7598768323604}},
                new DefaultVertex() {Position = new double[] {-8.7022901886211, -9.20874348983484, 39.9348888996217}},
                new DefaultVertex() {Position = new double[] {33.9144352510232, -13.9619152278454, 44.6880606376322}},
                new DefaultVertex() {Position = new double[] {-19.9144352510231, -20.3119393623678, 51.0380847721547}},
                new DefaultVertex() {Position = new double[] {6.12462612219888, -2.82012708039241, 54.7593677198152}},
                new DefaultVertex() {Position = new double[] {22.7022901886211, -25.0651111003783, 55.7912565101652}},
                new DefaultVertex() {Position = new double[] {9.18585783440108, -4.36576197780714, 56.3050026172299}},
                new DefaultVertex() {Position = new double[] {3.93876828779782, -4.98474478287388, 56.9239854222967}},
                new DefaultVertex() {Position = new double[] {12.2470895466033, -5.91139687522187, 57.8506375146446}},
                new DefaultVertex() {Position = new double[] {-4.21214506240203, -28.2401231676396, 58.9662685774264}},
                new DefaultVertex() {Position = new double[] {1.75291045339676, -7.14936248535535, 59.0886031247781}},
                new DefaultVertex() {Position = new double[] {10.0612317122022, -8.07601457770335, 60.0152552171261}},
                new DefaultVertex() {Position = new double[] {4.81414216559895, -8.69499738277009, 60.6342380221929}},
                new DefaultVertex() {Position = new double[] {7.87537387780114, -10.2406322801848, 62.1798729196076}},
                new DefaultVertex() {Position = new double[] {11.4901451262191, -36.1683069729113, 66.8944523826982}},
            };
            ConvexHull<DefaultVertex, DefaultConvexFace<DefaultVertex>> ch = ConvexHull.Create<DefaultVertex>(data2);
What can be the issue?

Needs The algorithm to a particular ordered array? What can we do to let the algorithm works also with the first unordered array data1?

Thanks to everyone for the help and the attention.

Image1:
Image1

Image2:
Image2
Oct 28, 2015 at 10:25 AM
Edited Oct 28, 2015 at 10:25 AM
We found that the problem is with coplanar points, and we resolved it by adding perturbation values to the points.

Thanks and Best regards.
Developer
Oct 29, 2015 at 3:53 PM
Hi Melissa,

yes, the problem is indeed with the coplanar points.

David
Nov 2, 2015 at 8:06 AM
Hi David,

Maybe there is the same problem in 2D with the algorithm?
I explain myself better: if I have a list of 2D point along a Rectangle (so there are collinear outer points), can the algorithm have the same problem?

Thanks,
Melissa
Developer
Nov 4, 2015 at 6:39 PM
The algorithm is the same for all dimensions (the original version had a specialized algorithm for 2D hulls but that has been replaced). Each time there are co-linear vertices (or also vertices that lie on a sphere in case of triangulation -- because in that case the triangulation might not be unique) it gets a bit tricky. The safest bet seems to be to use the small perturbations which should solve the problem in most cases.

You can also try to write some post processing routines of your own. For example, remove a vertex from the hull if it lies on a plane (line/plane/hyperplane) defined by its neighbor vertices. This is very straightforward in 2D, but can get a bit tricky in higher dimensions.

(There is also the possibility that I'm simply ignorant of some elegant method to solve this problem that would also work in the general n-dimensional case and as such would be a good fit to include in the library)
Nov 5, 2015 at 11:52 AM
Thanks for the explanation.
Have a nice day.

Best Regards,
Melissa