Простой метод нахождения булевой формулы многоугольника в дизъюнктивной нормальной форме

Abstract

Предложен достаточно простой и приемлемый на практике метод решения задачи построения булевой формулы многоугольника в дизъюнктивной нормальной форме, Метод основан на использовании двух простых операций: 1) вычисление угла между прямыми; 2) проверка факта принадлежности вершин многоугольника выпуклой компоненте. Простота метода снимает проблему вычислительной точности. Последняя заключается в том, что хотя теоретически можно строго обосновать правильность работы алгоритма, однако на практике встречаются задачи, для которых алгоритм не работает или работает некорректно в силу ограниченной точности представления вещественных чисел в памяти компьютера и потери точности в промежуточных вычислениях. Метод может быть использован, в частности, в системах автоматизированного проектирования топологии интегральных схем.