c - C - 凸多边形 - 排序点（顺时针）

Question

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

例如：

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

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

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

score 3 · Accepted Answer

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

score 2 · Accepted Answer

我认为您可以通过将它们转换为极坐标来逃脱。C有atan2，所以你可以逃脱：

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

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

2 回答 2