КАНОНИЧЕСКИЕ БУЛЕВЫ ФОРМУЛЫ МНОГОУГОЛЬНИКОВ
Full Text:
Abstract
Рассматривается задача о принадлежности точки многоугольнику, заданному на плоскости последовательностью угловых точек. В основу метода ее решения положены получение множества ориентированных прямых, продолжающих отрезки границы многоугольника, и переход в пространство соответствующих предикатов типа «точка расположена левее прямой». Предлагается метод построения представляющей многоугольник канонической булевой формулы над введенными предикатами. Задача о принадлежности сводится к подстановке в формулу координат рассматриваемой точки в пространстве предикатов.
About the Author
А. Закревский
Объединенный институт проблем информатики НАН Беларуси
Belarus
References
1. Рвачев, В.Л. Геометрические приложения алгебры логики / В.Л. Рвачев. – Киев : Техника, 1967.
2. Поттосин, Ю.В. Использование булевых функций для представления многоугольников / Ю.В. Поттосин, Е.А. Шестаков // Вестник Томского гос. ун-та. Управление, вычислительная техника и информатика. – 2008. – № 2 (3). – C. 106–115.
For citations:
. Informatics. 2009;1(2(22)):93-101.
(In Russ.)
Views: 471