ТЕОРЕТИКО-МНОЖЕСТВЕННАЯ ОПЕРАЦИЯ ПЕРЕСЕЧЕНИЯ ТОПОЛОГИЧЕСКИХ ОБЪЕКТОВ-МНОГОУГОЛЬНИКОВ НА ПЛОСКОСТИ

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

1. Фейнберг В.З. Геометрические задачи машинной графики больших интегральных схем. Москва: Радио и связь; 1987.

2. Шестаков Е.А., Бутов А.А., Орлова Т.Л., Воронов А.А. Автоматизированная система подготовки информации для формирования фотошаблонов. Искусственный интеллект. 2008;4:200-207.

3. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Москва: Мир; 1989.

4. Шестаков Е.А. Декомпозиция многосвязного многоугольника в множество прямоугольников. Вестник Брестского государственного технического университета. Физика, математика, информатика. 2008;5:82-86.

5. Бутов А.А. Устранение избыточности в покрытии топологического объекта прямоугольниками. Доклады БГУИР. 2017;8:13-20.

6. Бутов А.А. Теоретико-множественная операция объединения многоугольников в задачах топологического проектирования. Информатика. 2019;16(1):93-102.