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]);

После того, как вы получите соответствующие углы, вы можете использовать их для сортировки точек.