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
• 当达到顶级 Y 和顶级 X 时，它将从具有顶级 X 和顶级 Y ，对于仍然具有顶部 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

仅供引用，您正在寻找的形状称为凸包。这将有助于您搜索算法。