Using Boolean Function for Representation of Polygons .pdf Для решения задач вычислительной геометрии успешно применяются аналитическая геометрия, векторная алгебра, теория матриц [1 - 4]. Цель настоящей работы состоит в том, чтобы показать, как посредством булевых функций можно задавать области плоскости, ограниченные многоугольниками. Такое представление дает возможность эффективно решать некоторые задачи вычислительной геометрии, связанные с многоугольниками. Традиционно аппарат булевых функций широко используется для решения разнообразных задач проектирования цифровых устройств, распознавания закономерностей, анализа надежности систем [5]. Данная работа является примером того, что область применения аппарата булевых функций не ограничивается перечисленными задачами.1. Основные определенияТочки плоскости a и b, заданные соответственно координатами (xa, ya) и (xb, yb) в декартовой системе, где х и у - переменные, связанные соответственно с осью абсцисс OX и с осью ординат OY, совпадают, если xa = xb и ya = yb. Если хотя бы одно из этих равенств не выполняется, то точки считаются различными. Отрезком ab называется пара различных точек a и b плоскости, соединенных прямой линией. Точки плоскости, находящиеся на этой прямой, принадлежат данному отрезку. Точки a и b отрезка ab называются граничными. Рассмотрим различные точки плоскости a, b, c, d, ... , k, m. Соединим эти точки отрезками ab, bc, cd, ... , km, ma. Получим замкнутую ломанную, которую обозначим через L = abcd...km. Точки a, b, c, d, ... , k, m называются вершинами ломаной L, а отрезки ab, bc, cd, ... , km, ma - сторонами ломаной L. Две стороны ломаной L называются соседними, если одна из их граничных точек является общей. Общую граничную точку соседних сторон назовем точкой соединения.Два отрезка пересекаются, если существует хотя бы одна точка плоскости, принадлежащая каждому из них. Если такая точка отсутствует, то отрезки не пересекаются.Замкнутая ломаная L является непересекающейся, если любая точка, общая для двух ее сторон, является граничной для этих и только для этих сторон.В дальнейшем будем рассматривать только непересекающиеся замкнутые ломаные, которые будем называть просто ломаными.Ломаная L делит плоскость на две части. Одна часть содержит точки плоскости, находящиеся внутри ломаной L, другая - точки плоскости, находящиеся вне L. Под многоугольником M будем понимать часть плоскости, находящуюся внутри замкнутой ломаной L. Сторону такой ломаной L будем называть стороной многоугольника M. Многоугольник, очевидно, не может иметь менее трех сторон.Точки плоскости, находящиеся на сторонах многоугольника, могут по договоренности, обусловленной условиями конкретной задачи, отнесены либо к многоугольнику, либо к остальной части рассматриваемой плоскости. Если некоторая точка плоскости, находящаяся на некоторой стороне ломаной L, принадлежит многоугольнику M, то любая другая точка этой стороны также ему принадлежит, и если некоторая точка на стороне ломаной L не принадлежит многоугольнику M, то и любая другая точка этой стороны не принадлежит ему.Под булевой функцией f(x1, x2, ... , xn), зависящей от n булевых аргументов, понимается отображение /: {0, 1}" - {0, 1}. Введем векторную переменную x = (x1, x2, ... , xn), тогда булеву функцию f(x1, x2, ... , xn) можно рассматривать как функцию от векторного аргумента fx). Под значением x* векторной переменной x будем понимать булев вектор (xi*, x2*, ... , xn*), где либо x,* = 0, либо x,* = 1 (i = 1, 2, ... , n).2. Многоугольник и деление плоскости на выпуклые подобластиОбозначим через Pab прямую линию, проходящую через отрезок ab, а также уравнение этой прямой. Рассмотрим некоторую точку плоскости с, заданную координатами (xc, yc). Подставив координаты точки c в уравнение прямой Pab, получим число Pab(o).Прямая Pab делит плоскость на две части: Pab+ и Pab-. Точка плоскости c принадлежит области Pab+, если число Pab(e) является положительным. Если это число является отрицательным, то точка c принадлежит области Pab-. Если число Pab(e) равно нулю, то точка c принадлежит прямой Pab. Обычно считается, что прямая Pab делит плоскость на две части. В одну из них входит область Pab+, а также точки, принадлежащие Pab, в другую часть - область Pab-. Точка c принадлежит первой из этих частей, если и только если Pab(e) > 0. В противном случае точка c принадлежит второй части. Обозначим эти части плоскости соответственно через Pab~ и Pab. В этом случае точка c принадлежит Pab~, если Pab(e) < 0, и точка c принадлежит Pab>, если Pab(с) > 0.Пусть многоугольник M ограничен ломаной L. Проведем через каждую сторону ij многоугольника M прямую P,y. Эти прямые делят плоскость на конечное число областей.Пример 1. Рассмотрим многоугольник M, приведенный на рис.1. Вершины a, b, c, d, e многоугольника M заданы соответственно координатами xa = 1, ya = 7; xb = 6, yb = 6; xc = 6, yc = 12; xd = 11, yd = 7; xe = 6, ye = 2. Многоугольник задается ломаной L, которая состоит из отрезков ab, bc, cd, de и ae.Прямые, проведенные через стороны этого прямоугольника, на рис. 1 обозначены пунктирными линиями. Точки пересечения этих прямых помечены латинскими буквами. Эти прямые делят плоскость на 14 областей. Четыре из этих областей являются многоугольниками: L1 = abe, L2 = ebt, L3 = bcdt, R = drt. Остальные 10 областей ограничены ломаными и лучами, исходящими из концевых точек этих ломаных. Эти области помечены большими латинскими буквами: A, B, C, D,E, F, G, H, S, T. Так, одна из таких областей, которая помечена на рис. 1 буквой A, ограничена отрезками ab, bc, а также лучами, исходящим из точек a и с и являющимися продолжениями отрезков ае и cd. Считаем, что точки, находящиеся на отрезках ломаной L, не принадлежат области A. Наоборот, точки, находящиеся на лучах, ограничивающих область A, принадлежат этой области. Область, помеченная на рис. 1 буквой E, ограничена только двумя лучами. Лучи исходят из точки r, проходят через прямые Pcd, Pab и соответственно не содержат отрезки cd, ab. Точки, находящиеся на луче, проходящем через прямую Pcd, не принадлежат области E, а точки, находящиеся на луче, проходящем через прямую Pab, принадлежат области E.Области, на которые делят плоскость прямые, проведенные через грани многоугольника M, назовем индуцированными многоугольником M. Отрезки ломаных, а также лучи, ограничивающие эти области, назовем их сторонами.Рассмотрим некоторую область U, индуцированную многоугольником M. Выберем любую из ее сторон. Через эту сторону проходит прямая. Все точки области U находятся в одной из полуплоскостей, на которые эта прямая делит плоскость. Следовательно, все области, индуцированные многоугольником M, являются выпуклыми. При этом сам многоугольник M состоит из некоторого подмножества Li, L2, Lv областей, индуцированных им. Эти области являются выпуклыми многоугольниками.Пример 2. Многоугольник, приведенный в примере 1, состоит из трех индуцированных областей L1 = abe, L2 = ebt, L3 = bcdt.3. Булева функция многоугольникаРассмотрим некоторую прямую Pab. Свяжем с этой прямой и с определяющим ее отрезком ab предикат uab. Будем считать, что, если для некоторой точки с, заданной координатами (xc, yc), выполняется Pab(e) > 0, то uab(c) = 1. Если Pab(e) < 0, то uab(c) = 0. Таким образом, если точка c принадлежит области плоскости Pab~, то uab(c) = 1. Если точка c принадлежит области плоскости Pab, то предикат uab будет таким, что uab(c) = 1, если Pab(c) < 0, иначе uab(c) = 0.Рассмотрим многоугольник M. Пронумеруем его стороны и положим, что стороне ij соответствует номер q = N(ij). Прямой, проведенной через сторону ij, поставим в соответствие предикат uq = uy. Выберем точку c, расположенную внутри многоугольника M, но не принадлежащую стороне ij. Если число Py(c) положительно, то предикат uq принимает значение 1 для любой точки плоскости t, удовлетворяющей неравенству Py(t) > 0. Иначе uq= 0. Если число Py(c) отрицательно, то uq= 1 для любой точки плоскости t, удовлетворяющей неравенству Py(t) < 0. Иначе uq= 0. Поставим всем сторонам многоугольника вышеуказанным способом предикаты {u1, u2, ... , un}. Зададим на множестве этих предикатов векторную переменную u = (u1, u2, ... , un). Для каждой точки t плоскости можно найти значение uq* предиката uq, где (1 < q < n). Следовательно, для точки t можно найти единственный булев вектор u*(t) = (u1*, u2*, ... , un*).Рассмотрим некоторую область U, индуцированную многоугольником M.Утверждение 1. Для любых двух точек плоскости t1 и t2, принадлежащих области U, выполняется равенство u*(t1) = u*(t2).Доказательство. Рассмотрим прямую Py, проходящую через сторону ij многоугольника M. Этой прямой сопоставлен в соответствие предикат uq (q = N(ij)). Точки ti и t2 принадлежат области U, поэтому обе эти точки находятся в одной из полуплоскостей, на которые делится плоскость прямой Py. Следовательно, компоненты с номером q в векторах u*(t1) и u*(t2) равны. Это справедливо для любой грани многоугольника M, т. е. u*(t1) = u*(t2). Утверждение доказано.Таким образом, всем точкам области U соответствует один и тот же булев вектор, который обозначим через u*(U).Рассмотрим две различные области Ui и U2, индуцированные многоугольником M.Утверждение 2. u*(U1) * u*(U2).Доказательство. Пусть точка t1 принадлежит области U1, а точка t2 - области U2. Из способа построения индуцированных областей следует, что существует в многоугольнике M сторона ij, такая, что точки плоскости ti и t2 принадлежат разным полуплоскостям, на которые делит прямая Py плоскость. Положим, что этой прямой сопоставлен предикат uq. Тогда булевы вектора u*(U1) и u*(U2) будут отличаться друг от друга по значению компоненты с номером q. Утверждение доказано.Пример 3. Рассмотрим многоугольник M, представленный на рис. 1. Уравнения прямых, проходящих через эти отрезки, имеют следующий канонический вид:Pab = x + 5y - 36 = 0; Pbc = x - 6 = 0; Pcd = x + y - 18 = 0; Pde = x-y - 4 = 0; Pae = x +y - 8 = 0. Отрезкам ab, bc, cd, de и aе припишем соответственно предикаты и1, u2, u3, u4 и u5, значения которых определим следующим образом:и1 = 1, если x + 5y - 36 < 0; и2 = 1, если x - 6 > 0; и3 = 1, если x + y - 18 < 0;и4 = 1, если x - y - 4 < 0; и5 = 1, если x + y - 8 > 0. В остальных случаях каждый из предикатов имеет значение 0.На множестве введенных предикатов зададим векторную переменную u = (u1, u2, u3, u4, u5). В табл. 1 приведены булевы векторы, соответствующие индуцированным областям рассматриваемого многоугольника.Таким образом, каждой области, индуцированной многоугольником M, однозначно соответствует булев вектор, однако не всякому булеву вектору соответствует некоторая индуцированная область. Это видно на примере многоугольника на рис. 1.Пример 4. Многоугольник из рис. 1 индуцирует 14 областей, а булево пространство размерности 5 состоит из 25 = 32 векторов. Нетрудно определить остальные 18 векторов, для которых нет соответствующих индуцированных областей: {(0,0,0,0,0), (0,0,0,0,1), (0,0,0,1,0), (0,0,1,0,0), (0,0,1,0,1), (0,1,0,0,0), (0,1,0,1,0), (0,1,1,0,0), (0,1,1,1,0), (1,0,0,0,0), (1,0,0,0,1), (1,0,0,1,0), (1,0,0,1,1), (1,0,1,0,1), (1,1,0,0,0), (1,1,0,1,0), (1,1,0,1,1), (1,1,1,1,0)}.Подмножество значений векторной переменной и, которым сопоставлены области, индуцированные многоугольником M, обозначим через ZM. Подмножество значений векторной переменной и, которым не поставлены во взаимное соответствие области, индуцированные многоугольником M, обозначим через QM и назовем областью запрета.Пусть многоугольник M имеет n сторон. Для каждой стороны j многоугольника M определен предикат uq, где q = N(ij). Из этих предикатов составлена векторная переменная и = (ub u2, ... , u„). Пусть также для многоугольника M найдены все области P1, P2, ... , Pm, индуцированные им. Из множества полученных областей Р = {Pi, P2, ... , Pm} выделено подмножество областей L = {Li, L2, ... , /„}, которые находятся внутри многоугольника M. Для всякой области из множества P найдем соответствующий ей булев вектор, т. е. сформируем множество ZM и по этому множеству построим область запрета QM. Теперь многоугольнику M можно приписать частичную булеву функцию fM(u) такую, что fM(u*) = 1, если булев вектор и* принадлежит множеству ZM и поставлен в соответствие одному из многоугольников подмножества L; fM(u*) = 0, если u*e ZM и булев вектор и* поставлен в соответствие одному из многоугольников подмножества P \ L; и значение fM(u*) не определено, если u* е QM. Эта неопределенность обусловлена тем, что никакая точка не может попасть за пределы бесконечной плоскости. Следовательно, при данной интерпретации переменная и никогда не примет значение из множества Qm, и на этом множестве функцию fM(U) можно доопределить как угодно.Если при решении некоторой задачи на многоугольнике требуется вычислять значения функции fM(u), то естественно иметь такую форму представления этой функции, чтобы эти вычисления имели наименьшую сложность. В частности, такой формой может быть минимальная дизъюнктивная нормальная форма (ДНФ). Чтобы ее получить, достаточно воспользоваться любым известным методом минимизации частичной булевой функции в классе ДНФ [5].Пример 5. Для многоугольника M на рис. 1 в табл. 1 приведены значения векторной переменной и, составляющие множество ZM. Частичная булева функция fM(u) может быть задана двумя матрицами [5]. Строки одной из них, U0, представляют значения вектора и, где fM(u) = 0, строки другой, U1, - значения вектора и, где fM(U) = 1. Для рассматриваемого многоугольника имеемU\ug u4 u

Скачать электронную версию публикации