Алгоритм для объединения 4 координат, так что он всегда приводит к четырехстороннему

Question

Нам даны координаты 4 точек на 2D-плоскости. Как мы можем найти заказ, чтобы присоединиться к ним с линиями, чтобы сформировать quadilateral (когда это возможно)?

Answer 1

несколько этапов, предполагая, что конечный результат должен быть 4 пары точек (и/или уравнения линии между ними):

1. Возьмите любые три точки, и сделать треугольник.
2. Если четвертый пункт находится внутри трейлинга, поменяйте его на ny из трех.
3. Имея только последнюю точку слева, вычислите, к какой из двух точек вы хотите присоединить ее. Это делается путем игры с линиями и нахождения точек пересечения. Разъяснение ниже.
4. Возвращенные две стороны треугольника + на 2 линии между точкой четвертого и те, которые вы выбрали из стадии 2.

Шаг 2 осветления:
Будем говорить, что точка А не в треугольнике (который является BCD). Каждая линия разделяет равнину на две стороны. мы хотим найти точку (B, C или D) s.t. линия между ним и А пробегает между двумя другими (они находятся на противоположных сторонах линии). Это точка, которую мы НЕ хотим присоединить к A.

Пример: Данные A (0,0), B (10,0), C (10,10) и D (0,10). У нас есть треугольник BCD. Линия BC оставляет A & D на той же стороне равнины. Так же и DC. Линия AC оставляет B & D на противоположных сторонах равнины - поэтому мы хотим подключить A к B & C.

Answer 2

EDIT: Как указано в комментариях, оно работает только в конкретных ситуациях и, следовательно, является плохим ответом ,

Четырехугольник можно нарисовать, найдя, какая пара точек между четырьмя точками отделена самым большим расстоянием. Как только эта пара будет найдена, квадрилетерал рисуется путем связывания двух оставшихся точек с каждой точкой пары.

Answer 3

Редактировать: Этот ответ уже доказал свою правоту.

1. Рассчитать центр четырех пунктов.
2. Перечислите точки в направлении против часовой стрелки (или по часовой стрелке).
3. Связать их вместе.

Answer 4

Рассмотрим разбиение плоскости, полученное путем рисования трех линий, определенных в первых трех точках. Он определяет 7 регионов. Вы можете легко найти, к какому региону относится четвертый пункт с помощью трех подписанных тестовых площадок (алгебраическая область треугольников ABD, BCD, CAD).

Рисование четырехугольника в каждом случае является простым (в каждом случае может быть одно, два или три решения).

В примере ниже, с D в регионе -++, ADBC ​​будет делать.

На самом деле две оценки площади достаточно: если первый тест возвращает - (регионы -+-, -++ или --+), ADBC ​​является решением, иначе, если второе испытание возвращает - (регионы +-+ или +--), ABDC - это решение, другое (регионы ++- или +++) ABCD - это решение.

Answer 5

Вы можете использовать упрощение любого из well-known algorithms for convex hull. Джарвису было бы легко. Если выпуклая оболочка является треугольником, четырехугольник выпуклый. Просто вставьте отсутствующую точку в любом месте списка краев. Если выпуклая оболочка является линией (2 конечных точки), просто соберите все точки на x- или y-координате, чтобы получить вырожденный четырехугольник. (Если ближе к горизонтали (abs delta x> abs delta y), используйте x для сортировки, иначе используйте y.)

Answer 6

Мне кажется, вам просто нужно объединить два момента каждый раз, мы получим сегмент линии и проверим если остальные две точки находятся на одной стороне от этих отрезков линии, если нет, это не сегмент линии требуемого четырехугольника, если да, то переходите к другому набору точек (т. е. точка может быть одной из координат этого сегмента и другой бы остальные две точки формы) и проверить то же самое, пока у получить 4 линейных сегментов

Answer 7

Рассмотрим аффинное преобразование

Px = Ax + u (Bx - Ax) + v (Cx - Ax) 
Py = Ay + u (By - Ay) + v (Cy - Ay) 

Он отображает (0, 0) в A, (1, 0) - B и (0, 1) - C. (Это ставит треугольник ABC в каноническом положении.)

Решая линейную систему 2х2

Dx = Ax + u (Bx - Ax) + v (Cx - Ax) 
Dy = Ay + u (By - Ay) + v (Cy - Ay) 

дает вам значение (u, v) соответствующее D.

Затем

if u < 0 => ABCD 
else if v < 0 => BCAD 
else => CABD 

Полученный четырехугольник имеет ту же ориентацию, что и треугольник ABC.

Answer 8

Ради ясности, я рассматриваю в качестве точки p_n точку с координатами (x_n, y_n).

Для подключения 4 точек можно выполнить следующие действия:

1. Получить точку p_1 с наименьшим x.
2. Рассчитайте slope из 3 строк, которые идут от p_1 к каждой оставшейся точке.
3. Соедините p_1 с точкой p_2, которая составляет линию с наибольшим уклоном.
4. Соедините p_1 с точкой p_3, которая составляет линию с наименьшим углом.
5. Подключить оставшуюся точку p_4 с p_2 и p_3.

Сообщите мне, если что-то неясно.

Answer 9

Осмотрите выпуклые алгоритмы корпуса. Один из них состоит из двух шагов: создание обычного многоугольника на заданном множестве вершин (который может быть вогнутым), а затем удаление «вогнутых вершин», чтобы оставшийся многоугольник стал выпуклым.

Первый шаг - решение вашей проблемы.

Конечно, это своего рода перебор. Для 4 вершин просто установите их в последовательности (в любом порядке), затем проверьте, пересекаются ли сегменты линий, соединяющие точки 1-2 и 3-4; если это так, точки подкачки 2 и 3; или, возможно, края 2-3 и 1-4 пересекаются, а затем заменяют точки 3 и 4. Готово.

Чтобы проверить, пересекаются ли сегменты AB и CD, если точки A и B находятся на противоположных сторонах линии CD, а точки C и D находятся на противоположных сторонах линии AB.

Для того, чтобы определить сторону линии PQ, где точка К лежит, вычислить Z -части PQ × PK векторного произведения: (xq-xp)(yk-yp)-(yq-yp)(xk-xp). Выражение положительно на одной стороне линии, а отрицательное - на другом (и ноль на линии).

Answer 10

Очень легко решить эту проблему с помощью функции, которая говорит о пересечении двух сегментов линии.

Для точек A, B, C, D существует только три разных порядка для объединения вершин: ABCD, ABDC и ACBD (вершина A либо соединяется с вершиной B, либо нет. Если это так, то есть два способы заказа C и D. Если это не так, A соединяется как с C, так и с D, и каждый из них должен подключиться к B).

Упорядочение четырех точек создает четырехугольник, если ни один из ребер не пересекается (кроме углов). Это дает эту процедуру для нахождения рабочего порядка:

If AB intersects with CD then return ACBD. 
If AD intersects with BC then return ABDC. 
Otherwise return ABCD. 

Доказательство того, что это работает легко:

1. как ABCD и ABDC включают ребра AB и CD, так что если эти пары ребер пересекаются, хороший порядок должен быть ACBD.
2. Оба ABCD и ACBD включают в себя ребра AD и BC, поэтому, если эти пары ребер пересекаются, хорошим порядком должен быть ABDC.
3. Если ни AB/CD, ни AD/BC не пересекаются, тогда заказ ABCD создает четырехугольник.

Код для определения пересечения двух сегментов линии можно найти в Интернете, если вы не можете понять это самостоятельно.

Answer 11

Вот тривиальный, не математический способ сделать это. Я пробовал это на нескольких примерах и не мог доказать это неправильно. Пожалуйста, дайте мне знать, если вы или знают, как сделать это лучше:

1. Выберите две точки, которые находятся на праве других, говорят, точка 1 и 2.
2. точка Link 1-2 вместе, а также пункты 3-4.
3. Каждая точка должна быть связана только с двумя другими точками, поэтому есть только две возможности: точки привязки 1-3 и 2-4, или точки 1-4 и 2-3.
4. Проверьте, пересекается ли каждая линия с другой.

Это должно быть сделано.

Примечание: при выборе первых двух точек, вот некоторые специальные случаи:

1. Точка 1 находится на правом всех остальных, но пункты 2 и 3 находятся на координате те же х. Выберите точку, наиболее близкую к точке 1.
2. Если три точки 1,2 и 3 имеют одинаковую координату x, соедините два наиболее близких друг к другу. Если точки разделены равномерно, выберите одну из двух возможностей.