Draw polygon from unordered points

Question

So, I know that there are similar questions and I searched a lot before typing my code and asking this question.

In my case, the user clicks on a place on the screen to add a point. When the user finishes adding points, makes a right click to say that the points are ok and draw the polygon.

A the poins are irregularly placed, I must calculate the center point and the angle of each point to order the point list.

And then, when I move a point, I recalculate the angles with new positions and redraw the polygon.

It works but, when I move a point beyond two others beyond them, sometimes it doesn't draw the plygon. I couldn't find what is wrong.

here is my code and two images to explain the problem :

public class CustomPoint3D
{
    public double X { get; set; }
    public double Y { get; set; }
    public double Z { get; set; }
    public int Angle { get; set; }
    public CustomPoint3D()
    {

    }

    public CustomPoint3D(double x, double y, double z)
    {
        this.X = x;
        this.Y = y;
        this.Z = z;
    }
}



    private void AddZoneSurface(List<CustomPoint3D> customPoints, string guid)
    {

        //Calculates angles and orders / sorts the list of points
        List<Point2D> points = From3DTo2D(customPoints);

        //Draws a polygon in Eyeshot but it can be any tool to create a polygon.
        var polygon = devDept.Eyeshot.Entities.Region.CreatePolygon(points.ToArray());


        polygon.ColorMethod = colorMethodType.byEntity;
        polygon.EntityData = "tool-surface-" + guid;
        polygon.Color = System.Drawing.Color.FromArgb(80, 0, 0, 0);
        sceneLeft.Entities.Add(polygon);

       
        sceneLeft.Invalidate();
    }

    private List<Point2D> From3DTo2D(List<CustomPoint3D> points)
    {
        List<Point2D> retVal = new List<Point2D>();
        var minX = points.Min(ro => ro.X);
        var maxX = points.Max(ro => ro.X);
        var minY = points.Min(ro => ro.Y);
        var maxY = points.Max(ro => ro.Y);

        var center = new CustomPoint3D()
        {
            X = minX + (maxX - minX) / 2,
            Y = minY + (maxY - minY) / 2
        };

        // precalculate the angles of each point to avoid multiple calculations on sort
        for (var i = 0; i < points.Count; i++)
        {
            points[i].Angle = (int)(Math.Acos((points[i].X - center.X) / lineDistance(center, points[i])));

            if (points[i].Y > center.Y)
            {
                points[i].Angle = (int)(Math.PI + Math.PI - points[i].Angle);
            }
        }
        //points.Sort((a, b) => a.Angle - b.Angle);
        points = points.OrderBy(ro => ro.Angle).ToList();
        foreach (var item in points)
        {
            retVal.Add(new Point2D() { X = item.X, Y = item.Y });
        }
        return retVal;
    }


    double lineDistance(CustomPoint3D point1, CustomPoint3D point2)
    {
        double xs = 0;
        double ys = 0;

        xs = point2.X - point1.X;
        xs = xs * xs;

        ys = point2.Y - point1.Y;
        ys = ys * ys;

        return Math.Sqrt(xs + ys);
    }

On the first images, I move the point from its initial position to the indicated position, it doesn't draw the polygon.

Answer 1

So if someone needs a sample which works, I found the problem. I should have declared the angle property of th CustomPoint3D object like this As the property was integer, an angle 0,3 or 0,99 was giving 0 as angle.

 public class CustomPoint3D
 {
  public double X { get; set; }
  public double Y { get; set; }
  public double Z { get; set; }
  public double Angle { get; set; }
  public CustomPoint3D()
 {

}

  public CustomPoint3D(double x, double y, double z)
  {
    this.X = x;
    this.Y = y;
    this.Z = z;
  }
}

and calculate this values as double

     private List<Point2D> From3DTo2D(List<CustomPoint3D> points)
{
    List<Point2D> retVal = new List<Point2D>();
    var minX = points.Min(ro => ro.X);
    var maxX = points.Max(ro => ro.X);
    var minY = points.Min(ro => ro.Y);
    var maxY = points.Max(ro => ro.Y);

    var center = new CustomPoint3D()
    {
        X = minX + (maxX - minX) / 2,
        Y = minY + (maxY - minY) / 2
    };

    // precalculate the angles of each point to avoid multiple calculations on sort
    for (var i = 0; i < points.Count; i++)
    {
        points[i].Angle = Math.Acos((points[i].X - center.X) / lineDistance(center, points[i]));

        if (points[i].Y > center.Y)
        {
            points[i].Angle = Math.PI + Math.PI - points[i].Angle;
        }
    }
    //points.Sort((a, b) => a.Angle - b.Angle);
    points = points.OrderBy(ro => ro.Angle).ToList();
    foreach (var item in points)
    {
        retVal.Add(new Point2D() { X = item.X, Y = item.Y });
    }
    return retVal;
}

And 

Answer 2

You should read the Wikipedia page on convex hull algorithms and pick an algorithm that you feel comfortable implementing that also meets your O(n) complexity requirements.

If convex hull isn't what you're after then you'll need to be a bit more specific as to how you want the points to define the shape. One (probably sub-optimal) solution would be to calculate the convex hull, find the center, pick a point as your "start" point and then order the remaining points by angle from the start point.