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

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

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

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

На плоскости дан произвольный многоугольник с $N$ вершинами и точка $X$. Требуется определить положение точки относительно многоугольника: находится ли точка внутри многоугольника, на его границе, совпадает с вершиной или находится вне многоугольника.

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

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

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

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

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

• 1, если $X \in int(P)$
• 2, если $X \in V(P)$
• 0, если $X \in D(P)$
• -1, если $X \in out(P)$

Алгоритм:

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

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

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

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

$s_i = \langle v_i^l, v_i^r \rangle$ — скалярное произведение векторов $v_i^l, v_i^r$

$t_i = v_i^l \times v_i^r$ — модуль вектора, полученного векторным произведением векторов $v_i^l, v_i^r$

Теоретически, точка лежит на ребре (строго, не совпадает ни с одной из вершин ребер), если $s_i \lt 0$ и $d_i = 0$.

Практически, равенство нулю нужно превратить в $|d_i| \leqslant \varepsilon$.

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

3) Если $X \notin V(P)$ и $X \notin D(P)$:

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

$S = \sum_{i=0}^{N - 1} angle (v_i - X, v_{(i + 1) \% N} - X)$

где $angle(a, b)$ — ориентированный угол между векторами $a$ и $b$.

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

• $|S| \lt \varepsilon \Rightarrow X \in out(P)$
• $|S| \in \delta_{\varepsilon}(2 \pi) \Rightarrow X \in int(P)$

Замечание: здесь вводятся $\varepsilon$ - окрестности из-за того, что работа происходит с вещественными числами.

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

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

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

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

0) Чтение входных данных: точка $X$ и многоугольник $P$;

1) Проверка принадлежности $X$ набору $V(P)$;

2) Проверка принадлежности $X$ множеству $D(P)$;

3) Проверка принадлежности $X$ множеству $int(P)$.

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

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

# Ввод данных
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.6 Последовательная сложность алгоритма

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

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

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

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

2) $\text{edge_flag}_{p_i}$ — принадлежность точки $X$ одному из ребер $P_{p_i}$;

3) $\text{angle_sum}_{p_i}$ — сумма ориентированных углов, описанная в на п.1.2 в применении к $P_{p_i}$ (естественно, без замыкания этой ломанной по первой вершине).

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

1) $\text{vertex_flag} = \bigvee \limits_{p_i} \text{vertex_flag}_{p_i}$, $\bigvee$ — логическое ИЛИ;

2) $\text{edge_flag} = \bigvee \limits_{p_i} \text{edge_flag}_{p_i}$;

3) $\text{angle_sum} = \sum \limits_{p_i} \text{angle_sum}_{p_i}$;

На основе этих величин, очевидно, делается вывод о расположении точки $X$ относительно многоугольника $P$.

3 Литература

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