Алгоритм декомпозиции геометрических объектов в 2D-задачах упаковки и раскроя
Введено клас базових 2D-об’єктів, для яких відомі Φ-функції. Доведено теорему про розбиття довільних φ-об’єктів, межа яких утворюється об’єднанням дуг кіл та відрізків прямих на базові об’єкти. Запропоновано покроковий алгоритм, який реалізує декомпозицію довільних двовимірних φ-об’єктів. Розглян...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2011 |
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84248 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Алгоритм декомпозиции геометрических объектов в 2D-задачах упаковки и раскроя / Ю.Г. Стоян, Н.И. Гиль, Т.Е. Романова, М.В. Злотник // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 28-37. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860098302832279552 |
|---|---|
| author | Стоян, Ю.Г. Гиль, Н.И. Романова, Т.Е. Злотник, М.В. |
| author_facet | Стоян, Ю.Г. Гиль, Н.И. Романова, Т.Е. Злотник, М.В. |
| citation_txt | Алгоритм декомпозиции геометрических объектов в 2D-задачах упаковки и раскроя / Ю.Г. Стоян, Н.И. Гиль, Т.Е. Романова, М.В. Злотник // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 28-37. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Введено клас базових 2D-об’єктів, для яких відомі Φ-функції. Доведено теорему про розбиття довільних φ-об’єктів, межа яких утворюється об’єднанням дуг кіл та відрізків прямих на базові об’єкти. Запропоновано покроковий алгоритм, який реалізує декомпозицію довільних двовимірних φ-об’єктів. Розглянутий підхід ефективний для побудови Φ-функцій довільних об’єктів при математичному та комп’ютерному моделюванні 2D-задач пакування та розкрою. Наведено результати чисельних експериментів. Іл.: 16. Бібліогр.: 12 назв.
We introduce a class of basic 2D-objects whose Φ-functions are known and prove a theorem on the decomposition, into basic objects, of an arbitrary φ-object whose boundary is formed by circular arñs and line segments. We provide a step-by-step decomposition algorithm for arbitrary two-dimensional φ-objects. The algorithm performs well to derive Φ-functions of arbitrary φ-objects in mathematical and computer modeling of packing and cutting problems. Numerical results are presented.
|
| first_indexed | 2025-12-07T17:27:40Z |
| format | Article |
| fulltext |
ÓÄÊ 519.85
Þ.Ã. ÑÒÎßÍ, Í.È. ÃÈËÜ, Ò.Å. ÐÎÌÀÍÎÂÀ, Ì.Â. ÇËÎÒÍÈÊ
ÀËÃÎÐÈÒÌ ÄÅÊÎÌÏÎÇÈÖÈÈ ÃÅÎÌÅÒÐÈ×ÅÑÊÈÕ ÎÁÚÅÊÒÎÂ
 2D-ÇÀÄÀ×ÀÕ ÓÏÀÊÎÂÊÈ È ÐÀÑÊÐÎß
Êëþ÷åâûå ñëîâà: äåêîìïîçèöèÿ, ðàñêðîé, óïàêîâêà, ãåîìåòðè÷åñêèå 2D-îáúåê-
òû, Ô-ôóíêöèÿ, ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå.
Çàäà÷è óïàêîâêè è ðàñêðîÿ (â äàëüíåéøåì çàäà÷è ðàçìåùåíèÿ) âîçíèêàþò âî
ìíîãèõ îòðàñëÿõ ïðîìûøëåííîñòè, â òîì ÷èñëå ìàøèíîñòðîåíèè, êîðàáëåñòðî-
åíèè, òåêñòèëüíîé, áóìàæíîé, ëåãêîé ïðîìûøëåííîñòè, à òàêæå ïðè ïðîåêòè-
ðîâàíèè ñõåì ðàñêðîÿ ïðîìûøëåííûõ ìàòåðèàëîâ [1–4]. Ýòè çàäà÷è íàïðàâëå-
íû íà ïîèñê ðàöèîíàëüíîãî ðàñïîëîæåíèÿ îáúåêòîâ íà ïðîìûøëåííîì ìàòå-
ðèàëå c öåëüþ ìàêñèìèçàöèè êîýôôèöèåíòà èñïîëüçîâàíèÿ ìàòåðèàëà èëè
ìèíèìèçàöèè îòõîäîâ. Â áîëüøèíñòâå çàäà÷ ðàçìåùàåìûå îáúåêòû èìåþò
ïðîèçâîëüíóþ ôîðìó. Â íàñòîÿùåå âðåìÿ íàèáîëåå ðàñïðîñòðàíåííûì è âîñ-
òðåáîâàííûì ñòàíîâèòñÿ èíäèâèäóàëüíîå (ýêñêëþçèâíîå) ïðîèçâîäñòâî. Â ýòîé
ñâÿçè ïîÿâëÿåòñÿ íåîáõîäèìîñòü â ïîèñêå îïòèìàëüíîãî ðàñïîëîæåíèÿ îáúåê-
òîâ ïðîèçâîëüíîé ôîðìû ïðè ìèíèìàëüíûõ âðåìåííûõ çàòðàòàõ è ìàêñèìàëü-
íîé ýêîíîìèè ìàòåðèàëà.
Çàäà÷è ðàçìåùåíèÿ — îïòèìèçàöèîííûå, âñëåäñòâèå ýòîãî âîçíèêàåò
ïðîáëåìà ïðèìåíåíèÿ èçâåñòíûõ ìåòîäîâ ëîêàëüíîé è ãëîáàëüíîé îïòèìèçà-
öèè, îáóñëîâëåííàÿ îòñóòñòâèåì êîíñòðóêòèâíûõ ñðåäñòâ ìàòåìàòè÷åñêîãî ìî-
äåëèðîâàíèÿ, ïîçâîëÿþùèõ ïðåäñòàâèòü çàäà÷ó ðàçìåùåíèÿ ïðîèçâîëüíûõ ãåî-
ìåòðè÷åñêèõ îáúåêòîâ â âèäå çàäà÷è ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ.
 ðàáîòàõ [1–3] èçëîæåíû ñîâðåìåííûå ñðåäñòâà ìàòåìàòè÷åñêîãî ìîäåëèðî-
âàíèÿ è ìåòîäû ðåøåíèÿ çàäà÷ ðàçìåùåíèÿ ïðîèçâîëüíûõ ãåîìåòðè÷åñêèõ îáúåê-
òîâ. Îäíàêî ïðåäëàãàåìûå ïîäõîäû îñíîâàíû íà ýâðèñòèêàõ è ìîäèôèêàöèÿõ ìå-
òîäà îïòèìèçàöèè ïî ãðóïïàì ïåðåìåííûõ.
Ðàçðàáîòêà ýôôåêòèâíûõ ìåòîäîâ ðåøåíèÿ îïòèìèçàöèîííûõ çàäà÷ ðàçìå-
ùåíèÿ òðåáóåò ïîñòðîåíèÿ àäåêâàòíûõ ìàòåìàòè÷åñêèõ ìîäåëåé. Ôóíäàìåí-
òàëüíîé îñíîâîé ìàòåìàòè÷åñêîãî ìîäåëèðîâàíèÿ çàäà÷ äàííîãî êëàññà ÿâëÿåò-
ñÿ àíàëèòè÷åñêîå îïèñàíèå óñëîâèé ðàçìåùåíèÿ ïðîèçâîëüíûõ îáúåêòîâ â çà-
äàííîé îáëàñòè.
Êàê èçâåñòíî [2], â êëàññå îïòèìèçàöèîííûõ 2D-çàäà÷ ðàçìåùåíèÿ êîíñòðóê-
òèâíûì ñðåäñòâîì ìàòåìàòè÷åñêîãî ìîäåëèðîâàíèÿ îòíîøåíèé ãåîìåòðè÷åñêèõ
îáúåêòîâ ÿâëÿåòñÿ ìåòîä �-ôóíêöèé [5]. Âèä �-ôóíêöèè íåïîñðåäñòâåííî îïðå-
äåëÿåòñÿ ïðîñòðàíñòâåííîé ôîðìîé ãåîìåòðè÷åñêèõ îáúåêòîâ.  ðàáîòàõ [6–8]
ïîñòðîåíû �-ôóíêöèè äëÿ áàçîâûõ îáúåêòîâ (primary objects). Ïðèíöèïû ïîñòðî-
åíèÿ �-ôóíêöèé äëÿ ñîñòàâíûõ îáúåêòîâ (composed objects), ïðåäñòàâëåííûõ â
âèäå îáúåäèíåíèé è ïåðåñå÷åíèé áàçîâûõ îáúåêòîâ, äîñòàòî÷íî ïîäðîáíî èçëî-
æåíû â [9]. Ïðè ýòîì ê ñîñòàâíûì îáúåêòàì ïðåäúÿâëÿþòñÿ æåñòêèå òðåáîâàíèÿ,
êîòîðûå â çíà÷èòåëüíîé ìåðå ñóæàþò êëàññ ïðîñòðàíñòâåííûõ ôîðì ãåîìåòðè-
÷åñêèõ îáúåêòîâ, èñïîëüçóåìûõ â êà÷åñòâå ìîäåëåé ðåàëüíûõ îáúåêòîâ. Ïðè ðå-
øåíèè ïðàêòè÷åñêèõ çàäà÷ (íàïðèìåð, ïðè ñîçäàíèè ñîâðåìåííûõ èíôîðìàöèîí-
íûõ òåõíîëîãèé ðàñêðîÿ ïðîìûøëåííûõ ìàòåðèàëîâ) èíôîðìàöèÿ îá îáúåêòàõ
çàäàåòñÿ, êàê ïðàâèëî, â âèäå îïèñàíèÿ èõ ãðàíèö, â ÷àñòíîñòè ïîñëåäîâàòåëüíî-
ñòüþ äóã îêðóæíîñòåé è îòðåçêîâ ïðÿìûõ.
28 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
� Þ.Ã. Ñòîÿí, Í.È. Ãèëü, Ò.Å. Ðîìàíîâà, Ì.Â. Çëîòíèê, 2011
Ïîñòðîåíèå �-ôóíêöèé äëÿ îáúåêòîâ, ãðàíèöà êîòîðûõ ôîðìèðóåòñÿ îáúå-
äèíåíèåì äóã îêðóæíîñòåé è îòðåçêîâ ïðÿìûõ (äàëåå ïðîèçâîëüíûõ îáúåêòîâ),
ìîæíî ðåàëèçîâàòü, èñïîëüçóÿ ÷ðåçâû÷àéíî ïðîñòîå ïðåäñòàâëåíèå ïðîèçâîëüíî-
ãî îáúåêòà â âèäå îáúåäèíåíèÿ îáúåêòîâ (äàëåå áàçîâûõ îáúåêòîâ), äëÿ êîòîðûõ
�-ôóíêöèè èçâåñòíû.
 ïðåäåëàõ äàííîãî èññëåäîâàíèÿ â êà÷åñòâå áàçîâûõ îáúåêòîâ ðàññìàòðèâà-
þòñÿ âûïóêëûé ìíîãîóãîëüíèê Ê (ðèñ. 1, à), çàäàííûé âåðøèíàìè
{ , , },p p pk1 2 � ; êðóãîâîé ñåãìåíò D T C� � (ðèñ. 1, á), ãäå Ñ — êðóã ðàäèóñà r
ñ öåíòðîì O; T — òðåóãîëüíèê, çàäàííûé âåðøèíàìè p p p1 2 3
1 2, , ,� � �� �1 è
� 2 — êàñàòåëüíûå ê îêðóæíîñòè fr C â òî÷êàõ p1 è p2 ñîîòâåòñòâåííî, fr ( )� —
ãðàíèöà ìíîæåñòâà ( )� ; îáúåêò H T C� �
* (ðèñ. 1, â), ãäå C R C* \� 2 int , int ( )� —
âíóòðåííîñòü ìíîæåñòâà ( )� ; îáúåêò V H C� � 2 (ðèñ. 1, ã), ãäå H T C� � 1
* ,
C2 — êðóã ðàäèóñà r r2 1� ñ öåíòðîì â òî÷êå Î2 , ïðè ýòîì �Ñ Ñ*
— �-ôóíêöèÿ
C2
* è C1, êîòîðàÿ ðàâíà íóëþ.
Îáîñíîâàíèåì âûáîðà â êà÷åñòâå áàçîâûõ îáúåêòîâ K D H V, , , ÿâëÿåòñÿ ñëå-
äóþùåå óòâåðæäåíèå.
Òåîðåìà. Îãðàíè÷åííûé �-îáúåêò [7], ãðàíèöà êîòîðîãî ôîðìèðóåòñÿ îáúåäè-
íåíèåì îòðåçêîâ ïðÿìûõ è äóã îêðóæíîñòåé, âñåãäà ìîæíî ïðåäñòàâèòü â âèäå
À Ak
k
m
�
�1
� , (1)
ãäå int intA Ai j� � �, i j I mm, { , , , } � 1 2 � , i j
, A K D H Vk { , , , }.
Äîêàçàòåëüñòâî. Â îñíîâå äîêàçàòåëüñòâà ëåæèò óòâåðæäåíèå î òîì, ÷òî
âîêðóã êðóãà (â êðóã) âñåãäà ìîæíî îïèñàòü (âïèñàòü) âûïóêëûé ìíîãîóãîëüíèê
ñ íàïåðåä çàäàííîé òî÷íîñòüþ.
Ïóñòü A — âûïóêëûé �-îáúåêò, ãðàíèöà êîòîðîãî ôîðìèðóåòñÿ îòðåçêàìè
ïðÿìûõ è âûïóêëûìè äóãàìè. Äóãà arc ( , )p p1 2 íà ðèñ. 1, á — âûïóêëàÿ, à íà
ðèñ. 1, â — âîãíóòàÿ.  ýòîì ñëó÷àå îáúåêò A âñåãäà ìîæíî ïðåäñòàâèòü â âèäå
îáúåäèíåíèÿ êðóãîâûõ ñåãìåíòîâ D è âûïóêëûõ ìíîãîóãîëüíèêîâ K. Äàëåå ïî-
ëàãàåì, ÷òî A — íåâûïóêëûé îáúåêò, ãðàíèöà êîòîðîãî ôîðìèðóåòñÿ îòðåçêàìè
ïðÿìûõ è âîãíóòûìè äóãàìè.  ýòîì ñëó÷àå îáúåêò A âñåãäà ìîæíî ïðåäñòàâèòü
â âèäå îáúåäèíåíèÿ îáúåêòîâ H è âûïóêëûõ ìíîãîóãîëüíèêîâ K. Ïóñòü òåïåðü
A — íåâûïóêëûé îáúåêò, ãðàíèöà êîòîðîãî ôîðìèðóåòñÿ îòðåçêàìè ïðÿìûõ,
à òàêæå âûïóêëûìè è âîãíóòûìè äóãàìè.  ýòîì ñëó÷àå îáúåêò âñåãäà ìîæíî
ïðåäñòàâèòü â âèäå îáúåäèíåíèÿ îáúåêòîâ V D H, , è K.
Ñëåäîâàòåëüíî, ëþáîé îãðàíè÷åííûé �-îáúåêò A, ãðàíèöà êîòîðîãî ôîðìè-
ðóåòñÿ îáúåäèíåíèåì îòðåçêîâ ïðÿìûõ è äóã îêðóæíîñòåé, ìîæíî ïðåäñòàâèòü
â âèäå (1).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 29
Ðèñ. 1. Áàçîâûå îáúåêòû K D H V, , ,
ip
1ip �
il
K
i�
T
H
3p
2p
1p
C
*C
2p
1p3p
V
frH
1C
2C
à á â ã
 äàëüíåéøåì ïðåäñòàâëåíèå îáúåêòà A â âèäå (1) áóäåì íàçûâàòü äåêîìïî-
çèöèåé.
Åñòåñòâåííûì îáðàçîì âîçíèêàåò ñëåäóþùàÿ çàäà÷à.
Çàäà÷à. Ïðåäñòàâèòü â âèäå (1) ïðîèçâîëüíûé îãðàíè÷åííûé �-îáúåêò
A R
2 , ãðàíèöà êîòîðîãî ñîñòîèò èç îòðåçêîâ ïðÿìûõ è äóã îêðóæíîñòåé.
Ïóñòü A — îäíîñâÿçíûé îãðàíè÷åííûé îáúåêò, ãðàíèöà êîòîðîãî çàäàíà ïî-
ñëåäîâàòåëüíîñòüþ ýëåìåíòîâ li , i I n .
Êàæäûé ýëåìåíò li çàäàåòñÿ êîð-
òåæåì èíôîðìàöèè g p pi i i i� ( , , ,�
pi�1 ) îá îòðåçêå s, âûïóêëîé äóãå
�
a ëèáî âîãíóòîé äóãå
�
a. Çäåñü
p x yi i i� ( , ), x yi i, — êîîðäèíàòû íà-
÷àëà ýëåìåíòà l s a ai { , , }
� �
â ñîáñòâåí-
íîé ñèñòåìå êîîðäèíàò ìíîæåñòâà A;
� i — ïðèçíàê ýëåìåíòà li , ïðè÷åì
� i � 0, åñëè l si { }, � i �1 , åñëè
l ai { }
�
, � i � �1 , åñëè l ai { }
�
; p x yi i i� ( , ) — êîîðäèíàòû öåíòðà îòðåçêà s èëè
öåíòðà îêðóæíîñòè, ôîðìèðóþùåé äóãó
� �
a a( ); p x yi i i� � ��1 1 1( , ), x yi i� �1 1, —
êîîðäèíàòû êîíöà li è íà÷àëà li�1. Òàêèì îáðàçîì, èíôîðìàöèÿ î ãðàíèöå áàçîâî-
ãî îáúåêòà A K D H V { , , , } çàäàåòñÿ êîðòåæåì g g g gA
n� ( , , , )1 2 � , â òîì ÷èñëå
g g g gK s s sk� ( , , , )1 2 � , g g gD a s� ( , )
�
, g g g gH a s s� ( , , )
�
1 2 , g g g gV a a s� ( , , )
� �
èëè
g g g gV a a s� ( , , )
� �
.
Àëãîðèòì 1. Äåêîìïîçèöèè ìíîæåñòâà À
Ýòàï 1. Ôîðìèðîâàíèå îáúåêòîâ V . Ïóñòü l a a sV � ( , , )
� �
çàäàåò ãðàíèöó îáúåê-
òà V .  ýòîì ñëó÷àå g p p pa
i i
�
� � �( , , , )1 1 , g p p pa
i i
�
� � ��� �( , , , )1 11 , s p p� �� �[ , ] ,
ãäå s — îòðåçîê ïðÿìîé, êàñàòåëüíîé ê îêðóæíîñòè C a�
�
â òî÷êå �� �p li 1;
� p li . Åñëè l a a sV � ( , , )
� �
, òîãäà g p p pa
i i
�
� �� � �( , , , )1 1 , g p p pa
i i
�
� �� �( , , , )1 11 ,
s p p� �� �[ , ] , �� p li è � �p li 1.
Íàëè÷èå îáúåêòîâ îïðåäåëÿåòñÿ óñëîâèåì
� �i i i i i i i ir r x x y y� � � � � � � � �� � � �1 1
2
1
2
1
21 0, ( ) ( ) ( ) . (2)
Ïóñòü âûïîëíÿåòñÿ óñëîâèå (2) è � i � –1 (ðèñ. 2).
1. Íàõîäèì p p Ci i i
ci
i1 2
1, ( ) �� � fr . Çàìåòèì, ÷òî � �i
ci
i
i� �1 1| | è Îi
�� i
ci 1, ãäå Îi — öåíòð êðóãà Ci (ðèñ. 3, à).
2. Íàõîäèì ~ : ~p p p i1 1 1� , åñëè p li i1 è p li i2 � èëè � �i i i i, ,1 2� (ðèñ. 3, á);
~p p i1 2� , åñëè p li i2 è p li i1 � èëè � �i i i i, ,1 2� ; ~p pi1 � , åñëè p li i1 � è p li i2 � .
Çäåñü � ik — âåëè÷èíà öåíòðàëüíîãî óãëà � �p O pi i i 1, êîòîðûé îïèðàåòñÿ íà äóãó
l Ci
fr (ñì. ðèñ. 2).
3. Îïðåäåëÿåì ~p2 : ~p pi2 1� � .
4. Íàõîäèì p p Ci i i
p
i3 4 1
1, ( )
~
�� � fr (ðèñ. 3, â).
5. Íàõîäèì ~ : ~p p p i3 3 3� , åñëè � �(~ , ) (~ , )p p p pi i1 3 1 4� (ðèñ. 3, â, ã); ~p p i3 4� ,
åñëè � �(~ , ) (~ , )p p p pi i1 3 1 4� , ãäå � — åâêëèäîâî ðàññòîÿíèå.
30 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
ip
1ip �
iliO
A
Ðèñ. 2. Ýòàï ôîðìèðîâàíèÿ áàçîâîãî îáúåêòà V
6. Îñóùåñòâëÿåì ïðîâåðêó óñëîâèÿ ~p li3 1 � . Åñëè ~p li3 1 � , òî îáúåêò, çà-
äàííûé êîðòåæåì ( , , )g g ga a s
� �
, ãäå g p p pa
i
�
� �(~ , , , ~ )1 21 , g p p pa
i
�
� �(~ , , , ~ )2 1 31 ,
s p p� [~ , ~ ]3 1 , ÿâëÿåòñÿ áàçîâûì îáúåêòîì V A
. Åñëè ~p li3 1� � (ðèñ. 4, a), òî
~p pi3 2� � . Èç òî÷êè ~p3 ñòðîèì êàñàòåëüíûå ê fr Ci , ðåøàÿ ñèñòåìó
� �
� �
2 2
3 3
1
0
� �
� � � �
�
�
�
,
~ ~ .x y ri
Îïðåäåëÿåì � i
p� è � i
p��. Äàëåå íàõîäèì � � �p Ci i
pfr � � è �� � ��p Ci i
pfr � � ;
çäåñü � � � �p x r y ri i i i( , )� �1 1 , �� � � �p x r y ri i i i( , )� �2 2
(ðèñ. 4, á). Âûáèðàåì
~p p1 � �, åñëè � �(~ , ) (~ , )p p p p2 2� � �� , èëè ~p p1 � ��, åñëè � �(~ , ) (~ , )p p p p2 2� � ��
(ðèñ. 4, â). Åñëè ( ) \ (~ ~ )s A p p� �fr
1 3
�, s p p� [~ , ~ ]3 1 , òî îñóùåñòâëÿåì ïåðåáîð
îòñå÷åííûõ âåðøèí è îïðåäåëÿåì ~p1, à ~p3 íàõîäèì â ñîîòâåòñòâèè ñ ï. 4, 5.
Ïåðåáîð çàêàí÷èâàåòñÿ, êîãäà âûïîëíÿåòñÿ îäíî èç óñëîâèé: à) ( ) \s A� fr
\ (~ ~ )p p1 3� � � (íàéäåíî ðåøåíèå); á) ( ) \ (~ ~ )s A p p M� �fr 1 3 � �, �
M a j( \
�
\ ( ))p pj j� �1 , j i i
�, 1 . Ïðè óñëîâèè á) îïðåäåëÿåì � � � �x x x c y si p p p p ,
� � � �y y x s y ci p p p p , �� � � �x x x c y si p p p p , y y x s y ci p p p p� � � �' , ãäå sp �
� �1 2cp , c r x xp i p i� / ( , )� , x x d x xp i p j i� � �( ), y y d y yp i p j i� � �( ), d p �
� �r r ri i j/ ( ); ~p p
1
� �, åñëè � �(~ , ) (~ , )p p p p2 2� � �� , è ~p p1 � ��, åñëè �(~ , )p p2 � �
� ���(~ , )p p2 ; ~p3 íàõîäèì â ñîîòâåòñòâèè ñ ï. 4, 5.
7. Îïðåäåëÿåì l a a sV � ( , , )
� �
, ãäå g p x y pa
i i
�
� �{~ , , , , ~ }1 21 , g p xa
i
�
� �{~ , , ,2 11
y pi�1 3, ~ }, s p p� [~ , ~ ]3 1 , è ïîëó÷àåì � �A A Vcl ( \ ) . Ýëåìåíò ãðàíèöû l li i� �
1
fr A çàìåíÿåì íà ( , , , ~ ) [~ , ~ ] (~ , , , )p p p p p p p p Ai i i i i i� �1 1 3 3 1 1 2� � � � �
�fr .
 ñëó÷àå, åñëè ~p pi1 � èëè ~p pi3 2� � , âûðîæäåííàÿ äóãà íå ó÷àñòâóåò â ôîðìè-
ðîâàíèè ãðàíèöû ìíîæåñòâà �A .
Ïîñëå âûïîëíåíèÿ ïåðâîãî ýòàïà ïîëó÷àåì îáúåêò A A V1 = cl ( / )� (ðèñ. 5),
çäåñü cl ( )� — çàìûêàíèå ìíîæåñòâà ( )� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 31
Ðèñ. 3. Ïîñòðîåíèå òî÷åê p i1 , p i2 , ~p1, ~p2, ~p3
1ci
i
��
iO
i
i�
ip
1ip �
A
iC
1ip2ip
iO
1ci
i
��
1i
i
�� iO
A
iC
à á â ã
Ðèñ. 4. Ïîñòðîåíèå òî÷åê �p , ��p
à á â
Ýòàï 2. Ôîðìèðîâàíèå ñåãìåíòîâ D. Ïóñòü l a sD � ( , )
�
çàäàåò ãðàíèöó
îáúåêòà D, ïðè ýòîì l ai �
�
è âûïîëíÿþòñÿ óñëîâèÿ int D A� fr � � è ( , )x y Di i � .
Òîãäà äóãó
�
a îáúåêòà A1 çàìåíÿåì ñîîòâåòñòâóþùåé õîðäîé l si � (ðèñ. 6, à).
Åñëè int D A� fr
� èëè ( , )x y Di i (ðèñ. 6, á, â), òî íàõîäèì òî÷êó
� �p l ai
�
, ïîðîæäàþùóþ ñåãìåíòû D1 è D 2 , l a sD1 1 1� ( , )
�
, l a sD2 2 2� ( , )
�
, ãäå
s p pi
1 � �[ , ] , s p pi
2
1� � �[ , ] , òàêóþ, ÷òî int D A1
� fr � � è int D A2
� fr � �.
 ýòîì ñëó÷àå âûäåëÿåì îáúåêòû D1 è D 2 , à äóãó li çàìåíÿåì õîðäàìè s1 è s 2
(ðèñ. 6, ã).
Åñëè òàêîé òî÷êè íå ñóùåñòâóåò, òî íàõîäèì äâå (è áîëåå) òî÷êè è âûäåëÿåì
ñåãìåíòû, çàìåíÿÿ èõ â ïîñëåäóþùåì ñîîòâåòñòâóþùèìè õîðäàìè.
Ïîñëå âûïîëíåíèÿ ïåðâîãî è âòîðîãî ýòàïîâ ïîëó÷àåì îáúåêò
A A D2 1� cl ( / )� (ðèñ. 7), ãðàíèöà êîòîðîãî ñîñòîèò èç ýëåìåíòîâ l s ai { },
�
.
Ýòàï 3. Ôîðìèðîâàíèå îáúåêòîâ H . Ïóñòü l a s sH � ( , , )
� 1 2 çàäàåò ãðàíèöó
îáúåêòà H , ãäå
�
a li� . Ñòðîèì êàñàòåëüíûå � i è � i�1 ê îêðóæíîñòè Ñ a�
�
â òî÷êàõ pi è pi�1. Íàõîäèì � � �p i i� ��
1. Òîãäà g p p pa
i i i
�
� � �( , , , )1 1 ,
s p pi
1
1� ��[ , ] , s p pi
2 � �[ , ] . Åñëè ãðàäóñíàÿ ìåðà äóãè
�
a li� ìåíüøå 180� è
âûïîëíÿåòñÿ óñëîâèå int H A� fr 2 � �, òî
�
a çàìåíÿåì íà s p pi i� �[ , ]�
� s p pi i� �� �1 1[ , ] è ôîðìèðóåì îáúåêò � �A A H2 2cl ( \ ) (ðèñ. 8, à). Èíà÷å íàõîäèì
òî÷êó �p — ñåðåäèíó äóãè
�
a, òîãäà
� �
�
�
a a a� 1 2 , g p p pa
i i
� 1
1� �( , , , ' ) è
g p p pa
i i
� 2
1 1� � � �( , , , ) (ðèñ. 8, á, â).
32 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
Ðèñ. 5. Ôîðìèðîâàíèå îáúåêòà V
Ðèñ. 6. Ôîðìèðîâàíèå ñåãìåíòà D
à á â ã
Ðèñ. 7. Âûäåëåíèå ñåãìåíòîâ D
Äëÿ êàæäîé äóãè
�
a 1,
�
a 2 âûïîëíÿåòñÿ àíàëîãè÷íàÿ ïðîöåäóðà. Ïîëó÷àåì
ìíîæåñòâî A A H3 2� cl ( \ )� , ãðàíèöà êîòîðîãî ñîñòîèò èç ýëåìåíòîâ l si { } (ðèñ. 9).
Ýòàï 4. Äåêîìïîçèöèÿ íåâûïóêëîãî ìíîãîóãîëüíèêà A3 íà âûïóêëûå
ìíîãîóãîëüíèêè K . Ñ ýòîé öåëüþ ìîæíî èñïîëüçîâàòü ðàçëè÷íûå àëãîðèòìû
ìíîãîóãîëüíîé äåêîìïîçèöèè, íàïðèìåð ïðèâåäåííûé â [10]. Ïîëó÷àåì ìíîæåñ-
òâî A K3 � � (ðèñ. 10).
Òàêèì îáðàçîì, èìååì A D V H K� ( ) ( ) ( ) ( )� � � � � � � (ðèñ. 11).
Íà ðèñ. 12 ïðèâåäåíû ïðèìåðû äåêîìïîçèöèè ïðîèçâîëüíûõ �-îáúåêòîâ íà
áàçîâûå îáúåêòû âèäà K D H, , .
Ïóñòü A — ìíîãîñâÿçíûé îãðàíè÷åííûé îáúåêò, ò.å. ãðàíèöà A — íåñâÿçíîå
ìíîæåñòâî, ñîñòîÿùåå èç êîíå÷íîãî ÷èñëà êîìïîíåíòîâ ñâÿçíîñòè; fr A çàäàåòñÿ
ïîäîáíî ãðàíèöå îäíîñâÿçíîãî ìíîæåñòâà.  ýòîì ñëó÷àå èñïîëüçóåì àëãîðèòì
äåêîìïîçèöèè, ïðèâåäåííûé âûøå.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 33
Ðèñ. 8. Ôîðìèðîâàíèå îáúåêòà H
à á â
Ðèñ. 9. Âûäåëåíèå îáúåêòà H
Ðèñ. 10. Ðàçáèåíèå íåâûïóêëîãî ìíîãîóãîëüíèêà íà âûïóêëûå ìíîãîóãîëüíèêè
Ðèñ. 11. Ðàçáèåíèå �-îáúåêòà À íà áàçîâûå îáúåêòû âèäà K D H V, , ,
Ñ ïðàêòè÷åñêîé òî÷êè çðåíèÿ êëàññ áàçîâûõ îáúåêòîâ ìîæåò áûòü ðàñøèðåí ñ öåëüþ
óïðîùåíèÿ âèäà �-ôóíêöèè ïðîèçâîëüíûõ îáúåêòîâ, ïîñêîëüêó, ñëåäóÿ [8], �-ôóíêöèÿ
îáúåêòîâ A Ai
i
mA
�
�1
� è B B j
j
m
B
�
�1
� èìååò âèä � �AB A B
m
i j
A
i I� min , ,{ j I
mB
}.
Íàïðèìåð, íåöåëåñîîáðàçíî ïðåäñòàâëÿòü êðóãè â âèäå îáúåäèíåíèÿ ñåãìåí-
òîâ D è ìíîãîóãîëüíèêîâ K, òàê êàê �-ôóíêöèÿ äëÿ êðóãîâ èìååò áîëåå ïðîñòîé
âèä, ÷åì �-ôóíêöèÿ äëÿ ñåãìåíòîâ. Êðîìå òîãî, âèä �-ôóíêöèè äëÿ ñîñòàâíûõ
îáúåêòîâ ìîæåò áûòü çíà÷èòåëüíî óïðîùåí, åñëè èìåòü â «áèáëèîòåêå»
�-ôóíêöèè äëÿ îáúåêòîâ âèäà L K C� �
* (ðèñ. 13, a) è W C C S S� 1 2 1 2
*
� � �
(ðèñ. 13, á), ãäå S S1 2, — ïîëóïëîñêîñòè, ïðè ýòîì �C C*
� 0. Ïðÿìàÿ 1 1� fr S
ïðîõîäèò ÷åðåç íà÷àëî äóãè l a Ci� �
1 2
�
è êîíåö äóãè l a Ci �
�
1
* , à ïðÿìàÿ
2 2� fr S ïðîõîäèò ÷åðåç íà÷àëî è êîíåö äóãè l a Ci �
�
1
* . Èíôîðìàöèÿ î ãðà-
íèöå îáúåêòîâ L è W çàäàåòñÿ êîðòåæàìè g g g g gL a s s sk� �( , , , , )
�
1 2 , g gW V� . Çà-
ìåòèì, ÷òî ëþáîé îáúåêò âèäà V ÿâëÿåòñÿ îáúåêòîì âèäà W.
 ýòîé ñâÿçè àëãîðèòì äåêîìïîçèöèè ìîæíî ìîäèôèöèðîâàòü ñëåäóþùèì
îáðàçîì.
Ïîëàãàåì, ÷òî âûðàæåíèå (1) — ïîêðûòèå ìíîæåñòâà À, ïðè êîòîðîì â
îáùåì ñëó÷àå Ài è À j , i j I m, , i j
, ìîãóò èìåòü îáùèå âíóòðåííèå òî÷êè.
 êëàññ áàçîâûõ îáúåêòîâ ââåäåì äîïîëíèòåëüíî êðóãè Ñ, à òàêæå îáúåêòû L è W.
Ïðîöåññ ïîêðûòèÿ îáúåêòà À áàçîâûìè îáúåêòàìè èç ìíîæåñòâà
{ , , , , }Ñ D W K L âêëþ÷àåò òðè ýòàïà.
Àëãîðèòì 2. Ïîêðûòèå îáúåêòà À
Ýòàï 1. Âûäåëåíèå îáúåêòîâ âèäà W . Íà îñíîâå àíàëèçà èíôîðìàöèè î fr À
îïðåäåëÿåì òàêèå òî÷êè pi , i Jn , äëÿ êîòîðûõ âûïîëíÿþòñÿ óñëîâèÿ
{( ) ( ) ( )x x y y r ri i i i i i� � � � � �� � �1
2
1
2
1
2 0, � �i i� � �1 0, ãäå ri�1 è ri — ðàäèóñû
îêðóæíîñòåé fr C li i� ��1 1 è fr C li i� . Ôîðìèðóåì îáúåêò W, ãäå l a a sW � ( , , )
� �
,
g p p pa
i i
�
� �( ' , , , )1 1 , g p p pa
i i
� �
� � ���( , , , )1 1 , s p p� ��[ , ' ], � �p li 1, �� p li . Åñëè
l a a sW � ( , , )
� �
, òîãäà g p p pa
i i
�
� � � �( , , , )1 1 , g p p pa
i i
�
� ��( , , , )1 , s p p� �� �[ , ] ,
� �p li 1, �� p li . Ïóñòü l ai� �1
�
, l ai �
�
.
34 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
Ðèñ. 12. Ðàçáèåíèå �-îáúåêòîâ íà áàçîâûå îáúåêòû âèäà K D H, ,
Ðèñ. 13. Âèä îáúåêòîâ L è W
à á
1. Ïîëàãàåì � � �p pi 1, �� � �p pi 1 (ðèñ. 14, à). Åñëè âûïîëíÿþòñÿ óñëîâèÿ
p Si i� 1 2 , s i� int C � � è ñîîòíîøåíèå
( ) \ ( )s A p p� �fr � �� � �, (3)
òî îáúåêò, çàäàííûé êîðòåæåì ( , , )g g ga a s
� �
, ãäå g p p pa
i i i
�
� � �( , , , )1 11 ,
g p p pa
i i i
�
� � �( , , , )1 1 , s p pi i� � �[ , ]1 1 , ÿâëÿåòñÿ áàçîâûì îáúåêòîì W A
.
2. Åñëè p Si i� �1 2 (ðèñ. 14, á), òî ïîëàãàåì � � �p li i 2 1� , �� � �p pi 1. Ïðè âû-
ïîëíåíèè (3) îáúåêò, çàäàííûé êîðòåæåì ( , , )g g ga a s
� �
, ãäå g p p pa
i i
�
� �( ' , , , )1 1 ,
g p p pa
i i i
�
� � �( , , , )1 1 , s p pi� ��[ , ]1 , ÿâëÿåòñÿ áàçîâûì îáúåêòîì W.
3. Åñëè s Ci� int
� (ðèñ. 14, â), òî ïîëàãàåì � � �p pi 1, �� �p li i 1 � . Ïðè
âûïîëíåíèè (3) îáúåêò, çàäàííûé êîðòåæåì ( , , )g g ga a s
� �
, ãäå g pa
i
�
� �( , ,1 1
p pi i�1, ), g p p pa
i i
�
� � ��( , , , )1 , s p pi� �� �[ , ]1 , ÿâëÿåòñÿ áàçîâûì îáúåêòîì W.
4. Åñëè ( ) \ ( )s A p p� �fr � ��
�, òî W ôîðìèðóåì â ñîîòâåòñòâèè ñ ïîñòðîå-
íèåì îáúåêòà V (àëãîðèòì 1, ýòàï 1).
 ñëó÷àå, êîãäà l ai� �1
�
, l ai �
�
, áàçîâûé îáúåêò W ôîðìèðóåì àíàëîãè÷íûì
îáðàçîì, èñïîëüçóÿ çåðêàëüíîå îòîáðàæåíèå.
Ïîñëå âûïîëíåíèÿ ïåðâîãî ýòàïà èìååì îáúåêò A A W1 � cl ( \ )� .
Ýòàï 2. Ôîðìèðîâàíèå îáúåêòà C èëè D. Ñòðîèì áàçîâûé îáúåêò C òàêîé,
÷òî l a Ci �
�
fr , ïðè óñëîâèè int C l j� � �, j I n . Ïðè ýòîì l ai �
�
çàìåíÿåì õîð-
äîé l si � , à g p p pa
i i i
�
� �( , , , )1 1 èçìåíÿåì íà g p p ps
i i i� �( , , , )0 1 . Åñëè � j, j I n ,
ïðè êîòîðîì int C li j�
�, òî â êà÷åñòâå áàçîâîãî îáúåêòà âûäåëÿåì ñåãìåíò D
àíàëîãè÷íî ýòàïó 2 àëãîðèòìà 1.
Ïîñëå âûïîëíåíèÿ ïåðâîãî è âòîðîãî ýòàïîâ ïîëó÷àåì îáúåêò ��A , ãðàíèöà
êîòîðîãî ñîñòîèò èç ýëåìåíòîâ l s ai { , }
�
.
Ýòàï 3. Ïîñëåäîâàòåëüíàÿ äåêîìïîçèöèÿ îáúåêòà ��A . Êàæäàÿ ÷àñòü îáú-
åêòà ��A äåëèòñÿ íà äâå ÷àñòè, êîòðûå çàòåì âíîâü äåëÿòñÿ íà äâå ÷àñòè è ò.ä. äî
ôîðìèðîâàíèÿ ìíîæåñòâà áàçîâûõ îáúåêòîâ âèäà { , }K L . Åñëè îáúåêò ���A K L{ , },
òî îñóùåñòâëÿåòñÿ äåëåíèå îáúåêòà ��A íà äâå ÷àñòè: ��A1 è ��A2 ïðÿìîëèíåéíûì îò-
ðåçêîì. Çàìåòèì, ÷òî äåëåíèå îáúåêòà ��A îòðåçêîì [ , ]a b äîïóñòèìî, åñëè
[ , ]a b A
��, [ , ]a b A� int ��
� è a b A, ��fr .  êà÷åñòâå òî÷êè à áóäåì âûáèðàòü â
ïîðÿäêå óáûâàíèÿ ïðèîðèòåòíîñòè îäíó èç òî÷åê âèäà à p s si i i� �� �1 1� — íå-
âûïóêëóþ âåðøèíó îáúåêòà ��A ; à p a ai i i� �� �1 1
�
�
�
; à p s ai i i� �� �1 1�
�
; a si ,
i I n , à â êà÷åñòâå òî÷êè b áóäåì âûáèðàòü â ïîðÿäêå óáûâàíèÿ ïðèîðèòåòíîñòè
b p s sj j j� �� �1 1� íåâûïóêëóþ âåðøèíó îáúåêòà ��A ; b p a aj j j� �� �1 1
�
�
�
;
b p s aj j j� �� �1 1�
�
; b s j , b a j
�
, j I j in
, .
Ïîñëåäîâàòåëüíî ïåðåáèðàÿ âàðèàíòû âûáîðà òî÷åê a è b, íàõîäèì íàè-
ëó÷øèå, ñ òî÷êè çðåíèÿ èõ ïðèîðèòåòíîñòè, âàðèàíòû äåëåíèÿ îáúåêòà ��A îò-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 35
Ðèñ. 14. Ïîñòðîåíèå îáúåêòà W
à á â
ðåçêîì [ , ]a b . Ïðè ýòîì ïðè ðàâíûõ çíà÷åíèÿõ óðîâíåé ïðèîðèòåòíîñòè ïðåäïî÷-
òåíèå îòäàåòñÿ âàðèàíòó, ïðè êîòîðîì ãðàíèöû îáåèõ ÷àñòåé ðàçäåëåííîãî îáú-
åêòà ñîäåðæàò äóãè
�
a. Íà îñíîâå çàäàííîé èíôîðìàöèè î fr ��A ôîðìèðóåì äâà
íîâûõ îáúåêòà: ��A1 è ��A2 , êàæäûé èç êîòîðûõ çàòåì àíàëîãè÷íûì îáðàçîì äåëèì
íà äâå ÷àñòè: �� ��A A11 12, è �� ��A A21 22, è ò.ä. Ïðîöåññ äåëåíèÿ îáúåêòà ��A çàêàí÷èâàåò-
ñÿ, êîãäà âñå ïîëó÷åííûå îáúåêòû ïðèíàäëåæàò ìíîæåñòâó áàçîâûõ îáúåêòîâ { , }K L .
Òàêèì îáðàçîì, èìååì A Ñ D W L K� ( ) ( ) ( ) ( ) ( ).� � � � � � � � �
Íà ðèñ. 15 ïðèâåäåíû ïðèìåðû äåêîìïîçèöèè è ïîêðûòèÿ ïðîèçâîëüíûõ îáúåê-
òîâ áàçîâûìè îáúåêòàìè âèäà Ñ D K L, , , .
Ðåçóëüòàòû ÷èñëåííûõ ýêñïåðèìåíòîâ. Èìååòñÿ ìíîæåñòâî îáúåêòîâ
{ }T i Ii N, , , , �1 2 13� âèäà A1 (ðèñ. 16, à), A2 (ðèñ. 16, á), A3 (ðèñ. 16, â), ïðè-
÷åì { } { { }T i I T Ai N i, � 1 , i �1 4, ,� , T Ai { }2 , i � 5 8, ,� , T A ii �{ } }3 9 13, , ,� .
 ðåçóëüòàòå ðàçáèåíèÿ îáúåêòîâ A1, A2 , A3 èìååì A D K1 11 12� � , D11:
l1 173 1 1 0 1 173 1� �( . , , , , , . , ), s2 173 1 173 1� �[ . , , . , ] , K s12 1 25: [ . ,� �1 173 1, . , ], s2 173 1� [ . , ,
�173 1. , ], s3 173 1 25 1� � � �[ . , , . , ] , s4 25 1 25 1� � � �[ . , , . , ] ; A D D K2 21 22 23� � � , D21:
l1 1 15 1 0 15 1 15� �( , . , , , . , , . ), s2 1 15 1 15� �[ , . , , . ] ; D l22 1 1 15 1 0 15 1 15: ( , . , , , . , , , )� � � � � , s2 �
� � � �[ , . , , . ]1 15 1 15 ; K23 : s1 1 15 1 15� �[ , . , , . ] , s2 1 15� �[ , . , � �1 15, . ] , s3 1 15 1 15� � � �[ , . , , . ] ,
s4 1 15 1 15� �[ , . , , . ] ; A D K3 31 32� � , D31: l1 1 4 1� ( , , , 0 4 1 4, , , )� , s2 1 4 1 4� �[ , , , ] ; K32 :
s1 1 4 1 4� �[ , , , ] , s2 1 4 0 1� � �[ , , , ], s3 0 1 1 4� �[ , , , ] .
Íà ðèñ. 16, ã ïîêàçàíî ðàçìåùåíèå îáúåêòîâ { }T i Ii N, â ïîëîñå øèðèíû
w �15 ïåðåìåííîé äëèíû l , ñîîòâåòñòâóþùåå ëîêàëüíîìó ìèíèìóìó
l* ,� 8 90344 . Ïðè ýòîì âåêòîð ïàðàìåòðîâ ðàçìåùåíèÿ u u u u* * * *( , , , )� 1 2 13�
îáúåêòîâ T T T1 2 13, , ,� , ãäå u x yi i i i
* ( , , )�
, èìååò âèä u* (( . , . , . ),� 6903 12322 0808
( . , . , . )3 736 3233 0846 , ( . , . , . ),6 467 1997 2059 ( . , . ,359 8586 �0389. ), ( . , . , . )6522 6646 3536 ,
( . , . , . ),5398 11001 0 763� ( . , . , . )3011 6185 1183 , ( . ,1743 12696 5 765. , . ), ( . , . , . )0197 6152 6 481 ,
( . , . , . ),8 707 8 779 3339 ( . , . , . )0 461 4965 3009 , ( . ,7214 14803 4515. , . ), ( . , . , . ))1052 4 457 2614 .
Çäåñü ( , )x yi i — âåêòîð òðàíñëÿöèè îáúåêòà Ti ,
i — óãîë ïîâîðîòà. Äëÿ ðåøåíèÿ çà-
äà÷è ðàçìåùåíèÿ èñïîëüçîâàëàñü ñòðàòåãèÿ, èçëîæåííàÿ â [11].
36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
Ðèñ. 15. Ïîêðûòèå �-îáúåêòîâ áàçîâûìè îáúåêòàìè âèäà C D K L, , ,
Ðèñ. 16. Âèä îáúåêòîâ A A A1 2 3, , è ðàçìåùåíèå îáúåêòîâ Ti, i I 13, ñîîòâåòñòâóþùåå ëîêàëüíîìó
ìèíèìóìó
à á â ã
Äðóãèå ïðèìåðû ìàòåìàòè÷åñêîãî è êîìïüþòåðíîãî ìîäåëèðîâàíèÿ îïòèìè-
çàöèîííûõ çàäà÷ ðàçìåùåíèÿ, èñïîëüçóþùèå ïðåäëîæåííûé àëãîðèòì, ìîæíî
íàéòè â ñòàòüå [11] è íà Èíòåðíåò ñàéòå [12].
Òàêèì îáðàçîì, ðàçðàáîòàííûé â äàííîé ñòàòüå àëãîðèòì ðàçáèåíèÿ è ñîîò-
âåòñòâóþùèé ïðîãðàììíûé ìîäóëü ìîãóò áûòü èñïîëüçîâàíû äëÿ ìàòåìàòè÷åñ-
êîãî è êîïüþòåðíîãî ìîäåëèðîâàíèÿ â ñîâðåìåííûõ èíôîðìàöèîííûõ ñèñòåìàõ
ðåøåíèÿ 2D-çàäà÷ óïàêîâêè è ðàñêðîÿ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. D y c k h o f f H . , S c h e i t h a u e r G . , T e r n o J . Cutting and packing // M. Dell’Amico,
F. Maffioli and S. Martello, Eds. Annotated Bibliographies in Combinatorial Optimization, John
Wiley & Sons. — Chichester, 1997. — P. 393–412.
2. B e n n e l l J . A . , O l i v e i r a J . F . A tutorial in nesting problem: the geometry // European
J. Oper. Res. Invited review. — 2008. — 184. — P. 397–415.
3. B u r k e E . , H e l l e r R . , K e n d a l l G . , W h i t w e l l G . A new bottom-left-fill heuristic algo-
rithm for the two-dimensional irregular packing problem // Operational research. — 2006. — 54,
N 3. — P. 587–601.
4. Ê à í ò î ð î â è ÷ Ë . Â . , Ç à ë ã à ë ë å ð Â . À . Ðàöèîíàëüíûé ðàñêðîé ïðîìûøëåííûõ
ìàòåðèàëîâ. Èçä. 2-e. — Íîâîñèáèðñê: Íàóêà, 1971. — 299 ñ.
5. S t o y a n Y u . G . �-function and its basic properties // Äîï. ÍÀÍ Óêðà¿íè. — 2001. — ¹ 8. —
Ñ. 112–117.
6. S t o y a n Y u . , G i l M . , T e r n o M . , R o m a n o v a T . , S c h e i t h a u e r G . Construction of
a �-function for two convex polytopes // Appliñationes Mathematicae. — 2002. — 2, N 29. —
P. 199–218.
7. B e n n e l l J . , S c h e i t h a u e r G . , S t o y a n Y u . , R o m a n o v a T . Tools of mathematical
modelling of arbitrary object packing problems // J. Annals of Operations Research, Publisher
Springer Netherlands. — 2010. — 179, N 1. — C. 343–368.
8. S t o y a n Y u . , S c h e i t h a u e r G . , G i l N . , R o m a n o v a T . �-functions for complex
2D-objects // 4OR: Quarterly J. Belgian, French and Italian Operations Research Soc. — 2004. — 2.
— P. 69–84.
9. S t o y a n Y u . , T e r n o J . , S c h e i t h a u e r G . , G i l N . , R o m a n o v a T . �-functions for
primary 2D-objects // Studia Informatica Universalis. — 2001. — 2. — P. 1–32.
10. Ñ ò î ÿ í Þ . à . , à è ë ü Í . È . Ìåòîäû è àëãîðèòìû ðàçìåùåíèÿ ïëîñêèõ ãåîìåòðè÷åñêèõ
îáúåêòîâ. — Êèåâ: Íàóê. äóìêà, 1976. — 246 ñ.
11. C h e r n o v N . , S t o y a n Y u . , R o m a n o v a T . Mathematical model and efficient algorithms
for object packing problem // Computational Geometry: Theory and Applications. 43 (2010)
535–553.doi:10.1016/j.comgeo.2009.12.003
12. http://www.math.uab.edu/~chernov/CP
Ïîñòóïèëà 26.02.2010
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 37
|
| id | nasplib_isofts_kiev_ua-123456789-84248 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T17:27:40Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Стоян, Ю.Г. Гиль, Н.И. Романова, Т.Е. Злотник, М.В. 2015-07-04T14:50:50Z 2015-07-04T14:50:50Z 2011 Алгоритм декомпозиции геометрических объектов в 2D-задачах упаковки и раскроя / Ю.Г. Стоян, Н.И. Гиль, Т.Е. Романова, М.В. Злотник // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 28-37. — Бібліогр.: 12 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84248 519.85 Введено клас базових 2D-об’єктів, для яких відомі Φ-функції. Доведено теорему про розбиття довільних φ-об’єктів, межа яких утворюється об’єднанням дуг кіл та відрізків прямих на базові об’єкти. Запропоновано покроковий алгоритм, який реалізує декомпозицію довільних двовимірних φ-об’єктів. Розглянутий підхід ефективний для побудови Φ-функцій довільних об’єктів при математичному та комп’ютерному моделюванні 2D-задач пакування та розкрою. Наведено результати чисельних експериментів. Іл.: 16. Бібліогр.: 12 назв. We introduce a class of basic 2D-objects whose Φ-functions are known and prove a theorem on the decomposition, into basic objects, of an arbitrary φ-object whose boundary is formed by circular arñs and line segments. We provide a step-by-step decomposition algorithm for arbitrary two-dimensional φ-objects. The algorithm performs well to derive Φ-functions of arbitrary φ-objects in mathematical and computer modeling of packing and cutting problems. Numerical results are presented. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Алгоритм декомпозиции геометрических объектов в 2D-задачах упаковки и раскроя Алгоритм декомпозиції геометричних об’єктів в 2D-задачах пакування та розкрою Decomposition algorithm for geometric objects in 2D packing and cutting problems Article published earlier |
| spellingShingle | Алгоритм декомпозиции геометрических объектов в 2D-задачах упаковки и раскроя Стоян, Ю.Г. Гиль, Н.И. Романова, Т.Е. Злотник, М.В. Кибернетика |
| title | Алгоритм декомпозиции геометрических объектов в 2D-задачах упаковки и раскроя |
| title_alt | Алгоритм декомпозиції геометричних об’єктів в 2D-задачах пакування та розкрою Decomposition algorithm for geometric objects in 2D packing and cutting problems |
| title_full | Алгоритм декомпозиции геометрических объектов в 2D-задачах упаковки и раскроя |
| title_fullStr | Алгоритм декомпозиции геометрических объектов в 2D-задачах упаковки и раскроя |
| title_full_unstemmed | Алгоритм декомпозиции геометрических объектов в 2D-задачах упаковки и раскроя |
| title_short | Алгоритм декомпозиции геометрических объектов в 2D-задачах упаковки и раскроя |
| title_sort | алгоритм декомпозиции геометрических объектов в 2d-задачах упаковки и раскроя |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84248 |
| work_keys_str_mv | AT stoânûg algoritmdekompoziciigeometričeskihobʺektovv2dzadačahupakovkiiraskroâ AT gilʹni algoritmdekompoziciigeometričeskihobʺektovv2dzadačahupakovkiiraskroâ AT romanovate algoritmdekompoziciigeometričeskihobʺektovv2dzadačahupakovkiiraskroâ AT zlotnikmv algoritmdekompoziciigeometričeskihobʺektovv2dzadačahupakovkiiraskroâ AT stoânûg algoritmdekompozicíígeometričnihobêktívv2dzadačahpakuvannâtarozkroû AT gilʹni algoritmdekompozicíígeometričnihobêktívv2dzadačahpakuvannâtarozkroû AT romanovate algoritmdekompozicíígeometričnihobêktívv2dzadačahpakuvannâtarozkroû AT zlotnikmv algoritmdekompozicíígeometričnihobêktívv2dzadačahpakuvannâtarozkroû AT stoânûg decompositionalgorithmforgeometricobjectsin2dpackingandcuttingproblems AT gilʹni decompositionalgorithmforgeometricobjectsin2dpackingandcuttingproblems AT romanovate decompositionalgorithmforgeometricobjectsin2dpackingandcuttingproblems AT zlotnikmv decompositionalgorithmforgeometricobjectsin2dpackingandcuttingproblems |