Принадлежность точки многоугольнику

Здравствуйте, нашёл на другом форуме один из методов определения принадлежности точки многоугольнику:

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

Не пойму, то ли я не так понял, то ли метод действительно ошибочен.

0

Ближайшая линия -- как я понял, выбирается тот отрезок расстояние которого от точки M наименьшее. Расстояние измеряется от точки М не до средней точки, а до ближайшей точки. Это надо либо перпендикуляр опускать, либо, если перпендикуляр не попадает на отрезок, сравнивать расстояния до концов отрезка.

Могу предложить другой алгоритм для плоского случая. Через M проводим горизонтальную прямую и ищем точки пересечения этой прямой с отрезками ломаной. Сначала проверяем, не лежит ли M на ломаной (тогда будет особый ответ). Если слева и справа четное число пересечений, то M -- вне, если нечетное, -- то внутри. Если чет-нечет, то ломаная незамкнута либо вообще не ломаная. Вместо горизонтальной прямой можно взять вертикальную или вообще произвольную. Для простоты вычислений берем прямую параллельно какой-либо оси координат.

1

Судя по малограмотной фразе: "средняя точка ограничивающей линии", можно сделать определённый вывод!

0

palva Не, я правильно понял. У него оказывается ошибка в алгоритме, он потом поздно осознал это и расписал в другой теме исправленную версию:

Про алгоритм подсчёта пересечений я знаю, но он сложнее расписывается (там нужно ещё учитывать случаи, когда луч проходит через вершины или сразу через 2 вершины ребра). На algolist подробно расписано.
Вообще, я изучаю разные методы, чтобы понять, как обобщить это всё на 3-х мерный случай с замкнутой поверхностью.

Кстати, если не ошибаюсь, то его метод можно упростить:
1) Найти ближайшую к точке М вершину P. Эта вершина принадлежит двум ребрам.
2) Найти скалярное произведение PM*n1 и PM*n2 (где n1 и n2 - внешние нормали к рёбрам)
Если точка находится внутри многоугольника (или на ребре), то оба скалярных произведения не должны быть положительными.

0

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

Если многоугольник не выпуклый, то его нужно разбить на выпуклые

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

Добавлено через 1 минуту
подправил )

Добавлено через 6 минут
хорошей оптимизацией может оказаться отсечение по охватывающему прямоугольнику и вписанной окружности

1

Сообщение от Алексей1153 насколько я помню, метод определения следующий: для выпуклого многоугольника из точки проводятся отрезки ко всем вершинам. Получается много треугольников. Сумма площадей этих треугольников должна быть равна площади многоугольника. Если многоугольник не выпуклый, то его нужно разбить на выпуклые

Метод интересный, только вот непонятно, как его разбивать в программе.
Для выпуклого многоугольника думаю проще проверить, с какой стороны от каждого ребра (ребро - направленный отрезок) лежит точка с помощью векторного произведение. Если все векторные произведения >=0 или <= 0, то точка принадлежит многоугольника.

Добавлено через 3 минуты

Сообщение от kzru_hunter Кстати, если не ошибаюсь, то его метод можно упростить: 1) Найти ближайшую к точке М вершину P. Эта вершина принадлежит двум ребрам. 2) Найти скалярное произведение PM*n1 и PM*n2 (где n1 и n2 - внешние нормали к рёбрам) Если точка находится внутри многоугольника (или на ребре), то оба скалярных произведения не должны быть положительными.

Сейчас подумал и вроде как такой метод можно обобщить и для замкнутой поверхности. Только там нужно будет найти, как минимум три скалярных произведения PM*n1, PM*n2, PM*n3, ... (где n1,n2,n3 - внешние нормали к плоскостям граней, имеющих общую точку P)

0

Сообщение от kzru_hunter только вот непонятно, как его разбивать в программе.

можно разбить просто на треугольники, к примеру

Сообщение от kzru_hunter Для выпуклого многоугольника думаю проще проверить

вычислений будет столько же и, не побоюсь этого слова, таких же - будут операции с теми же векторами

0

Сообщение от Алексей1153 можно разбить просто на треугольники, к примеру

Спасибо, не заметил

Сообщение от Алексей1153 вычислений будет столько же и, не побоюсь этого слова, таких же - будут операции с теми же векторами

Вроде бы это делается через векторное произведение, т.к. оно равно площади параллелограмма, построенного на двух ребрах. Половина этой площади равна площади треугольника. Три площади - три векторных произведения.
И в том способе тоже три векторных произведений.
В одной статье была приведена производительность обоих способов и почему-то способ с площадями оказался медленней в 2 раза.
Добавлено через 1 минуту

Сообщение от kzru_hunter Кстати, если не ошибаюсь, то его метод можно упростить: 1) Найти ближайшую к точке М вершину P. Эта вершина принадлежит двум ребрам. 2) Найти скалярное произведение PM*n1 и PM*n2 (где n1 и n2 - внешние нормали к рёбрам) Если точка находится внутри многоугольника (или на ребре), то оба скалярных произведения не должны быть положительными.

Как можно доказать, что этот способ не даст ошибок?

Сообщение от kzru_hunter Как можно доказать, что этот способ не даст ошибок?

Всё-таки даёт ошибку в следующем случае:

Исправленный алгоритм пользователя О. Федор тоже даёт ошибку для этого (см. пред. рис. ) многоугольника

Сообщение от palva Ближайшая линия -- как я понял, выбирается тот отрезок расстояние которого от точки M наименьшее. Расстояние измеряется от точки М не до средней точки, а до ближайшей точки. Это надо либо перпендикуляр опускать, либо, если перпендикуляр не попадает на отрезок, сравнивать расстояния до концов отрезка.

Кстати, действительно, именно так и нужно было делать. Метод называется "Ближняя точка и ее нормаль". Для себя доказал, что этот метод действительно рабочий, но ещё самое важное - он должен работать и для замкнутой поверхности (по крайней мере я это для себя доказал).

0

А так не проще?

1

VSI Спасибо. Плюс за mathcad. Как я понял, это метод трассировки луча, не сразу понял

0

VSI Очень круто, что у Вас алгоритм оптимизирован до предела. Не так просто это сделать обычному юзеру )
Как я понял, если неравенство строгое, то будут отбрасываться точки лежащие на границе n-угольника, а чтобы и они включались, нужно изменить неравенство на нестрогое (<=)
Кстати, цикл можно упростить:

0

Просмотрел разные способы, но по моему мнению только трассировка луча является наиболее предпочтительным методом, т.к. он быстро отсеивает ребра, лежащие выше и ниже и остаются только максимум 4 ребра (2 слева и два справа и то, если луч проходит через вершину), которые нужно рассмотреть более внимательнее. Вдобавок, возможно за раз отсеивать группы ребер, если применять деревья. Также можно применить метод трассировки луча и для многогранника (но там он напорядок сложнее), и также быстро отсеивать грани, если как бы запаковывать их в параллелепипеды и сразу отбрасывать те грани, для которых луч не пересекает их параллелепипеды.

Сообщение от kzru_hunter Как я понял, если неравенство строгое, то будут отбрасываться точки лежащие на границе n-угольника, а чтобы и они включались, нужно изменить неравенство на нестрогое (<=)

К сожалению, это не всех случаев достаточно (когда, например, есть горизонтальные ребра). Нужно проводить немало дополнительных проверок. Вдобавок, в некоторых задачах может понадобиться узнать не просто принадлежности точки многоугольнику, а принадлежит ли точка его границе. И чтобы всё это учесть, нужно достаточно сильно переделать алгоритм, предложенный VSI, а потом ещё и на разных тестах перепроверить. Попробовал над этим заморочиться, но алгоритм сильно разросся, при этом в полученном виде его неудобно переписывать на какие-нибудь языки программирования, и решил, что лучше предложенного на хабре алгоритма ничего нету: https://habr.com/ru/post/161237/ (см. check2; check3 практически также отсекает ребра, но менее читабелен).
P.S. надеюсь эта ссылка разрешена

0

Сообщение от kzru_hunter Не пойму, то ли я не так понял, то ли метод действительно ошибочен.

Это не метод, это чушь какая-то.

Сообщение от kzru_hunter У него оказывается ошибка в алгоритме, он потом поздно осознал это и расписал в другой теме исправленную версию:

"Исправленная версия" ничуть не лучше исходной версии.

Сообщение от kzru_hunter К сожалению, это не всех случаев достаточно (когда, например, есть горизонтальные ребра). Нужно проводить немало дополнительных проверок.

Никаких сложных проверок там нет. Все совершенно элементарно. Подсчитываем пересечения ребер с горизонтальным лучом, выпущенным из тестируемой точки M(x,y). Принадлежность точки горизонтальному ребру - элементарная проверка. После этого в подсчете пересечений нас интересуют только ребра, у которых есть точка строго ниже луча, т.е ребра, для которых min(y1, y2) < y. Все.

Странно слышать рассуждения об этих проверках в рамках рассмотрения какого-то странного, но очевидно на порядки существенно более вычислительно тяжелого алгоритма.

---

Весь алгоритм для точки M(mx, my) выглядит так

0

Сообщение от TheCalligrapher Никаких сложных проверок там нет.

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

Сообщение от TheCalligrapher Весь алгоритм для точки M(mx, my) выглядит так

Попробуйте теперь это упаковать в реальный код. Да и как бы уже подробно про алгоритм трассировки луча давно всё расписано (выше писал). Ну и как бы это опять велосипед, когда уже всё за нас сделали и на сто рядов перепроверили. Ну и тема не совсем про алгоритм трассировки луча был. Потом VSI предложил реальный минимальный код, но нечитабельный. Мне он понравился, но переделка его под другие нужды оказалась не совсем неудачной из-за разрошенности, поэтому весь минимализм кода просто исчез и вдобавок осталась нечитабельность.

Сообщение от TheCalligrapher Отлавливаем попадание M на горизонтальное ребро - ответ готов

Лучше сначала отсеить ребра, лежашие выше и ниже, чем отлавливать это попадание.

Вот весь оптимизированный перепроверенный на сто рядов код проверки пересечения луча с ребром (возвращает 0, если принадлежит ребру; -1, если пересекает; 1, если не пересекает):
Вложение 1231052
Тут можно ещё даже оптимизировать, если лишние проверки опустить ниже, а именно ax и bx поставить после первого if'a

0

Сообщение от kzru_hunter Я говорил, что их немало, вследствие чего код в 2 раза увеличится по размеру и вдобавок некрасиво будет смотреть при переносе на разные языки программирования.

Ну тогда вам нужен язык программирования, в котором в готовом виде есть примитив определения принадлежности точки многоугольнику. Вот там все будет красиво.

Сообщение от kzru_hunter Попробуйте теперь это упаковать в реальный код.

Да уж десятки раз упаковывал. В каждой программе - по новой.

Сообщение от kzru_hunter Лучше сначала отсеить ребра, лежашие выше и ниже, чем отлавливать это попадание.

Я описал алгоритм. А "сначала отсеить" (sic) - это посторонняя оптимизационно-реализационная деталь, к алгоритму как таковому не имеющая никакого отношения.

Сообщение от kzru_hunter Вложение 1231052

"Вложение не существует или не указан идентификатор (номер)."

0