Как определить точки четырехугольника?
У меня есть точки четырехугольника:
x1 = 81.0582
y1 = 348.106
x2 = 127.111
y2 = 367.577
x3 = 120
y3 = 256
x4 = 166.053
y4 = 275.471
Они заданы в случайном порядке. У меня задача, в том, чтобы определить, находится ли точка в этом четырехугольнике. Для этого я использую следующую функцию
from matplotlib import path
p = path.Path([(x1,y1), (x2, y2), (x3, y3), (x4, y4)])
p.contains_points([(i, j)]) #i,j - случайная точка для проверки
Но точки не всегда правильно определяются из-за того, параметры четырехугольника заданы случайным образом. Как я понял, в данную функцию нужно вводить значения последовательно x1->x2->x3->x4 (то же самое с y), которые последовательно соединяются друг с другом, образую нужный четырех угольник. Иначе функция внутри себя построит неверную фигуру.
Я думал действовать перебором, брать точки в разном порядке (высчитывать их площадь, смотреть какой порядок точек образовал большую площадь, а потом этот порядок и использовать), но это не кажется мне разумным.
Какую функцию нужно написать, чтобы выявить верный порядок для задания в функцию (т.е. какая из этих точек является первая, какая вторая и.т.д.)?
Четырехугольник должен получиться выпуклым.
Ответы (1 шт):
Лучшее что вы можете сделать это построить выпуклую оболочку этих точек. Возможны следующие варианты:
Выпуклая оболочка из одной точки. Это значит что все точки совпадают. Что делать в этом случае - решайте сами.
Выпуклая оболочка из двух точек. Все точки в этом случае лежат на одной прямой. Опять решение за вами.
Выпуклая оболочка из трёх точек. Три точки образуют треугольник, четвёртая лежит внутри треугольника. На такой конфигурации можно построить три различных четырёхугольника. У вас нет способа отдать предпочтение какому-то одному без дополнительной информации.
Выпуклая оболочка из четырех точек. Ура! Четырехугольник возможен только один, и вы его уже построили, когда построили выпуклую оболочку.
Вообще есть забавный факт: если на данном множестве точек вы можете построить многоугольник только одим способом, то это множество совпадает со своей выпуклой оболочкой.
P.S. Подглядел в комментариях что всегда ожидается выпуклое множество. Четвёртый пункт решает задачу в этом случае.
P.P.S Если вы знаете что точки образуют параллелепипед, то построить его выпуклую оболочку легко: первая точка - самая правая (а если их две, то из них верхняя), вторая - самая верхняя (если их две, то из них левая), третья - самая левая (если их две, то из них нижняя), четвёртая - самая нижняя (если их две, то из них правая).