Метод трассировки луча

Лабораторная работа №5.2

Тема: Разработка программ с использованием массивов

Цель работы: Формирование умений и навыков в разработке сложных циклических алгоритмов обработки массивов с использованием процедур и функций пользователя.

Время на выполнение работы: 2 часа

Этапы работы:

I. Ознакомиться с теоретическими сведениями.

II. Выполнить задания, предложенные преподавателем.

III. Ответить на контрольные вопросы.

I. Краткие теоретические сведения

Уравнение прямой, проходящей через две различные точки на плоскости

Если прямая проходит через две точки A(x1, y1) и B(x2, y2), такие что x1 ≠ x2 и y1 ≠ y2 то уравнение прямой можно найти, используя следующую формулу

Отношение прямой и точки

Определяется так. Предположим, у нас есть 3 точки: А(х1, у1), Б(х2, у2), С(х3, у3). Через точки А и Б проведена прямая. И нам надо определить, как расположена точка С относительно прямой АБ. Для этого вычисляем значение:

D = (х3 - х1) * (у2 - у1) - (у3 - у1) * (х2 - х1)

- Если D = 0 - значит, точка С лежит на прямой АБ.

- Если D < 0 - значит, точка С лежит слева от прямой.

- Если D > 0 - значит, точка С лежит справа от прямой.

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

Метод трассировки луча

Учёт числа пересечений

Один из стандартных методов определения принадлежности точки произвольному простому многоугольнику заключается в следующем. Выпустим луч из данной точки в произвольном направлении (например в положительном направлении горизонтальной оси), и посчитаем сколько раз луч пересекает рёбра многоугольника. Для этого достаточно пройтись в цикле по рёбрам многоугольника и определить, пересекает ли луч каждое ребро. Если число пересечений нечётно, то объявляется, что точка лежит внутри многоугольника, если чётно — то снаружи. Это основано на том простом наблюдении, что при движении по лучу с каждым пересечением границы точка попеременно оказывается то внутри, то снаружи многоугольника. Алгоритм известен под такими названиями, как crossing number (count) algorithm или even-odd rule.

В алгоритме возникает затруднение в вырожденном случае, когда луч пересекает вершину многоугольника. Один из приёмов для его преодоления заключается в том, чтобы считать, что такие вершины многоугольника лежат на бесконечно малую величину выше (или ниже) прямой луча, и стало быть пересечения на самом деле и нет. Таким образом, пересечение луча с ребром засчитывается, если один из концов ребра лежит строго ниже луча, а другой конец — выше или лежит на луче.

Алгоритм работает за время O(N) для N -угольника.