close

Вход

Забыли?

вход по аккаунту

?

Построение оптимальной трассы ограниченной кривизны в неодносвязной области.

код для вставкиСкачать
окружности O радиуса r .Тогда ее параметрическое
уравнение имеет вид
УДК 519.2
ПОСТРОЕНИЕ ОПТИМАЛЬНОЙ
ТРАССЫ ОГРАНИЧЕННОЙ
s
s
? s2 ?
? s2 ?
x = ? cos? ?ds ,
y = ? sin ? ?ds .
(4)
? 2a ?
? 2a ?
0
0
? ?
? ?
Найдем координаты центра окружности O и
точки M . Поскольку угол поворота ?? кривой (3)
на дуге ZM не превышает ? / 2 , точка M лежит на
КРИВИЗНЫ В НЕОДНОСВЯЗНОЙ
ОБЛАСТИ
ПЛЕХОВА А. А.
дуге с угловой мерой ? / 2 относительно точки D? ,
Предлагаются условия оптимальности и метод решения задачи о построении в неодносвязной многоугольной области кратчайшей гладкой трассы, составленной из дуг окружностей, отрезков и сопрягающих их
клотоид.
1. Постановка базовой задачи на классе SCK
где OD ? перпендикуляр к оси абсцисс. По определению кривизны k дуги имеем
d?
,
(5)
ds
где ? ? угол касательной к оси абсцисс. Используя
(3), получаем s / ? = d? / ds, а значит, угол поворота
k=
Рассмотрим класс линий SCK , составленных из
отрезков (S i ) , фрагментов клотоид (K i ) и дуг окружностей (C i ) вида
p = S1 K1C1 K1? S 2 K 2C 2 K 2? S3 ... K n C n K n? S n +1 , n ? 1, (1)
которые в общих точках удовлетворяют условию
трансверсальности. Радиусы этих окружностей r и
параметры клотоид a считаем фиксированными,
причем фрагменты клотоид K i , K i? , примыкающие к
клотоиды на фрагменте дуги ZM длины s = a / r
составит
a
.
?? =
(6)
2r 2
С учетом (4) координаты точки M равны
одной дуге C i , конгруэнтны и рассматриваются на
интервале от точки с нулевой кривизной (в точке
сопряжения с отрезком) до точки с требуемым
радиусом кривизны. Угол поворота клотоиды на
этом интервале не превышает ? / 2 .
Sr
? s2 ?
y M = ? sin ? ?ds ,
? 2a ?
0
? ?
откуда получаем координаты точки O :
Пусть P? , SCK [ A, B ] ? множество линий класса
SCK , которые лежат в классе эквивалентности путей
[? ] , представленном ломаной минимальной длины ? ,
а L( p) ? длина пути p.
Базовая задача SCK . Для данной ломаной ? = ACB
найти
p* = arg min L( p) ;.
(2)
p ? P? , SCK [A, B ] .
Поскольку ломаная ? ? кратчайшая в [? ] , из [1]
следует, что решение задачи (2), если существует,
содержит минимум один (n = 1) фрагмент вида (1).
Обобщение этой задачи на случай многофрагментного (n > 1) пути вида (1) назовем стандартной задачей
на классе SCK l .
Рассмотрим клотоиду, заданную натуральным
уравнением
a
s
?= ,
s
(3)
? длина дуги; ? ? радиус
кривизны, и расположенную на плоскости Zxy
традиционным образом, т.е. так, что она касается оси
абсцисс в начале координат Z , где ее радиус кривизны равен бесконечности. Пусть ее фрагмент ? дуга
ZM расположена в I квадранте и касается в точке M
где a ? параметр;
22
Sr
? s2 ?
a
x M = ? cos? ?ds , sr = ,
?
?
2
a
r
0
? ?
(7)
? x0 = x M ? r sin (?? ) ;
?
? y0 = y M + r cos(?? ).
(8)
Проведем через нее окружность радиуса R = y o :
a r
? s2 ?
? a
R = ? sin ?? ??ds + r cos? 2
a
? 2r
? 2a ?
?
?,
?
(9)
а точку ее касания с осью абсцисс обозначим D .
Пусть A ? произвольная точка на оси абсцисс,
лежащая левее точки Z , а C ? ? произвольная точка
на окружности O радиуса R, полярный угол которой
? A относительно луча OD удовлетворяет условию
?? ? ? A ? ? / 2 . Тогда по построению линия
p = AD ? arcDC ? ? SC однозначно определяет линию
q = AZ ? arcZM ? arcMC ?? SCK ; операцию перехода
от p к q назовем сглаживанием (линии класса SC )
клотоидой.
2. Решение базовой задачи
Решение задачи (2) построим, опираясь на решение аналогичной задачи для класса SC [1].
Лемма. Если в базовой задаче SC точка C
расположена внутри круга радиуса R на расстоянии
r ? R от центра, то условия связи и оптимальности
примут вид
R ? r sin ( x ? ? ) = a sin ? ,
(10)
a sin ? = b sin ? ,
(11)
РИ, 1999, № 3
2 x =? + ? ? ? ,
(12)
где стороны и углы определены относительно точек A, B и C . В этом случае базовую задачу SC
обозначим SC rR , а ее решение ? p*rR .
Теорема. Если решение q* базовой задачи (2) для
радиуса r существует, оно задается (нормальным или
сингулярным) решением p*rR оптимизационной базовой задачи SC относительно параметров A, B,? , ? ,?
для радиусов r и R вида (9), определяемым условиями
связи и оптимальности (10)-(12), к которым применена процедура сглаживания клотоидой. При этом
разность длин кривых p*rR и q* равна ?L = 2? +
( A + B + ? + ? )(R ? r ) ,
т.е. константе, а положение
точек Z и M определяется относительно точки
касания D и луча OD соответственно отрезком
длины x0 из (8) и углом ?? из (6).
Трудоемкость получения решения задачи на классе SCK по решению p*rR задачи на классе SC
требует порядка 30-40 операций. При этом существенно важно, что при решении задачи (2) для
общего случая (1) эти действия следует выполнять
только один раз.
3. Решение задачи SC l
В этом случае оптимальная трасса имеет вид
p* = S1C1S2C 2 ... C n Sn +1 , n ? 1.
(13)
Не теряя общности, положим, что решение (13)
существует и все фрагменты
? i = S i C i S i +1, S i = Ei ?1Di , C i = arcDi Ei ,
трассы p* определяют нормальные решения. Для
каждого из этих фрагментов остаются в силе условия
связи и оптимальности [1] для точек, лежащих на
касательных.
Алгоритм.
1.Пусть ? ? некоторый угол, задающий граничное условие задачи SC? для точек A и C1 . Он
arcC1 E1 = ? / 2 + ? ? x .
(15)
2. Зная точку E1 и ориентацию касательной E1E1? ,
определяемую вектором, ортогональным к O1E1 ,
получаем окружность O2 , проходящую через C 2 и
касающуюся E1E1? , а по ней ? подобно пункту 1 ?
точку E 2 и соответствующую касательную E 2 E2? , и
т.д. до E n En? .
3. Полученную трассу обозначим p? :
p? = AD1 ? arcD1 E1 ? E1 D2 ? ... ? E n B? ,
где B? ? точка на E n En? такая, что E n B? = En B .
По построению этого алгоритма получаем, что
при B? = B трасса p? доставляет решение задаче SC .
Однако поскольку угол ? выбран произвольно, угол
? (? ) = ?BE n En? , в общем, не равен нулю, но является
непрерывной функцией малой вариации относительно угла ? (и наоборот, так как точки A, B входят
в постановку задачи симметрично). Поэтому в некоторой окрестности ? = (?1,? 2 ) начального угла ?
содержится решение поставленной задачи, т.е. такой
угол ?* ?? , что ? (? ) = 0 . Для построения этой
окрестности достаточно варьировать угол ? с шагом
?? ( ? ?1 = ? ? ?? , ?1 = ? + 2?? ,... ), пока не получим
пару прямых вида E n E n? и E n E n?? , содержащих между
собой точку B . Если шаг ?? достаточно мал, при
некотором k = k* получим ? (? k * ) < ?, где ? ?
требуемая точность решения. Если шаг ?? достаточно велик, на полученном интервале ? с требуемой
точностью ? решение задачи минимизации
? (? ), ? ?? , можно эффективно получить методом
хорд. При этом трудоемкость решения задачи SC в
общем случае можно оценить величиной
? SC ? 102 n / ? (операций) .
(16)
определяет окружность O1 , положение которой удовлетворяет условиям связи и оптимальности, а также
прямую E1 E1? (для любой точки которой E1? фраг-
Литература. 1. Плехова А.А. Метод оптимального решения базовой задачи о кратчайшем скруглении / Информатика. К.: Наук. думка, 1998. С.124-126.
мент AD1 ? arcD1E1 ? E1E1? является оптимальным
Поступила в редколлегию 28.08.99
Рецензент: д-р физ.-мат. наук Смеляков С.В.
решением задачи SC? для A и E1? ), исходя из
соотношений
? a
?
x1 = ? + arcsin?1 ? sin ? ? ,
? R
?
РИ, 1999, № 3
(14)
Плехова Анна Анатольевна, аспирантка Института
Проблем машиностроения НАН Украины. Научные
интересы: методы оптимизации, геометрическое проектирование. Адрес: Украина, 310000, Харьков, ул. Калининградская, 9, тел. 10-27-82.
23
Документ
Категория
Без категории
Просмотров
3
Размер файла
244 Кб
Теги
оптимальное, построение, трасса, неодносвязной, кривизна, области, ограниченной
1/--страниц
Пожаловаться на содержимое документа