Метод объединения множества пересекающихся контуров

Abstract

Рассмотрена одна из классических задач вычислительной геометрии – задача объединения множества контуров, которая, в частности, может быть использована в автоматизированных системах подготовки и оптимизации входной информации для генераторов изображений микрофотонаборных установок. Цель работы заключается в том, чтобы для множества пересекающихся контуров B1, B2, …, Bn получить один результирующий контур Bn и некоторое, возможно пустое, множество так называемых контуров-разрезов С1, С2 ,…, Сp, задающих те внутренние области контура Bn, точки которых не принадлежат ни одному из объединяемых контуров. Объектом исследования является множество контуров – замкнутых ломаных, которыми моделируются элементы топологии фотошаблонов. Разработан метод объединения множества пересекающихся контуров, основу которого составляют такие операции, как маркировка концевых точек ребер контуров, преобразование ребер в чередующиеся отрезки прямых и формирование на их основе результирующего контура и контуров-разрезов. Предлагаемый метод позволяет, например, при изготовлении фотошаблонов проводить анализ корректности покрытия многосвязного многоугольника прямоугольниками.