VIII Международная студенческая научная конференция Студенческий научный форум - 2016

Применение векторной алгебры, аналитической геометрии, теории матриц достаточно четко прослеживается в вычислительной геометрии. [1 – 2]. Области плоскости, ограниченные многоугольниками, можно задать посредством булевых функций, основоположником которых является английский математик и логик Дж. Буль (1815- 1864 гг.).

Часто метод булевых функций применяется для решения разнообразных задач распознавания закономерностей, проектирования цифровых механизмов, рассмотрения надежности систем [1]. В этой работе покажем, что область применения аппарата булевых функций не ограничивается перечисленными задачами.

Рассмотрим основные понятия.

Расположим на плоскости точки a и b, зададим им координаты и в декартовой системе, где и – переменные, связанные в соответствии с осью абсцисс OX и с осью ординат OY, совпадают, если и [1] Точки будут неодинаковыми, если хоть одно из неравенств не реализовывается [1]. Точки и на плоскости связанные прямой линией, создают отрезок ab [1]. Стало быть, точки плоскости, находящиеся на настоящей прямой, относятся к представленному отрезку [1]. В отрезке точки a и b являются граничными. Нанесем на плоскость различные точки . Рассмотри отрезки образованные точками Таким образом, у нас образовалась замкнутая ломанная . Вершинами ломанной являются точки a, b, c, d, … , k, m, а сторонами ломанной отрезки .Если две стороны ломанной берут начало из одной из граничных точек, то они будет являться соседними. Граничная точна при этом будет именоваться точкой соединения.

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

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

В след за тем рассмотрим непересекающиеся замкнутые ломанные и именовать их будем просто ломанными [1].

Анализируемая мной ломанная делит плоскость на две части. В одной части находится точки плоскости, находящиеся внутри ломаной , в другой части – точки плоскости, находящиеся вне [1]. Часть плоскости, находящаяся внутри ломанной , образует многоугольник [1]. При этом сторона ломанной будет именоваться стороной многоугольника Многоугольник соответственно должен состоять более чем из трех сторон. На сторонах многоугольника разместим точки плоскости, они могут принадлежать или многоугольнику, или данной плоскости [1]. Если некоторая точка плоскости, находящаяся на некоторой стороне ломаной, принадлежит многоугольнику то всякая другая точка этой стороны также ему принадлежит, и если некоторая точка на стороне ломаной L не принадлежит многоугольнику M, то и любая иная точка этой стороны не принадлежит ему . Булева функция зависящая от n булевых аргументов, воссоздается как [3].Обозначим векторную переменную, выходит, булеву функцию можем рассмотреть как функцию от векторного аргумента Под значением x* векторной переменной будем полагать булев вектор [3].

Многоугольник и деление плоскости на выпуклые подобласти.

Проведем прямую линию , пересекающую отрезок , а также уравнение представленной прямой [1]. Возьмем точку c на плоскости, обозначенную координатами В уравнение прямой , подставим координаты прямой точки С, в результате получим число . Поделим плоскость на две части: и прямой . Допустим, что число является положительным, в настоящем случае точка плоскости с принадлежит области [1]. Предположим, что число, есть число отрицательное, таким образом, точка c является точкой области[1]. В случае, если число равняется нулю, соответственно точка c относится к прямой [1]. Чаще всего прямая делит плоскость на две части. В первостепенной части находится область , а также точки, принадлежащие, во второстепенной – область В том случае, если с точка c принадлежит первой из этих частей[1]. В противоположном случае точка c является частью второстепенной части. Наименуем эти части плоскости должным образом и [1]. Прямая делит плоскость на части и . Тогда точка c принадлежит если , и точка c принадлежит если[1]. Предположим многоугольник M ограничен ломаной L. Проведем через каждую сторону многоугольника прямую . Данные прямые делят плоскость на конечное число областей[3].

Пример 1. Рассмотрим многоугольник , приведенный на рис.1. Вершины многоугольника M заданы в соответствии координатами = 7; [3].

Многоугольник задается ломаной , которая состоит из отрезков Прямые, прочерченные через стороны этого прямоугольника, на рис. 1 намечены пунктирными линиями [3]. Точки пересечения данных прямых обозначены латинскими буквами [1]. Эти прямые разделяют плоскость на 14 областей [1]. Четыре из этих областей являются многоугольниками: Остальные 10 областей ограничены ломаными и лучами, идущими из концевых точек этих ломаных. Эти области намечены большими латинскими буквами: [3].

Так, одна из таких областей, которая помечена на рис. 1 буквой A, ограничена отрезками, а также лучами, идущим из точек и и являющимися продолжениями отрезков Считаем, что точки, находящиеся на отрезках ломаной L, не относятся к области [3]. Наоборот, точки, находящиеся на лучах, ограничивающих область , принадлежат этой области [3]. Область, помеченная на рис. 1 буквой , ограничена только двумя лучами. Лучи исходят из точки r, проходят через прямые и должно быть не содержат отрезки [3]. Точки, находящиеся на луче, проходящем через прямую , не принадлежат области E, а точки, находящиеся на луче, проходящем через прямую , принадлежат области [3].

Рис. 1. Многоугольник из примера 1

Области, на которые делят плоскость прямые, проведенные через грани многоугольника , будем именовать индуцированными многоугольником . Отрезки ломаных, а также лучи, ограничивающие эти области, назовем их сторонами [1]. Проанализируем некоторую область U, индуцированную многоугольником [1]. Предпочтем любую из ее сторон. Через эту сторону проходит прямая. Все точки области находятся в одной из полуплоскостей, на которые эта прямая делит плоскость [3]. Таким образом, все области, индуцированные многоугольником M, являются выпуклыми. При этом сам многоугольник состоит из некоторого подмножества областей, индуцированных им [3]. Эти области являются выпуклыми многоугольниками.

Булева функция многоугольника

Возьмем прямую . Совместим данной прямой и с обусловливающим ее отрезком предикат

Предикат-(n – местный, или n – арный) – это функция с множеством значений {0,1} (или {ложь, истина}) определенная на множестве . Таким образом, каждый набор элементов множества М характеризуется либо как «истинный», либо как «ложный». [2]

Рассмотрим точку с координатами выполняется, то . Если , то . Отсюда следует, если точка c является частью области плоскости , то . Если точка c принадлежит области плоскости то

Допустим, необходимо рассмотреть полуплоскостии то предикат uab будет таким, что , если , иначе [3]. Возьмем многоугольник . Обозначим его стороны и положим, что стороне соответствует обозначение ). Через сторону проведем прямую, и поставим в соответствие предикат Обозначим точку , внутри многоугольника , при условии, что точка не принадлежащую стороне. Предположим число ) положительно, то предикат равняется 1 для любой точки плоскости , соответствующий неравенству. В другом случае Допустим, число имеет отрицательное значение, то для любой точки плоскости , соответствует неравенству . В другом случае . Определи для всех сторон многоугольника предикаты.,так как делали это ранее. На множестве данных предикатов зададим векторную переменную Для каждой точки плоскости можно найти значение предиката , где ) [1]. Отсюда следует, что точки t возможно найти единственный булев вектор [1].Проанализируем предложенную область U, индуцированную многоугольником .

Математическая индукция – метод доказательства для последовательности натуральных чисел либо объектов, однозначно занумерованных натуральными числами [2].

Утверждение 1. Любые две точки плоскости и относятся к области U [1], им соответствует равенство

Доказательство. Разберём прямую , пересекающую сторону многоугольника M. Данной прямой сопоставлен в соответствие предикат . Точки и относятся к области U, соответствующе эти точки находятся в одной из полуплоскостей [3], на которые разделяется плоскость прямой . Отсюда следует, компоненты со значением q в векторах и равны. Это соответствует для любой грани многоугольника M, т. е. Утверждение доказано. Вышесказанное позволяет мне сделать вывод о том, что всем точкам области U соответствует один и тот же булев вектор, который обозначим через. Разберем две различные области U1 и U2, индуцированные многоугольником M.

Утверждение 2.

Доказательство. Допустим, точка лежит в области U1, а точка t2 – области . Из способа построения индуцированных областей следует, что существует в многоугольнике сторона , такая, что точки плоскости и принадлежат разным полуплоскостям, на которые делит прямая плоскость [1]. Предположим, данной прямой сопоставлен предикат [1]. Значит, булевы вектора ) и будут различными по значению компоненты с номером [1]. Утверждение доказано.

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

Для решения последующих задач, действенно может быть применена булева функция. Предположим для кое-какого многоугольника M, намеченного контуром, найдена его булева функция . Контур состоит из n сторон, каковым приписаны надлежащие предикаты . Требуется для заданной своими координатами точки плоскости p аргументировать, где находится точка в многоугольнике или нет. Для того чтобы решить данную задачу надобно найти для точки p булев вектор.

Допустим, тогда точка является частью многоугольника М, тогда когда ,в этом случае точка р не принадлежит многоугольнику

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

Список используемых источников

1. Поттосин Ю.В., Шестаков Е.А. / Использование булевых функций для представления многоугольников. / Журнал: Вестник томского государственного университета. Выпуск №2 / (2008г.) [Электронный ресурс]. - Режим доступа: http://cyberleninka.ru

2. Википедия. Свободная энциклопедия [Электронный ресурс]. – Режим доступа: https://ru.wikipedia.org

3. Рефераты на Refereed.ru [Электронный ресурс] - http://refereed.ru

Код для цитирования: Скопировать