Анализ корректности покрытия многосвязного многоугольника

Abstract

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