Триангуляция монотонных полигонов.

Теперь рассмотрим проблему вычисления области пересечения двух выпуклых полигонов P и Q . За исключением особо оговоренных случаев будем предполагать, что два полигона пересекаются невырожденно : пересечение двух ребер происходит в одной единственной точке, не являющейся вершиной какого-либо полигона. Учитывая такое предположение о невырожденности , всегда получим, что полигон состоит из попеременных цепочек из Р и Q . Каждая пара последовательных цепочек соединяется в точке пересечения, в которой пересекаются границы полигоновP и Q (рис. 6.11).

Существует несколько решений этой задачи с линейной зависимостью времени выполнения от суммарного числа вершин. Описываемый здесь алгоритм обладает особым изяществом и его легко применять. Для двух заданных на входе выпуклых полигонов P и Q алгоритм определяет окно на ребре полигона P ещё одно окно на ребре полигона Q . Идея заключается

Рис. 6.11. Структура полигона пересечения .

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

Для объяснения работы оказывается весьма полезным ввести понятие серпа. На рис. 6.12 серпами будут шесть затененных полигонов. Каждый из них ограничен цепочкой, взятой от полигона P , и цепочкой от полигона Q , ограниченных двумя последовательными точками пересечения. Внутренней цепочкой серпа будет та часть, которая принадлежит полигону пересечения. Отметим, что полигон пересечения окружен четным числом серпов, внутренние цепочки которых попеременно являются частями границ полигонов P и Q .

Рис. 6.12. Серпы, окружающие полигон пересечения.

В терминах серпов алгоритм поиска полигона пересечения проходит две фазы. В процессе первой фазы окно p полигона P и окно q полигона Q перемещаются в направлении по движению часовой стрелки до тех пор, пока они не будут установлены на ребрах, принадлежащих одновременно одному и тому же серпу. Каждое окно начинает свое движение с произвольной позиции. Здесь для краткости будем использовать один и тот же символ p для обозначения как окна полигона P , так и ребра в этом окне. Тогда термин "начало p " будет относиться к точке начала ребра в окне полигона P , а команда "продвинуть p " будет означать, что необходимо переместить окно полигона P на следующее ребро. Аналогичным образом буквой q будем обозначать как окно полигона Q , так и ребро в окне. Иногда ребра p и q будем считать текущими ребрами.

Во время фазы 2 p и q продолжают перемещаться в направлении по часовой стрелке, но на этот раз они двигаются в унисон от одного серпа к соседнему серпу. Перед тем как любое окно перейдет из текущего серпа в соседний , ребра p и q пересекутся в точке пересечения, соединяющей оба серпа. Полигон пересечения строится именно во время второй фазы. Перед каждым перемещением p конечная точка ребра p заносится в полигон пересечения, если ребро p принадлежит внутренней цепочке текущего серпа. Аналогичным образом перед перемещением q фиксируется конечная точка ребра q , если q принадлежит внутренней цепочке текущего серпа. При каждом пересечении ребер p и q точка пересечения, в которой они пересекаются, записывается в полигон пересечения.

Для принятия решения, какое из окон должно перемещаться, в алгоритме используется правило перемещения. Это правило основано на следующих замечаниях: говорят, что ребро a нацелено на ребро b , если бесконечная прямая линия, определяемая ребром b , расположена перед а (рис. 6.13).

Рис. 6.13. Только показанные толстыми линиями ребра нацелены на ребро q , остальные - нет.

Ребро a нацелено на b , если выполняется одно из условий:

Заметим, что соотношение соответствует случаю, при котором угол между векторами a и b меньше 180 градусов.

Функция aimsAt возвращает значение TRUE , если и только если ребро a нацелено на ребро b . Параметр aclass указывает на положение конечной точки а.dest относительно ребра b .

Параметр crossType принимает значение COLLINEAR , если и только если ребра a и b коллинеарные.

bool aimsAt (Edge & а , Edge &b, int aclass , int crossType )
{Point2 va = a.dest a.org;
Point2 vb = b.dest b.org;
if (crossType != COLLINEAR)
{if((va.x * vb.y ) >= (vb.x * va.y ))
return (aclass != RIGHT);
else
return (aclass != LEFT);
}
else
{return (aclass != BEYOND);
}
}

Если ребра a и b коллинеарны , то ребро a нацелено на b , если конечная точка a.dest не лежит после b . Это обстоятельство используется для того, чтобы продвинуть a вместо b , когда два ребра пересекаются вырожденно более, чем в одной точке. Позволяя a "догонять" b , мы обеспечиваем, что ни одна точка пересечения не будет пропущена.

Возвратимся к обсуждению правил перемещения. Они сформулированы таким образом, чтобы не пропустить следующую точку пересечения. Правила отличают текущее ребро, которое может содержать следующую точку пересечения, от текущего ребра, которое возможно не может содержать следующей точки пересечения, причем в этом случае окно переносится вполне безопасно. Правила перемещения различают четыре ситуации, показанные на рис. 6.14. Здесь ребро a считается находящимся вне ребра b , если конечная точка a.dest расположена слева от b .

Рис. 6.14. Четыре правила перемещения: (а) - продвинуть p ; (б) - продвинуть p ; (в) - продвинуть p , (г) - продвинуть р.

1. p и q нацелены друг на друга: перемещается окно, соответствующее тому ребру (p или q ), которое находится снаружи другого. В ситуации рис. 6.14 а должно быть перенесено окно на ребре р . Следующая точка пересечения не может лежать на p , поскольку ребро p находится вне полигона пересечения.

2. p нацелено на q , но q не нацелено на p p p не находится снаружи q и затем окно p переносится. На рис. 6.14б ребро p не может содержать следующей точки пересечения (хотя оно может содержать некоторую точку пересечения, если p находится не снаружи от q ). На рис. показана ситуация, в которой ребро p , окно которого должно быть перенесено, не находится снаружи от ребра q .

3. q нацелено на p , но p не нацелено на q : конечная концевая точка ребра q заносится в полигон пересечения, если q не находится снаружи от p , после чего переносится окно q (рис. 6.14в). Этот случай симметричен предыдущему. На рис. показана ситуация, при которой ребро q , окно которого должно быть перенесено, находится снаружи от ребра p .

4. p и q не нацелены друг на друга: переносится то окно, которое относится к ребру, расположенному снаружи от другого. Согласно рис. 6.14 необходимо перенести окно p , поскольку ребро p находится снаружи от ребра q .

Работа алгоритма показана на рис. 6.15. Каждое ребро имеет метку i , если оно обрабатывается на шаге i (у некоторых ребер показана двойная метка, поскольку они обрабатываются дважды). Два начальных ребра имеют

Рис. 6.15. Поиск полигона пересечения. Для ребра указана метка i , если оно обрабатывается на шаге i . Два начальных ребра обозначены меткой 0.

метку 0 . На этом рисунке фаза 2 (когда два текущих ребра оказываются принадлежащими одному и тому же серпу) начинается после трех итераций. Алгоритм реализован в программе convexPolygonIntersect . Программе передаются полигоны P и Q , она возвращает указатель на результирующий полигон пересечения R . Обращение к функции advance использовано для переноса одного из двух текущих ребер и для включения конечной концевой точки ребра в полигон R в соответствии с выполнением определенных условий. Используются окна, существующие внутри класса Polygon .

enum (UNKNOWN, P_IS_INSIDE, Q_IS_INSIDE) ;
Polygon *convexPolygonIntersect (Polygon &P, Polygon &Q)
{Polygon *R;
Point iPnt , startPnt ;
int inflag = UNKNOWN;
int phase = 1;
int maxItns = 2 * (P.size О + Q.size О);
// начало цикла for
for (int i = 1; (i <=maxItns ) || (phase==2); i++ )
{Edge p = P.edge ();
Edge q = Q.edge ();
int pclass = p.dest.classify (q );
int qclass = q.dest.classify (p );
int crossType = crossingPoint (p , q , iPnt );
if (crossType == SKEW_CROSS)
{ if (phase == 1)
{phase = 2;
R = new Polygon ;
R->insert (iPnt );
startPnt = iPnt ;
}
else
if (iPnt != R->point())
{if (iPnt != startPnt )
R->insert(iPnt );
else
return R;
}
if (pclass ==RIGHT)
inflag = P_IS_INSIDE;
else
if(qclass ==RIGHT)
inflag = Q_IS_INSIDE;
else inflag = UNKNOWN;
}
else
if((crossType ==COLLINEAR) &&
(pclass != BEHIND) && (qclass != BEHIND))
inflag = UNKNOWN;
bool pAIMSq = aimsAt (p, q, pclass , crossType );
bool qAIMSp = aimsAt (q, p, qclass , crossType );
if (pAIMSq && qAIMSp )
{if ((inf lag == Q_IS__INSIDE)||
((inflag == UNKNOWN)&&(pclass ==LEFT)))
advance(P, *R, FALSE);
else
advance(Q, *R, FALSE);
}
else
if(pAIMSq )
{advance(P, *R, inflag == P_IS_INSIDE);
}
else
if (qAIMSp )
{advance(Q, *R, inflag == Q_IS_INSIDE);
}
else
{if ((inflag == Q_IS_INSIDE)
((inflag == UNKNOWN) && (pclass == LEFT)))
advance(P, *R, FALSE);
else
advance(Q, *R, FALSE);
}
}
// конец цикла for
if (pointInConvexPolygon (P.point (), Q))
return new Polygon(P);
else
if (pointlnConvexPolygon (Q.point (), P))
return new Polygon(Q);
return new Polygon;
}

Если после выполнения итераций не будет обнаружено ни одной точки пересечения, то основной цикл завершается, поскольку это означает, что границы полигона не пересекаются. Последующие обращения к функции pointInConvexPolygon производятся с целью обнаружения ситуаций , или =0. В противном случае, если найдена некоторая точка пересечения iPnt , то алгоритм продолжает построение полигона пересечения R и останавливается только после того, как точка iPnt будет обнаружена вторично.

Переменная inflag показывает, какой из двух входных полигонов находится в данный момент внутри другого - т. е. указывает на полигон, текущее ребро которого находится в составе внутренней цепочки текущего серпа. Более того, переменная inflag принимает значение UNKNOWN (неизвестно) во время первой фазы, а также всякий раз, когда оба текущих ребра коллинеарны или перекрывают друг друга. Значение этой переменной меняется при каждом обнаружении новой точки пересечения.

Процедура advance продвигает текущее ребро полигона A , представляющее либо P , либо Q . Эта же процедура заносит конечную концевую точку ребра x в полигон пересечения R , если A находится внутри другого полигона и x не была последней точкой, записанной в R :

void advance(Polygon2 &A, Polygon2 &R, int inside)
{A.advance (CLOCKWISE);
if(inside && (R.point () != A.point ()))
R. insert (A.point ()) ;
}

Анализ и корректность.

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

Корректность алгоритма следует из двух утверждений:

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

Рассмотрим сначала утверждение 1. Предположим, что p и q принадлежат одному и тому же серпу и q достигает некоторой точки пересечения раньше, чем р . Мы покажем, что тогда q останется неподвижным, пока p не достигнет точки пересечения после ряда последовательных продвижений. Могут возникнуть две ситуации. Сначала предположим, что p находится снаружи от q (рис. 6.16а). При этом q останется фиксированным, пока p будет продвигаться согласно нулю или нескольким применениям правила 4, затем нулю или нескольким применениям правила 1 и потом нулю или нескольким применениям правила 2. Во второй ситуации предположим, что p не находится снаружи от q (рис. 6.16б). Здесь q будет оставаться фиксированным, пока p будет продвигаться путем нуля или нескольких применений правила 2. В симметричной ситуации, когда p достигает точки пересечения раньше, чем q , ребро q остается фиксированным, а ребро q продвигается до точки встречи. Это можно показать аналогичным образом, только меняется роль p и q и правило 3 заменяет правило 2. Из этого следует утверждение 1.

Чтобы показать утверждение 2, предположим, что границы P и Q пересекаются. После итераций либо p , либо q должны совершить полный оборот вокруг своего полигона. Предположим, что это произошло с р . В некоторый момент времени ребро p должно расположиться так, что оно будет содержать точку пересечения, в которой полигон Q переходит извне полигона P внутрь его. Это происходит потому, что существуют по крайней мере две точки пересечения и направление пересечения меняется. Пусть q будет ребром внутри окна полигона Q в момент обнаружения такого р .

На рис. 6.17 граница полигона Q разбита на две цепочки и . Первая цепочка заканчивается в ребре , в том ребре полигона Q , которое входит внутрь полигона P через его ребро p . Другая цепочка заканчивается

Рис. 6.16. Продвижение к следующей точке пересечения.

в ребре , конечная точка которого лежит справа от бесконечной прямой линии, определяемой ребром p , и она наиболее удалена от этой прямой линии. Следует рассмотреть два случая в зависимости от того, какой из двух цепочек принадлежит ребро q :

Случай 1 . Здесь p остается фиксированным, тогда как q продвигается согласно нулю или нескольким применениям правила 3, затем правила 4, потом правила 1 и, наконец, правила 3, когда обнаруживается точка пересечения.

Случай 2 . Здесь q остается фиксированным, а p продвигается согласно нулю или нескольких применений правила 2, затем правила 4, потом правила 1 и, наконец, правила 2 в момент, когда p окажется внутри q . С этого момента оба ребра p и q могут продвигаться несколько раз, однако ребро q не может быть продвинуто за его следующую точку пересечения, пока p сначала не достигнет предыдущей точки пересечения ребра q (если этого уже не произошло с ребром p ). Поскольку p и q заканчиваются в одном и том же серпе, утверждение 1 гарантирует, что после некоторого числа дополнительных продвижений они пересекутся в точке пересечения, в которой заканчивается текущий серп.

Чтобы показать, что достаточно итераций для поиска некоторой точки пересечения, заметим, что при доказательстве утверждения 2 (о том, что граница полигона Q входит внутрь полигона P через ребро p при произвольном положении ребра q ) начальные позиции p и q достигались при выполнении не более итераций. Фактически такая ситуация, либо симметричная ей, в которой роли p и q взаимно заменяются, достигается за меньшее число итераций. Поскольку после этого ни p , ни q не будут продвинуты на полный оборот прежде, чем будет достигнута первая точка пересечения, потребуется не более дополнительных продвижений.

Рис. 6.17. Иллюстрация к доказательству, что можно найти точку пересечения, если границы P и Q пересекаются.

Пусть р будет монотонный полигон и переименуем его вершины как 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 вершин.

Poly много+ gonia угол. 1 . мат. Многоугольник (замкнутый или незамкнутый). БАС-1. Также вышеупомянутые грунтрис я желал такова, каким образом чертят сию маниру и с кругом или четвероугольника и зачинают с которого полигона - внешнего или внутренного. 1712. ПБП 12 (1) 99. || Замкнутый и незамкнутый многоугольник на местности и на плане. БАС-1. ♦ Крепостной полигон . Расположение крепостных сооружений в форме многоугольника . БАС-1. Атаки с двух сторон к Азову вести наискорее: первую, действительную, против обоих полигонов бастиона.. водяных ворот и к доку; другую фос-атаку - по реке Дону. 1736. Осада Азова. // СВИМ 3 188. Против прожектированному, для прикрывания некоторых каменных небольших зделал я новые три полигона с равелинами. 1737. М. А. Муравьев Зап. // РОА 5 13. Изъяснение крепостного плана. 1). Два полигона, кои уже тут находятся для укрепления линии a, b, c, d. 1763. Бецкой Прил. 13. По предписанным правилам сделаны конструкции (сочинения) для всех правильных полигонов от 4 до 12 сторон. 1777. Кург. Кн. науки воен. 55. Для закрытия главного вала в полигонах.. назначены полумесяцы (demi-lune ) и контр-гарды; фланки во всех земли полигонах защищены большими орлионами и имеют в себе казематы для горизонтальной рва обороны. 1785. Потемкин Бум. 131. Соразмерно сему взять и Севастопольского укрепления полигон, который вышел гораздо меньше определенного гг. Вобаном и Кегорном, ибо у первого обороны 150, а у последнего 180 тоазов. 1785. Потемкин Бум. 131. Полигон <крепости> остается прежний. Гарнизон отвечает протяжению линии фортов. План обороны должен строиться к сокращению полигона. Осада Порт-Артура. // Из боевого прошлого 319. || Сторона крепости . Положение Екатеринбурхской крепости - на ровном месте: один полигон к зюйду, другой к норду, третей к осту, четвертый к весту в Уральских горах. от которых около оного небольшие горы имеются. 1735. Геннин Опис. урал. и сиб. заводов. // Седой Урал 340. Редко случается, что неприятель своею атакою больше одной стороны крепости захватывает: и ежели своей атакою две и три стороны крепости (то есть три полигона) охватит, то только для занятия надлежащего места под положение батарей и против фланков атакованных бастионов сие учинит. 1744. Вобан 180. Обыкновенно в регулярных крепостях полагается для обороны на всякой полигон по баталиону . Тат. Лекс. // Т. Избр. 230. Она <крепость> имеет шесть полигонов регулярных, а по пропорции сей должно для защищения быть гарнизону двенадцати батальонам, которого здесь только три. Румянцев 2 110. Хотя есть крепости, имеющие менее шести полигонов. 1830. Вессель 227.

2. устар. Здание с многоугольным основанием. Павленков 1911. Находятся три большия сдания <так> Академии Наук особо, и суть ради берега в таком положении, будьто составляли часть многоугольнаго полигона. ГС 1801 1 70.

3. Границы какого-л. участка земли, сняты посредством обхода с помощью угломерного инструмента. Павленков 1911.

4. Участок местности, специально оборудованный для проведения испытаний технических средств вооружения, учебных артиллерийских стрельб и тренировок технических родов войск. БАС-1. Он отправился туда <в Африку>, как отправляются на охоту, в фехтовальный зал или полигон. Слово 1879 8 2 136. Учения на казарменном дворе и на полигоне, выправка солдат, чистка лошадей - сколько всем этим хлопот и беспокойства. Набл. 1888 4 1 249. С треском, гулом и грохотом, разражаясь пальбой, как пулемет на полигоне.. мчал это чудовище. Федин Братья. // Ф. 3 36. Инспектировали буи.., готовились к полигонам, провдили полигоны <в море>. О. Кучкина Голос золы. // Нева 2002 10 7. || расш . Регламентация вида и типа домов, застройки улиц, частей города были элементом тотального полицейского контроля над жизнью петербуржцев, который установился при Петре - истовом проповеднике концепции "регулярного" государства. Петербург стал настоящим полигоном для осуществления насильственно перевоспитываемых подданных. Звезда 2003 5 146.

5. Открытая площадка с оборудованием для изготовления элементов сборных конструкций и деталей. СИС 1985. БАС-1.

6. Свалка мусора вне города в специально отведенном месте . Сов. Рос. 4. 7. 1987.

7. шутл., угол. Площадь . Мокиенко 2000.

8. арест. Плац в ИТУ . Мокиенко 2000.

9. Из лексикона игроков в ролевые игры . За границы полигона не выходить. Запись 1999. Мокиенко 2000. - Лекс. Ян. 1806: полигон; САН 1847: полиго/н.

Исторический словарь галлицизмов русского языка. - М.: Словарное издательство ЭТС http://www.ets.ru/pg/r/dict/gall_dict.htm . Николай Иванович Епишкин [email protected] . 2010 .

Синонимы :

Смотреть что такое "полигон" в других словарях:

ПОЛИГОН - (греч., от polys многий, и gonia угол). 1) многоугольник. 2) место за городом, где происходит артиллерийское учение, пальба из орудий. 3) в фортификации: линия, соединяющая углы двух смежных бастионов. Словарь иностранных слов, вошедших в состав… … Словарь иностранных слов русского языка

полигон - автодром, многоугольник, капустин яр, стрельбище, планеродром, площадка, автополигон Словарь русских синонимов. полигон стрельбище Словарь синонимов русского языка. Практический справочник. М.: Русский язык. З. Е. Александрова. 2011 … Словарь синонимов

Полигон 2 - Жанр Комедия, Пародия, Ужасы Режиссёр Павел Фоминенко Продюсер Павел Фоминенко Автор сценария … Википедия

ПОЛИГОН - ПОЛИГОН, полигона, муж. (от греч. poly много и gonia угол). 1. Большой незаселенный участок, служащий местом для опытных или учебных занятий и упражнений специальных войск, стрельбище (воен.). Артиллерийский полигон. 2. Расположение крепостных… … Толковый словарь Ушакова

полигон - ПОЛИГОН, стрельбище … Словарь-тезаурус синонимов русской речи

Полигон - – вид производства железобетона, располагаемого на открытом воздухе, иногда имеющего навес (кровлю); входит в состав заводов железобетонных изделий или является самостоятельным предприятием. [Терминологический словарь по бетону и… … Энциклопедия терминов, определений и пояснений строительных материалов

ПОЛИГОН - (от греч. polygonos многоугольный) участок суши или моря, предназначен для испытаний оружия, военной техники, боевой подготовки войск …

ПОЛИГОН - то же, что многоугольник … Большой Энциклопедический словарь

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

Если флажок установлен (опция 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})

Параметр	Объяснение	Тип данных
	Входные объекты, которые должны быть полигонами.	Feature Layer
out_feature_class	Выходной класс линейных объектов.	Feature Class
(дополнительно)	Устанавливает, нужно ли идентифицировать и хранить информацию о соседних полигонах. IDENTIFY_NEIGHBORS -Информация о соседних полигонах будет сохраняться в выходных данных. Если различные сегменты полигона имеют общую границу с другими полигонами, граница будет разбита, так чтобы каждый уникально хранящийся сегмент стал линией с двумя идентификаторами соседних полигонов, хранящихся в выходных данных. Это значение используется по умолчанию. IGNORE_NEIGHBORS -Информация о соседних полигонах будет игнорироваться; граница каждого полигона станет линейным объектом с идентификатором исходного полигонального объекта, хранящимся в выходных данных.	Boolean

Пример кода

Полигон в линию. Пример 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

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

В форме свойств полигона пока­заны: его собственный номер, площадь, собственный условный знак, которым он будет изображаться в режиме Установки.
Ниже показана изменяемая ин­формация: групповая принадлежность, собственные символ и цвет, признак выбора (галочка). Если полигон относится к группе, которая не имеет базы данных в блоке, групповую при­надлежность полигона можно менять свободно. Если база данных для этой группы определена, полигон можно только Удалить и создать снова, уже другой группы.
Примечание. Если полигон отно­сится к группе с БД, изменить его группы можно с некоторыми ограничениями, используя отдельную специальную операцию изменения группы (см. 2.6.2.2)
Кнопка Указать позволяет ука­зать новое положение точки внутри полигона (выдела), на котором будет показана его метка (номер выдела или формула). Предварительную расстановку меток при создании полигонов TopoL выполняет автоматически, однако их положение для полигонов сложной формы может не быть удачным. Подправить придется вручную.
Кнопка OK подтверждает выполненную операцию, Cancel - отменяет. Кнопка Выход завершает операцию редактирования полигонов.
Кнопка БД атри­бутов вызыва­ет форму редактора текущей записи БД при полигонах, по­ка­зан­ную на рис. слева. Для примера здесь показанна запись"длин­ного" фор­мата (см. 6.3.3) полиго­нов группы 7550 - выделов, исполь­зуемого в ин­форма­ци­он­ной сис­те­ме TopoL_L.
Серые строчки в таблице - систем­ные поля БД блока, которые TopoL зано­сит и изменяет сам, редактировать их невозможно.
При создании новых полигонов группы, для которой определена БД блока, форма редактора записи БД полиго­нов вызывается автоматически сразу после создания полигона.
Кнопка Browse / Просмотреть поз­во­ляет увидеть сразу всю таблицу внутренней БД блока для выделов. Для просмотра БД в TopoL используется специальная форма (см. 2.6.6).
Кнопка Join / Связать позволяет увидеть через модель данных блока TopoL запись или записи присоединенной внешней базы данных, как показано на следующем рисунке. Для случая базы данных повыдельного блока через модель видна запись таксационной базы для того же выдела. Именно такой механизм доступа используется для тематической раскраски карт на основе данных таксации выделов.
Последняя кнопка Делить позволяет разделить полигон на две части с контролем площадей при делении. Эта операция может оказаться очень полезной, если требуется, чтобы площадь какого-то полигона точно соответствовала некоторой величине (например, чтобы площадь выдела культур на карте соответствовала документам). При ее нажатии появляется форма, показан­ная на рисунке слева.
Выполнить деление можно, либо автоматически, либо настраивая положение линии деления вручную, что дает бóльшую гибкость настрой­ки.
Автоматически деление выпол­няется только смещением заданной линии деления. Для автоматического деления нужно сначала настроить площади. В верхней части формы надо указать, какой из полигонов будет иметь Приоритет по площади, а под ним либо в верхней строке Область указать ожидаемую площадь правого полигона, либо под ним - левого полиго­на. Вы задаете желаемую площадь приоритетного полигона и щелкаете мышкой в поле площади второго - программа автоматически относит туда всю остальную площадь.
Затем надо задать направление линии деления. Направление задается либо явным указанием Угла, либо указанием мышкой в окне карты направления линии деления. Для указания мышкой надо в режиме Передвинуть нажать кнопку Указать параметры. Далее заданием двух точек задается направление линии деления. Для возврата в форму деления используется правая кнопка мышки.
После настройки параметров надо нажать кнопку Запуск. Полигон будет разделен в соответствии с заданными параметрами. Если результат автоматического деления Вам не понравился, отмените эту операцию (см. 1.12.2).
Для настройки и выполнения деления вручную площади задавать не нужно. Просто в нижней части формы настраиваются правила деления. Перераспре­делять площади между правым и левым полигонами можно либо смещением границы деления - Передвинуть, либо ее поворотом - Вращать. Для указания начальных параметров деления используется кнопка Указать параметры. В режиме смещения можно, указав мышкой две точки в окне карты, задать направление линии деления. В режиме поворота указывается одна точка, относительно которой вращается линия деления. Кнопка OK активизирует операцию деления, но деление можно начать и сразу после задания начальных параметров.
Для деления полигона используются стрелочные клавиши на клавиатуре. Нажатие на левую стрелку смещает или поворачивает линию деления влево, на правую - соответственно, вправо. В информационной строке ниже окна карты программа показывает площади левой и правой частей полигона. Стрелка вверх увеличивает шаг перемещения линии деления, стрелка вниз - уменьшает. Используя эти инструменты и постепенно уменьшая шаг смещение можно подобрать требуемые значения площадей.
Практический совет. Если требуется, чтобы площадь полигона инстру­мен­тального выдела точно соответствовала учетному значению, используйте операцию деления полигона. Можно в режиме деления построить последнюю замыкающую линию полигона между инструментальным и соседним полигонами, либо, если полигон уже существует и литерован, отрезать делением от него лишнюю площадь, затем этот осколок слиянием полигонов (см. ниже) присоединить к соседнему выделу. Если у исходного выдела площади не хватает, увеличить ее можно смещением узлов (см. 2.6.3.36).

2.6.2.2 Изменить код группы

Меню при кнопке позволяет вызывать операции с полигонами. Операция Изменить код группы позволяет переводить объекты из группы в группу. Перевести в заданную группу можно как все объекты одной или нескольких исходных групп, так и только выбранные объекты этих групп. Вид формы см. в разделе 2.6.3.14 . Если объекты исходной и целевой групп не имеют базы данных, этой операцией можно пользоваться свободно. Если объекты имеют базу данных одинакового формата, либо в целевой группе нет пока ни одного объекта, проблем также не будет - все атрибуты базы данных будут перемещены в целевую группу вместе с объектами. Но если форматы БД исходной группы и целевой различаются, при переводе потери данных БД избежать не удастся.

2.6.2.3 Сохранить атрибуты

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

2.6.2.4 Удалить выбранные

Операция Удалить выбранные просто удаляет все выбранные полигоны и связанные с ними записи БД блока. Линии границ полигонов остаются.

2.6.2.5 Слить указанные курсором

Операция Слить указанные курсором является расширением стандартного набора операций TopoL (см. рисунок слева). Она позволяет присоединить в указан­ному первым полигону ядра (выделен диагональной штриховкой) другие выбранные мышкой полигоны (показаны цветом выборки, здесь - красным). Резуль­тирующий слитый полигон имеет такие же атрибуты и запись базы данных, какие были у полигона ядра, но, соответственно, бóльшую площадь.
Эта операция похожа на операцию слияния выде­лов из линейки Таксация (см. 1.12.12), но в отличие от нее ничего не знает о содер­жании баз данных.

2.6.2.6 Создать все видимые

Операция Создать все видимые - способ автоматического создания сразу многих полигонов. Программа пытается создать все полигоны, которые можно создать при существующей топологии линий, и которые находятся в области видимости. Если требуется создать все возможные полигоны, надо сначала сделать видимым весь блок (см. 1.8.2).

2.6.2.7 Создать по заданным точкам

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

2.6.2.8 Корректировать топологию

Операция Корректировать топологию выполняет проверку и, при необхо­ди­мости, коррекцию топологии полигонов в блоке. Используется очень редко.