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

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

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

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

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

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

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

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

• $int(P)$ — множество строго внутренних точек многоугольника $P$
• $V(P)$ — множество точек, являющихся вершинами многоугольника $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 = (A_x, A_y)$.

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

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

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

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

Если $v \notin V(P)$:

Пусть порядок вершин в многоугольнике $P$ = $\{v_0, v_1, v_2, \dots, v_{N - 1}\}$. Посчитаем следующую сумму ориентированных углов:

$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}(\pi) \Rightarrow X \in D(P)$
• $|S| \in \delta_{\varepsilon}(2 \pi) \Rightarrow X \in int(P)$

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

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