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

Материал из Алговики
Перейти к навигации Перейти к поиску
м
Строка 8: Строка 8:
  
 
'''Обозначения:'''
 
'''Обозначения:'''
* <math>int(P)</math> &mdash; множество строго внутренних точек многоугольника <math>P</math>
+
* <math>int(P)</math> &mdash; множество строго внутренних точек многоугольника <math>P</math>;
* <math>V(P) = \{v_0, v_2, \dots, v_{N - 1} \}</math> &mdash; упорядоченноый набор точек, являющихся вершинами многоугольника <math>P</math>
+
* <math>V(P) = \{v_0, v_2, \dots, v_{N - 1} \}</math> &mdash; упорядоченноый набор точек, являющихся вершинами многоугольника <math>P</math>;
* <math>D(P)</math> &mdash; множество граничных точек многоугольника <math>P</math>, без учета вершин многоугольника.
+
* <math>D(P)</math> &mdash; множество граничных точек многоугольника <math>P</math>, без учета вершин многоугольника;
* <math>out(P)</math> &mdash; множество строго внешних по отношению к <math>P</math> точек
+
* <math>out(P)</math> &mdash; множество строго внешних по отношению к <math>P</math> точек;
 
* <math>\delta_{\varepsilon}(X)</math> &mdash; <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> &mdash; Евклидово расстояние между точками <math>A</math> и <math>B</math>, а <math>A = (A_x, A_y)</math> &mdash; точка, задающаяся своими координатами по осям.
 
* <math>\delta_{\varepsilon}(X)</math> &mdash; <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> &mdash; Евклидово расстояние между точками <math>A</math> и <math>B</math>, а <math>A = (A_x, A_y)</math> &mdash; точка, задающаяся своими координатами по осям.
  
Строка 61: Строка 61:
 
== Вычислительное ядро алгоритма ==
 
== Вычислительное ядро алгоритма ==
  
Как нетрудно видеть, сложность выполнения каждого из шагов 1) &ndash; 3) равна <math>O(N)</math>. Но в данной задаче есть один нюанс &mdash; сложность чтения данных составляет также <math>O(N)</math>. Причем, скорость чтения данных с диска гораздо медленее, чем оперирование с данными в процессе выполненения программы, поэтому, если говорить честно, то основная сложность алгоритма приходится именно на чтение данных (что впоследствии и будет видно на графиках сильной масштабируемости). Но проблема в том, что чтение с диска, без специальной предобработки хранения данных, достаточно плохо параллелится (с точки зрения времени чтения), то есть является "узким местом" алгоритма.  
+
Как нетрудно видеть, сложность выполнения каждого из шагов 1) &ndash; 3) равна <math>O(N)</math>. Но в данной задаче есть один нюанс &mdash; сложность чтения данных составляет также <math>O(N)</math>. Причем, скорость чтения данных с диска гораздо медленее, чем оперирование с данными в процессе выполненения программы, поэтому, если говорить честно, то основная сложность алгоритма приходится именно на чтение данных (что впоследствии и будет видно на графиках сильной масштабируемости). Но проблема в том, что чтение с диска достаточно плохо параллелится (с точки зрения времени чтения), то есть является "узким местом" алгоритма.  
  
 
Поэтому, будем считать, что данные '''уже лежат в памяти программы''' (такое запросто может быть, так как выбранный алгоритм спокойно может быть подзадачей какой-то программы), и тогда, основная сложность алгоритма придется на шаги 1) &ndash; 3).  
 
Поэтому, будем считать, что данные '''уже лежат в памяти программы''' (такое запросто может быть, так как выбранный алгоритм спокойно может быть подзадачей какой-то программы), и тогда, основная сложность алгоритма придется на шаги 1) &ndash; 3).  
  
 
== Макроструктура алгоритма ==
 
== Макроструктура алгоритма ==
 +
 +
0) Чтение входных данных: точка <math>X</math> и многоугольник <math>P</math>;
 +
1) Проверка принадлежности <math>X</math> набору <math>V(P)</math>;
 +
2) Проверка принадлежности <math>X</math> множеству <math>D(P)</math>;
 +
3) Проверка принадлежности <math>X</math> множеству <math>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)
  
 
== Последовательная сложность алгоритма ==
 
== Последовательная сложность алгоритма ==

Версия 00:11, 30 ноября 2017

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

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) = \{v_0, v_2, \dots, v_{N - 1} \}[/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]

Алгоритм:

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

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


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

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

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

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

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

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

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

3) Если [math]X \notin V(P)[/math] и [math]X \notin D(P)[/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}(2 \pi) \Rightarrow X \in int(P)[/math]

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

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

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

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

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

0) Чтение входных данных: точка [math]X[/math] и многоугольник [math]P[/math]; 1) Проверка принадлежности [math]X[/math] набору [math]V(P)[/math]; 2) Проверка принадлежности [math]X[/math] множеству [math]D(P)[/math]; 3) Проверка принадлежности [math]X[/math] множеству [math]int(P)[/math].

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.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