Изменения

Перейти к: навигация, поиск
м
Невыпуклый многоугольник
Пустим луч, например, по иксу и за <tex>O(n)</tex> переберём все рёбра и проверим их на пересечение с лучом. Как проверять: сначала проверим, что ордината точки лежит между ординатами концов ребра, затем {{Acronym|посмотрим, до ребра или после него начался луч|для альтернативно одарённых: это делается тоже поворотом}}.
Луч может попасть в точку, при этом прохождение через точку учтётся два раза (по разу для каждого отрезка, к которым принадлежит точка). Иногда это и есть то, чего нам хочется (когда фигура находится выше или ниже луча), но иногда нам хочется учесть только один раз. Для этого делаем такую штуку: для каждого отрезка учитываем {{Acronym|только верхнюю точку|А если отрезок горизонтальный, то забиваем на него, если точка не лежит на нём. После недолгих раздумий и разглядываний смежных отрезков станет очевидно, что на чётность числа пересечений он никак не влияет}}. Дальше {{Acronym|всё очевидно|Кому не очевидно, тот может порисовать картинки с лучом, попадающим в точку, и посчитать, сколько раз в каком случае учитывается пересечение}}.
[[Категория: Вычислительная геометрия]]
355
правок

Навигация