Псевдонормализованные Φ-функции для двумерных φ-объектов
Вводиться поняття вільної від радикалів псевдонормалізованої Φ-функції, що дозволяє описувати обмеження на мінімально та максимально припустимі відстані між двовимірними φ-об'єктами. Будується повний клас псевдонормалізованих Φ-функцій для класу базових φ-об'єктів. Допускаються афінні відо...
Збережено в:
| Опубліковано в: : | Доповіді НАН України |
|---|---|
| Дата: | 2011 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/37809 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Псевдонормализованные Φ-функции для двумерных φ-объектов / Ю.Г. Стоян, Т.Е. Романова, Н.И. Чернов // Доп. НАН України. — 2011. — № 6. — С. 29-34. — Бібліогр.: 10 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860089250724184064 |
|---|---|
| author | Стоян, Ю.Г. Романова, Т.Е. Чернов, Н.И. |
| author_facet | Стоян, Ю.Г. Романова, Т.Е. Чернов, Н.И. |
| citation_txt | Псевдонормализованные Φ-функции для двумерных φ-объектов / Ю.Г. Стоян, Т.Е. Романова, Н.И. Чернов // Доп. НАН України. — 2011. — № 6. — С. 29-34. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | Вводиться поняття вільної від радикалів псевдонормалізованої Φ-функції, що дозволяє описувати обмеження на мінімально та максимально припустимі відстані між двовимірними φ-об'єктами. Будується повний клас псевдонормалізованих Φ-функцій для класу базових φ-об'єктів. Допускаються афінні відображення трансляції та повороту. Наводиться теорема про існування вільної від радикалів псевдонормалізованої Φ-функції для пари довільних φ-об'єктів, границі яких формуються об'єднанням дуг кіл і відрізків прямих.
We consider a concept of radical free pseudonormalized Φ-functions which allow us to describe restrictions on minimal and maximal allowable distances between two-dimensional φ-objects. A complete class of pseudonormalized Φ-functions for a family of basic two-dimensional φ-objects is derived. We allow translations and rotations of the φ-objects in a two-dimensional Euclidean space. The theorem of 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:21:52Z |
| format | Article |
| fulltext |
УДК 519.85
© 2011
Член-корреспондент НАН Украины Ю.Г. Стоян, Т. Е. Романова,
Н.И. Чернов
Псевдонормализованные Φ-функции для двумерных
ϕ-объектов
Вводиться поняття в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дрiзкiв
прямих.
При построении математических моделей оптимизационных задач упаковки и раскроя [1]
возникает необходимость в формализации ограничений на допустимые расстояния между
реальными объектами. Применение нормализованных Φ-функций [2] иногда приводит к сло-
жным вычислительным процедурам. Цель данной работы — построение свободных от ради-
калов Φ-функций, учитывающих ограничения на допустимые расстояния между двумер-
ными объектами.
Имеются замкнутые ограниченные ϕ-объекты A, B ⊂ R
2 [3]. Полагаем, что граница
объекта A задана последовательностью дуг окружностей и отрезков прямых, здесь R
2 —
двумерное арифметическое евклидовое пространство. Допускаются аффинные отображе-
ния трансляции и поворота объекта A. Положение A в пространстве R
2 определяет вектор
u = (xt, yt, θ), а координаты точек (x, y) ∈ A определяются по формуле x = x0 cos θ +
+ y0 sin θ + xt, y = −x0 sin θ + y0 cos θ + yt, где (x0, y0) — произвольная точка объекта A
в собственной системе координат объекта A, θ — угол поворота объекта A, (xt, yt) — вектор
трансляции объекта A в пространстве R
2.
Пусть задано ограничение на допустимое расстояние ρ между объектами A и B, т. е.
dist(A,B) > ρ−, если ρ = ρ−, или dist(A,B) 6 ρ+, если ρ = ρ+, где ρ− (ρ+) — минимально
(максимально) допустимое расстояние между объектами A и B, dist(A,B) = min
a∈A,b∈B
d(a, b),
d(a, b) — евклидово расстояние в R
2. В терминах Φ-функций ограничение dist(A,B) > ρ−
можно описать в виде Φ̃AB
> ρ−, а dist(A,B) 6 ρ+ ⇔ 0 6 Φ̃AB
6 ρ+, где Φ̃AB — норма-
лизованная Φ-функция объектов A и B [4]. Заметим, что Φ̃AB зависит от uA = (xAt , y
A
t , θ
A)
и uB = (xBt , y
B
t , θ
B).
Построение нормализованных Φ-функций для произвольных ϕ-объектов — достаточно
сложная процедура. Кроме того, нормализованные Φ-функции неизбежно содержат ради-
калы, что нежелательно для решения оптимизационных задач упаковки и раскроя с при-
менением градиентных методов оптимизации.
Определение. Непрерывная всюду определенная функция
a
ΦAB называется псевдонор-
мализованной Φ-функцией объектов A и B, если выполняются следующие свойства:
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2011, №6 29
a
ΦAB > 0, если dist(A,B) > ρ,
a
ΦAB = 0, если dist(A,B) = ρ,
a
ΦAB < 0, если dist(A,B) < ρ.
В частности, из определения следуют соотношения
dist(A,B) > ρ− ⇔ Φ̃AB
> ρ− ⇔
a
ΦAB
> 0,
dist(A,B) 6 ρ+ ⇔ 0 6 Φ̃AB
6 ρ+ ⇔
a
ΦAB
6 0, ΦAB
> 0.
(1)
Таким образом, Φ̃AB = ρ влечет
a
ΦAB = 0, где ρ — заданное допустимое расстояние
между объектами A и B.
Рассмотрим множество
a
A = A ⊕ C(ρ), где C(ρ) — круг радиуса ρ с центром в начале
собственной системы координат множества A, ⊕ — символ операции суммы Минковского [5].
Тогда
a
ΦAB = Φ
a
AB , где Φ
a
AB — Φ-функция
a
A и B.
В [3] показано, что всегда существует свободная от радикалов Φ-функция для двух
произвольных ϕ-объектов, граница которых описывается последовательностью отрезков
прямых и дуг окружностей, в частности, для
a
A и B, которая может быть определена как
Φ
a
AB = min{Φ1,Φ2, . . . ,Φ“n}, (2)
где Φi, i = 1, . . ., “n, “n — число пар базовых объектов [3], полученных в результате де-
композиции объектов
a
A и B. В этом случае для определения Φ-функции (2) необходимо
построение множества
a
A в явном виде.
Один из очевидных методов формирования множества
a
A — построение эквидистан-
ты [6, 7] для границы множества A с использованием трудоемких алгоритмов, например,
приведенных в [6, 7]. В пределах данного исследования предлагается иной подход, учитыва-
ющий особенности построения Φ-функций для ϕ-объектов, границы которых описываются
дугами окружностей и отрезками прямых.
В [3] приведено утверждение о том, что объект A всегда может быть представлен в виде
A = A1
⋃
. . .
⋃
Ap, (3)
где intAi
⋂
intAj = ∅, i, j ∈ Ip = {1, 2, . . . , p}, i 6= j, Ai, Aj ∈ ℑ = {K,D,H, V }, int(·) —
внутренность множества (·), K — выпуклый многоугольник, заданный вершинами pi =
= (xi, yi), i = 1, . . . ,m; D = C
⋂
T — круговой сегмент, T = conv{p1, p2, p3}, C — круг
радиуса r с центром (xc, yc), p1 и p2 — концевые точки хорды сегмента D; H = T
⋂
C∗,
C∗ = R
2\intC, T = conv{H}, заданный вершинами pi = (xi, yi), i = 1, 2, 3; V = T
⋂
C∗
1
⋂
C2,
где C2 — круг радиуса r2 > r1, при этом ΦC∗C = 0, ΦC∗C — Φ-функция C∗
2 и C1 [8].
Из этого утверждения следует, что множество
a
A всегда может быть задано так:
a
A =
a
A1
⋃
. . .
⋃ a
Ap, (4)
где
a
Ai ∈ ℑ = {
a
K,
a
D,
a
H,
a
V },
a
Ai = Ai ⊕ C(ρ).
30 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2011, №6
Рис. 1. Объекты
a
K (m = 3) и
a
D. Декомпозиция объектов
a
K и
a
D
Рис. 2. Объект
a
H: ρ > r, α < 90
◦. Объект
a
V : ρ < r1
Учитывая (4), Φ-функция для
a
A и B примет вид
a
ΦAB = min{Φij , i ∈ Ip, j ∈ Iq}, (5)
где Φij — Φ-функция для множеств
a
Ai ∈
a
ℑ, Bj ∈ ℑ.
Из (5) следует необходимость построения полного класса псевдонормализованных
Φ-функций
a
ΦAB для множеств A и B из семейства базовых объектов ℑ, что эквивален-
тно построению Φ-функций
a
ΦB для всех пар
a
A ∈
a
ℑ и B ∈ ℑ.
Осуществим декомпозицию каждого объекта
a
A ∈
a
ℑ, используя алгоритм [9]. Заметим,
что результат декомпозиции объектов
a
K и
a
D (рис. 1, a) может быть однозначно определен
так (см. рис. 1, б ):
a
K=
m⋃
i=1
Di
⋃
K2m, где K2m = conv{“p1, . . . , “p2m};
a
D =
3⋃
i=1
Di
⋃
K4, где K4 = conv{“p1, . . . , “p4}.
В случае декомпозиции объектов
a
A ∈ {
a
H,
a
V } на базовые объекты из множества ℑ
(рис. 2), в зависимости от соотношений ρ и r, а также от величины угла α, имеем:
a
H =
3⋃
i=1
Di
⋃
K5, где K5 = conv{“p1, . . . , “p5} (рис. 3, а), если ρ > r, α 6 90◦;
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2011, №6 31
Рис. 3. Объекты вида
a
H. Декомпозиция объектов
a
H
Рис. 4. Объекты вида
a
V и декомпозиция объектов
a
V
a
H =
5⋃
i=1
Di
⋃
K4
⋃
K5, где K4 = conv{“p1, . . . , “p4}, K5 = conv{“p1, . . . , “p5}
(см. рис. 3, б ), если ρ = r, α 6 90◦;
a
H =
5⋃
i=1
Di
⋃
H ′
⋃
K6
⋃
K5, где K6 = conv{“p1, . . . , “p6}, K5 = conv{“p1, . . . , “p5}
(см. рис. 3, в), если ∀α ρ < r;
a
H =
5⋃
i=1
Di
⋃
K7, где K7=conv{“p1, . . . , “p7} (см. рис. 3, г), если ρ> r, α> 90◦;
a
V =
6⋃
i=1
Di
⋃
K7, где K7 = conv{“p1, . . . , “p7} (см. рис. 4, a), если ρ > r1;
a
V =
6⋃
i=1
Di
⋃
H ′
⋃
K6
⋃
K5, где K6 = conv{“p1, . . . , “p6}, K5 = conv{“p1, . . . , “p5}
(см. рис. 4, б ), если ρ < r1.
32 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2011, №6
Тогда для B ∈ ℑ, имеем
Φ
a
KB = min{ΦKB,ΦDiB, i = 1, . . . ,m}; (6)
Φ
a
DB = min{ΦKB,ΦDiB, i = 1, 2, 3}; (7)
Φ
a
HB = min{ΦKB,ΦDiB, i = 1, 2, 3}, если ρ > r, α 6 90◦, (8)
Φ
a
HB = min{ΦKjB , j = 1, 2,ΦDiB, i = 1, . . ., 5}, если ρ = r, α 6 90◦,
Φ
a
HB = min{ΦH′B ,ΦKjB , j = 1, 2,ΦDiB, i = 1, . . ., 5}, если ∀α ρ < r,
Φ
a
HB = min{ΦKB,ΦDiB, i = 1, . . ., 5}, если ρ > r, α > 90◦;
Φ
a
V B = min{ΦKB,ΦDiB, i = 1, . . ., 6}, если ρ > r1, (9)
Φ
a
V B = min{ΦH′B ,ΦKjB , j = 1, 2,ΦDiB , i = 1, . . ., 6}, если ρ < r1, (10)
где ΦKB, ΦDB, ΦHB — Φ-функции для объектов K,D,H ∈ ℑ и объекта B.
Таким образом, формулы (6)–(10) описывают полный класс псевдонормализованных
Φ-функций
a
ΦAB для базовых объектов A,B ∈ ℑ.
Из (1)–(10) и вида Φ-функций для базовых объектов [10] следует справедливость сле-
дующего утверждения.
Теорема. Для ϕ-объектов A и B, границы которых формируются последовательнос-
тью дуг окружностей и отрезков прямых, всегда существует свободная от радикалов
псевдонормализованная Φ-функция
a
ΦAB.
Таким образом, псевдонормализованная Φ-функция
a
ΦAB (5) для множеств A и B может
быть определена как Φ-функция Φ
a
AB для множеств
a
A =
a
A1
⋃
· · ·
⋃ a
Ap и B = B1
⋃
· · ·
⋃
Bq,
a
Ai ∈
a
ℑ, Bj ∈ ℑ, i ∈ Ip, j ∈ Iq, вида
Φ
a
AB = min{Φ1,Φ2, . . . ,Φn},
где Φi ∈ Φℑ = {ΦKK ,ΦDK ,ΦHK ,ΦV K ,ΦDH ,ΦHH ,ΦV H ,ΦDD,ΦDV ,ΦV V }, n = q
p∑
i=1
ni, ni —
число базовых объектов Ail ∈ ℑ, формирующих декомпозицию объектов
a
Ai ∈
a
ℑ,
a
Ai =
=
ni⋃
l=1
Ail.
Для формирования Φ-функций
a
ΦAB может быть также использована Φ-функция ΦA
a
B
для объектов A и
a
B. Этот факт позволяет сократить вычислительные процедуры за счет
выбора наименьшего числа базовых объектов при декомпозиции, а также выбора наиболее
простых Φ-функций. Например,
a
ΦV K для объектов K3 (см. рис. 3, а) и V (см. рис. 4, б )
может быть построена как
a
ΦV K = Φ
a
VK или
a
ΦV K = Φ
a
KV . Из результата декомпозиции
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2011, №6 33
множеств
a
K3 (см. рис. 3, б ) и
a
V (см. рис. 4, б ) и формул (6), (10) следует, что наиболее
эффективен выбор Φ-функции Φ
a
KV .
Заметим, что при построении Φ-функций
a
ΦAB используются только линейные, квадра-
тичные и тригонометрические функции вида sin θ и cos θ.
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, 16. – P. 1109–1130.
2. Stoyan Y.G., Chugay A. Packing cylinders and rectangular parallelepipeds with distances between them //
Ibid. – 2008. – 197. – P. 446–455.
3. 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.
4. Bennell J., Scheithauer G., Stoyan Yu., Romanova T. Tools of mathematical modelling of arbitrary object
packing problems // J. Ann. Operat. Res. – 2010. – 179, is. 1. – P. 343–368.
5. Minkowski H. Dichteste gitterformige. Lagerung kongruenter Körper // Nachr. Kon. Ges. Wiss. Gottin-
gen. – 1904. – P. 311–355.
6. Farouki R.T., Koenig T., Tarabanis K.A. et al. Path planning with offset curves for layered fabrication
processes // J. Manufact. Syst. – 1995. – 14. – P. 355–368.
7. Gray A. Parallel curves // Modern Differential Geometry of Curves and Surfaces with Mathematica. –
Boca Raton, FL: CRC Press, 1997. – P. 115–117.
8. Stoyan Y., Terno J., Scheithauer G., Gil N., Romanova T. Phi-functions for primary 2D-objects // Studia
Informatica Universalis. – 2001. – 2. – P. 1–32.
9. Гиль Н.И., Романова Т. Е., Злотник М.В. Декомпозиция двумерных геометрических объектов //
Доп. НАН України. – 2010. – № 7. – С. 33–37.
10. Стоян Ю.Г., Романова Т. Е., Чернов Н.И., Панкратов А.В. Полный класс Φ-функций для базовых
двумерных ϕ-объектов // Там само. – 2010. – № 12. – С. 25–30.
Поступило в редакцию 04.10.2010Институт проблем машиностроения
им. А. Н. Подгорного НАН Украины, Харьков
Corresponding Member of the NAS of Ukraine Yu.G. Stoyan, T. E. Romanova,
N. I. Chernov
Pseudonormalized Φ-functions for two-dimensional ϕ-objects
We consider a concept of radical free pseudonormalized Φ-functions which allow us to descri-
be restrictions on minimal and maximal allowable distances between two-dimensional ϕ-objects.
A complete class of pseudonormalized Φ-functions for a family of basic two-dimensional ϕ-objects
is derived. We allow translations and rotations of the ϕ-objects in a two-dimensional Euclidean
space. The theorem of existence of a radical free pseudonormalized Φ-function for a pair of arbi-
trary shaped ϕ-objects whose frontiers are formed by the union of line segments and circular arcs
is formulated.
34 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2011, №6
|
| id | nasplib_isofts_kiev_ua-123456789-37809 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Russian |
| last_indexed | 2025-12-07T17:21:52Z |
| publishDate | 2011 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Стоян, Ю.Г. Романова, Т.Е. Чернов, Н.И. 2012-10-22T17:06:16Z 2012-10-22T17:06:16Z 2011 Псевдонормализованные Φ-функции для двумерных φ-объектов / Ю.Г. Стоян, Т.Е. Романова, Н.И. Чернов // Доп. НАН України. — 2011. — № 6. — С. 29-34. — Бібліогр.: 10 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/37809 519.85 Вводиться поняття вільної від радикалів псевдонормалізованої Φ-функції, що дозволяє описувати обмеження на мінімально та максимально припустимі відстані між двовимірними φ-об'єктами. Будується повний клас псевдонормалізованих Φ-функцій для класу базових φ-об'єктів. Допускаються афінні відображення трансляції та повороту. Наводиться теорема про існування вільної від радикалів псевдонормалізованої Φ-функції для пари довільних φ-об'єктів, границі яких формуються об'єднанням дуг кіл і відрізків прямих. We consider a concept of radical free pseudonormalized Φ-functions which allow us to describe restrictions on minimal and maximal allowable distances between two-dimensional φ-objects. A complete class of pseudonormalized Φ-functions for a family of basic two-dimensional φ-objects is derived. We allow translations and rotations of the φ-objects in a two-dimensional Euclidean space. The theorem of 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 Видавничий дім "Академперіодика" НАН України Доповіді НАН України Математика Псевдонормализованные Φ-функции для двумерных φ-объектов Pseudonormalized Φ-functions for two-dimensional φ-objects Article published earlier |
| spellingShingle | Псевдонормализованные Φ-функции для двумерных φ-объектов Стоян, Ю.Г. Романова, Т.Е. Чернов, Н.И. Математика |
| title | Псевдонормализованные Φ-функции для двумерных φ-объектов |
| title_alt | Pseudonormalized Φ-functions 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/37809 |
| work_keys_str_mv | AT stoânûg psevdonormalizovannyeφfunkciidlâdvumernyhφobʺektov AT romanovate psevdonormalizovannyeφfunkciidlâdvumernyhφobʺektov AT černovni psevdonormalizovannyeφfunkciidlâdvumernyhφobʺektov AT stoânûg pseudonormalizedφfunctionsfortwodimensionalφobjects AT romanovate pseudonormalizedφfunctionsfortwodimensionalφobjects AT černovni pseudonormalizedφfunctionsfortwodimensionalφobjects |