Полный класс Φ-функций для базовых двумерных φ-объектов
Розглядається сім'я J базових двовимірних φ-об'єктів. Допускаються афінні відображення φ-об'єктів типу трансляції й повороту у двовимірному арифметичному евклідовому просторі. Будується повний клас Φ-функцій для об'єктів сім'ї J з використанням тільки нескінченно диференційо...
Saved in:
| Date: | 2010 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Видавничий дім "Академперіодика" НАН України
2010
|
| Series: | Доповіді НАН України |
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/31109 |
| 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: | Полный класс Φ-функций для базовых двумерных φ-объектов / Ю.Г. Стоян, Т.Е. Романова, Н.И. Чернов, А.В. Панкратов // Доп. НАН України. — 2010. — № 12. — С. 25-30. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-31109 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-311092014-02-23T12:28:28Z Полный класс Φ-функций для базовых двумерных φ-объектов Стоян, Ю.Г. Романова, Т.Е. Чернов, Н.И. Панкратов, А.В. Математика Розглядається сім'я J базових двовимірних φ-об'єктів. Допускаються афінні відображення φ-об'єктів типу трансляції й повороту у двовимірному арифметичному евклідовому просторі. Будується повний клас Φ-функцій для об'єктів сім'ї J з використанням тільки нескінченно диференційованих функцій. Наведено теорему про існування вільної від радикалів Φ-функції для пари довільних φ-об'єктів, межі яких формуються об'єднанням дуг кіл і відрізків прямих. The article considers a family J of basic two-dimensional φ-objects. We allow translation and rotation affine mappings of the φ-objects in a two-dimensional Euclidean space. We derive a complete class of Φ-functions for φ-objects of the family J, using infinitely differentiable functions only. The theorem of existence of a free radical Φ-function for a pair of arbitrary φ-objects, whose boundaries are formed by the union of line segments and circular arcs, is formulated. 2010 Article Полный класс Φ-функций для базовых двумерных φ-объектов / Ю.Г. Стоян, Т.Е. Романова, Н.И. Чернов, А.В. Панкратов // Доп. НАН України. — 2010. — № 12. — С. 25-30. — Бібліогр.: 8 назв. — рос. 1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/31109 519.85 ru Доповіді НАН України Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Математика Математика |
| spellingShingle |
Математика Математика Стоян, Ю.Г. Романова, Т.Е. Чернов, Н.И. Панкратов, А.В. Полный класс Φ-функций для базовых двумерных φ-объектов Доповіді НАН України |
| description |
Розглядається сім'я J базових двовимірних φ-об'єктів. Допускаються афінні відображення φ-об'єктів типу трансляції й повороту у двовимірному арифметичному евклідовому просторі. Будується повний клас Φ-функцій для об'єктів сім'ї J з використанням тільки нескінченно диференційованих функцій. Наведено теорему про існування вільної від радикалів Φ-функції для пари довільних φ-об'єктів, межі яких формуються об'єднанням дуг кіл і відрізків прямих. |
| format |
Article |
| author |
Стоян, Ю.Г. Романова, Т.Е. Чернов, Н.И. Панкратов, А.В. |
| author_facet |
Стоян, Ю.Г. Романова, Т.Е. Чернов, Н.И. Панкратов, А.В. |
| author_sort |
Стоян, Ю.Г. |
| title |
Полный класс Φ-функций для базовых двумерных φ-объектов |
| title_short |
Полный класс Φ-функций для базовых двумерных φ-объектов |
| title_full |
Полный класс Φ-функций для базовых двумерных φ-объектов |
| title_fullStr |
Полный класс Φ-функций для базовых двумерных φ-объектов |
| title_full_unstemmed |
Полный класс Φ-функций для базовых двумерных φ-объектов |
| title_sort |
полный класс φ-функций для базовых двумерных φ-объектов |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| publishDate |
2010 |
| topic_facet |
Математика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/31109 |
| citation_txt |
Полный класс Φ-функций для базовых двумерных φ-объектов / Ю.Г. Стоян, Т.Е. Романова, Н.И. Чернов, А.В. Панкратов // Доп. НАН України. — 2010. — № 12. — С. 25-30. — Бібліогр.: 8 назв. — рос. |
| series |
Доповіді НАН України |
| work_keys_str_mv |
AT stoânûg polnyjklassphfunkcijdlâbazovyhdvumernyhphobʺektov AT romanovate polnyjklassphfunkcijdlâbazovyhdvumernyhphobʺektov AT černovni polnyjklassphfunkcijdlâbazovyhdvumernyhphobʺektov AT pankratovav polnyjklassphfunkcijdlâbazovyhdvumernyhphobʺektov |
| first_indexed |
2025-07-03T11:29:19Z |
| last_indexed |
2025-07-03T11:29:19Z |
| _version_ |
1836625071818407936 |
| fulltext |
УДК 519.85
© 2010
Член-корреспондент НАН Украины Ю.Г. Стоян, Т. Е. Романова,
Н.И. Чернов, А. В. Панкратов
Полный класс Φ-функций для базовых двумерных
ϕ-объектов
Розглядається сiм’я ℑ базових двовимiрних ϕ-об’єктiв. Допускаються афiннi вiдображе-
ння ϕ-об’єктiв типу трансляцiї й повороту у двовимiрному арифметичному евклiдово-
му просторi. Будується повний клас Φ-функцiй для об’єктiв сiм’ї ℑ з використанням
тiльки нескiнченно диференцiйованих функцiй. Наведено теорему про iснування вiльної
вiд радикалiв Φ-функцiї для пари довiльних ϕ-об’єктiв, межi яких формуються об’єдна-
нням дуг кiл i вiдрiзкiв прямих.
Фундаментальной основой математического моделирования оптимизационных задач упа-
ковки и раскроя [1] является аналитическое описание отношений включения, пересечения,
касания геометрических объектов. В статье [2] приводится достаточно полный обзор и срав-
нение современных методов моделирования отношений двумерных геометрических объек-
тов. Наиболее эффективным средством является метод Φ-функций [3–6].
Пусть A ⊂ R2 и B ⊂ R2 — замкнутые ϕ-объекты [3, 4], граница которых задана последо-
вательностью дуг окружностей и отрезков прямых, здесь R2 — двумерное арифметическое
евклидовое пространство. Допускаются аффинные отображения трансляции и поворота
множеств A и B в пространстве R2.
Здесь и далее полагаем, что положение объекта A в пространстве R2 определяет вектор
u = (xt, yt, θ), а координаты точек (x, y) ∈ A определяются по формуле
x = x0 cos θ + y0 sin θ + xt, y = −x0 sin θ + y0 cos θ + yt,
где (x0, y0) — произвольная точка объекта A в собственной системе координат объекта A,
θ — угол поворота, (xt, yt) — вектор трансляции объекта A в пространстве R2.
В [4] показано, что множества A и B (рис. 1) всегда могут быть представлены в виде
A = A1
⋃
· · ·
⋃
Ap, B = B1
⋃
· · ·
⋃
Bq, (1)
где intAi
⋂
intBj = ∅, i ∈ Ip = {1, 2, . . . , p}, j ∈ Iq, i 6= j, Ai, Bj принадлежат семейст-
ву базовых объектов ℑ = {K,D,H, V }, int(·) — внутренность множества (·). Здесь K —
Рис. 1. Объекты A и B
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2010, №12 25
Рис. 2. Базовые объекты D, H , V
выпуклый многоугольник, заданный вершинами (xi, yi), i = 1, . . . ,m, а стороны K — урав-
нениями αix+βiy+γi = 0, α2
i +β
2
i = 1; D = T
⋂
C (рис. 2, а), T — треугольник c вершинами
pi = (xi, yi), i = 1, 2, 3, C — круг радиуса r с центром (xc, yc), p1 = (x1, y1) и p2 = (x2, y2) —
концевые точки хорды сегмента D;H = T
⋂
C∗ (см. рис. 2, б ), C∗ = R2\intC, T = conv{H},
где conv{·} — выпуклая оболочка множества {·}; V = T
⋂
C∗
1
⋂
C2 (см. рис. 2, в), где C2 —
круг радиуса r2 > r1, при этом ΦC∗C = 0, ΦC∗C — Φ-функция C∗
2 и C1 [4, 6]. Подробное опи-
сание объектов семейства ℑ и метод декомпозиции произвольных ϕ-объектов на базовые
объекты приведены в работах [4, 7].
Как известно [4, 5], Φ-функция для объектов A и B вида (1) определяется так:
ΦAB(uA, uB) = min{Φij(uA, uB), i ∈ Ip, j ∈ Iq}, (2)
где Φij — Φ-функция для множеств Ai ∈ ℑ, Bj ∈ ℑ.
Из (2) следует, что для построения функции ΦAB необходимо построить полный класс
Φ-функций Φℑ для множеств из семейства ℑ, т. е.
Φℑ = {ΦKK,ΦKH ,ΦKD,ΦKV ,ΦDD,ΦDH ,ΦDV ,ΦHH ,ΦHV ,ΦV V }.
Более того, поскольку для эффективного решения класса задач упаковки и раскроя
используются градиентные методы оптимизации, Φ-функция ΦAB(uA, uB), а следовательно,
и функция Φij ∈ Φℑ должны быть свободны от радикалов.
Определим каждую Φ-функцию из класса Φℑ.
Прежде всего рассмотрим Φ-функции для выпуклых объектов E ∈ {K,C}
ΦDE = max{ΦCE ,ΦTE}, (3)
где Φ-функции ΦTK (в общем случае ΦKK) и ΦCC приведены в [4–6], а ΦCK (ΦKC) опре-
делена так:
ΦCK = max
i=1,...,m
max{αix+ βiy + γi − r, ψi}, (4)
ψi = min{(xC − xi)
2 + (yC − yi)
2 − r2,
(βi−1 − βi)(xC − xi)− (αi−1 − αi)(yC − yi) + r(αi−1βi − αiβi−1)}.
26 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2010, №12
Рис. 3. Объекты H = G
⋂
T и G
Φ-функция для сегментов Di = Ci
⋂
Ti, i = 1, 2, имеет вид
ΦDD = max{ΦC1C2 ,ΦC1T2 ,ΦT1C2 ,ΦT1T2}. (5)
Прежде чем построить Φ-функции для невыпуклых базовых объектов, определим
Φ-функции для пар объектов C∗ и H; C∗ и D.
Φ-функция для C∗ и H имеет вид
ΦC∗H = min
i=1,2,3
(r2C − (xC − xi)
2 − (yC − yi)
2),
где (xi, yi), i = 1, 2, 3, — вершины T = conv{H}.
Далее полагаем D = T
⋂
C ′, где C ′ — круг радиуса rC′ с центром (xC′ , yC′). Тогда, если
rC′ > rC , имеем ΦC∗D = ψ0, где
ψ0 = min
i=1,2
(r2C − (xC − xi)
2 − (yC − yi)
2). (6)
Если rC′ < rC , то
ΦC∗D = min{ψ0,max{ψ1, χ1,−χ2}}, (7)
где ψ0 определяется (6),
χi = (xC′ − xC)(yi − yC′)− (yC′ − yC)(xi − xC′), i = 1, 2,
ψ1 =
r2C
(rC − rC′)2
· ΦC∗C′
.
Далее рассмотрим объекты K и H. Для H = T
⋂
C∗ введем множество G = C∗
⋂
P , где
P = {αx + βy + γ 6 0}, T ⊂ P , тогда H = G
⋂
T (рис. 3, a).
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2010, №12 27
Если E — любой выпуклый ϕ-объект, то ΦEH = max{ΦET ,ΦEG}, в частности
ΦKH = max{ΦKT ,ΦKG}, (8)
где
ΦKG = min{ΦK1K ,ΦK2K , ψ}, (9)
здесь ψ = min
i=1,...,m
max{r2C − (xC − xi)
2 − (yC − yi)
2, αxi + βyi + γ}, rC — радиус круга C =
= R2 \ intC∗ (см. рис. 3, а).
Далее рассмотрим объекты D и H. Пусть D = TD
⋂
CD, H = G
⋂
T , G = C∗
⋂
P
и rD > rC , тогда функция ΦDH определяется формулами (8), (9) при m = 2.
Если rD < rC , то Φ-функция для D и H задается так:
ΦDH = max{ΦDT ,ΦDG}, (10)
где
ΦDG = min{ΦK1D,ΦK2D, ψ}, (11)
здесь ψ = max{ΦC∗D,ΦGTD ,ΦGCD}, ΦGTD — Φ-функция для G и TD; ΦGCD — Φ-функция
для G и круга CD вида
ΦGCD = max{ΦC∗CD ,ΦPCD ,min{ω1, ψ1, ω2, ψ2}}, (12)
где ωi = (x − xi)
2 + (y − yi)
2 − (rD)
2, ψi = 0 — уравнения прямых Li, проходящих через
точки pi1 и pi2, ψi(Oc) > 0, i = 1, 2 (см. рис. 3, б ).
Пусть Hi = Gi
⋂
Ti, i = 1, 2, Gi = C∗
i
⋂
Pi, где Pi = {αix+ βiy + γi 6 0}, Ti ⊂ Pi. Тогда
Φ-функцию для объектов H1 и H2 можно определить следующим образом:
ΦHH = max{ΦT1H2 ,ΦT2H1 ,ΦG1H2 ,ΦG2H1 , ω}, (13)
где ΦTH определяется выражением (8),
ω = min{α1x23 + β1y23 + γ1, α2x13 + β2y13 + γ2,
max
i=1,2
min{(rC1
)2 − (xC1
− x2i)
2 − (yC1
− y2i)
2, (rC2
)2 − (xC2
− x1i)
2 − (yC2
− y1i)
2},
а ΦGH задается в виде
ΦGH = min{ΦK1H ,ΦK2H , ψ}, (14)
здесь ψ = min
i=1,2,3
max{r2C − (xC − xi)
2 − (yC − yi)
2, αxi + βyi + γ}.
Далее рассмотрим Φ-функции для объекта V и объектов семейства ℑ = {K,D,H, V }.
Пусть V = HV
⋂
W , где W = D
⋃
T , T — треугольник с вершинами p1, p2, p3, D —
сегмент с концевыми “вершинами” p2, p3 (рис. 4).
Φ-функцию для объектов V и K зададим так:
ΦVK = max{ΦHK ,ΦWK}, (15)
где ΦWK = min{ΦDK ,ΦTK}.
28 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2010, №12
Рис. 4. Объект V = HV
⋂
W
Φ-функция для пар объектов V и D, V и H определяется аналогично:
ΦV D = max{ΦHD,ΦWD}, (16)
ΦV H = max{ΦHV H ,ΦWH}, (17)
где ΦWD = min{ΦDD,ΦTD}, ΦWH = min{ΦDH ,ΦTH}.
Пусть Vi, i = 1, 2, где Vi = Hi
⋂
Wi, Wi = Di
⋃
Ti, тогда Φ-функция для V1 и V2 примет
вид
ΦV V = max{ΦH1H2 ,ΦH1W2 ,ΦH2W1 ,ΦW1W2}, (18)
где ΦWW = min{ΦD2D1 ,ΦT2T1 ,ΦD2T1 ,ΦD1T2} — Φ-функция для объектов W1 = D1
⋃
T1
и W2 = D2
⋃
T2.
Таким образом, формулы (3)–(18) описывают полный класс Φ-функций для базовых
объектов семейства ℑ.
Из (1)–(18) вытекает следующее утверждение.
Теорема. Для замкнутых ϕ-объектов A и B, границы которых формируются объеди-
нением дуг окружностей и отрезков прямых, всегда существует свободная от радикалов
Φ-функция.
Следует отметить, что для формирования Φ-функций используются только бесконечно
дифференцируемые функции.
Рассмотрим пример построения Φ-функции для объектов A и B, приведенных на рис. 1.
Применения алгоритм декомпозиции [7], имеем: A = A1
⋃
· · ·
⋃
A5 и B = B1
⋃
· · ·
⋃
B7. То-
гда Φ-функция ΦAB примет вид ΦAB = min{Φ11,Φ21, . . . ,Φ57}, где Φij ∈ {ΦKK ,ΦDK ,ΦHK ,
ΦHD,ΦHH}, i = 1, 2, . . . , 5, j = 1, 2, . . . , 7.
Результаты данных исследований могут быть использованы при решении 2D-задач упа-
ковки и раскроя [1, 2, 8].
1. Wäscher G., Haußner, H., Schumann H. An improved typology of cutting and packing problems // Eur.
J. Operat. Res. – 2007. – 183, Is. 3, No 16. – P. 1109–1130.
2. Bennell J. A., Oliveira J. F. The geometry of nesting problems: a tutorial // Ibid. – 2008. – 184. – P. 397–
415.
3. Stoyan Yu.G. Φ-function and its basic properties // Доп. НАН України. – 2001. – No 8. – С. 112–117.
4. Chernov N., Stoyan Y., Romanova T. Mathematical model and efficient algorithms for object packing
problem // Comput. Geometry: Theory and Applications. – 2010. – 43, No 5. – P. 535–553.
5. Bennell J., Scheithauer G., Stoyan Yu., Romanova T. Tools of mathematical modeling of arbitrary object
packing problems // J. Ann. Oper. Res. – 2010. – 179, No 1. – 343–368.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2010, №12 29
6. Stoyan Yu., Terno J., Scheithauer G., Gil N., Romanova T. Phi-functions for primary 2D-objects // Studia
Informatica Universalis. – 2001. – 2. – P. 1–32.
7. Гиль Н.И., Романова Т. Е., Злотник М.В. Декомпозиция двумерных геометрических объектов //
Доп. НАН України. – 2010. – № 7. – С. 33–37.
8. Burke E., Hellier R., Kendall G., Whitwell G. A new bottom-left-fill heuristic algorithm for the two-
dimensional irregular packing problem // Oper. Res. – 2006. – 54. – P. 587–601.
Поступило в редакцию 21.04.2010Институт проблем машиностроения
им. А.Н. Подгорного НАН Украины, Харьков
Университет Алабамы, Бирмингем, США
Corresponding Member of the NAS of Ukraine Yu.G. Stoyan, T. E. Romanova,
N. I. Chernov, A. V. Pankratov
Complete class of Φ-functions for basic two-dimensional ϕ-objects
The article considers a family ℑ of basic two-dimensional ϕ-objects. We allow translation and
rotation affine mappings of the ϕ-objects in a two-dimensional Euclidean space. We derive a comp-
lete class of Φ-functions for ϕ-objects of the family ℑ, using infinitely differentiable functions
only. The theorem of existence of a free radical Φ-function for a pair of arbitrary ϕ-objects, whose
boundaries are formed by the union of line segments and circular arcs, is formulated.
30 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2010, №12
|