Как связать четыре точки с выпуклым многоугольником

Question

Как связать четыре точки с выпуклым многоугольником? Я имею в виду, как определить порядок этих четырех точек.

Спасибо.

Zhong

Answer 1

Возьмите центральную точку (т.е. среднее из координат x и y), затем вычислите значения x / y для y<centery, затем для y>=centery.Я думаю, что это будет быстрее всего.

(то есть, если бы я понял вопрос в первую очередь ...)

Answer 2

Сортируйте их по вертикали, соедините 2 верхних друг с другом и два нижних друг с другом.
Сортируйте по горизонтали и затем соедините 2 крайних слева друг с другом и два крайних справа друг от друга.Прикольный связанный раздел SO справа предлагает ответный дубликат: Сортировка четырех точек по часовой стрелке

Answer 3

Метод atan2 () удобен для этого и встречается в большинстве языков.

atan2(y,x) и преобразует прямоугольные координаты (x,y) в угол theta изполярные координаты (r,theta).

Учитывая 4 балла, найдите их среднее значение.Затем вычислите четыре (x, y) вектора, полученные путем вычитания среднего значения из каждой из четырех точек.

Для каждого из этих (x, y) векторов рассчитайте угол θ = atan2 (y, x),θ будет между -π / 2 и π / 2.

Сортировка θ.Это даст вам порядок точек по часовой стрелке.

Это работает только для выпуклых четырехугольников.