对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

仅供参考,您正在寻找的形状称为凸壳.这将有助于您搜索算法.