Декомпозиция двумерных геометрических объектов
Розглядається алгоритм, що реалiзує декомпозицiю довiльних двовимiрних φ-об’єктiв, межа яких утворена об’єднанням дуг кiл та вiдрiзкiв прямих. Запропонований пiдхiд є ефективним для побудови Φ-функцiй складених φ-об’єктiв при математичному моделюваннi задач геометричного проектування. Алгоритм грунт...
Gespeichert in:
| Veröffentlicht in: | Доповіді НАН України |
|---|---|
| Datum: | 2010 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2010
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/29921 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Декомпозиция двумерных геометрических объектов / Н.И. Гиль, Т.Е. Романова, М.В. Злотник // Доп. НАН України. — 2010. — № 7. — С. 33-37. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859816662077800448 |
|---|---|
| author | Гиль, Н.И. Романова, Т.Е. Злотник, М.В. |
| author_facet | Гиль, Н.И. Романова, Т.Е. Злотник, М.В. |
| citation_txt | Декомпозиция двумерных геометрических объектов / Н.И. Гиль, Т.Е. Романова, М.В. Злотник // Доп. НАН України. — 2010. — № 7. — С. 33-37. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | Розглядається алгоритм, що реалiзує декомпозицiю довiльних двовимiрних φ-об’єктiв, межа яких утворена об’єднанням дуг кiл та вiдрiзкiв прямих. Запропонований пiдхiд є ефективним для побудови Φ-функцiй складених φ-об’єктiв при математичному моделюваннi задач геометричного проектування. Алгоритм грунтується на видiленнi класу базових φ-об’єктiв, для яких вiдомi Φ-функцiї. Наведено результати чисельних експериментiв.
We consider the decomposition algorithm for arbitrarily shaped 2D φ-objects, whose boundaries are formed by a union of segments of straight lines and circular arcs. The algorithm is a powerful tool for deriving the Φ-functions of composed φ-objects in mathematical modeling of geometric design problems. The algorithm uses a class of basic φ-objects, whose Φ-functions are known, as a basis. A number of computational results is given.
|
| first_indexed | 2025-12-07T15:22:39Z |
| format | Article |
| fulltext |
оповiдi
НАЦIОНАЛЬНОЇ
АКАДЕМIЇ НАУК
УКРАЇНИ
7 • 2010
IНФОРМАТИКА ТА КIБЕРНЕТИКА
УДК 519.85
© 2010
Н.И. Гиль, Т.Е. Романова, М. В. Злотник
Декомпозиция двумерных геометрических объектов
(Представлено членом-корреспондентом НАН Украины Ю.Г. Стояном)
Розглядається алгоритм, що реалiзує декомпозицiю довiльних двовимiрних ϕ-об’єктiв,
межа яких утворена об’єднанням дуг кiл та вiдрiзкiв прямих. Запропонований пiдхiд
є ефективним для побудови Φ-функцiй складених ϕ-об’єктiв при математичному моде-
люваннi задач геометричного проектування. Алгоритм грунтується на видiленнi класу
базових ϕ-об’єктiв, для яких вiдомi Φ-функцiї. Наведено результати чисельних експе-
риментiв.
В классе оптимизационных 2D задач упаковки и раскроя (Packing and Cutting) [1] конструк-
тивным средством математического моделирования отношений геометрических объектов
является метод Φ-функций [2]. В работах [3–6] построены Φ-функции для примитивных
объектов (primary objects) и некоторых классов составных объектов (composed objects).
Построение Ф-функций для произвольных ϕ-объектов [4], граница которых формируется
объединением дуг окружностей и отрезков прямых, можно реализовать, используя чре-
звычайно простую идею о представлении произвольного ϕ-объекта в виде объединения
объектов (далее — базовых объектов), для которых Φ-функции известны.
В пределах данного исследования в качестве базовых рассматриваются следующие
объекты: выпуклый многоугольник K (рис. 1, а), заданный вершинами {p1, p2, . . . , pk}; кру-
говой сегмент D = T
⋂
C (рис. 1, б ), где C — круг радиусом r с центром O(x, y), O /∈ D;
T — треугольник, заданный вершинами p1, p2, p3, где p3 = ω1
⋂
ω2, ω1 и ω2 — касательные
Рис. 1. Базовые объекты K, D, H , V
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2010, №7 33
к окружности frC в точках p1 и p2 соответственно; fr(·) — граница множества (·); объект
H = T
⋂
C∗ (рис. 1, в), C∗ = R2 \ intC, где int(·) — внутренность множества (·); объект
V = H
⋂
C2 (рис. 1, г), где H = T
⋂
C∗
1 , C2 — круг радиусом r2 > r1 с центром в точке O2,
при этом ΦC∗C = 0; ΦC∗C — Φ-функция C∗
2 и C1.
Обоснованием выбора в качестве базовых объектов K, D, H, V является следующее
утверждение.
Теорема. Ограниченный ϕ-объект A ⊂ R2, граница которого формируется объедине-
нием отрезков прямых и дуг окружностей, всегда можно представить в виде
A =
m⋃
k=1
Ak, (1)
где intAi
⋂
intAj = ∅, i, j ∈ Im = {1, 2, . . . ,m}, i 6= j, Ak ∈ {K,D,H, V }.
Задача. Необходимо представить ограниченный ϕ-объект A ⊂ R2, граница которого
состоит из отрезков прямых и дуг окружностей в виде (1).
Пусть A — односвязный ограниченный ϕ-объект, граница которого задана последо-
вательностью элементов li, i ∈ In. Каждый элемент li задается кортежем информации
gi = (pi, λi, pi, pi+1) об отрезке s, “выпуклой” дуге
⌢
a либо “вогнутой” дуге
⌣
a. Дуга arc(p1, p2)
на рис. 1, б — “выпуклая”, а на рис. 1, в — “вогнутая”. Здесь pi = (xi, yi), xi, yi — координаты
начала элемента li ∈ {s,
⌢
a,
⌣
a} в собственной системе координат множества A; λi — признак
элемента li, причем λi = 0, если li ∈ {s}, λi = 1, если li ∈ {
⌢
a}, λi = −1, если li ∈ {
⌣
a};
pi = (xi, yi) — координаты центра отрезка s или центра окружности, формирующей дугу
⌢
a
(
⌣
a); pi+1 = (xi+1, yi+1), xi+1, yi+1 — координаты конца li и начала li+1.
Таким образом, информация о границе базового объекта A задается кортежем gA =
= (g1, g2, . . . , gn), в том числе gK = (gs1 , gs2 , . . . , gsk), gD = (g
⌢
a , gs), gH = (g
⌣
a , gs1 , gs2),
gV = (g
⌢
a , g
⌣
a , gs) или gV = (g
⌢
a , g
⌣
a , gs).
Алгоритм декомпозиции множества A на базовые объекты включает в себя четыре
основных этапа.
1. Выделение объектов вида V .
Формируем базовый объект V . Пусть lV =
⌢
a,
⌣
a, s). В этом случае g
⌢
a = (p′, 1, pi, pi+1),
g
⌣
a = (pi+1,−1, pi+1, p
′′), s = [p′′, p′], где s — часть прямой, касательной к окружности C ⊃
⌣
a
в точке p′′ ∈ li+1; p
′ ∈ li. Если lV = (
⌣
a,
⌢
a, s), то g
⌣
a = (p′′,−1, pi, pi+1), g
⌢
a = (pi+1, 1, pi+1, p
′),
s = [p′′, p′], p′′ ∈ li и p′ ∈ li+1. После выполнения первого этапа получаем объект A1 =
= cl(A \
⋃
V ), где cl(·) — замыкание множества (·).
2. Выделение сегментов D.
Формируем базовый объект D, lD = (
⌢
a, s), такой что li =
⌢
a, при условии, что
intD
⋂
frA1 = ∅ и (xi, yi) /∈ D, а дугу
⌢
a объекта A1 заменяем соответствующей хордой
li = s. Если же intD
⋂
frA1 6= ∅, то находим точку p′ ∈ li =
⌢
a, порождающую сегмен-
ты D1 и D2, lD
1
= (
⌢
a
1
, s1), lD
2
= (
⌢
a
2
, s2), где s1 = [pi, p
′], s2 = [p′, pi+1], такую, что
intD1
⋂
frA1 = ∅ и intD2
⋂
frA1 = ∅. В этом случае выделяем объекты D1и D2, а дугу li
заменяем хордами s1и s2. Если такой точки не существует, то находим две (три и более)
точки и выделяем сегменты, заменяя их в последующем соответствующими хордами. После
выполнения первого и второго этапов получаем объект A2 = cl(A1 \
⋃
D), граница которого
состоит из элементов li ∈ {s,
⌣
a}.
3. Выделение объектов H.
34 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2010, №7
Рис. 2. Разбиение ϕ-объектов A, B, C на базовые объекты вида K, D, H , V
Формируем базовый объект H, lH = (
⌣
a, s1, s2),
⌣
a = li. Строим касательные ωi и ωi+1
к окружности C ⊃
⌣
a в точках pi, и pi+1. Находим p′ = ωi
⋂
ωi+1. Тогда g
⌣
a = (pi,−1, pi, pi+1),
s1 = [pi+1, p
′], s2 = [p′, pi]. Если градусная мера дуги
⌣
a = li меньше 180◦ и выполняется
условие intH
⋂
frA2 = ∅, то
⌣
a заменяется на si = [pi, p
′]
⋃
si+1 = [p′, pi+1], формируем
объект A′
2 = cl(A2 \ H). Иначе, находим точку p′ — середину дуги
⌣
a, тогда
⌣
a =
⌣
a
1 ⋃⌣
a
2
,
g
⌣
a
1
= (pi,−1, pi, p
′) и g
⌣
a
2
= (p′,−1, pi, pi+1). Для каждой из дуг
⌣
a
1
,
⌣
a
2
выполняется анало-
гичная процедура и т. д. Получаем множество A3 = cl(A2 \ H), граница которого состоит
из элементов li ∈ {s}.
4. Декомпозиция невыпуклого многоугольника A3 на выпуклые многоугольники K.
С этой целью используется алгоритм многоугольного разбиения, приведенный в [7]. По-
лучаем множество A3 =
⋃
K.
Таким образом, имеем: A = (
⋃
D)
⋃
(
⋃
V )
⋃
(
⋃
H)
⋃
(
⋃
K).
На рис. 2 приведены примеры разбиения ϕ-объектов A, B и C на базовые объекты
вида K, D, H, V .
Пусть A — многосвязный ограниченный ϕ-объект. Граница A — несвязное множество,
состоящее из конечного числа компонент связности (петель). Определим каждую петлю
подобно тому, как задается граница односвязного множества. Затем используем алгоритм
декомпозиции, приведенный выше.
С практической точки зрения класс базовых объектов может быть расширен с целью
упрощения вида Φ-функции произвольных объектов, поскольку, следуя [5], Φ-функция
объектов A и B вида (1) может быть определена так:
ΦAB = min{ΦAiBj , i ∈ ImA
, j ∈ ImB
}.
Например, неразумно представлять круги в виде объединения сегментов D и многоу-
гольников K, так как Φ-функция для кругов имеет более простой вид, чем Φ-функции для
сегментов. Кроме того, вид Φ-функции для составных объектов может быть значительно
упрощен, если иметь в “библиотеке” Φ-функции для ϕ-объектов вида K
⋂
C∗. В этой связи
алгоритм разбиения можно модифицировать следующим образом.
Полагаем, что (1) — покрытие множества A, при котором, в общем случае, Ai и Aj
могут иметь общие внутренние точки, i, j ∈ Im, i 6= j. В класс базовых объектов введем
дополнительно круги C, а также ϕ-объекты L. Объект V здесь определяется в виде: V =
= C∗
1
⋂
C2
⋂
P , где P — полуплоскость.
Процесс покрытия объекта A базовыми объектами из множества {C,D,K,L, V } вклю-
чает в себя три этапа.
1. Выделение объектов V . Формируем базовый объект Vi, граница которого состоит из
элементов li−1 =
⌢
a, li =
⌣
a (или li =
⌢
a, li−1 =
⌣
a) и l′i+1 = s, где gs = (pi−1, 0, pi, pi+1).
Отрезок l′i+1 делит A на два объекта: Vi и A′ = cl(A \ Vi). После выполнения первого этапа
отсекаются все базовые объекты вида V .
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2010, №7 35
Рис. 3. Покрытие ϕ-объекта базовыми объектами вида C, D, K, L
2. Выделение объектов C или D на основе замены дуг
⌢
a хордами s. Выделяем базовый
объект C, такой, что li =
⌢
a ⊂ frC, при условии, что intC
⋂
lj = ∅, j ∈ In. При этом li =
⌢
a
заменяем хордой li = s, т. е. меняем g
⌢
a = (pi, 1, pi, pi+1) на gs = (pi, 0, pi, pi+1). Если ∃ j,
j ∈ In, при котором intCi
⋂
lj 6= ∅, то в качестве базового объекта выделяем сегмент D,
аналогично п. 2 предыдущего алгоритма.
После выполнения первого и второго этапов получаем объект A′′, граница которого
состоит из элементов li ∈ {s,
⌣
a}.
3. Последовательное (на основе принципа “разделяй и властвуй”) разбиение объекта A′′
на две части, каждая из которых затем вновь делится на две части и т. д. до формиро-
вания множества базовых объектов вида {K,L}. Если объект A′′ не является базовым, то
осуществляется деление объекта A′′ на две части A′′
1 и A′′
2 прямолинейным отрезком. Заме-
тим, что деление объекта A′′ отрезком [a, b] допустимо, если [a, b] ⊂ A′′, [a, b]
⋂
intA′′ 6= ∅
и a, b ∈ frA′′.
В качестве точки a будем выбирать, в порядке убывания приоритетности, одну из точек
вида: 1) a = pi+1 = si
⋂
si+1 — “невыпуклую” вершину объекта A′′; 2) a = pi+1 =
⌣
ai
⋂⌣
ai+1;
3) a = pi+1 = si
⋂⌣
ai+1; 4) a ∈ si, i ∈ In, а в качестве точки b: 1) b = pj+1 = sj
⋂
sj+1 —
“невыпуклую” вершину объекта A′′; 2) b = pj+1 =
⌣
aj
⋂⌣
aj+1; 3) b = pj+1 = sj
⋂⌣
aj+1;
4) b ∈ sj, 5) b ∈
⌣
aj , j ∈ In, j 6= i. Последовательно перебирая варианты выбора точек
a и b, с учетом их приоритетности, находим допустимые варианты деления объекта A′′
отрезком [a, b]. Далее на основе информации о frA′′ формируем два новых объекта A′′
1
и A′′
2 , каждый из которых в свою очередь аналогичным образом делим на две части A′′
11,
A′′
12 и A′′
21, A
′′
22 и т. д. Процесс деления объекта A′′ заканчивается, когда все полученные
объекты принадлежат множеству базовых объектов {K,L}.
Таким образом, имеем A = (
⋃
C)
⋃
(
⋃
D)
⋃
(
⋃
V )
⋃
(
⋃
L)(
⋃
K).
На рис. 3 приведен пример покрытия ϕ-объекта базовыми объектами вида C, D, K, L.
36 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2010, №7
1. Dyckhoff H., Scheithauer G., Terno J. Cutting and packing // Annotated Bibliographies in Combinatorial
Optimization / Dell’Amico M., Maffioli F., Martello S. – Chichester: Wiley, 1997. – P. 393–412.
2. Stoyan Yu.G. Φ-function and its basic properties // Доп. НАН України. – 2001. – No 8. – С. 112–117.
3. Stoyan Y., Gil M., Terno et al. Construction of a Φ-function for two convex polytopes // Appl. Math. –
2002. – 2, No 29. – P. 199–218.
4. Bennell J., Scheithauer G., Stoyan Yu., Romanova T. Tools of mathematical modelling of arbitrary object
packing problems // Annals of Oper. Res. – 2008. – 35. – P. 267–281.
5. Stoyan Y., Scheithauer G., Gil N., Romanova T. Φ-functions for complex 2D-objects, 4OR // Quarterly
J. Belgian, French and Italian Operations Research Soc. – 2004. – No 2. – P. 69–84.
6. Stoyan Yu., Terno J., Scheithauer G., Gil N., Romanova T. Φ-functions for primary 2D-objects // Studia
Informatica Universalis. – 2001. – No 2. – P. 1–32.
7. Стоян Ю.Г., Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов. – Киев:
Наук. думка, 1976. – 246 с.
Поступило в редакцию 21.12.2009Институт проблем машиностроения
им. А.Н. Подгорного НАН Украины, Харьков
N. I. Gil’, T. E. Romanova, M. V. Zlotnik
Decomposition of 2D-geometric objects
We consider the decomposition algorithm for arbitrarily shaped 2D ϕ-objects, whose boundaries are
formed by a union of segments of straight lines and circular arcs. The algorithm is a powerful tool
for deriving the Φ-functions of composed ϕ-objects in mathematical modeling of geometric design
problems. The algorithm uses a class of basic ϕ-objects, whose Φ-functions are known, as a basis.
A number of computational results is given.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2010, №7 37
|
| id | nasplib_isofts_kiev_ua-123456789-29921 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Russian |
| last_indexed | 2025-12-07T15:22:39Z |
| publishDate | 2010 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Гиль, Н.И. Романова, Т.Е. Злотник, М.В. 2012-01-11T17:40:45Z 2012-01-11T17:40:45Z 2010 Декомпозиция двумерных геометрических объектов / Н.И. Гиль, Т.Е. Романова, М.В. Злотник // Доп. НАН України. — 2010. — № 7. — С. 33-37. — Бібліогр.: 7 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/29921 519.85 Розглядається алгоритм, що реалiзує декомпозицiю довiльних двовимiрних φ-об’єктiв, межа яких утворена об’єднанням дуг кiл та вiдрiзкiв прямих. Запропонований пiдхiд є ефективним для побудови Φ-функцiй складених φ-об’єктiв при математичному моделюваннi задач геометричного проектування. Алгоритм грунтується на видiленнi класу базових φ-об’єктiв, для яких вiдомi Φ-функцiї. Наведено результати чисельних експериментiв. We consider the decomposition algorithm for arbitrarily shaped 2D φ-objects, whose boundaries are formed by a union of segments of straight lines and circular arcs. The algorithm is a powerful tool for deriving the Φ-functions of composed φ-objects in mathematical modeling of geometric design problems. The algorithm uses a class of basic φ-objects, whose Φ-functions are known, as a basis. A number of computational results is given. ru Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика Декомпозиция двумерных геометрических объектов Decomposition of 2D-geometric objects Article published earlier |
| spellingShingle | Декомпозиция двумерных геометрических объектов Гиль, Н.И. Романова, Т.Е. Злотник, М.В. Інформатика та кібернетика |
| title | Декомпозиция двумерных геометрических объектов |
| title_alt | Decomposition of 2D-geometric objects |
| title_full | Декомпозиция двумерных геометрических объектов |
| title_fullStr | Декомпозиция двумерных геометрических объектов |
| title_full_unstemmed | Декомпозиция двумерных геометрических объектов |
| title_short | Декомпозиция двумерных геометрических объектов |
| title_sort | декомпозиция двумерных геометрических объектов |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/29921 |
| work_keys_str_mv | AT gilʹni dekompoziciâdvumernyhgeometričeskihobʺektov AT romanovate dekompoziciâdvumernyhgeometričeskihobʺektov AT zlotnikmv dekompoziciâdvumernyhgeometričeskihobʺektov AT gilʹni decompositionof2dgeometricobjects AT romanovate decompositionof2dgeometricobjects AT zlotnikmv decompositionof2dgeometricobjects |