Участник:Liebeann/Принадлежность точки многоугольнику
Автор статьи: Липкина Анна
Содержание
- 1 Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
На плоскости дан произвольный многоугольник с [math]N[/math] вершинами и точка [math]X[/math]. Требуется определить положение точки относительно многоугольника: находится ли точка внутри многоугольника, на его границе, совпадает с вершиной или находится вне многоугольника.
1.2 Математическое описание алгоритма
Дано: Многоугольник [math]P[/math]с [math]N[/math] вершинами и точка [math]X[/math]. Каждая вершина многоугольника и точка [math]X[/math] описываются парой координат [math](x, y)[/math].
Обозначения:
- [math]int(P)[/math] — множество строго внутренних точек многоугольника [math]P[/math]
- [math]V(P)[/math] — множество точек, являющихся вершинами многоугольника [math]P[/math]
- [math]D(P)[/math] — множество граничных точек многоугольника [math]P[/math], без учета вершин многоугольника.
- [math]out(P)[/math] — множество строго внешних по отношению к [math]P[/math] точек
- [math]\delta_{\varepsilon}(X)[/math] — [math]\varepsilon[/math]-окрестность точки [math]X[/math], или это следующее множество точек: [math]\{x \in \mathbb{R}^2 | \rho(x, X) \leqslant \varepsilon \}[/math], где [math]\rho(A, B) = \sqrt{(A_x - B_x)^2 + (A_y - B_y) ^ 2}[/math] — Евклидово расстояние между точками [math]A[/math] и [math]B[/math], а [math]A = (A_x, A_y)[/math] — точка, задающаяся своими координатами по осям.
Выход: вывести:
- 1, если [math]X \in int(P)[/math]
- 2, если [math]X \in V(P)[/math]
- 0, если [math]X \in D(P)[/math]
- -1, если [math]X \in out(P)[/math]
Алгоритм: Сначала проверим, принадлежит ли [math]X[/math] множеству [math]V(P)[/math]. Для этого достаточно перебрать все вершины [math]V(P)[/math] и для каждой проверить, лежит ли [math]X[/math] в маленькой [math]\varepsilon[/math]-окрестности текущей вершины многоугольника. Более формально:
для всех v принадлежащих V(P): если X принадлежит епсилон-окрестности v: вернуть 2
Если [math]v \notin V(P)[/math]:
Пусть порядок вершин в многоугольнике [math]P[/math] = [math]\{v_0, v_1, v_2, \dots, v_{N - 1}\}[/math]. Посчитаем следующую сумму ориентированных углов:
[math]S = \sum_{i=0}^{N - 1} angle (v_i - X, v_{(i + 1) \% N} - X)[/math]
где [math]angle(a, b)[/math] — ориентированный угол между векторами [math]a[/math] и [math]b[/math].
Есть следующие три варианта:
- [math]|S| \lt \varepsilon \Rightarrow X \in out(P) [/math]
- [math]|S| \in \delta_{\varepsilon}(\pi) \Rightarrow X \in D(P)[/math]
- [math]|S| \in \delta_{\varepsilon}(2 \pi) \Rightarrow X \in int(P)[/math]
Замечание: здесь вводятся [math]\varepsilon[/math] - окрестности из-за того, что работа происходит с вещественными числами.
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
1.9 Входные и выходные данные алгоритма
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
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