Теоретико-множественная операция пересечения топологических объектов-многоугольников на плоскости

Abstract

Технологический процесс изготовления сверхбольших интегральных схем включает в себя целый ряд этапов, одним из которых является подготовка с помощью систем автоматизированного проектирования входной информации для генератора изображений фотонаборной установки. Для каждого объекта топологии создается изображение, которое составляется из отдельных областей-прямоугольников, объединение которых дает изображение всего объекта. Создание управляющей программы для генерации изображения порождает большое число задач, многие из которых решаются методами вычислительной геометрии и оперируют обычно геометрическими объектами типа многоугольник или прямоугольник. При решении такого рода задач часто возникает необходимость в использовании теоретико-множественных операций над многоугольниками, позволяющих находить их объединение, пересечение и разность. Целью данной работы явилась разработка способов выполнения теоретико-множественной операции пересечения над топологическими объектами типа многоугольник. В работе проанализированы различные варианты пересечения сторон многоугольников между собой и введены понятия вырожденных и возможных точек пересечения. Сформулированы правила, позволяющие выявить вырожденные точки пересечения сторон многоугольников с целью уменьшения числа фрагментов, на которые разбиваются границы многоугольников точками пересечения, а также уточнить статус возможных точек пересечения. Предложены два метода нахождения пересечения многоугольников: более простой базовый метод, применимый для решения широкого круга практических задач, и более сложный общий метод, применяемый на практике значительно реже. Материал статьи относится к исследованиям, связанным с общей задачей по разработке программной системы подготовки топологической информации для микрофотонаборных генераторов изображений.