Математическое моделирование ограничений на допустимые расстояния между геометрическими объектами
Введено поняття вільної від радикалів псевдонормалізованої Ф-функції, що дозволяє описувати обмеження на мінімально та максимально припустимі відстані між двовимірними φ-об’єктами. Допускаються афінні відображення трансляції та повороту. Наведено теорему про існування вільної від радикалів псевдоно...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2012 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84104 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Математическое моделирование ограничений на допустимые расстояния между геометрическими объектами / Ю.Г. Стоян, А.В. Панкратов, Т.Е. Романова // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 12-17. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860106209976123392 |
|---|---|
| author | Стоян, Ю.Г. Панкратов, А.В. Романова, Т.Е. |
| author_facet | Стоян, Ю.Г. Панкратов, А.В. Романова, Т.Е. |
| citation_txt | Математическое моделирование ограничений на допустимые расстояния между геометрическими объектами / Ю.Г. Стоян, А.В. Панкратов, Т.Е. Романова // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 12-17. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Введено поняття вільної від радикалів псевдонормалізованої Ф-функції, що дозволяє описувати обмеження на мінімально та максимально припустимі відстані між двовимірними φ-об’єктами. Допускаються афінні відображення трансляції та повороту. Наведено теорему про існування вільної від радикалів псевдонормалізованої Ф-функції для пари довільних φ-об’єктів, границі яких формуються об’єднанням дуг кіл і відрізків прямих. Запропоновано ефективний алгоритм побудови псевдонормалізованих Ф-функцій.
The paper introduces the concept of radical-free pseudonormalized Ф-functions, which allows us to describe constraints for minimum and maximum a φ-objects. We allow translations and rotations of φ-objects in a two-dimensional Euclidean space. The theorem about the existence of a radical-free pseudonormalized Ф-function for a pair of arbitrary-shaped φ-objects whose frontiers are formed by the union of line segments and circular arcs is formulated.
|
| first_indexed | 2025-12-07T17:31:51Z |
| format | Article |
| fulltext |
ÓÄÊ 519.85
Þ.Ã. ÑÒÎßÍ, À.Â. ÏÀÍÊÐÀÒÎÂ, Ò.Å. ÐÎÌÀÍÎÂÀ
ÌÀÒÅÌÀÒÈ×ÅÑÊÎÅ ÌÎÄÅËÈÐÎÂÀÍÈÅ ÎÃÐÀÍÈ×ÅÍÈÉ
ÍÀ ÄÎÏÓÑÒÈÌÛÅ ÐÀÑÑÒÎßÍÈß
ÌÅÆÄÓ ÃÅÎÌÅÒÐÈ×ÅÑÊÈÌÈ ÎÁÚÅÊÒÀÌÈ
Êëþ÷åâûå ñëîâà: ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå, ãåîìåòðè÷åñêèå îáúåêòû,
äîïóñòèìûå ðàññòîÿíèÿ, Ô-ôóíêöèÿ.
Ïðè ïîñòðîåíèè ìàòåìàòè÷åñêèõ ìîäåëåé îïòèìèçàöèîííûõ çàäà÷ óïàêîâêè è
ðàñêðîÿ [1] âîçíèêàåò íåîáõîäèìîñòü ôîðìàëèçàöèè îãðàíè÷åíèé íà ìèíè-
ìàëüíî è ìàêñèìàëüíî äîïóñòèìûå ðàññòîÿíèÿ ìåæäó ðåàëüíûìè îáúåêòàìè.
Ïðèìåíåíèå íîðìàëèçîâàííûõ Ô-ôóíêöèé [2] èíîãäà ïðèâîäèò ê ñëîæíûì
âû÷èñëèòåëüíûì ïðîöåäóðàì. Öåëü äàííîé ðàáîòû — ïîñòðîåíèå ñâîáîäíûõ
îò ðàäèêàëîâ �-ôóíêöèé, ó÷èòûâàþùèõ îãðàíè÷åíèÿ íà äîïóñòèìûå ðàññòîÿ-
íèÿ ìåæäó äâóìåðíûìè ãåîìåòðè÷åñêèìè îáúåêòàìè.
Èìåþòñÿ çàìêíóòûå îãðàíè÷åííûå �-îáúåêòû A B R, � 2[3]. Ïîëàãàåì, ÷òî
ãðàíèöà îáúåêòà A çàäàíà ïîñëåäîâàòåëüíîñòüþ äóã îêðóæíîñòåé è îòðåçêîâ ïðÿ-
ìûõ, R 2 — äâóìåðíîå àðèôìåòè÷åñêîå åâêëèäîâî ïðîñòðàíñòâî. Äîïóñêàþòñÿ
àôôèííûå îòîáðàæåíèÿ òðàíñëÿöèè è ïîâîðîòà îáúåêòà A, ò.å. îáúåêò A — íå-
îðèåíòèðîâàííûé. Ïîëîæåíèå A â ïðîñòðàíñòâå R 2 îïðåäåëÿåò âåêòîð
u x yt t� ( , , )� , à êîîðäèíàòû òî÷åê ( , )x y A� îïðåäåëÿþòñÿ ïî ôîðìóëå
x x y xt� � �0 0cos sin� � , y x y y� � � � � �0 0sin cos� � t , ãäå ( , )x y0 0 — ïðîèçâîëü-
íàÿ òî÷êà îáúåêòà A â ñîáñòâåííîé ñèñòåìå êîîðäèíàò îáúåêòà A; � — óãîë ïîâî-
ðîòà îáúåêòà A; ( , )x yt t — âåêòîð òðàíñëÿöèè îáúåêòà A â ïðîñòðàíñòâå R 2 .
Ïóñòü çàäàíî îãðàíè÷åíèå íà äîïóñòèìîå ðàññòîÿíèå � ìåæäó îáúåêòàìè
A è B, ò.å. dist ( , )A B �� , åñëè � �� � , èëè dist ( , )A B
�� , åñëè � �� � , ãäå
� �� �( ) — ìèíèìàëüíî (ìàêñèìàëüíî) äîïóñòèìîå ðàññòîÿíèå ìåæäó îáúåêòàìè
A è B, dist ( , ) min ( , )
,
A B d a b
a A b B
�
� �
, ãäå d a b( , ) — åâêëèäîâî ðàññòîÿíèå ìåæäó
òî÷êàìè a è b â R 2 .  òåðìèíàõ � -ôóíêöèé îãðàíè÷åíèå dist ( , )A B �� ìîæíî
îïèñàòü â âèäå
~
�AB �� , à dist ( , )
~
A B AB
�
� �� �0 � , ãäå
~
�AB — íîð-
ìàëèçîâàííàÿ � -ôóíêöèÿ îáúåêòîâ A è B [4].
Çàìåòèì, ÷òî �-ôóíêöèÿ çàâèñèò îò u x yA
t
A
t
A A� ( , , )� è u x yB
t
B
t
B B� ( , , )� .
Ïîñòðîåíèå íîðìàëèçîâàííûõ �-ôóíêöèé äëÿ ïðîèçâîëüíûõ �-îáúåêòîâ —
äîñòàòî÷íî ñëîæíàÿ ïðîöåäóðà. Êðîìå òîãî, íîðìàëèçîâàííûå �-ôóíêöèè íåèç-
áåæíî ñîäåðæàò ðàäèêàëû, ÷òî íåæåëàòåëüíî äëÿ ðåøåíèÿ îïòèìèçàöèîííûõ çà-
äà÷ óïàêîâêè è ðàñêðîÿ ñ ïðèìåíåíèåì ãðàäèåíòíûõ ìåòîäîâ îïòèìèçàöèè.
Îïðåäåëåíèå. Íåïðåðûâíàÿ âñþäó îïðåäåëåííàÿ ôóíêöèÿ
�
�AB íàçûâàåòñÿ
ïñåâäîíîðìàëèçîâàííîé �-ôóíêöèåé îáúåêòîâ A è B, åñëè âûïîëíÿþòñÿ ñëåäóþ-
ùèå ñâîéñòâà:
�
�AB � 0, åñëè dist ( , )A B � �,
�
�AB � 0, åñëè dist ( , )A B � �,
�
�AB
0, åñëè dist ( , )A B
�.
12 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
� Þ.Ã. Ñòîÿí, À.Â. Ïàíêðàòîâ, Ò.Å. Ðîìàíîâà, 2012
 ÷àñòíîñòè, èç îïðåäåëåíèÿ ñëåäóþò ñîîòíîøåíèÿ
dist ( , )
~
A B AB AB � � �� �� �
�
0,
(1)
dist {( , )
~
min , }A B AB AB AB
�
� � � �� �0 0� � �
�
.
Òàêèì îáðàçîì,
~
�AB � � âëå÷åò
�
� � �AB , ãäå � — çàäàííîå äîïóñòèìîå ðàñ-
ñòîÿíèå ìåæäó îáúåêòàìè A è B.
Ðàññìîòðèì ìíîæåñòâî
�
A A C� � ( )� , ãäå C ( )� — êðóã ðàäèóñà � ñ öåíòðîì
â íà÷àëå ñîáñòâåííîé ñèñòåìû êîîðäèíàò ìíîæåñòâà A, � — ñèìâîë îïåðàöèè
ñóììû Ìèíêîâñêîãî [5]. Òîãäà
� �
� �AB AB� , ãäå �
�
AB — �-ôóíêöèÿ äëÿ
�
A è B.
Êàê èçâåñòíî [3], âñåãäà ñóùåñòâóåò ñâîáîäíàÿ îò ðàäèêàëîâ �-ôóíêöèÿ äëÿ
äâóõ ïðîèçâîëüíûõ �-îáúåêòîâ, ãðàíèöà êîòîðûõ îïèñûâàåòñÿ ïîñëåäîâàòåëü-
íîñòüþ îòðåçêîâ ïðÿìûõ è äóã îêðóæíîñòåé.  ÷àñòíîñòè, �-ôóíêöèÿ äëÿ
�
A è B
ìîæåò áûòü îïðåäåëåíà òàê:
� � � �
�
�AB
n� min , , ....,{ }1 2 , (2)
ãäå
�
n — ÷èñëî ïàð áàçîâûõ îáúåêòîâ [3], ïîëó÷åííûõ â ðåçóëüòàòå äåêîìïîçè-
öèè îáúåêòîâ
�
A è B (â êà÷åñòâå áàçîâûõ îáúåêòîâ, ïðåäñòàâëåííûõ íèæå, ðàñ-
ñìàòðèâàþòñÿ îáúåêòû, äëÿ êîòîðûõ �-ôóíêöèè èçâåñòíû).  ýòîì ñëó÷àå äëÿ
ïîñòðîåíèÿ �-ôóíêöèè (2) íåîáõîäèìî ôîðìèðîâàíèå ìíîæåñòâà
�
A â ÿâíîì
âèäå.
Îäèí èç î÷åâèäíûõ ìåòîäîâ ôîðìèðîâàíèÿ ìíîæåñòâà
�
A — ïîñòðîåíèå ýê-
âèäèñòàíòû äëÿ ãðàíèöû ìíîæåñòâà
�
A ñ èñïîëüçîâàíèåì òðóäîåìêèõ àëãî-
ðèòìîâ, íàïðèìåð ïðèâåäåííûõ â [6, 7]. Â ïðåäåëàõ äàííîãî èññëåäîâàíèÿ ïðåä-
ëàãàåòñÿ èíîé ïîäõîä, ó÷èòûâàþùèé îñîáåííîñòè ïîñòðîåíèÿ �-ôóíêöèé äëÿ
�-îáúåêòîâ, ãðàíèöà êîòîðûõ îïèñûâàåòñÿ äóãàìè îêðóæíîñòåé è îòðåçêàìè
ïðÿìûõ.
 [3] ïðèâåäåíî óòâåðæäåíèå î òîì, ÷òî îáúåêò A âñåãäà ìîæåò áûòü ïðåä-
ñòàâëåí â âèäå
A A An� � �1 � . (3)
Çäåñü int intA Ai j� � �, i j I nn, , , ,� � { }1 2 � , i j� , Ai , A K D H Vj � �J { }, , , ,
int( )� — âíóòðåííîñòü ìíîæåñòâà ( )� ; K — âûïóêëûé ìíîãîóãîëüíèê, çàäàí-
íûé âåðøèíàìè p x yi i i� ( , ), i m�1, ,� ; D C T� � — êðóãîâîé ñåãìåíò,
T p p p� conv { }1 2 3, , , ãäå conv { }� — âûïóêëàÿ îáîëî÷êà ìíîæåñòâà { }� , C —
êðóã ðàäèóñà r ñ öåíòðîì ( , )x yc c , p1 è p2 — êîíöåâûå òî÷êè õîðäû ñåãìåíòà D;
H T C� � * , C R C* \� 2 int , T H� conv { } ñ âåðøèíàìè p1, p2 , p3 ;
V T C� � �C1 2
* , ãäå C2 — êðóã ðàäèóñà r r2 1� ; ïðè ýòîì îáúåêòû C1
* è C2
êàñàþòñÿ, ò.å. �
C C2 1 0
*
� [8].
Ïðåäñòàâèì
�
A â âèäå
�
A A A� � � , ãäå � �A A C� �fr ( ), fr ( )� — ãðàíèöà ìíî-
æåñòâà ( )� .
Ïîñêîëüêó fr A çàäàåòñÿ ïîñëåäîâàòåëüíîñòüþ äóã îêðóæíîñòåé a è îòðåçêîâ
ïðÿìûõ s, ïðåäñòàâèì ìíîæåñòâî �
�
A â âèäå îáúåäèíåíèÿ îáúåêòîâ èç J � { }
� �
R P, ,
ãäå
�
R s C� � ( )� (ðèñ. 1, à),
�
P a C� � ( )� . Â çàâèñèìîñòè îò ñîîòíîøåíèé � è ra
ìíîæåñòâî
�
P èìååò âèä
�
P1, åñëè �
ra (ðèñ. 1, á), èëè
�
P2 , åñëè � ra (ðèñ. 1, â).
Òàêèì îáðàçîì, èìååì
�
� �
�
�
A A Ap� � �1 , (4)
ãäå
� �
Ai �J .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 13
Ó÷èòûâàÿ (4), �-ôóíêöèÿ äëÿ
�
A è B ïðèìåò âèä
�
� � �AB AB
i pi I� �min , ,{ }, (5)
çäåñü �AB — �-ôóíêöèÿ ìíîæåñòâ A è B [3, 9], �i — �-ôóíêöèÿ ìíîæåñòâ
� �
Ai � J è B.
Ñëåäóÿ (3), B B Bq� � �1 � , B j �J , ïîýòîìó � �i ij qj I� �min { }, , ãäå
�ij — �-ôóíêöèÿ ìíîæåñòâ
� �
Ai � J è B j � J .
Òàêèì îáðàçîì, äëÿ ïîñòðîåíèÿ �-ôóíêöèè (5) òðåáóåòñÿ îïðåäåëåíèå
�-ôóíêöèé äëÿ âñåõ ïàð ìíîæåñòâ èç
�
J è J .
 ðàáîòå [9] ïðèâåäåí ïîëíûé êëàññ �-ôóíêöèé
äëÿ áàçîâûõ îáúåêòîâ èç J . Â äàííîì èññëåäî-
âàíèè ðàññìîòðèì �-ôóíêöèè äëÿ îáúåêòîâ
� �
Ai �J è B.
�-ôóíêöèÿ îáúåêòîâ
�
R è B. Ïîëàãàåì
�
R C R C� � �1 2 (ðèñ. 2), òîãäà
� � � �
�
RB C B C B RB� min { }1 2, , . (6)
�-ôóíêöèÿ îáúåêòîâ
�
P1 è B. Ïóñòü
�
P C E C1 1 2� � � , �
r (ðèñ. 3, à), ãäå E W H W� � �1 2 (ðèñ. 3, á), W D Ki i i� � ,
i �1 2, (ðèñ. 3, â).
Òîãäà �-ôóíêöèÿ èìååò âèä
� � � �
�
RB BW BW BH� min{ }1 2, , , (7)
ãäå � � �BW BD BT� min { }, [10].
14 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
Ðèñ. 1
à á â
�
R
�
P1
Ðèñ. 2
Ñ1 Ñ2
R
Ðèñ. 3
â
D
K
à á
C1
C2
E
W1 W2
H
�
P2
Åñëè
�
P èìååò âèä, ïðèâåäåííûé íà ðèñ. 4, ïðåäñòàâèì E W C H� � � �1 ( )
�W2 . Òîãäà
� � � � � � �
�
PB C B C B BW BW BH BC� min , , , , max ,{ { }}1 2 1 2 . (8)
�-ôóíêöèÿ îáúåêòîâ
�
P2 è B.  ñëó÷àå � r ïîëàãàåì
�
P C D C2 1 2� � �
(ðèñ. 5), òîãäà
� � � �
�
PB BC BC BD� min{ 1 2, , }, � � �BD BC BT� max ,{ }. (9)
Ïóñòü fr A li
i
m
�
�1
� , l s ai �{ }, , òîãäà �A Ai
i
m
�
�
�
�
1
, ãäå
� � �
A R Pi � �J { }, . Ïîñêîëüêó
êàæäûé èç ýëåìåíòîâ
�
Ai âêëþ÷àåò äâà êðóãà ñ öåíòðàìè â òî÷êàõ v l li i i� � �1,
i m�1, ,� , îáúåêòà A è ïðè ýòîì
� �
A A Ci i i� �� �1 1 ( )� , (m � �1 1), òî ìíîæåñòâî �
�
A
ìîæíî îïèñàòü â âèäå �
� �
�A li
i
m
�
�1
2
, ãäå êàæ-
äîé òî÷êå vi ñîîòâåòñòâóåò êðóã
�
l C vi i i� ( , )� , à êàæäîìó ýëåìåíòó
l s ai �{ }, — ýëåìåíò
�
l R s E ai �{ }( ), ( ) . Íà
ðèñ. 6 ïðèâåäåí ïðèìåð ïîñòðîåíèÿ ìíî-
æåñòâà �
�
A äëÿ ìíîæåñòâà A, ãðàíèöà êîòîðî-
ãî ñîñòîèò èç ÷åòûðåõ ýëåìåíòîâ
{ }s a s a1 2 3 4, , , :
�A li
i
� �
�
�
�
1
8
C E D Ri
i
i
i� �
� � �
1
4
1
2
� � .
Òàêèì îáðàçîì, �-ôóíêöèþ îáúåêòîâ
�
A è B ìîæíî îïðåäåëèòü òàê:
� � �
�
AB AB
i mi I� �min { }, , 2 , (10)
ãäå �i — �-ôóíêöèÿ ìíîæåñòâ
�
l C R Ei �{ }, , è B.
Òåîðåìà. Äëÿ �-îáúåêòîâ A è B, ãðàíèöû êîòîðûõ ôîðìèðóþòñÿ ïîñëåäîâà-
òåëüíîñòüþ äóã îêðóæíîñòåé è îòðåçêîâ ïðÿìûõ, âñåãäà ñóùåñòâóåò ñâîáîäíàÿ
îò ðàäèêàëîâ ïñåâäîíîðìàëèçîâàííàÿ �-ôóíêöèÿ
�
�AB .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 15
Ðèñ. 4
W1
C
H
W2
Ðèñ. 5
D
C2C1
Ðèñ. 6
C1
C3
A E
C4
C2
R1
R2
D
Ñïðàâåäëèâîñòü ýòîãî óòâåðæäåíèÿ ñëåäóåò èç óòâåðæäåíèÿ î ðàçáèåíèè
ìíîæåñòâà A íà áàçîâûå îáúåêòû [3] ôîðìóë, îïðåäåëÿþùèõ ïîëíûé êëàññ
�-ôóíêöèé äëÿ áàçîâûõ îáúåêòîâ [9] è ñîîòíîøåíèé (5)–(10).
Äëÿ ôîðìèðîâàíèÿ ïñåâäîíîðìàëèçîâàííîé �-ôóíêöèè
�
�AB òàêæå ìîæåò
èñïîëüçîâàòüñÿ �-ôóíêöèÿ �AB
�
äëÿ îáúåêòîâ A è
�
B. Ýòîò ôàêò ïîçâîëÿåò ñî-
êðàòèòü âû÷èñëèòåëüíûå ïðîöåäóðû çà ñ÷åò âûáîðà íàèìåíüøåãî ÷èñëà áàçî-
âûõ îáúåêòîâ ïðè äåêîìïîçèöèè, à òàêæå âûáîðà íàèáîëåå ïðîñòûõ �-ôóíêöèé.
Çàìåòèì, ÷òî ïðè ïîñòðîåíèè �-ôóíêöèé
�
�AB èñïîëüçóþòñÿ òîëüêî ëèíåé-
íûå, êâàäðàòè÷íûå è òðèãîíîìåòðè÷åñêèå ôóíêöèè âèäà sin � è cos �.
Àëãîðèòì ïîñòðîåíèÿ ïñåâäîíîðìàëèçîâàííûõ �-ôóíêöèé äëÿ �-îáúåêòîâ A
è B, ãðàíèöà êîòîðûõ çàäàíà ïîñëåäîâàòåëüíîñòüþ äóã îêðóæíîñòåé è îòðåçêîâ
ïðÿìûõ (ðèñ. 7), âêëþ÷àåò â ñåáÿ ñëåäóþùèå ýòàïû.
1. Äåêîìïîçèöèÿ îáúåêòîâ A è B â âèäå îáúåäèíåíèÿ áàçîâûõ îáúåêòîâ:
A A An� � �1 � , B B Bq� � �1 � (ðèñ. 8) ñîãëàñíî àëãîðèòìó, ïðèâåäåííîìó â [10].
2. Ïîñòðîåíèå ìíîæåñòâà �A (ðèñ. 9, à) â âèäå �A li
i
m
�
�
�
�
1
2
,
�
l C R Ei �{ }, , (ðèñ. 9, á).
16 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
Ðèñ. 7
A
B
Ðèñ. 8
A
B
Ðèñ. 9
�A
à á
3. Ïîñòðîåíèå ïñåâäîíîðìàëèçîâàííîé �-ôóíêöèè
�
�AB îáúåêòîâ A è B
â âèäå �-ôóíêöèè îáúåêòîâ
� �
A A A� � � è B:
� � �
�
AB
ij kj n q mi I j I k I� � � �min { }, , , , 2 ,
ãäå �ij — �-ôóíêöèÿ ìíîæåñòâ Ai � J è B j � J , �kj — �-ôóíêöèÿ ìíîæåñòâ
�
l C R Ei �{ }, , è B j � J .
Ïî ðåçóëüòàòàì èññëåäîâàíèé ñîçäàí ïðîãðàììíûé ïðîäóêò, ðåàëèçóþùèé
ïîñòðîåíèå ïñåâäîíîðìàëèçîâàííûõ �-ôóíêöèé äëÿ ïðîèçâîëüíûõ íåîðèåíòèðî-
âàííûõ äâóìåðíûõ �-îáúåêòîâ, ãðàíèöà êîòîðûõ çàäàíà ïîñëåäîâàòåëüíîñòüþ
äóã îêðóæíîñòåé è îòðåçêîâ ïðÿìûõ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. W ��a s c h e r G . , H a u � n e r H . , S c h u m a n n H . An improved typology of cutting and packing
problems // Europ. J. of Oper. Res. — 2007. — 183. — P. 1109–1130.
2. S t o y a n Y . G . , C h u g a y A . Packing cylinders and rectangular parallelepipeds with distances
between them // Ibid. — 2008. — 197. — P. 446–455.
3. C h e r n o v N . , S t o y a n Y . , R o m a n o v a T . Mathematical model and efficient algorithms
for object packing problem // Computational Geometry: Theory and Appls. — 2010. — 43, N 5. —
P. 535–553.
4. 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 Oper. Res. — 2010. — 179, N 1. —
P. 343–368.
5. M i n k o w s k i H . Dichteste gitterformige Lagerung kongruenter Korper. — Nachr. Qes. Wiss.
Qottingen, 1904. — P. 311–355.
6. F a r o u k i R . T . , K o e n i g T . , T a r a b a n i s K . A . , K o r e i n J . U . , B a t c h e l d e r J . S .
Path planning with offset curves for layered fabrication processes // J. Manufact. Syst. — 1995. —
N 14. — P. 355–368.
7. G r a y A . Parallel curves // Modern Differential Geometry of Curves and Surfaces with
Mathematica, 2nd ed., CRC Press, 1997. — P. 115–117.
8. S t o y a n Y . , 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 . Phi-functions for
primary 2D-objects // Studia Informatica Universalis. — 2001. — N 2. — P. 1–32.
9. Ã è ë ü Í . È . , Ð î ì à í î â à Ò . Å . , Ç ë î ò í è ê Ì . Â . Äåêîìïîçèöèÿ äâóìåðíûõ ãåîìåòðè-
÷åñêèõ îáúåêòîâ // Äîï. ÍÀÍ Óêðà¿íè. — 2010. — ¹ 8. — C. 43–48.
10. Ñ ò î ÿ í Þ . Ã . , Ð î ì à í î â à Ò . Å . , × å ð í î â Í . È . , Ï à í ê ð à ò î â À . Â . Ïîëíûé êëàññ
�-ôóíêöèé äëÿ áàçîâûõ îáúåêòîâ // Òàì æå. — 2010. — ¹ 12. — C. 25–30.
Ïîñòóïèëà 07.12.2010
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 17
|
| id | nasplib_isofts_kiev_ua-123456789-84104 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T17:31:51Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Стоян, Ю.Г. Панкратов, А.В. Романова, Т.Е. 2015-07-03T08:01:54Z 2015-07-03T08:01:54Z 2012 Математическое моделирование ограничений на допустимые расстояния между геометрическими объектами / Ю.Г. Стоян, А.В. Панкратов, Т.Е. Романова // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 12-17. — Бібліогр.: 10 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84104 519.85 Введено поняття вільної від радикалів псевдонормалізованої Ф-функції, що дозволяє описувати обмеження на мінімально та максимально припустимі відстані між двовимірними φ-об’єктами. Допускаються афінні відображення трансляції та повороту. Наведено теорему про існування вільної від радикалів псевдонормалізованої Ф-функції для пари довільних φ-об’єктів, границі яких формуються об’єднанням дуг кіл і відрізків прямих. Запропоновано ефективний алгоритм побудови псевдонормалізованих Ф-функцій. The paper introduces the concept of radical-free pseudonormalized Ф-functions, which allows us to describe constraints for minimum and maximum a φ-objects. We allow translations and rotations of φ-objects in a two-dimensional Euclidean space. The theorem about the existence of a radical-free pseudonormalized Ф-function for a pair of arbitrary-shaped φ-objects whose frontiers are formed by the union of line segments and circular arcs is formulated. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Математическое моделирование ограничений на допустимые расстояния между геометрическими объектами Математичне моделювання обмежень на припустимі відстані між геометричними об’єктами Мathematical modeling of distance constrains for two-dimensional objects Article published earlier |
| spellingShingle | Математическое моделирование ограничений на допустимые расстояния между геометрическими объектами Стоян, Ю.Г. Панкратов, А.В. Романова, Т.Е. Кибернетика |
| title | Математическое моделирование ограничений на допустимые расстояния между геометрическими объектами |
| title_alt | Математичне моделювання обмежень на припустимі відстані між геометричними об’єктами Мathematical modeling of distance constrains for two-dimensional objects |
| title_full | Математическое моделирование ограничений на допустимые расстояния между геометрическими объектами |
| title_fullStr | Математическое моделирование ограничений на допустимые расстояния между геометрическими объектами |
| title_full_unstemmed | Математическое моделирование ограничений на допустимые расстояния между геометрическими объектами |
| title_short | Математическое моделирование ограничений на допустимые расстояния между геометрическими объектами |
| title_sort | математическое моделирование ограничений на допустимые расстояния между геометрическими объектами |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84104 |
| work_keys_str_mv | AT stoânûg matematičeskoemodelirovanieograničeniinadopustimyerasstoâniâmeždugeometričeskimiobʺektami AT pankratovav matematičeskoemodelirovanieograničeniinadopustimyerasstoâniâmeždugeometričeskimiobʺektami AT romanovate matematičeskoemodelirovanieograničeniinadopustimyerasstoâniâmeždugeometričeskimiobʺektami AT stoânûg matematičnemodelûvannâobmeženʹnapripustimívídstanímížgeometričnimiobêktami AT pankratovav matematičnemodelûvannâobmeženʹnapripustimívídstanímížgeometričnimiobêktami AT romanovate matematičnemodelûvannâobmeženʹnapripustimívídstanímížgeometričnimiobêktami AT stoânûg mathematicalmodelingofdistanceconstrainsfortwodimensionalobjects AT pankratovav mathematicalmodelingofdistanceconstrainsfortwodimensionalobjects AT romanovate mathematicalmodelingofdistanceconstrainsfortwodimensionalobjects |