*120018*

о локализации точки относительно плоских областей.

Недошивина А.И.

Воронежский институт МВД России, Воронеж, Россия

 

Введение. Одним из направлений вычислительной геометрии является геометрический поиск, в котором принято выделять две основные проблемы: задачи локализации и регионального поиска. Рассмотрим задачи первого типа.

 Один из типичных примеров приложения задачи локализации точки -  это задача определения местоположения. В качестве исходных данных может выступать, например, дорожная карта, а в качестве запроса -  пара координат от глобальной системы навигации и определения местоположения (GPS). Ответом может быть номер дороги,  на которой находится автомобиль.

 Ознакомимся со следующими алгоритмами локализации точки: метод луча, метод суммирования углов, локализация точки для выпуклого и звездного многоугольника, метод полос, метод цепей, метод детализации триангуляции, метод трапеций.

Задача локализации точки. Одной из главных моделей геометрического поиска является задача локализации точки, когда файл представляет собой разбиение геометрического пространства на области, а запрос является точкой. Локализация состоит в определении области, содержащей запрошенную точку.

 Трудоемкость этой задачи существенно зависит от природы пространства и от способа его разбиения.

Метод трассировки луча. Учёт числа пересечений. Один из стандартных методов определения принадлежности точки произвольному простому многоугольнику заключается в следующем. Выпустим луч из данной точки в произвольном направлении (например, в положительном направлении горизонтальной оси), и посчитаем: сколько раз луч пересекает рёбра многоугольника. Если число пересечений нечётно, то объявляется, что точка лежит внутри многоугольника, если чётно — то снаружи. Это основано на том, что при движении по лучу с каждым пересечением границы точка попеременно оказывается то внутри, то снаружи многоугольника (рис.1)

Рис.1

Учёт числа оборотов. Рассмотрим число оборотов, которое делает ориентированная граница многоугольника вокруг данной точки. Оно может быть вычислено следующим образом. Как и раньше, выпустим луч из этой точки в произвольном направлении и рассмотрим рёбра, которые он пересекает. Каждому пересечению присвоим число +1 или   -1  в зависимости от того, как ребро пересекает луч — по часовой (слева направо) или против часовой стрелки (справа налево). Эти два случая можно различить по знаку скалярного произведения между направляющим вектором ребра и нормалью к направляющему вектору луча. Если сумма не равна нулю, то будем считать, что точка лежит внутри многоугольника, иначе — снаружи.

Метод (суммирования) углов. Можно определить, что данная точка (P) находится внутри многоугольника c вершинами V0, V1, ..., Vn = V0, вычислив сумму: , где φi — угол между лучами PVi - 1 и PVi, т.е.: .

Можно доказать, что эта сумма есть не что иное, как windingnumber (число намоток или винтовое число) точки P относительно границы многоугольника, с точностью до константного множителя 2π. Поэтому можно считать, что точка лежит снаружи многоугольника, если сумма равна нулю (или достаточно близка к нему, если используется приближённая арифметика). Однако данный метод весьма непрактичен, так как требует вычисления дорогостоящих операций для каждого ребра (обратных тригонометрических функций, квадратных корней, деления), и был даже назван «худшим в мире алгоритмом» для данной задачи.

 

 

Локализация точки относительно выпуклого и звездного многоугольников.

Метод для выпуклого многоугольника. В данном случае мы можем построить алгоритм намного более быстрый, чем линейный. Возьмем любую точку q внутри многоугольника (например, геометрический центр масс), проведем из нее все отрезки до вершин многоугольника. В силу выпуклости многоугольник разобьется на непересекающиеся клинья (Рис. 3)

Рис.3

Теперь заметим, что возможно упорядочить данные клинья по полярному углу против часовой стрелки и применить бинарный поиск для поиска нужного клина. После того, как клин найден, осталось только проверить, лежит ли точка внутри клина или снаружи. Точка z лежит внутри клина, тогда и только тогда, когда поворот правый, если поворот левый, то точка снаружи.

Чтобы можно было применить двоичный поиск, вершины должны быть упорядочены по углу относитель­но некоторой точки. Существует более обширный класс простых, многоугольни­ков, включающий в себя и выпуклые многоугольники, который   обладает этим свойством: это класс звездных многоугольников. Действительно, звездный многоугольник Р (рис.4) содержит по меньшей мере одну точку q та­кую, что отрезок qpi лежит целиком внутри многоуголь­ника Р для любой вершины pi из Р, i=1,…N.

Рис.4

Методы локализации точки на планарном подразбиении.  Любой плоский прямолинейный граф (ППЛГ) определяет подразбиение плоскости (планарное подразбиение). Локализация точки на планарном подразбиении – это процесс определения области, содержащей запрошенную точку.

 Чтобы вести поиск на планарном подразбиении, на этапе предобработки производится декомпозиция исходных областей на такие области, для которых поисковая операция относительно проста (например, треугольники или трапеции). Тогда успех в локализации точки зависит от возможности быстро сузить множество компонент декомпозиции, которые следует просмотреть. Среди методов, таких как метод полос, метод цепей, метод детализации триангуляции и метод трапеции, с точки зрения затрат времени на предобработку наилучшими являются методы цепей и трапеций. В то время как метод полос обладает наихудшим временем на предобработку из всех представленных. А вот с точки зрения затрат времени на запрос наихудшим является метод цепей. Метод трапеции демонстрирует наилучшие результаты и является эффективным методом, но прямая процедура данных поиска использует неоптимальное количество памяти.

Метод комплексного интегрирования в  задаче о локализации точки относительно стандартного многоугольника на плоскости. Рассмотрим задачу о локализации точки относительно многоугольника на плоскости.

Это известная задача вычислительной геометрии, имеющая много различных известных способов решения. Наряду с достоинствами, каждое такое решение имеет свои недостатки и ограничения. В основе нового метода лежит неожиданное применение теорем Коши о вычетах из теории функций комплексного переменного. Этот метод решения в некоторых отношениях превосходит известные на сегодняшний день алгоритмы.

Как уже было указано, алгоритм основан на использовании теорем Коши из теории функций комплексного переменного.

Вычислим величину где ∆ - это контур данного многоугольника М, W- данная точка плоскости. Тогда из теоремы и формулы Коши следует, что при K=0 точка W М, при K=2πi точка W М, а при K=∞ точка Ω ∆.

Вычислим формулы для величины K при данных координатах вершин многоугольника М и точки плоскости W.

Вначале рассмотрим в качестве простого примера случай треугольника АВС, стороны которого заданы прямыми: y=1-x, x=0, y=0. И данной точки с координатами W=(x0, y0). (рис.5)

Рис.5

Для этого треугольника вычислим величину K, равную интегралу от функции комплексного переменного по контуру треугольника ∆:

Проанализируем формулу. В результате величина K оказалась равной с точностью до множителя сумме арктангенсов, аргументы которых представляются в виде дробей. Знаменатели дробей – это уравнения сторон данного треугольника, а числители – это уравнения перпендикуляров к каждой стороне в вершинах треугольника.

Перейдём к рассмотрению общего случая многоугольника. Для этого возьмем одну его сторону и произведем все вычисления для нее.

Пусть отрезок АВ имеет координаты вершин А(х1,у1), В(х2,у2). (рис.6)

Рис.6

Тогда прямая, на которой расположен треугольник, задана уравнением: . Для отрезка  интеграл от функции комплексного переменного будет равен:

.

Таким образом, получаем, что для стороны многоугольника интеграл равен сумме арктангенсов и натуральных логарифмов. Но если включить сторону в замкнутый контур многоугольника, логарифмы сокращают. Величина K для многоугольника становится равной сумме арктангенсов. Аргументы – дроби, где знаменатели – уравнения сторон и числители – уравнения перпендикуляров к каждой стороне в вершинах.

Когда этот интеграл равен нулю (K=0), точка не принадлежит многоугольнику; K=2πі, точка принадлежит многоугольнику; и если K=∞, точка находится на контуре многоугольника.

Окончательная формула имеет вид

где ( ) – точка, принадлежность которой многоугольнику мы исследуем, а суммирование распространяется на все стороны многоугольника.

Полученная формула не упрощается при помощи выражения для суммы арктангенсов. Однако суммирование арктангенсов можно корректно провести частично в том случае, если известна дополнительная частичная неполная информация о координатах точки.

Применением полученной формулы является метод получения семейства тождеств для сумм арктангенсов. Например, очевидно, что точка с координатами D=(666,13) лежит вне треугольника,  рассмотренного в примере 1. Следовательно, получаем

Полученная общая формула для произвольного многоугольника позволяет решать поставленную задачу о локализации точки относительно многоугольника аналитически при помощи вычислений.

Применение метода  комплексного интегрирования к задаче о локализации точки относительно криволинейных многоугольных областей на плоскости. Данный метод работает и для криволинейных границ.

Рассмотрим в качестве частного случая пример, с криволинейной стороной, заданной уравнением: .

Рис.7

Для параболы от 0 до 1 интеграл от функции  комплексного переменного будет равен:

Для точки W(-1;1):

Приложения. Метод позволяет решать поставленную задачу о локализации точки относительно криволинейных многоугольных областей аналитически при помощи вычислений. Автору неизвестен другой подобный аналитический метод решения задачи о локализации. Кроме того, представляется, что к числу достоинств предложенного метода можно отнести три его особенности:

1.       метод работает для криволинейных границ, составленных из кусков сплайнов, кривых Безье и т.д. при этом вычисления с помощью пакета MATHEMATICA несколько усложняются, однако без принципиальных затруднений доводятся до явных формул, как только заданы уравнения частей границы. Кроме того, для каждой области вычисление проводится только один раз, далее выполняется простая подстановка в уже полученную формулу;

2.       метод выгодно применять, когда точка лежит вблизи границы области. Конкурирующие методы приводят к необходимости сравнивать практически равные числа, тогда как в данном методе сравнивать приходится существенно различающиеся по модулю величины: 0, 2π, ∞.

3.       данный метод не требует выпуклости многоугольника в отличие от большинства  других известных методов.

Методика может быть использована для оптимизации сохранения данных, получаемых, например, при записи на компьютер результатов слежения видеоаппаратурой или другой аппаратурой, относящейся к спецтехнике.

В настоящее время видеонаблюдение активно используется во всех сферах деятельности. Например, на производстве, в торговых и развлекательных центрах, на дорогах и парковках, для охраны частной собственности и прочее.  Видеоизображения просматриваются дистанционно и сохраняются в видеоархив или используется только часть видеоматериалов, например для создания доказательной базы фактов правонарушения.

В кадр зачастую попадает ненужная информация. Если это видео с места запрещенной парковки на пешеходном переходе (в зоне остановки), то в кадре нас интересует только участок дороги с пешеходным переходом (с зоной парковки), остальные участки захватываемые объективом ненужные. Если мы хотим зафиксировать запрещенный проезд по тротуару (на запрещающий сигнал светофора) – то будем отслеживать определенную область кадра видеоряда. То же самое происходит при наблюдении, например, за входом в здание. В кадре нам необходимо видеть только вход и ничего более, чтобы объем видеоинформации был минимально возможным.

В этом случае подходяще было бы применить метод комплексного интегрирования.

Для стационарной камеры определим область кадра, которая необходима. Зададим эту область координатами и вычисляем формулу для величины K при данных координатах вершин криволинейной многоугольной области М. Точки плоскости в данном случае – это пиксели кадра, подставим в вычисленную формулу с помощью программы. Программа осуществляет следующий порядок действий:

1.     выхватывает каждый кадр видеопотока;

2.     для каждого кадра осуществляет попиксельную проверку:

1)     координаты каждого пикселя подставляются в вычисленную формулу К,

2)     сохраняет все точки в новый массив, если величина К =2πi,

3.     Массив сохраняется как новый кадр видеофайла, который содержит только интересующую нас область.

Таким образом, мы сохранили лишь те пиксели, которые находились в интересующей нас области, и значительно сократили объем видеофайла.

 

ЛИТЕРАТУРА

1.       Препарата Ф. Вычислительная геометрия. Введение/ Ф.Препарата, М.Шеймос. – М.: Мир, 1989.

2.       Ласло М. Вычислительная геометрия и компьютерная графика на С++/ М.Ласло. – М.: Бином, 1997

3.       Роджерс Д. Алгоритмические основы машинной графики/ Д.Роджерс. – М.: Мир, 1989

4.       Евграфов М.А. Аналитические функции/ М.А.Евграфов. – М.: Наука, 1991.

5.       Вышегородцева А.И., Ситник С.М.   О математическом алгоритме определения принадлежности точки треугольнику. Всероссийская научно - практическая конференция   "Охрана, безопасность и связь - 2005", часть 1.

6.       Вышегородцева А.И., Ситник С.М. О применении методов теории функций комплексного переменного к задаче о локализации точки относительно многоугольника, возникающей при сжатии данных видеонаблюдения. Чернозёмный альманах научных исследований. Серия "Фундаментальная математика".№ 1 (8), 2009, С. 324--339.

7.       Недошивина А.И., Ситник С.М. Применение методов теории функций комплексного переменного к одной задаче компьютерной геометрии. Сборник материалов Всероссийской научно-практической конференции "Охрана, безопасность и связь-2009". Воронежский институт МВД России, Воронеж, 2010, С. 202--203.

8.       Недошивина А.И. Об одной задаче компьютерной геометрии, применяемой при сжатии результатов видеонаблюдений. Международная конференция молодых ученых «Математический анализ и математическое моделирование», Владикавказ, (Учреждение Российской академии наук Южный математический институт ВНЦ РАН и РСО-А; 2010г.).

9.       Недошивина А.И. О локализации областей при видеонаблюдении. Международная конференция Современные методы и проблемы теории операторов и гармонического анализа и их приложения. Тезисы докладов, Ростов-на-Дону, Южный Федеральный университет, 2012г. С.85-86

10.   Недошивина А.И. Сжатие видеоинформации с использованием методов теории функций комплексного переменного. Информационная безопасность в государственных и негосударственных структурах, “Информтех-2012”. Сборник материалов. Юго-Западный государственный университет, Курск 2012, C.45-50.