Set-theoretic operation of polygons unification on a plane 1
Abstract
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.
About the Author
A. A. Butov
Belarusian State University of Informatics and Radioelectronics
Belarus
Cand. Sci. (Eng.), Assoc. Prof.
Belarus
Cand. Sci. (Eng.), Assoc. Prof.
References
1. 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).
2. 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).
3. 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.
4. Preparata F., Sheymos M. Computational Geometry: Introduction. New York, Springer-Verlag, 1985, 478 p.
5. 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.
6. Zakrevskij A. D. Logicheskij sintez kaskadnyh shem. Logical Synthesis of Cascade Circuits. Moscow, Nauka, 1981, 416 p. (in Russian).
7. 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).
8. 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).
9. Butov A. A. Metod objedineniya mnozhestva peresekayushhihsya konturov [The method of combining the
10. 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).
11. 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
12. 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).
13. 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).
14. 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).
Review
For citations:
Butov A.A. Set-theoretic operation of polygons unification on a plane 1. Informatics. 2019;16(1):93-102. (In Russ.)
Views: 942
Email this article 