Заметки о подходах к построению Φ-функций для эллипсов
Предлагается ряд подходов для построения Ф-функций. В явном виде найдена нормализованная Ф-функция для описания взаимного расположения произвольно ориентированного эллипса и полуплоскости. Пропонується ряд підходів до побудови Ф-функцій. У явному вигляді знайдено нормалізовану Ф-функцію для опису вз...
Збережено в:
| Опубліковано в: : | Компьютерная математика |
|---|---|
| Дата: | 2013 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84747 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Заметки о подходах к построению Φ-функций для эллипсов / Т.А. Бардадым, О.А. Березовский // Компьютерная математика. — 2013. — № 2. — С. 50-56. — Бібліогр.: 11 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859519571136872448 |
|---|---|
| author | Бардадым, Т.А. Березовский, О.А. |
| author_facet | Бардадым, Т.А. Березовский, О.А. |
| citation_txt | Заметки о подходах к построению Φ-функций для эллипсов / Т.А. Бардадым, О.А. Березовский // Компьютерная математика. — 2013. — № 2. — С. 50-56. — Бібліогр.: 11 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Предлагается ряд подходов для построения Ф-функций. В явном виде найдена нормализованная Ф-функция для описания взаимного расположения произвольно ориентированного эллипса и полуплоскости.
Пропонується ряд підходів до побудови Ф-функцій. У явному вигляді знайдено нормалізовану Ф-функцію для опису взаємного розташування довільно орієнтованого еліпса та півплощини.
Some approaches for construction of Ф–fucntions are proposed. A normalised Ф–fucntion decsribing mutual disposition of arbitrarily oriented ellipse and a half-plane is found in exact form.
|
| first_indexed | 2025-11-25T20:53:18Z |
| format | Article |
| fulltext |
50 Компьютерная математика. 2013, № 2
Инструментальные
средства
информационных
технологий
Предлагается ряд подходов для
построения Ф-функций. В явном
виде найдена нормализованная
Ф-функция для описания взаимно-
го расположения произвольно ори-
ентированного эллипса и полу-
плоскости.
T.А. Бардадым,
О.А. Березовский, 2013
Компьютерная математика. 2013, № 2 51
УДК 519.85
Т.А. БАРДАДЫМ,
О.А. БЕРЕЗОВСКИЙ
ЗАМЕТКИ О
ПОДХОДАХ
К ПОСТРОЕНИЮ Φ -
ФУНКЦИЙ
ДЛЯ ЭЛЛИПСОВ∗
Введение. Огромное
количество важных
практических задач
непосредственно связано с
необходимостью описывать и
моделиро- вать взаимное
расположение рассматривае-
мых объектов. К наиболее
распространен-ным типам
таких задач относятся задачи
упаковки, раскроя, покрытия,
компоновки оборудования.
Во всех этих задачах прихо-
дится тем или иным
способом описывать касание,
пересечение, наложение
одного объекта на другой,
принадлежность одного
объекта другому и т. п.
Эффективным сред-ством
построения соответствующих
матема-тических моделей
является метод Φ -функ-ций
[1–2]. С помощью этого
метода построе-ны средства
∗Работа выполнена при
совместной поддержке
Национальной академии наук
Украины и Украин-ского
научно-технологического центра
(проект 5710).
описания взаимных расположе-ний кругов,
шаров, многоугольников, парал-лелепипедов,
конусов, цилиндров и разрабо-таны подходы
к исследованию комбинаций базовых
элементов [3–5]. В работе [6] построены Φ -
функции для двумерных объектов,
состоящих из отрезков прямых и дуг
окружностей. На основе метода Φ -функ-ций
создаются эффективные алгоритмиче-
ские и программные средства.
В предлагаемой работе предприняты
попытки найти методы построения Φ -функ-
ций для описания эллипсов. Это позволило
бы расширить список базовых объектов и
способствовало бы практическому примене-
нию данного метода.
ЗАМЕТКИ О ПОДХОДАХ К ПОСТРОЕНИЮ Ф-ФУНКЦИЙ ...
Компьютерная математика. 2013, № 2 51
Рассмотрим пару канонически замкнутых объектов 2( , )A AA A R= ν ϑ ⊂ и
2( , )B BB B R= ν ϑ ⊂ , границы которых не имеют самопересечений, а аргументы
характеризуют их расположение на плоскости. В качестве Φ -функции может
использоваться любая всюду определенная непрерывная функция, характеризу-
ющая взаимное расположение объектов следующим образом:
,
Ø.)int()int(если,0
Ø&Ø)int()int(если,0
Ø,если,0
≠∩<Φ
≠∂∩∂=∩=Φ
=∩>Φ
BA
BABA
BA
В работах [3, 4] предлагается класс базовых Φ -функций для ограниченного
набора базовых объектов и универсальный подход к построению свободных от
радикалов Φ -функций для произвольных неориентированных Φ -объектов,
ограниченных отрезками прямых и дугами окружностей (см. доказательства
в [4]). Например, для двух кругов 1C и 2C радиусов 1r и 2r с центрами в точках
),( 11 yx νν и ),( 22 yx νν соответственно предлагается использовать не содержа-
щую радикалов функцию
1 2 2 2 2
1 2 1 2 1 2( ) ( ) ( ) .C C
x x y y r rΦ = ν − ν + ν − ν − + (1)
1. Геометрические особенности описания взаимного расположения
объектов. Один из способов построения Φ -функций для ориентированных
базовых объектов основан на аналитическом описании поверхности ABγ
нулевого уровня Φ -функции, характеризующей возможное расположение
объектов A и B при их касании (см. [3]), )}0()1()0({ BAfrAB −⊕=γ ,
}0)(:{ =Φ≅γ uuAB , где u – вектор переменных параметров размещения
объектов A и ,B ⊕ – символ суммы Минковского (об использовании этой
операции для описания взаимного расположения объектов см., например, [7–8]).
Для построения ABγ может оказаться полезной и операция геометрического
вычитания [9], которая для множеств A и B определяется как множество
{ }*
: .nA B u R u B A= ∈ + ⊂ Для операции геометрического вычитания имеет
место соотношение )())((
*
bABABA
Bb
cc −=−⊕=
∈
I , где cA – дополнение
множества A до всего пространства, поэтому множество, необходимое для
построения поверхности ABγ , может задаваться и так:
cc
Bb
cc bABABA ))(()
*
()1( −==−⊕
∈
I .
Переход к дополнениям множеств может оказаться особенно эффективным в
задачах размещения объектов в ограниченных полостях.
Т.А. БАРДАДЫМ, О.А. БЕРЕЗОВСКИЙ
Компьютерная математика. 2013, № 2 52
2. Параметрическое представление кривой ABγ для описания
взаимного расположения эллипса и круга. Следует отметить, что найти в
явном виде уравнение поверхности ABγ и построить Φ -функции удалось
только для некоторых классов базовых объектов [1–3] достаточно простой
геометрической формы. Далее будут рассмотрены подходы к построению
Φ -функций для эллипсов.
Рассмотрим эллипс A с центром в начале координат, касающийся в точке
),( 00 yx круга B радиуса r с центром в точке ),( yxD = . Уравнение ABγ
задает кривую, по которой движется центр круга B , касаясь эллипса A , и урав-
нение этой кривой удается записать лишь в параметрическом виде. Пусть 1a и
1b – главные полуоси эллипса, тогда координаты точки ),( 00 yx параметри-
чески выражаются как )sin,cos(),( 010100 tbtayx = , а координаты центра круга,
точки D , задаются как ϕ+= cos0 rxx , ϕ+= sin0 ryy , где ϕ – угол наклона
касательной в точке ),( 00 yx к оси Oy (см. рис. 1).
РИС. 1. Касание эллипса и круга
Из уравнения касательной к эллипсу в точке ),( 00 yx несложно получить
соотношение 0
1
1 ttg
b
a
tg =ϕ , что приводит к следующему параметрическому
представлению линии ABγ :
0
0
1
01 coscos t
R
rb
tax += , 0
0
1
01 sinsin t
R
ra
tby += , (2)
где 2 2 2 2
0 1 0 1 0cos sin .R b t a t= +
ЗАМЕТКИ О ПОДХОДАХ К ПОСТРОЕНИЮ Ф-ФУНКЦИЙ ...
Компьютерная математика. 2013, № 2 53
3. Параметрическое представление кривой ABγ для описания
взаимного расположения двух эллипсов с параллельными полуосями.
Аналогично можно получить и параметрическое представление кривой ABγ для
случая касания двух эллипсов A и B со взаимно параллельными полуосями 1a ,
1b и 2a , 2b соответственно. Предполагается, что центр эллипса A находится в
начале координат, центр эллипса B находится в точке ),( yxD = , а координаты
точки ),( 00 yx параметрически выражаются как )sin,cos(),( 010100 tbtayx = .
Тогда 0
12
21 ttg
ba
ba
tg =ϕ (см. рис. 2), а
0
2
21
01 coscos t
R
ab
tax += , 0
2
21
01 sinsin t
R
ba
tby += ,
где 2 2
2 1 0 1 2 0( cos ) ( sin )R a b t a b t= + , что в случае rba == 22 сводится к (2).
РИС. 2. Касание двух эллипсов
4. Φ -функция, описывающая взаимное расположение эллипса про-
извольной ориентации и полуплоскости. Φ -функцию, описывающую
взаимное расположение эллипса произвольной ориентации и полуплоскости
можно указать в явном виде. Пусть прямая ,L ограничивающая полуплоскость,
совпадает с осью Ox , т. е. эта полуплоскость задается неравенством 0≤y , и на
этой прямой выбрана точка 0=x , через которую проходит ось Oy . Пусть точка
0 0( , )x y принадлежит эллипсу. Уравнение эллипса E в точке 0 0( , )x y задается как
2 2
11 0 12 0 0 22 0 13 0 23 0 332 2 2 0a x a x y a y a x a y a+ + + + + = . (3)
φ
Т.А. БАРДАДЫМ, О.А. БЕРЕЗОВСКИЙ
Компьютерная математика. 2013, № 2 54
Запишем уравнение касательной к эллипсу в точке 0 0( , )x y
11 0 12 0 0 22 0 13 0 23 0 33( ) ( ) ( ) 0a x x a y x x y a y y a x x a y y a+ + + + + + + + = (4)
и выразим из (4) y :
12 0 22 0 23 33 11 0 12 0 13 13 0 23 0( ) ( ) .y a x a y a a x a x a y a a x a y+ + = − − + + − −
Касательная будет параллельна оси Ox (что соответствует минимальному
или максимальному расстоянию до полуплоскости), если коэффициент при x
будет равен нулю:
11 0 12 0 13( ) 0.a x a y a+ + =
Отсюда
12 13
0 0
11 11
a a
x y
a a
= − − . (5)
Подставим (5) в (3):
2 2 2
0 11 22 12 0 11 23 12 13 11 33 13( ) 2 ( ) ( ) 0y a a a y a a a a a a a− + − + − =
и получим окончательное выражение для 0y :
±−−= )( 131223110 aaaay 2 2 2
11 23 12 13 11 22 12 11 33 13( ) ( )( )a a a a a a a a a a− − − − . (6)
Значение 0 0y y−= из (6), взятое со знаком минус, и является искомой
Φ -функцией, причем нормализованной, – оно равно расстоянию между эллип-
сом и полуплоскостью, если 0 0,y > равно нулю при касании и меньше нуля при
пересечении фигур. Значение 0 0y y+= из (6), взятое со знаком плюс, соответ-
ствует касательной к эллипсу, параллельной оси Ox , но расположенной над
эллипсом. Это выражение может использоваться для построения Φ -функции,
характеризующей расположение эллипса в полосе. Если полоса задается
неравенством My ≤≤0 , то
},min{),,( 00
+− −=Φ yMyMEL .
Аналогично можно выписать выражения, характеризующие расположение
эллипса и вертикальной полуплоскости, что в результате позволит определить
Φ -функцию, характеризующую расположение эллипса в прямоугольнике.
5. Об использовании функции Минковского для построения Φ -функ-
ций. Существует функция, которая представляется очень удобной и достаточно
универсальной для использования в качестве Φ -функции для пары объектов
nA R⊂ и ,nB R⊂ 2n ≥ (по крайней мере для случая, когда ABγ известно). Это
1)( −⋅=Φ CR , где CR – функция Минковского (или, как ее иногда называют,
масштабная или калибровочная функция, см. [8]; для замкнутого выпуклого
множества C , содержащего ноль, она определяется как ( )CR x =
inf{ : 0, }x C= λ λ > ∈λ ), а в качестве C используется множество, граница
которого определяется поверхностью ABγ . Как вариант можно рассмотреть и
ЗАМЕТКИ О ПОДХОДАХ К ПОСТРОЕНИЮ Ф-ФУНКЦИЙ ...
Компьютерная математика. 2013, № 2 55
функцию 2 ( ) 1CCRΦ = ⋅ − , которая для строго выпуклого множества C будет
строго выпуклой [11]. Предложенная в (1) для описания взаимного
расположения кругов Φ -функция может трактоваться с этих позиций как
1 2 2 2
1 2 1 2 1 2( , ) ( )C C
Ñ x x y yR r rν ν ν νΦ = − − − + . Аналогично Φ -функция, приведенная в
[6] для описания взаимного расположения двух квадратов 1Q и 2Q со сторонами
12a и 22a соответственно, может быть представлена как 1 2Q QΦ =
1 2 1 2 1 2( ( , ) 1) ( ),C x x y yR a a= ν − ν ν − ν − ⋅ + где множество C представляет собой
квадрат со стороной 1 22( ).a a+
Авторы выражают благодарность Т.Е. Романовой за ценные замечания.
1. Stoyan Yu., Romanova T. Mathematical Models of Placement Optimisation: Two- and Three-
Dimensional Problems and Applications / chapter in book "Modeling and Optimization in
Space Engineering Springer Optimization and Its Applications" Editors G. Fasano and J. Pintér,
Publisher Springer New York, 2013. – Vol. 73. – Р. 363–388.
2. Stoyan Yu.G. Φ -function and its basic properties // Докл. НАН Украины. Сер. А. – 2001. –
№ 8. – С. 157–186.
3. Стоян Ю.Г., Романова Т.Е., Шайтхауэр Г. Математическое моделирование взаимо-
действий базовых геометрических 3D объектов // Кибернетика и системный анализ. –
2005. – № 3. – С. 19–31.
4. Bennell J., Scheithauer G., Stoyan Yu., and Romanova T. Tools of mathematical modelling of
arbitrary object packing problems // J. Annals of Operations Research. – 2010. – Vol. 179, N 1.
– P. 343 – 368.
5. Chernov N., Stoyan Yu., Romanova T. Mathematical model and efficient algorithms for object
packing problem // Computational Geometry: Theory and Applications. – 2010. – 43:5. –
P. 535–553.
6. Chernov N., Stoyan Y., Romanova T. and Pankratov A. Phi-Functions for 2D Objects Formed
by Line Segments and Circular Arcs // Advances in Operations Research, vol. 2012, Article ID
346358, 26 pages, 2012. doi:10.1155/2012/346358.
7. Milenkovic I. and Sacks E. Two approximate minkowski sum algorithms // Int. J. Comp.
Geometry & App., 2010. – N 20. – P. 485–509.
8. Стоян Ю.Г., Пономаренко Л.Д. Сумма Минковского и годограф вектор-функции
плотной упаковки // Доповіді АН УРСР. – 1977. – Сер. А. – № 10. – С. 51–57.
9. Половинкин Е.С., Балашов М.В. Элементы выпуклого и сильно выпуклого анализа. – М.:
ФИЗМАТГИЗ, 2004. – 416 c.
10. Hiriart-Urruty J.-B., Lemaréchal C. Convex Analysis and Minimization Algorithms. I and II. –
Berlin: Springer Verlag, 1991. – N 417. – 347 p.
11. Лаптин Ю.П., Бардадым Т.А., Щетинин Е.И. Использование некоторых точных
вспомогательных функций в задачах оптимизации // Тр. ІІІ Междунар. конф.
«Математическое моделирование, оптимизация и информационные технологии»,
г. Кишинеу, Республика Молдова, 19–23 марта 2012. – С. 394–404.
Получено 15.05.2013
Т.А. БАРДАДЫМ, О.А. БЕРЕЗОВСКИЙ
Компьютерная математика. 2013, № 2 56
Т.О. Бардадим, О.А. Березовський
НОТАТКИ ПРО ПІДХОДИ ДО ПОБУДОВИ Ф-ФУНКЦІЙ ДЛЯ ЕЛІПСІВ
Пропонується ряд підходів до побудови Ф-функцій. У явному вигляді знайдено норма-
лізовану Ф-функцію для опису взаємного розташування довільно орієнтованого еліпса та
півплощини.
T.O. Bardadym, O.A. Berezovskyi
NOTES ON THE APPROACHES TO THE CONSTRUCTION OF Ф-FUNCTIONS FOR
ELLIPSES
Some approaches for construction of Ф–fucntions are proposed. A normalised Ф–fucntion
decsribing mutual disposition of arbitrarily oriented ellipse and a half-plane is found in exact form.
Об авторах:
Бардадым Тамара Алексеевна,
кандидат физико-математических наук,
старший научный сотрудник
Института кибернетики имени В.М. Глушкова НАН Украины,
E-mail: tbardadym@gmail.com
Березовский Олег Анатольевич,
кандидат физико-математических наук,
старший научный сотрудник
Института кибернетики имени В.М. Глушкова НАН Украины.
E-mail: berezovskyi@mail.ru
|
| id | nasplib_isofts_kiev_ua-123456789-84747 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-11-25T20:53:18Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Бардадым, Т.А. Березовский, О.А. 2015-07-14T15:38:25Z 2015-07-14T15:38:25Z 2013 Заметки о подходах к построению Φ-функций для эллипсов / Т.А. Бардадым, О.А. Березовский // Компьютерная математика. — 2013. — № 2. — С. 50-56. — Бібліогр.: 11 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84747 519.85 Предлагается ряд подходов для построения Ф-функций. В явном виде найдена нормализованная Ф-функция для описания взаимного расположения произвольно ориентированного эллипса и полуплоскости. Пропонується ряд підходів до побудови Ф-функцій. У явному вигляді знайдено нормалізовану Ф-функцію для опису взаємного розташування довільно орієнтованого еліпса та півплощини. Some approaches for construction of Ф–fucntions are proposed. A normalised Ф–fucntion decsribing mutual disposition of arbitrarily oriented ellipse and a half-plane is found in exact form. Работа выполнена при совместной поддержке Национальной академии наук Украины и Украинского научно-технологического центра (проект 5710). Авторы выражают благодарность Т.Е. Романовой за ценные замечания. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Инструментальные средства информационных технологий Заметки о подходах к построению Φ-функций для эллипсов Нотатки про підходи до побудови Ф-функцій для еліпсів Notes on the approaches to the construction of Ф-functions for ellipses Article published earlier |
| spellingShingle | Заметки о подходах к построению Φ-функций для эллипсов Бардадым, Т.А. Березовский, О.А. Инструментальные средства информационных технологий |
| title | Заметки о подходах к построению Φ-функций для эллипсов |
| title_alt | Нотатки про підходи до побудови Ф-функцій для еліпсів Notes on the approaches to the construction of Ф-functions for ellipses |
| title_full | Заметки о подходах к построению Φ-функций для эллипсов |
| title_fullStr | Заметки о подходах к построению Φ-функций для эллипсов |
| title_full_unstemmed | Заметки о подходах к построению Φ-функций для эллипсов |
| title_short | Заметки о подходах к построению Φ-функций для эллипсов |
| title_sort | заметки о подходах к построению φ-функций для эллипсов |
| topic | Инструментальные средства информационных технологий |
| topic_facet | Инструментальные средства информационных технологий |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84747 |
| work_keys_str_mv | AT bardadymta zametkiopodhodahkpostroeniûφfunkciidlâéllipsov AT berezovskiioa zametkiopodhodahkpostroeniûφfunkciidlâéllipsov AT bardadymta notatkipropídhodidopobudoviffunkcíidlâelípsív AT berezovskiioa notatkipropídhodidopobudoviffunkcíidlâelípsív AT bardadymta notesontheapproachestotheconstructionofffunctionsforellipses AT berezovskiioa notesontheapproachestotheconstructionofffunctionsforellipses |