0

У меня есть точки четырехугольника:

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), которые последовательно соединяются друг с другом, образую нужный четырех угольник. Иначе функция внутри себя построит неверную фигуру.

Я думал действовать перебором, брать точки в разном порядке (высчитывать их площадь, смотреть какой порядок точек образовал большую площадь, а потом этот порядок и использовать), но это не кажется мне разумным.

Какую функцию нужно написать, чтобы выявить верный порядок для задания в функцию (т.е. какая из этих точек является первая, какая вторая и.т.д.)?

Четырехугольник должен получиться выпуклым.

8
  • "Какую функцию нужно написать" - Никакую. Правильного порядка не существует.
    – user176262
    3 мая 2021 в 20:59
  • Задача нерешаема. Скажем, i.stack.imgur.com/RmVNJ.png - ну как определить, какой из них "правильнее"? Вот если бы, скажем, было известно, что четырёхугольник выпуклый - тогда другое дело...
    – Akina
    3 мая 2021 в 21:01
  • 1
    coderoad.ru/10846431/…
    – splash58
    3 мая 2021 в 21:02
  • 1
    @ИльяПетров Тогда выбираешь любую пару такую, что остальные две точки лежат по разные стороны от прямой, проходящей через выбранную пару. Эта пара получает номера 1 и 3 (порядок неважен), остальные точки - номера 2 и 4 (и тоже порядок пофиг).
    – Akina
    3 мая 2021 в 21:13
  • 1
    вот тут на stackoverflow stackoverflow.com/questions/10846431/…
    – splash58
    3 мая 2021 в 21:30

1 ответ 1

2

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

  1. Выпуклая оболочка из одной точки. Это значит что все точки совпадают. Что делать в этом случае - решайте сами.

  2. Выпуклая оболочка из двух точек. Все точки в этом случае лежат на одной прямой. Опять решение за вами.

  3. Выпуклая оболочка из трёх точек. Три точки образуют треугольник, четвёртая лежит внутри треугольника. На такой конфигурации можно построить три различных четырёхугольника. У вас нет способа отдать предпочтение какому-то одному без дополнительной информации.

  4. Выпуклая оболочка из четырех точек. Ура! Четырехугольник возможен только один, и вы его уже построили, когда построили выпуклую оболочку.

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

P.S. Подглядел в комментариях что всегда ожидается выпуклое множество. Четвёртый пункт решает задачу в этом случае.

P.P.S Если вы знаете что точки образуют параллелепипед, то построить его выпуклую оболочку легко: первая точка - самая правая (а если их две, то из них верхняя), вторая - самая верхняя (если их две, то из них левая), третья - самая левая (если их две, то из них нижняя), четвёртая - самая нижняя (если их две, то из них правая).

5
  • если на данном множестве точек вы можете построить многоугольник только одним способом - то количество точек не превышает трёх. Ибо никаких дополнительных ограничений Вы на строимый многоугольник не вводите.
    – Akina
    3 мая 2021 в 21:16
  • Вы ошибаетесь: (0, 0), (1, 0), (1, 1), (0, 1) допускает построение единственного простого многоугольника (напомню, задействуем все вершины). 3 мая 2021 в 21:18
  • Где в Вашей формулировке слово "простой"? Я построю "песочные часы" - и попробуйте, глядя на собственную формулировку, доказать, что такой вариант не соответствует.
    – Akina
    3 мая 2021 в 21:20
  • Обычно под многоугольником подразумевается множество у которого есть внутренность и внешность. Если граница самопересекается, то определить их не удаётся. В этом случае фигуру называют циклической ломаной, не многоугольником. (Я к тому что под "многоугольником" обычно подразумевается "простая циклическая ломаная"). 3 мая 2021 в 21:22
  • Да мало ли что там "обычно"! Вот неочевидно. Всё, что не описано явно, имеет право быть как угодно.
    – Akina
    3 мая 2021 в 21:27

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.