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

Автор статьи: Липкина Анна

Свойства и структура алгоритмов

Общее описание алгоритма

На плоскости дан произвольный многоугольник с [math]\displaystyle{ N }[/math] вершинами и точка [math]\displaystyle{ X }[/math]. Требуется определить положение точки относительно многоугольника: находится ли точка внутри многоугольника, на его границе, совпадает с вершиной или находится вне многоугольника.

Математическое описание алгоритма

Дано: Многоугольник [math]\displaystyle{ P }[/math]с [math]\displaystyle{ N }[/math] вершинами и точка [math]\displaystyle{ X }[/math]. Каждая вершина многоугольника и точка [math]\displaystyle{ X }[/math] описываются парой координат [math]\displaystyle{ (x, y) }[/math].

Обозначения:

• [math]\displaystyle{ int(P) }[/math] — множество строго внутренних точек многоугольника [math]\displaystyle{ P }[/math];
• [math]\displaystyle{ V(P) = \{v_0, v_2, \dots, v_{N - 1} \} }[/math] — упорядоченноый набор точек, являющихся вершинами многоугольника [math]\displaystyle{ P }[/math];
• [math]\displaystyle{ D(P) }[/math] — множество граничных точек многоугольника [math]\displaystyle{ P }[/math], без учета вершин многоугольника;
• [math]\displaystyle{ out(P) }[/math] — множество строго внешних по отношению к [math]\displaystyle{ P }[/math] точек;
• [math]\displaystyle{ \delta_{\varepsilon}(X) }[/math] — [math]\displaystyle{ \varepsilon }[/math]-окрестность точки [math]\displaystyle{ X }[/math], или это следующее множество точек: [math]\displaystyle{ \{x \in \mathbb{R}^2 | \rho(x, X) \leqslant \varepsilon \} }[/math], где [math]\displaystyle{ \rho(A, B) = \sqrt{(A_x - B_x)^2 + (A_y - B_y) ^ 2} }[/math] — Евклидово расстояние между точками [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math], а [math]\displaystyle{ A = (A_x, A_y) }[/math] — точка, задающаяся своими координатами по осям.

Выход: вывести:

• 1, если [math]\displaystyle{ X \in int(P) }[/math]
• 2, если [math]\displaystyle{ X \in V(P) }[/math]
• 0, если [math]\displaystyle{ X \in D(P) }[/math]
• -1, если [math]\displaystyle{ X \in out(P) }[/math]

Алгоритм:

1) Сначала проверим, принадлежит ли [math]\displaystyle{ X }[/math] множеству [math]\displaystyle{ V(P) }[/math]. Для этого достаточно перебрать все вершины [math]\displaystyle{ V(P) }[/math] и для каждой проверить, лежит ли [math]\displaystyle{ X }[/math] в маленькой [math]\displaystyle{ \varepsilon }[/math]-окрестности текущей вершины многоугольника. Более формально:

для всех v принадлежащих V(P):
   если X принадлежит епсилон-окрестности v:
        вернуть 2

2) Если точка не совпадает ни с одной вершиной, то проверим, принадлежит ли [math]\displaystyle{ X }[/math] множеству [math]\displaystyle{ D(P) }[/math]. Для этого переберем все ребра многоугольника [math]\displaystyle{ (v_i, v_{i + 1}) }[/math] и посчитаем следующие величины:

Пусть [math]\displaystyle{ v_i^l = v_i - X, v_i^r = v_{(i + 1) \% N} - X }[/math]

[math]\displaystyle{ s_i = \langle v_i^l, v_i^r \rangle }[/math] — скалярное произведение векторов [math]\displaystyle{ v_i^l, v_i^r }[/math]

[math]\displaystyle{ t_i = v_i^l \times v_i^r }[/math] — модуль вектора, полученного векторным произведением векторов [math]\displaystyle{ v_i^l, v_i^r }[/math]

Теоретически, точка лежит на ребре (строго, не совпадает ни с одной из вершин ребер), если [math]\displaystyle{ s_i \lt 0 }[/math] и [math]\displaystyle{ d_i = 0 }[/math].

Практически, равенство нулю нужно превратить в [math]\displaystyle{ |d_i| \leqslant \varepsilon }[/math].

Если все условия выполнены, то возвращаем 0.

3) Если [math]\displaystyle{ X \notin V(P) }[/math] и [math]\displaystyle{ X \notin D(P) }[/math]:

Посчитаем следующую сумму ориентированных углов:

[math]\displaystyle{ S = \sum_{i=0}^{N - 1} angle (v_i - X, v_{(i + 1) \% N} - X) }[/math]

где [math]\displaystyle{ angle(a, b) }[/math] — ориентированный угол между векторами [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math].

Есть следующие два варианта:

• [math]\displaystyle{ |S| \lt \varepsilon \Rightarrow X \in out(P) }[/math]
• [math]\displaystyle{ |S| \in \delta_{\varepsilon}(2 \pi) \Rightarrow X \in int(P) }[/math]

Замечание: здесь вводятся [math]\displaystyle{ \varepsilon }[/math] - окрестности из-за того, что работа происходит с вещественными числами.

Вычислительное ядро алгоритма

Как нетрудно видеть, сложность выполнения каждого из шагов 1) – 3) равна [math]\displaystyle{ O(N) }[/math]. Но в данной задаче есть один нюанс — сложность чтения данных составляет также [math]\displaystyle{ O(N) }[/math]. Причем, скорость чтения данных с диска гораздо медленее, чем оперирование с данными в процессе выполненения программы, поэтому, если говорить честно, то основная сложность алгоритма приходится именно на чтение данных (что впоследствии и будет видно на графиках сильной масштабируемости). Но проблема в том, что чтение с диска достаточно плохо параллелится (с точки зрения времени чтения), то есть является "узким местом" алгоритма.

Поэтому, будем считать, что данные уже лежат в памяти программы (то есть чтение данных не вносит значительный вклад в время работы алгоритма) (такое запросто может быть, так как выбранный алгоритм спокойно может быть подзадачей какой-то программы), и тогда, основная сложность алгоритма придется на шаги 1) – 3). Формально, я продолжу писать, что данные считываются из памяти.

Макроструктура алгоритма

0) Чтение входных данных: точка [math]\displaystyle{ X }[/math] и многоугольник [math]\displaystyle{ P }[/math];

1) Проверка принадлежности [math]\displaystyle{ X }[/math] набору [math]\displaystyle{ V(P) }[/math];

2) Проверка принадлежности [math]\displaystyle{ X }[/math] множеству [math]\displaystyle{ D(P) }[/math];

3) Проверка принадлежности [math]\displaystyle{ X }[/math] множеству [math]\displaystyle{ int(P) }[/math].

Схема реализации последовательного алгоритма

Псевдокод алгоритма:

# Ввод данных
X = input_point()
P = input_polygon()

if is_one_of_vertex(X, P): # Если точка X является одной из вершин многоугольника
   print(2)
else if is_one_of_edge(X, P): # Если точка X лежит на одном из ребер многоульника
   print(0)
else if is_inside(X, P): # Если точка X строго внутри многоугольника
   print(1)
else: # Если точка X строго снаружи многоугольника
   print(-1) 

Последовательная сложность алгоритма

В силу описания предложенного алгоритма с разделе на п.1.2, время работы всего алгоритма линейное от количества вершин многоульника [math]\displaystyle{ P }[/math], то есть([math]\displaystyle{ O(N) }[/math] операций) (под операциями здесь подразумеваются сложения и умножения чисел).

Ресурс параллелизма алгоритма

Как нетрудно видеть, вычислительное ядро алгоритма легко параллелится: достаточно каждому процессу [math]\displaystyle{ p_i }[/math] дать свой "кусок" (ломанную последовательных вершин многоугольника) [math]\displaystyle{ P_{p_i} }[/math] так, чтобы в объединении эти ломанные давали весь многоугольник. Далее посчитаем для каждого процесса следующие величины:

1) [math]\displaystyle{ \text{vertex_flag}_{p_i} }[/math] — принадлежность точки [math]\displaystyle{ X }[/math] одной из вершин [math]\displaystyle{ P_{p_i} }[/math];

2) [math]\displaystyle{ edge\_flag_{p_i} }[/math] — принадлежность точки [math]\displaystyle{ X }[/math] одному из ребер [math]\displaystyle{ P_{p_i} }[/math];

3) [math]\displaystyle{ angle\_sum_{p_i} }[/math] — сумма ориентированных углов, описанная в на п.1.2 в применении к [math]\displaystyle{ P_{p_i} }[/math] (естественно, без замыкания этой ломанной по первой вершине).

Теперь, чтобы получить исходный ответ, посчитаем следующие величины:

1) [math]\displaystyle{ vertex\_flag = \bigvee \limits_{p_i} vertex\_flag_{p_i} }[/math], [math]\displaystyle{ \bigvee }[/math] — логическое ИЛИ;

2) [math]\displaystyle{ edge\_flag = \bigvee \limits_{p_i} edge\_flag_{p_i} }[/math];

3) [math]\displaystyle{ angle\_sum = \sum \limits_{p_i} angle\_sum_{p_i} }[/math];

На основе этих величин, очевидно, делается вывод о расположении точки [math]\displaystyle{ X }[/math] относительно многоугольника [math]\displaystyle{ P }[/math].

Литература

http://ru-wiki.org/wiki/Задача_о_принадлежности_точки_многоугольнику https://habrahabr.ru/post/301102/ http://neerc.ifmo.ru/wiki/index.php?title=Принадлежность_точки_выпуклому_и_невыпуклому_многоугольникам http://www.e-maxx-ru.1gb.ru/algo/pt_in_polygon