Preview

Доклады БГУИР

Расширенный поиск

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

https://doi.org/10.35596/1729-7648-2019-126-8-58-65

Полный текст:

Аннотация

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

Об авторе

А. А. Бутов
Белорусский государственный университет информатики и радиоэлектроники
Беларусь

Бутов Алексей Александрович, к.т.н., доцент, доцент кафедры экономической информатики

220013, г. Минск, ул. П. Бровки, д. 6



Список литературы

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.


Для цитирования:


Бутов А.А. ТЕОРЕТИКО-МНОЖЕСТВЕННАЯ ОПЕРАЦИЯ ПЕРЕСЕЧЕНИЯ ТОПОЛОГИЧЕСКИХ ОБЪЕКТОВ-МНОГОУГОЛЬНИКОВ НА ПЛОСКОСТИ. Доклады БГУИР. 2019;(7-8):58-65. https://doi.org/10.35596/1729-7648-2019-126-8-58-65

For citation:


Butov A.A. SET-THEORETIC OPERATION OF INTERSECTION OF TOPOLOGICAL OBJECTS-POLYGONS ON THE PLANE. Doklady BGUIR. 2019;(7-8):58-65. (In Russ.) https://doi.org/10.35596/1729-7648-2019-126-8-58-65

Просмотров: 113


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1729-7648 (Print)
ISSN 2708-0382 (Online)