从无序点绘制多边形

Question

所以，我知道有类似的问题，在输入我的代码并提出这个问题之前我进行了很多搜索。

在我的例子中，用户点击屏幕上的一个地方来添加一个点。当用户完成添加点后，右击表示点已确定并绘制多边形。

A点不规则放置，我必须计算中心点和每个点的角度才能对点列表进行排序。

然后，当我移动一个点时，我会重新计算新位置的角度并重新绘制多边形。

它可以工作，但是，当我将一个点移到另外两个点之外时，有时它不会绘制多边形。我找不到问题所在。

这是我的代码和两张图片来解释问题：

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);
    }

在第一张图片上，我将点从它的初始位置移动到指定位置，它没有绘制多边形。

Answer 1

您应该阅读 the Wikipedia page on convex hull algorithms 并选择一个您觉得可以轻松实现并且也满足您的 O(n) 复杂度要求的算法。

如果凸包不是您想要的，那么您需要更具体地说明您希望这些点如何定义形状。一种（可能 sub-optimal）解决方案是计算凸包，find the center，选择一个点作为“起点”，然后从起点开始按角度对剩余点进行排序。

Answer 2

所以如果有人需要一个有效的样本，我就发现了问题所在。我应该像这样声明 CustomPoint3D 对象的角度属性由于属性是整数，因此角度 0,3 或 0,99 给出 0 作为角度。

 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;
  }
}

并将此值计算为双倍

     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

从无序点绘制多边形

Draw polygon from unordered points

c#

wpf

computational-geometry

eyeshot