Пересечение выпуклых оболочект.

Пусть р будет монотонный полигон и переименуем его вершины как v 1 , v 2 ,..., v n в порядке увеличения координаты х, поскольку наш алгоритм будет обрабатывать эти вершины именно в таком порядке. Алгоритм формирует последовательность монотонных полигонов р = p 1 , p 2 ,... , p n = 0. Полигон p i , как результат обработки вершины v i , получается путем отсечения нуля или нескольких треугольников от предыдущего полигона p i-1 . Алгоритм заканчивает свою работу после выхода с p m , пустым полигоном, а коллекция треугольников, накопленная в процессе обработки, представляет собой триангуляцию исходного полигона р.

Алгоритм хранит стек s вершин, которые были проверены, но еще не обработаны полностью (возможно, обнаружены еще не все треугольники, связанные с этой вершиной). Перед началом обработки вершины v i в стеке содержатся некоторые вершины, принадлежащие полигону p i-1 . По мере выполнения алгоритма сохраняются определенные инварианты стека(Инвариантом называется состояние, существующее на определенной стадии работы алгоритма, например, в начале каждой итерации данного цикла). Пусть вершины в стеке обозначены как s 1 , s 2 ,..., s t в порядке снизу вверх, тогда могут встретиться четыре ситуации:

1. s 1 , s 2 ,..., s t упорядочены по возрастанию координаты х и содержат каждую из вершин полигона p i-1 , расположенную справа от s 1 и слева от s t .
2. s 1 , s 2 ,..., s t являются последовательными вершинами либо в верхней, либо в нижней цепочках полигона p i-1 .
3. Вершины s 1 , s 2 ,..., s t являются вогнутыми вершинами полигона p i-1 (величина внутреннего угла при каждой из них превышает 180 градусов).
4. Следующая подлежащая обработке вершина v i в полигоне p i-1 находится в следующем соотношении с вершинами s t и s 1:
   • a. v i соседняя с s t , но не с s 1 ,
   • б. v i соседняя с s 1 , но не с s t ,
   • в. v i соседняя с обеими вершинами s 1 и s t .

Все эти три случая условия 4 показаны на рис. 2.

Действия по обработке вершины v i будут различны для каждого из этих трех случаев, отражающих текущее состояние стека:

Рис. 2

Случай 4а. Вершина v i соседняя с s t , но не с s 1 : Если t > 1 и внутренний угол v i s t s t-1 меньше 180 градусов, то отсекается треугольник v i s t s t-1 и s t исключается из стека. После этого в стек заносится v i . В алгоритме используется тот факт, что угол v i s t s t-1 < 180 только в том случае, когда либо s t-1 лежит слева от вектора v i s t , если v i принадлежит полигону p i-1 из верхней цепочки, либо s t-1 лежит справа от вектора v i s t , если v i принадлежит нижней цепочке.

Ядром полигона называется подмножество его точек, из которых виден весь полигон. В частности, ядро выпуклого полигона - он сам. Полигон называется веерообразным , если ядро содержит одну или более вершин - корней полигона.

Случай 46. Вершина v i соседняя с s 1 , но не с s t . Отсекаем полигон, определяемый вершинами v i , s 1 , s 2 ,..., s t , очищаем стек и затем заносим в него сначала s t , потом v i . Полигон, определяемый вершинами v i , s 1 , s 2 ,..., s t фактически является веерообразным с узлом в точке v i (т. е. вершина v i принадлежит корню веера). После этого алгоритм выполняет триангуляцию полученного полигона.

Случай 4в.

Вершина v i соседняя с обеими вершинами s 1 и s t:

В этом случае v i = v n и полигон p i-1 , определяемый вершинами v i , s 1 , s 2 ,..., s t , является веерообразным с узлом в точке v n . Алгоритм непосредственно выполняет триангуляцию этого полигона и заканчивается.

На рис. 3 показан процесс работы алгоритма при решении простой задачи (порядок выполнения шагов сверху вниз и слева направо). На каждом шаге обрабатываемые вершины отмечены кружком, а вершины в стеке обозначены последовательностью s 1 , s 2 ,..., s t .

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

Enum (UPPER, LOWER); List *triangulateMonotonePolygon(Polygon &p} { Stack s; List *triangles = new List; Vertex *v, *vu, *vl; leastVertex(p, leftToRightCmp); v = vu = vl = p.v(); s.push(v); int chain = advancePtr(vl, vu, v); s.push(v); while (1) { // внешний цикл while chain = advancePtr(vl, vu, v); if (adjacent(v, s.top()) && !adjacent(v, s . bottom ())) {// случай 4a int side = (chain == UPPER) ? LEFT: RIGHT; Vertex *a = s.top(); Vertex *b = s.nextToTop(); while ((s. size() > 1) && (b->classify(v->point() ,a->point()) == side)) { if (chain == UPPER) { p.setV(b); triangles->append (p.split(v)); } else { p.setv (v); triangles->append (p.split(b)); } s.pop(); a = b; b = s.nextToTop(); } s.push (v); } else if (! adjacent (v, s.top())) { // случай 4б Polygon *q; Vertex *t = s.pop(); if (chain == UPPER) { p.setV(t); q = p.split(v); } else { p.setV(v); q = p.split(t); q->advance(CLOCKWISE); } triangulateFanPolygon (*q, triangles); while (! s.empty ()) s.pop(); s.push(t); s.push(v); } else { // случай 4в p.setV (v); triangulateFanPolygon (p, triangles); return triangles; } } // конец внешнего цикла while }

Функция adjacent возвращает значение TRUE только в том случае, если две указанные в обращении вершины, являются соседними.

Bool adjacent (Vertex *v, Vertex *w) { return ((w == v->cw()) || (w = v->ccw())); }

Рис. 3

Программа triangulateMonotonePolygon при обработке полигона р анализирует одновременно верхнюю и нижнюю цепочки полигона, используя преимущества уже выполненного упорядочения вершин по возрастанию координаты х (в противном случае потребовалась бы дополнительная сортировка за время О(n log n)). На каждой итерации переменная v указывает на обрабатываемую вершину. В программе формируются еще две переменные vu и vl, которые указывают на последнюю обрабатываемую вершину в верхней и нижней цепочках полигона р соответственно. По мере работы программы эти указатели функцией advancePtr продвигаются слева направо. При каждом обращении к функции advancePtr она изменяет значение либо vu, либо vl и корректирует указатель v в соответствии с произведенным изменением:

Int advancePtr(Vertex* &vu, Vertex* &vl, Vertex* &v} { Vertex *vun = vu->cw(); Vertex *vln = vl->ccw(); if (vun->point() < vln->point()) { v = vu = vun; return UPPER; } else { v = vl = vln; return LOWER; } }

Функция advancePtr возвращает значение UPPER или LOWER, показывающее, к какой из двух цепочек вершин v относится произведенное действие. Это значение используется в программе triangulateMonotonePolygon для контроля, чтобы ее последующее обращение к функции split вызывало возврат части, выделенной из основного полигона, а не основного полигона, из которого эта часть исключена.

При триангуляции веерообразного полигона последовательно находятся все треугольники, имеющие одну корневую вершину и. Для этого полигон обходится, начиная с вершины v, и в каждой вершине w, не являющейся соседней с v, отсекается треугольник по хорде, соединяющей вершины v и w. Это выполняется функцией triangulateFanPolygon, которая деструктивно разбивает n-угольник р на n - 2 треугольников и добавляет их в список треугольников. В функции предполагается, что полигон р веерообразный с окном, расположенным на его корне:

Void triangulateFanPolygon(Polygon &p, List *triangles) { Vertex *w = p.v()->cw()->cw(); int size = p.size(); for (int i = 3; i < size; i++) { triangles->append(p.split(w)); w = w->cw(); } triangles->append(&p); }

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

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

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

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

Как видите, появился новый полигон, и все границы автоматически добавлены. Ведь мы рисовали не все границы. Несмотря на то, что данная процедура очень похожа на топологичное покрытие, это не так. Прочитайте "Шаг 3 - Понятие топологии" . Граница для двух объектом должны быть одна, а мы можем, воспользовавшись инструментом указатель

Взять и отодвинуть любую площадь.

Вернуть назад можно командой Undo .

Шаг 28 - Вырезание из площади

Обычно карта ограничена рамкой, и границы полигонов должны точно стыковаться с границей карты. Если мы будем поступать, как в прошлом шаге , то у нас граница будет не ровная. Можно сделать по другому. Удалим нашу темуBASEA .

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

Воспользуемся инструментом прямоугольник.

И нарисуем рамку, которая покрывает весь чертеж.

В инструментах рисования полигона у нас есть тот, который может нам помочь.

Выберем его и попробуем отрезать кусок.

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

Шаг 29 - Прозрачность площадной темы

Рисовать как в прошлом шаге - это рисовать наугад. Но у площадной темы есть легенда, значит мы можем настроить отображение. Идем в легенду, щелкаем два раза на символе.

У нас в площадной легенде есть четыре понятия. Первое понятие - это заливка.

Я выбрал точечную, чтобы сквозь точки было видно рисунок внизу. Дальше цвет значков в заливке - Foreground .

Здесь я поставил, что фона нет. И последнее понятие - цвет границы Outline .

Все можно нажимать OK и сквозь Вашу тему будет просвечиваться тема ниже.

Шаг 30 - Копирование темы

Разобравшись с рамкой в прошлом шаге тут же возникает вопрос. Ведь у нас можем быть много тем, которые содержат площади и должны содержать одну и туже рамку. Самый простой выход - это воспользоваться возможностью копирования темы в ArcView . После того, как тема создана, Вы можете воспользоваться пунктом менюConvert .

После выбора этого пункта меню у Вас опять спросят имя новой темы.

Укажите его и у Вас будет точно такая же тема в проекте с другим именем.

Шаг 31 - Линейная тема

Добавляется точно так же как и остальные темы, только тип нужно выбрать LINE .

Использование

Если флажок установлен (опция neighbor_option установлена как IDENTIFY_NEIGHBORS в скриптах), для каждого выходного объекта будет сохранена информация о соседних полигонах. Как показано выше, границы конвертируются в линии, с учетом пересечений и общих сегментов; два новых поля, LEFT_FID и RIGHT_FID, будут добавлены в выходной класс объектов и установлены на идентификаторы объектов входных полигонов слева и справа от каждой выходной линии. Атрибты входных объектов не будут поддерживаться в выходном классе объектов. Ниже детально проанализирован сам процесс и варианты выходных данных:

• В полигональной геометрии, выходная граница всегда строится в направлении по часовой стрелке. Если полигон имеет отверстие, граница отверстия (или внутренняя) всегда строится в направлении против часовой стрелки. Таким образом, для полигона, у которого нет соседей слева (с внешней стороны) от его внешней границы и слева (с внутренней стороны) от границы отверстия, результирующие линии будут иметь значение -1 для LEFT_FID и идентификатор полигонального объекта как RIGHT_FID.
• Если полигон содержит другой полигон, будет создана одна выходная линия в направлении по часовой стрелке, представляющая общую границу, где LEFT_FID установлен на идентификатор объекта внешнего полигона, а RIGHT_FID установлен на идентификатор объекта внутреннего полигона.
• Если два полигона имеют общую часть границы, будет создана одна выходная линия, представляющая общий сегмент. Направление линии будет произвольным; LEFT_FID и RIGHT_FID будут установлены на идентификатор левого и правого полигональных объектов соответственно.
• Если полигон перекрывает другой полигон, будут созданы две выходные линии, представляющие каждую границу пересечения дважды: первая линия будет представлять внешнюю границу одного из перекрывающихся полигонов, таким образом, LEFT_FID - это идентификатор объекта полигона, который он пересекает, а RIGHT_FID будет ее собственным идентификатором полигона; вторая линия будет в противоположном направлении, разбивая другие полигоны, таким образом LEFT_FID и RIGHT_FID будут такими же, как другие идентификаторы полигонального объекта.
• Составные объекты во входных полигонах не поддерживаются; все выходные линии простые.

• Если флажок Идентифицировать и хранить информацию о соседних полигонов не установлен (neighbor_option установлено на IGNORE_NEIGHBORS в скриптах), информация о соседних полигонах будет игнорироваться. Каждая граница входного полигона будет записана как отдельный линейный объект. Составной полигон станет составной линией в выходных данных. Атрибуты входных объектов будут скопированы в выходной класс объектов. Новое поле, ORIG_FID, будет добавлено к выходным даным и установлено на идентификатор входного объекта каждой линии.

  Для входных объектов параметрических (истиных) кривых, выходные линии остануться истиными кривыми, даже если они разбиты. Не применяется к данным шейп-файла.

Синтаксис

PolygonToLine_management (in_features, out_feature_class, {neighbor_option})

Пример кода

Полигон в линию. Пример 1 (окно Python)

Пример скрипта Python для выполнения функции Полигон в линию (Polygon To Line) с запуском из окна Python в ArcGIS.

import arcpy from arcpy import env env . workspace = "C:/data" arcpy . PolygonToLine_management ("Habitat_Analysis.gdb/vegtype" , "C:/output/Output.gdb/vegtype_lines" , "IGNORE_NEIGHBORS" )

Полигон в линию. Пример 2 (автономный скрипт)

Пример скрипта Python для выполнения функции Полигон в линию (Polygon To Line) в автономном режиме.

# Name: PolygonToLine_Example2.py # Description: Use PolygonToLine function to convert polygons to lines, # and report how many shared or overlapping boundary lines # were found. # # import system modules import arcpy from arcpy import env # Set environment settings env . workspace = "C:/data/landcovers.gdb" # Create variables for the input and output feature classes inFeatureClass = "bldgs" outFeatureClass = "bldgs_lines" # Use error trapping in case a problem occurs when running the tool try : # Run PolygonToLine to convert polygons to lines using default neighbor_option arcpy . PolygonToLine_management (inFeatureClass , outFeatureClass ) # Select lines that have LEFT_FID values greater than -1 arcpy . MakeFeatureLayer_management (outFeatureClass , "selection_lyr" , " \" LEFT_FID \" > -1" ) result = arcpy . GetCount_management ("selection_lyr" ) if (result . getOutput (0 ) == "0" ): print "No overlapping or shared boundary lines were found." else : print result . getOutput (0 ) + " overlapping or shared " + \ "boundary lines were found." except Exception , e : # If an error occurred, print line number and error message import traceback , sys tb = sys . exc_info ()[ 2 ] print "Line %i " % tb . tb_lineno print e . message