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

Question

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

例如:

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

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

---

是否有不使用 atan2 或ma​​th.h 中的其他函数的解决方案？

Answer 1

我建议您按极角对它们进行排序，但最好以凸多边形内部的一个点作为原点来进行排序。要得到这样的点，您可以只使用多边形的任何对角线的中点，例如 ( (x[0] + x[2])/2, (y[0]+y[2])/2 ).