c# - 排序 PointF 数组

Question

任何人都可以帮助我创建一个算法、IComparer 或一些可以对数组或PointF元素列表进行排序的方法。假设我PointF的数组中有以下元素：

• [0] { X = 50.0 Y = 0.0}
• [1] { X = 100.0 Y = 100.0}
• [2] { X = 0.0 Y = 100.0}
• [3] { X = 100.0 Y = 0.0}
• [4] { X = 0.0 Y = 0.0}
• [5] { X = 100.0 Y = 50.0}
• [6] { X = 50.0 Y = 100.0}

我想要实现的是：

• 首先是Y和X最低的元素
• 仍然是 Y最低但X会变大的元素
• 然后，随着在这个最低Y处的最高可能X得到实现，所有具有此X的元素都会消失，但Y越来越大
• 随着 top Y和 top X的实现，它将从 top X和 top Y的元素到仍然 top Y的元素，但X越来越低

所以这个排序后的数组看起来像这样：

• [4] { X = 0.0 Y = 0.0}
• [0] { X = 50.0 Y = 0.0}
• [3] { X = 100.0 Y = 0.0}
• [5] { X = 100.0 Y = 50.0}
• [1] { X = 100.0 Y = 100.0}
• [6] { X = 50.0 Y = 100.0}
• [2] { X = 0.0 Y = 100.0}

意思是，最后，如果我要使用这些点来绘制这些点，Graphics.DrawPolygon()我会得到一个封闭的多边形（在这种情况下是一个矩形），没有线相互交叉。

感谢您的时间

Answer 1

您想要的算法是格雷厄姆扫描。你可以在这里读到它：

http://en.wikipedia.org/wiki/Graham_scan

juharr 的评论是正确的；您将无法做到这一点，IComparable因为这不是比较排序问题。要使比较排序起作用，您需要能够比较任意两个元素的相对大小。

一个更简单但更慢的算法是礼品包装算法：

http://en.wikipedia.org/wiki/Gift_wrapping_algorithm

仅供参考，您正在寻找的形状称为凸包。这将在搜索算法时为您提供帮助。