
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:
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.



Hi Melissa,
yes, the problem is indeed with the coplanar points.
David



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



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 colinear 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 ndimensional case and as such would be a good fit to include in the library)



Thanks for the explanation.
Have a nice day.
Best Regards,
Melissa

