This project is read-only.

Sorting the points in the convexhull

Apr 2, 2013 at 12:32 PM
Hi the library looks great,

I am using the following sample:

http://stackoverflow.com/questions/10020949/gift-wrapping-algorithm

But in some case it's infinite loop. I managed to reproduce the case and now I wanted to change to your library. The algorithm works perfect but in the end I come up with disordered points. When I put all points in Polyline in WPF they should be in the correct order to draw a contour without lines inside the contour. You can see from the screenshot that the points are not ordered correctly.

Image

See the example code bellow:
    var vertices = new Vertex[points.Count];

            for (var i = 0; i < points.Count; i++)
            {
                vertices[i] = new Vertex(points[i].X, points[i].Y);
            }

            var convexHull = MIConvexHull.ConvexHull.Create(vertices);

        

            var poly = DrawContour(convexHull.Points.ToList());

            Canvas1.Children.Add(poly);

        }

        private Polyline DrawContour(List<Point> points)
        {
            Polyline polyVisual = new Polyline();

            polyVisual.Stroke = new SolidColorBrush(Colors.Red);
            polyVisual.StrokeThickness = 1;
            polyVisual.HorizontalAlignment = HorizontalAlignment.Left;
            polyVisual.VerticalAlignment = VerticalAlignment.Center;

            for (int i = 0; i < points.Count; i++)
            {

                polyVisual.Points.Add(points[i]);
            }

            return polyVisual;
        }
Apr 2, 2013 at 12:56 PM
Apr 10, 2013 at 9:35 PM
Okay, I'm looking into this one now. Sorry for the delay.
Apr 12, 2013 at 11:31 PM
Edited Apr 12, 2013 at 11:38 PM
The points are not sorted because in the general n-dimensional case there is no notion of sorting the points clock- or counterclock-wise.

The sorting in the 2D case can be done easily using the ConvexHull.Faces field. What you do is to start with the first face and then traverse all of them using the Adjacency.

The code should look along these lines:
var pivot = faces[0];
var sortedPoints = { pivot.Vertices[0] };
var previous = pivot;
var current = pivot.Adjacency[0];
while (current != pivot)
{
  if (current.Vertices[0] == previous.Vertices[1]) 
  { 
    sortedPoints.Add(current.Vertices[0]); 
    current = current.Adjacency[0]; 
  }
  else 
  { 
    sortedPoints.Add(current.Vertices[1]); 
    current = current.Adjacency[1]; 
  }
  previous = current;
}
EDIT: thinking about it, even a simple version that looks like this should work due to how the vertices are (should be :)) ordered inside the edges. Also I might have made a mistake in the adjacency indices. Tho it should be easy to figure out once you play with it.
var pivot = faces[0];
var sortedPoints = { pivot.Vertices[0] };
var current = pivot.Adjacency[0];
while (current != pivot)
{
  sortedPoints.Add(current.Vertices[0]); 
  current = current.Adjacency[0]; 
}
Apr 14, 2013 at 11:30 AM
Thanks, I will try it when I am back in the office :)
Aug 7, 2013 at 9:59 PM
Edited Aug 26, 2013 at 5:12 PM
Thanks for this suggestion. It is working for me, but for some sets of points it is failing. I think the issue may be with degeneracy in the input data (2D in this case).