wpf - 如何从一组无序点绘制多边形

Question

目前，我正在使用凸包算法从一组随机放置的点中获取最外层的点。我的目标是从凸包返回的一组点中绘制一个多边形，但是，当我尝试绘制多边形时，它看起来很奇怪。

我的问题，如何对点进行排序以便正确绘制多边形？

谢谢。

编辑：

另外，我尝试使用 orderby(...).ThenBy(...) 进行排序，但似乎无法正常工作。

Answer 1

您是否尝试过礼品包装算法（http://en.wikipedia.org/wiki/Gift_wrapping_algorithm）？这应该以正确的顺序返回点。

Answer 2

我遇到了一个问题，其中生成了一组随机点，其中一个包裹的高程向量需要一个基本轮廓。阅读了@user1149913 提供的链接并找到了一个礼品包装的样本 hull，以下是我的实现示例：

  private static PointCollection CalculateContour (List<Point> points) {
     // locate lower-leftmost point
     int hull = 0;
     int i;
     for (i = 1 ; i < points.Count ; i++) {
        if (ComparePoint(points[i], points[hull])) {
           hull = i;
        }
     }

     // wrap contour
     var outIndices = new int[points.Count];
     int endPt;
     i = 0;
     do {
        outIndices[i++] = hull;
        endPt = 0;
        for (int j = 1 ; j < points.Count ; j++)
           if (hull == endPt || IsLeft(points[hull], points[endPt], points[j]))
              endPt = j;
        hull = endPt;
     } while (endPt != outIndices[0]);

     // build countour points
     var contourPoints = new PointCollection(points.Capacity);
     int results = i;
     for (i = 0 ; i < results ; i++)
        contourPoints.Add(points[outIndices[i]]);
     return contourPoints;
  }

Answer 3

这不是一个完整的解决方案，而是一个正确方向的指南。我最近遇到了一个非常相似的问题，我发现一个带有答案的 reddit 帖子（https://www.reddit.com/r/DnDBehindTheScreen/comments/8efeta/a_random_star_chart_generator/dxvlsyt/ ）建议使用基本上返回一个在您拥有的数据点内制作所有可能三角形的解决方案。一旦你有了所有可能的三角形，根据定义，你知道不会在任何重叠线上产生，你可以选择你使用哪些线，在所有连接的节点上产生哪个结果。

我在 python 上编写我的解决方案，幸运的是，python 上有很多科学库。我正在研究一个随机的天空图生成器，它可以从这些星星中画出星座。为了获得所有可能的三角形（并绘制它们，只是为了好玩），在进入算法绘制实际星座之前，我所要做的就是：

    # 2D array of the coordinates of every star generated randomly before
    points = list(points_dict.keys())
        
    from scipy.spatial import Delaunay
    tri = Delaunay(points)
    
    # Draw the debug constellation with the full array of lines
    debug_constellation = Constellation(quadrants = quadrants, name_display_style = config.constellation_name_display_style)
    for star in available_stars:
        debug_constellation.add_star(star)
    for triangle in tri.simplices:
        star_ids = []
        for index in triangle:
            star_ids.append(points_dict[points[index]].id)
        debug_constellation.draw_segment(star_ids, is_closed = True)

    # Code to generate the image follows below

你可以在这里看到完整的实现：fake_sky_chart_generator/fake_libs/constellation_algorithms/delaunay.py

这是结果：