informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-527Research ArticleАВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯCOMPUTER AIDED DESIGNТеоретико-множественная операция объединения многоугольников в задачах топологического проектированияSet-theoretic operation of polygons unification on a plane 1БутовА. А.ButovA. A.

кандидат технических наук, доцент

Cand. Sci. (Eng.), Assoc. Prof.

tmkrb9@gmail.comБелорусский государственный университет информатики и радиоэлектроники, МинскBelarusian State University of Informatics and Radioelectronics20190612201816193102Copyright © Бутов А.А., 20192019Бутов А.А.Butov A.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/527

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

The methods for performing the set-theoretic operation of combining topological objects defined as polygons on a plane are developed. The basic concepts and definitions associated with the consideration of a polygon and a combination of two intersecting polygons are given. The analysis of various options for intersection of the sides of polygons is performed. The rules, that allow to identify the degenerate intersection points of polygons sides to reduce the number of fragments in their borders and to clarify the status of possible intersection points, are formulated. Two methods of combining of polygons are proposed: a simpler basic method for solving a wide range of practical problems, and more complex general method, applicable also to topological objects, which are described by multiply connected polygons with "emptiness". The article refers to the research related to a general task of developing a software system for preparing topological information for micro-indent image generators. 

САПР СБИСтопологическое проектированиевычислительная геометриятеоретикомножественные операцииобъединение многоугольниковCAD VLSItopological designcomputational geometryset-theoretic operationsunion of polygonsReferencesФейнберг, В. З. Геометрические задачи машинной графики больших интегральных схем / В. З. Фейнберг. – М. : Радио и связь, 1987. – 178 с.Fejnberg V. Z. Geometricheskie zadachi mashinnoy grafiki bol’shih integralnyh shem. Geometric Problems of Computer Graphics of Large Integrated Circuits. Moscow, Radio i svjyaz', 1987, 178 p. (in Russian).Автоматизированная система подготовки информации для формирования фотошаблонов / Е. А. Шестаков [и др.] // Искусственный интеллект. – 2008. – № 4. – С. 200–207.Shestakov E. A., Butov A. A., Orlova T. L., Voronov A. A. Avtomatizirovannaya sistema podgotovki informacii dlya formirovaniya fotoshablonov [Automated system for preparing information for forming photomasks]. Iskusstvennyy intellect [Artificial Intelligence], 2008, no. 4, pp. 200–207 (in Russian).The automated system of input data preparation for integrated circuit layout generators / E. Shestakov [et al.] // Proc. Intern. Conf. "Neural Networks and Artificial Intelligence" (ICNNAI’2008). – Minsk, 2008. – P. 217–219.Shestakov E., Butov A., Orlova T., Voronov A. The automated system of input data preparation for integrated circuit layout generators. Proceedings International Conference "Neural Networks and Artificial Intelligence" (ICNNAI’2008), Minsk, 2008, pp. 217–219.Препарата, Ф. Вычислительная геометрия: введение : пер. с англ. С. А. Вичеса, М. М. Комарова ; под ред. Ю. М. Банковского / Ф. Препарата, М. Шеймос. – М. : Мир, 1989. – 478 с.Preparata F., Sheymos M. Computational Geometry: Introduction. New York, Springer-Verlag, 1985, 478 p.Ласло, М. Вычислительная геометрия и компьютерная графика на C : пер. с англ. / М. Ласло. – М. : БИНОМ, 1997. – 304 с.Laslo M. Vychislitel’naya geometriya i kompyuternaya grafika na C++. Computational Geometry and Computer Graphics in C ++. Englewood Cliffs, NJ, Prentice Hall, 1996, 304 p.Закревский, А. Д. Логический синтез каскадных схем / А. Д. Закревский. – М. : Наука, 1981. – 416 с.Zakrevskij A. D. Logicheskij sintez kaskadnyh shem. Logical Synthesis of Cascade Circuits. Moscow, Nauka, 1981, 416 p. (in Russian).Шестаков, Е. А. Декомпозиция многосвязного многоугольника в множество прямоугольников / Е. А. Шестаков // Вестник Брестского гос. техн. ун-та. Физика, математика, информатика. – 2008. – № 5. – С. 82–86.Shestakov E. A. Dekompoziciya mnogosvyaznogo mnogougol’nika v mnozhestvo pryamougol’nikov [Decomposition of a multiply connected polygon into a set of rectangles]. Vestnik Brestskogo gosudarstvennogo tehnicheskogo universiteta. Fisika, matematika, informatika [Bulletin of Brest State Technical University. Physics, Mathematics, Computer Science], 2008, no. 5, pp. 82–86 (in Russian).Шестаков, Е. А. Декомпозиция многосвязного многоугольника в множество ортогональных многоугольников / Е. А. Шестаков, А. А. Воронов // Вестник Брестского гос. техн. ун-та. Физика, математика, информатика. – 2008. – № 5. – С. 87–91.Shestakov E. A., Voronov A. A. Dekompoziciya mnogosvyaznogo mnogougol’nika v mnozhestvo ortogonalnyh mnogougol’nikov [Decomposition of a multiply connected polygon into a set of orthogonal polygons]. Vestnik Brestskogo gosudarstvennogo tehnicheskogo universiteta. Fisika, matematika, informatika [Bulletin of Brest State Technical University. Physics, Mathematics, Computer Science], 2008, no. 5, pp. 87–91 (in Russian).Бутов, А. А. Метод объединения множества пересекающихся контуров / А. А. Бутов // Вестник Брестского гос. техн. ун-та. Физика, математика, информатика. – 2008. – № 5. – С. 65–70.Butov A. A. Metod objedineniya mnozhestva peresekayushhihsya konturov [The method of combining theМинимизация площади заказных СБИС на этапе топологического проектирования цифровых схем / Л. Д. Черемисинова [и др.] // Управляющие системы и машины. – 2012. – № 4. – С. 42–50.set of intersecting contours]. Vestnik Brestskogo gosudarstvennogo tehnicheskogo universiteta. Fisika, matematika, informatika [Bulletin of Brest State Technical University. Physics, Mathematics, Computer Science], 2008, no. 5, pp. 65–70 (in Russian).Бутов, А. А. Устранение избыточности в покрытии топологического объекта прямоугольниками / А. А. Бутов // Доклады БГУИР. – 2017. – № 8. – С. 13–20.Cheremisinova L. D., Bazilevich R. P., Loginova I. P., Scherbyuk I. F., Bazilevich L. V. Minimizatsiya ploschadi zakaznyh SBIS na etape topologicheskogo proektirovaniya tsifrovyh shem [Minimization of the area ofБутов, А. А. Анализ корректности покрытия многосвязного многоугольника / А. А. Бутов, Е. А. Шестаков // Вестник Брестского гос. техн. ун-та. Физика, математика, информатика. – 2008. – № 5. – С. 57–60.custom VLSI at the stage of topological design of digital circuits]. Upravlyayuschie sistemy i mashiny [Control Systems and Machines], 2012, no. 4, pp. 42–50 (in Russian).Butov A. A. Ustranenie izbytochnosti v pokrytii topologicheskogo objekta pryamougolnikami [About elimination the redundancy in coverage of a topological object with rectangles]. Doklady BGUIR [Reports of the Belarusian State University of Informatics and Radioelectronics], 2017, no. 8, pp. 13–20 (in Russian).Butov A. A. Ustranenie izbytochnosti v pokrytii topologicheskogo objekta pryamougolnikami [About elimination the redundancy in coverage of a topological object with rectangles]. Doklady BGUIR [Reports of the Belarusian State University of Informatics and Radioelectronics], 2017, no. 8, pp. 13–20 (in Russian).Butov A. A., Shestakov E. A. Analiz korrektnosti pokrytiya mnogosvyaznogo mnogougol’nika [Elimination of redundancy in the coverage of a topological object with rectangles]. Vestnik Brestskogo gosudarstvennogo tehnicheskogo universiteta. Fisika, matematika, informatika [Bulletin of Brest State Technical University. Physics, Mathematics, Computer Science], 2008, no. 5, pp. 57–60 (in Russian).Butov A. A., Shestakov E. A. Analiz korrektnosti pokrytiya mnogosvyaznogo mnogougol’nika [Elimination of redundancy in the coverage of a topological object with rectangles]. Vestnik Brestskogo gosudarstvennogo tehnicheskogo universiteta. Fisika, matematika, informatika [Bulletin of Brest State Technical University. Physics, Mathematics, Computer Science], 2008, no. 5, pp. 57–60 (in Russian).

The authors declare that there are no conflicts of interest present.