C -凸多边形-排序点(顺时针)

Question

我有一个凸多边形用点表示。点由 x坐标数组和 y坐标数组表示。例如:

X = {6, 1, 5, 0, 3}
Y = {4, 0, 0, 4, 6}

我如何按顺时针排序这些点?点的数目并不总是相同的，但多边形仍然是凸的。

---

是否有一个解决方案不使用 atan2或其他函数从math.h?

Answer 1

我建议你按极角排序，但最好在凸多边形内部有一个点作为原点。为了得到这样一个点，你可以使用任意多边形对角线的中点，例如((x[0] + x[2])/2， (y[0]+y[2])/2)。

Answer 2

我想你可以把它们转换成极坐标。C有atan2，所以你可以用:

atan2(y[0], x[0]);

获得各自的角度后，可以使用它们对点进行排序。