Лучевой алгоритм

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



Редактировалось 1 раз(а). Последний 31.10.2020 22:56.

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

Цитата
oneman
https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA#:~:text=%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%CC%81%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%20%E2%80%94%20%D0%B3%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F%20%D1%84%D0%B8%D0%B3%D1%83%D1%80%D0%B0%2C%20%D0%BE%D0%B1%D1%8B%D1%87%D0%BD%D0%BE%20%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D1%8F%D0%B5%D0%BC%D0%B0%D1%8F,%2C%20%D0%B0%20%D0%BF%D1%8F%D1%82%D0%B8%D0%BA%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D0%B0%D1%8F%20%D0%B7%D0%B2%D0%B5%D0%B7%D0%B4%D0%B0%20%E2%80%94%20%D0%BD%D0%B5%D1%82.

Цитата
ascension
…имеется ввиду отрезок.

Цитата
ascension
Не поняла, что вы имели ввиду.

В данных случаях пишется “в виду”.

Цитата
ascension
Какие есть способы для рассмотрения и решения этого вырожденного случая без прибегания к "бесконечно малым величинам"?

Есть способ искать пересечение луча с отрезком, когда они заданы параметрически на основе метода гомотопии. На том же киберфоруме подобный вопрос задавался много раз. Например,
https://www.cyberforum.ru/cpp-beginners/thread1564199.html
При значении параметра отрезка 0 или 1, точка пересечения будет точно на одном из его концов.

Тогда при значение параметра луча равному 0 наша точка находится на стороне, верно поняла?

Цитата
oneman

Цитата
ascension
верно поняла?

тогда сам луч будет стартовать непосредственно от стороны многоугольника. Речь идёт о параметре отрезка.

Огромное спасибо, без вас бы не разобралась! :)