Аппроксимация плоских кривых

Многие практически важные задачи для своего решения требуют замены непрерывной плоской кривой, заданной графически, её аналитическим выражением. Эта задача решается с помощью известных в вычислительной математике методов аппроксимации. Используются ортогональные полиномы, ряды Фурье и др. Вместе с тем в ряде случаев этих методов оказывается недостаточно и требуется заменить заданную кривую последовательность элементов определённого вида, на которые накладываются дополнительные ограничения. Исходная кривая может быть получена в виде последовательности точек (отсчётов) или в виде непрерывной кривой (запись некоторого прибора). В любом случае можно считать, что она задана в виде ломаной с не постоянным шагом, если вершины ломаной (переломы) располагать достаточно часто.

Если рассматривать эту кривую как график функции одной переменной, то эта функция не обязательно является однозначной, хотя случай аппроксимации однозначных функций, заданных дискретно, имеет самостоятельное значение.

Рассмотренная выше задача проектирования продольного профиля трассы линейного сооружения также может рассматриваться как задача аппроксимации при наличии многочисленных ограничений.

Аппроксимирующая кривая (рис. 3.15) может быть ломаной линией, но точки перелома должны быть расположены друг относительно друга не менее, чем на заданном расстоянии. Другими словами, появляется ограничение на длины элементов аппроксимирующей ломаной (или на разность абсцисс точек перелома Xj+l- Xj> lmin ). Кроме того, есть и другие ограничения. Так или иначе, речь идёт о кусочно-линейной аппроксимации с ограничениями.

Аналогично ставится задача в том случае, когда элементами аппроксимирующей кривой являются параболы (например, второй степени). Это кусочно- параболическая аппроксимация с возможными ограничениями на параметры элементов.

Кусочно- линейная аппроксимация

Рис. 3.15. Кусочно- линейная аппроксимация.

Сюда же относится случай, при котором элементами аппроксимирующей кривой являются отрезки прямых и дуги окружностей.

В качестве критерия близости исходной и аппроксимирующей кривых в различных задачах аппроксимации могут рассматриваться различные показатели, например, интеграл от квадрата их разности (при не постоянном шаге) или сумма квадратов отклонений в заданных точках (квадратическое приближение), а также максимум модуля разности (равномерное приближение) и др.

В задачах проектирования трасс линейных сооружений изначально требуется найти непрерывную кривую, состоящую из элементов заданного вида, являющуюся экстремалью некоторого функционала, в общем случае выражающего затраты на строительство и последующую эксплуатацию сооружения. Если можно не учитывать взаимосвязь отдельных элементов, обусловленную спецификой задачи (например, сооружение насыпей из грунта выемок при дорожном строительстве), то принципиальных отличий рассматриваемых проектных задач и задач аппроксимации с ограничениями нет.

В проектировании трасс элементы искомой кривой должны удовлетворять целому ряду технических ограничений, выражаемых системой неравенств. Получается сложная вариационная задача. Её принципиальная особенность состоит в том, что число элементов искомой кривой неизвестно. Переход от исходной вариационной задачи к задаче нелинейного программирования приводит к тому, что неизвестна размерность задачи. Именно поэтому, как уже отмечалось, задача решается в несколько этапов, причём на втором этапе решается задача аппроксимации в узкой полосе отклонений при использовании простого геометрического критерия качества аппроксимации.

В проектировании трасс этот этап нужен только для определения числа и приближённого положения элементов искомой экстремали, то есть для определения размерности и начального приближения в задаче нелинейного программирования [24].

В других задачах аппроксимации этот этап является основным и практически единственным.

Задачу кусочно- линейной аппроксимации при наличии ограничений и неизвестном числе элементов, будем решать как задачу динамического программирования.

Если абсциссы переломов искомой аппроксимирующей ломаной обозначить через Xi, а ординаты через yi(i=l,2,...,n), то должны быть выполнены ограничения трёх типов:

Здесь yj- неизвестные ординаты переломов искомой ломаной, a lj=Xj-Xj-i.

Ограничение второго типа является дискретным аналогом ограничения на первую производную искомой линии. По-существу это ограничение на уклон (тангенс угла с осью х) элемента аппроксимирующей ломаной. Ограничение третьего типа является ограничением на разность уклонов смежных элементов. При малых значениях предельных уклонов Cj и dj, как это имеет место в проектировании трасс линейных сооружений, длина элемента практически равна разности абсцисс его концов, а разность уклонов равна углу поворота. Таким образом, при фиксированных длинах элементов ограничение типа 3 является дискретным аналогом ограничения на кривизну, которая при малых уклонах (порядка 0.001) практически совпадает со второй производной.

Задача кусочно- линейной аппроксимации, как второй этап задачи проектирования продольного профиля дороги, отличается малыми отклонениями исходной и аппроксимирующей кривых. Это позволило реализовать метод динамического программирования при достаточно мелкой сетке, если абсциссы точек перелома искомой ломаной заданы.

При этом «состояние системы» должно задаваться не только точкой, но и направлением, то есть реально это двухпараметрическая задача динамического программирования.

В практической реализации удобно считать состоянием системы отрезок, соединяющий две точки соседних вертикалей, и сравнивать пути, у которых общим является последний отрезок, а не конечная точка. На рис. 3.15 это отрезок DE.

В общем случае в рассматриваемой нами задаче аппроксимации предположение о том, что абсциссы (xj) вершин искомой ломаной известны должно быть отброшено. Правда, в проектировании линейных сооружений их приближённые значения можно найти с помощью простых алгоритмов последовательной локальной аппроксимации с возвратами, но иногда этого недостаточно. Поэтому рассмотрим более общий случай.

Предположим пока, что известно число вершин искомой ломаной линии и приближённые значения их абсцисс Xj, которые требуется уточнить. В дальнейшем рассмотрим кусочно- линейную и кусочно- параболическую аппроксимацию при неизвестном числе элементов, то есть пойдём по пути последовательного усложнения задачи. И, наконец, обобщим полученные результаты на задачи, в которых требуется использование других элементов, например, дуг окружностей, сопрягаемых встык (с общей касательной) или отрезками прямых.

Поиск при известном числе вершин

Рис. 3.16. Поиск при известном числе вершин

Итак, если приближённые значения абсцисс границ элементов известны, то вместо одной вертикали на каждую вершину (рис. 3.15) можно задать несколько вертикалей (рис. 3.16).

В этом случае очередной этап поиска это переход из текущего состояния к одной из вертикалей очередной группы. Состояние системы на каждом этапе определяется номером вертикали в группе, положением точки на этой вертикали и при наличии ограничений на разность уклонов (ограничения 3 типа) ещё и направлением, то есть точкой на одной из вертикалей предыдущей группы, так что число состояний существенно возрастает. Однако, метод динамического программирования применим и в этом случае. Более того, если на каждой вертикали задавать один и тот же дискрет и число дискретов (например, вверх и вниз от исходной линии по 5 дискретов - 11 точек на вертикаль) и в каждой группе задать одно и то же число вертикалей, то задача остаётся двухпараметрической. Первый параметр - номер точки на правой вертикали, а второй - на левой. Так, если точки на каждой вертикали пронумерованы сверху вниз, а вертикали слева направо, то номер точки позволяет найти и вертикаль и соответствующую точку на ней.

Программные реализации на ПЭВМ Pentium 2 с тактовой частотой 200 мГц показали, что в отсутствие ограничений типа 3 никаких вычислительных сложностей практически нет. При наличии ограничений типа 3 решение удаётся получить в приемлемое время при числе групп вертикалей порядка 100, числе вертикалей в группе до 13 и числе точек на вертикали до 11.

На ПЭВМ с объёмом памяти 512 мб и более и тактовой частотой 2000мГц была решена и задача с неизвестным числом вершин аппроксимирующей ломаной, которая представляет наибольший интерес. Практически она отличается от рассмотренной задачи аппроксимации с фиксированным числом вершин только количеством вертикалей и соответственно ростом требований к мощности ПЭВМ.

Рассмотрим сначала задачу без ограничений по разности уклонов. Будем считать, что переломы искомой линии возможны во всех равноотстоящих (по абсциссам) точках (постоянный шаг поиска), но есть ограничение на разность их абсцисс снизу и сверху:

lmin

Случай неравноотстоящих абсцисс точек перелома принципиально ничем не отличается, также как и случай наличия зон запрещённых переломов.

На первом шаге соединяем начальную точку А со всеми точками на всех вертикалях в пределах хд+ lmin

Из всех возможных соединений точки А с точками всех вертикалей рассматриваются только те, которые удовлетворяют всем ограничениям, и для каждого такого соединения вычисляется величина критерия принятого для оценки качества аппроксимации.

Варианты первого шага при неизвестных абсциссах вершин

Рис. 3.17. Варианты первого шага при неизвестных абсциссах вершин.

Далее, в качестве начальной точки второго шага (вместо точки А) рассматриваются по очереди все точки па всех вертикалях, начиная с вертикали хд+ lmin и кончая вертикалью хд+ 1тах. Из каждой такой точки получаем «веер» допустимых продолжений подобно тому как мы получали возможные элементы первого шага. В результате будем иметь все допустимые комбинации первых двух элементов искомой ломаной линии. Естественно, что из всех допустимых путей, сходящихся в одной точке, оставляем только один с наилучшим показателем качества аппроксимации на всем протяжении кривой от точки А до рассматриваемой точки на вертикали (рис.3.18 точка М). При этом запоминаем не только оценку показателя качества аппроксимации, но и начальную точку последнего элемента (для первого элемента это точка А). Практически удобно запоминать номер вертикали и номер точки на ней, если разбивка на каждой вертикали идёт по фиксированному правилу, например с равным шагом вниз и вверх от исходной линии.

Отбраковка вариантов, сходящихся в одной точке

Рис. 3.18. Отбраковка вариантов, сходящихся в одной точке.

Естественно, устанавливая на каждом шаге правую границу и пытаясь построить очередной элемент, необходимо следить за тем, чтобы до точки В осталось не меньше, чем lmin. Это означает, в частности, что если при построении очередного элемента от очередной точки до точки В осталось (по оси х) меньше, чем 21min, то эта точка просто соединяется с точкой В, так как ещё один перелом сделать нельзя. В итоге в точке В могут сходиться пути, у которых последний элемент имеет разность абсцисс в пределах от lmin ДО lmax. При больших значениях отношения lmax/lmin и большом числе точек на каждой вертикали этот алгоритм может быть реализован только на мощных компьютерах. Ещё более сложно было реализовать алгоритм, учитывающий ограничения типа 3 (на разность уклонов), то есть решить трёхпараметрическую задачу с неизвестным числом элементов. Характерно, что при наличии ограничений типа 3 общее число возможных ломаных при заданной сетке варьирования и прочих равных условиях резко сокращается, но реально эти ограничения существенно усложняют задачу, так как резко растёт число состояний из-за усложнённого правила отбраковки вариантов (сравнение не «в точку», а в «отрезок»). Для сокращения времени счёта и требуемой памяти целесообразно определять 1Шах динамически. Поскольку при меньшей разности абсцисс точек перелома при прочих равных условиях построить очередной элемент проще, то нет смысла искать длинные элементы из рассматриваемой точки, если не удаётся построить короткий элемент. Например, если требуется найти наилучшую аппроксимацию в заданной полосе отклонений, то после неудачной попытки построить из текущей точки очередной элемент рассмотрение этой точки должно быть закончено. Вообще рассмотрение lmax >2 lmin при малых значениях дискрета по вертикали нецелесообразно, так как элементы большой длины получаются как несколько элементов малой длины с одним и тем же уклоном.

При большом числе точек на вертикали и большом числе рассматриваемых возможных границ элементов время счёта даже на мощных современных компьютерах велико. Так при шаге поиска по горизонтали 10м., по вертикали

0.01м., числе шагов вверх и вниз по вертикали в каждой точке перелома профиля 50, числе шагов по горизонтали на расстоянии от lmin ДО lmax равном 20 и 1тт=200м время счёта при длине участка примерно 20 км превышает 1час. на наиболее мощных из широко доступных современных персональных компьютерах. Но если число дискретов по вертикали не превышает 30 (вверх и вниз от аппроксимируемой линии), то проблем по времени счёта и требуемой памяти практически не возникает.

Именно поэтому соответствующий алгоритм был использован при проектировании продольного профиля реконструируемых железных дорог, где не требуется задание широкой области варьирования. При проектировании новых дорог соответствующий алгоритм используется в комбинации с алгоритмами нелинейного программирования, как вспомогательное средство поиска числа элементов и приближённого положения их границ.

Необходимо отметить, что динамическое программирование может использоваться и для аппроксимации плоских кривых, которые нельзя считать графиком однозначной функции (рис. 3.19).

В этом случае вместо отклонений по ординатам могут использоваться отклонения по нормалям к исходной кривой как при разбиении сетки поиска, так и при оценке отклонений.

Аппроксимация с использованием нормалей

Рис. 3.19. Аппроксимация с использованием нормалей

В каждой вершине исходной ломаной вычисляется направление к центру окружности, соединяющей три смежные точки. Это направление отождествляется с направлением нормали к исходной ломаной в рассматриваемой вершине. Если критерием качества аппроксимации служит максимальное отклонение, то нормалей в промежуточных точках вычислять не надо. Действительно, в силу линейности элементов исходной кривой отклонение в промежуточных точках элемента не может быть больше максимального отклонения на его концах. Вычисление отклонений очередного элемента аппроксимирующей ломаной от исходной сводится таким образом к поочерёдному вычислению координат точек пересечения этого элемента и нормалей в тех вершинах исходной ломаной, которые захватывает этот элемент. Далее вычисляются расстояния точек пересечения от соответствующих вершин и берётся максимальное из них (рис.3.20).

Вычисление отклонений. АС- элемент, т, Н2, пз - нормали

Рис. 3.20. Вычисление отклонений. АС- элемент, т, Н2, пз - нормали

Аппроксимация кривых, не являющихся графиками однозначных функций, может осуществляться и при наличии ограничений. Так, ограничения типа 1 переходят в ограничения на отклонение по нормали в отдельных точках (в частности они могут задавать фиксированные точки), ограничения типа 2 особого смысла не имеют, а ограничения типа 3 переходят в ограничения на угол поворота в вершине искомой ломаной и фактически ограничивают кривизну. В остальном в рассмотренных выше алгоритмах аппроксимации однозначных функций принципиально ничего не изменяется.

Рассмотрим теперь кусочно-параболическую аппроксимацию. Будем рассматривать только однозначные функции, по-прежнему считая, что исходная функция представлена дискретным набором точек, между которыми возможна линейная интерполяции. Аппроксимирующая кривая теперь состоит из параболических элементов, число которых в общем случае неизвестно. Кроме ограничения на разность абсцисс концов каждого элемента, на искомую кривую могут быть наложены ограничения по ординатам отдельных точек, по первой производной (уклон касательной) и по второй производной. В заданной начальной точке может быть зафиксировано и начальное направление (начальный уклон). Будем считать, что в точке сопряжения элементы имеют общую касательную.

Эта задача возникает при проектировании продольного профиля автомобильных дорог подобно тому как при проектировании продольного профиля железных дорог возникает задача кусочно- линейной аппроксимации.

Рассмотрим сначала простой случай, когда известно и число элементов и абсциссы их концов и разобьём сетку варьирования по вертикали (рис. 3.21).

Варианты первой параболы

Рис.3.21. Варианты первой параболы

На первом шаге (рис. 3.21) в каждый узел сетки на вертикали 1 приходит только одна парабола. Уравнение параболы у=ах2 + Ьх +с. В системе координат при ха=0 неизвестным является только параметр а, так как параметр с=уд, а b это начальный уклон, Ь=1нач. Параметр а определяется ординатой конца элемента ус, так как абсцисса хс задана, ахс2 + iHa4xc + уд = ус. Отсюда имеем

а уклон в конце элемента

Если то вместо параболы имеем прямую, как частный

случай. При различных значениях ус получаем различные очертания элемента (выпуклое, вогнутое, с вершиной внутри или вне элемента). Отметим, что при изменении ус на А (шаг сетки) конечный уклон меняется на 2А/ хс. Естественно, что из всех парабол остаются только те, параметры которых удовлетворяют всем ограничениям. Для каждой допустимой параболы вычисляется оценка критерия (показателя качества аппроксимации). Можно было бы (как впрочем и для кусочно-линейной аппроксимации) не перебирать варианты ус, а вычислить параметр а из условия минимума интеграла от квадрата разности исходной и аппроксимирующей кривой на рассматриваемом интервале. Если при этом нарушаются ограничения, то скорректировать полученное значение и вычислить соответствующее ему ус. Однако всё равно придётся разбивать сетку относительно полученной точки, которая близка к точке на исходной кривой с той же абсциссой, поэтому в использовании наилучшего (локально!) приближения особого смысла нет, что подтвердилось в практических расчётах.

При построении второго и всех последующих элементов каждая точка на вертикали 1 должна рассматриваться как начальная. На первом элементе это была точка А с одним возможным значением начального уклона, теперь таких точек много и, что очень важно, в каждой из них есть несколько значений начального уклона. Если число точек на каждой вертикали равно ш, то без учёта ограничений, на второй вертикали в каждой точке будет m сходящихся парабол, на третьей соответственно ш2 и так далее. В качестве состояния системы нельзя принять отдельную точку на вертикали, нужно ещё и значение начального направления (уклона). Сравнивать можно, только варианты сходящиеся в точке с одним и тем же уклоном. Если длины искомых элементов (точнее разности абсцисс концов элементов) равны между собой, то такие варианты, как следует из формулы (3.6) для конечного уклона, будут иметь место. Однако мы не только не предполагаем равенство длин, но и в дальнейшем хотим обобщить наше рассмотрение на переменные длины элементов и их число. Поэтому задачу приходится рассматривать как двухпараметрическую без разбиения регулярной сетки по второму параметру (уклону). Вместо этого во избежание полного перебора вариантов на втором и всех последующих шагах поступим следующим образом (рис.3.22).

1. Берём точку уже рассмотренной вертикали (на втором шаге это вертикаль 1) с наименьшей ординатой (точка С) и строим допустимые параболы в точку с наименьшей ординатой следующей вертикали (точка D). Для двух таких парабол разность конечных уклонов (в точке D) будет равна разности начальных (в точке С). Все допустимые по ограничениям варианты оставляем для дальнейшего анализа и для каждого из них вычисляем величину критерия качества аппроксимации суммарно от начала кривой (точка А) до точки D.

Варианты второй параболы

Рис. 3.22. Варианты второй параболы

В итоге на правой вертикали в каждой точке останется «веер» уклонов, которые на следующем шаге рассматриваются как начальные. Естественно, что на последнем шаге есть только одна точка на правой вертикали, это конечная точка В. Для неё определяется точка на предыдущей вертикали, соответствующая наилучшему варианту. А для этой точки ранее запомнили уклон и точку на предыдущей вертикали, что и даёт возможность восстановить всю линию обратным разворотом от точки В.

Если в точке В задано конечное направление, то это приходится учитывать при расчёте возможных вариантов последней параболы.

При отбраковке вариантов, сходящихся в одной точке с близкими значениями уклонов, целесообразно исключать один из них (худший по критерию), если ТКОн^ i2KOH 3KOH и i3KOH - i^OH <8.

При наличии ограничений число уклонов в «веере» растёт не очень резко, так что решение задачи вполне реально даже при 8=0.0001 (imax- imin) и числе точек на вертикали 40 и более. Здесь imax, imin соответственно максимальный и минимальный уклоны, определяемые ограничениями типа 2. Реально в задачах проектирования трасс линейных сооружений достаточно 8=0.001 вместо 0.0001.

Отметим, что в отличие от кусочно-линейной аппроксимации, кроме дискретности по ординатам, для кусочно - параболической аппроксимации пришлось вводить дискретность по уклонам.

Если известно только приближённое положение границ элементов, то по аналогии с кусочно-линейной аппроксимацией может решаться задача по группам вертикалей (рис.3.16), но при этом должен быть ещё один параметр состояния, а именно, номер вертикали в группе слева.

При неизвестном числе элементов задача может быть решена по аналогии с кусочно-линейной аппроксимацией (рис. 3.17,3.18). Она остаётся трёхпараметрической, но число значений третьего параметра (номер вертикали слева) возрастает.

Задача кусочно- параболической аппроксимации может ставиться и при дополнительном условии: при сопряжении элементов допускается отсутствие общей касательной, но образующаяся разность уклонов на стыках элементов по абсолютной величине не должна превышать заданной величины еь Рассмотренная выше задача кусочно-параболической аппроксимации является частным случаем при ei=0. Такая задача кусочно- параболической аппроксимации с переломами в точках сопряжения 8^0 возникает, например, при проектировании автомобильных дорог низких категорий.

Оказывается, что это дополнительное условие не влечёт существенных усложнений алгоритмов динамического программирования как при известном числе элементов аппроксимирующей кривой, так и в общем случае, когда неизвестны не только абсциссы границ элементов, но и их число.

Действительно, при построении элементов, начиная с первого, приходится рассматривать большее число вариантов. Так, при ei=0 из начальной точки А в каждую точку вертикали 1 (рис. 3.21) можно было построить только одну параболу при заданном начальном уклоне iA. Теперь приходится рассматривать несколько значений начального уклона iHa4 в интервале iA- щ <=1нач<= iA+si с заданным шагом s. (s< si используется и для отбраковки вариантов, сходящихся в одной точке). Число вариантов конечного уклона в каждой точке возрастает, но оно и ранее уже за несколько шагов достигало своего максимума, определяемого как (imax- imin)/e. Фактически это число в несколько раз меньше, так как в реальных задачах при большом различии уклонов, соответствующие варианты просто не вписываются в полосу допустимых отклонений от исходной ломаной.

«Состояние системы», как и при ei=0, определяется точкой на вертикали и конечным уклоном. Отбраковка вариантов проводится по тому же правилу с использованием г. Запоминаются для каждого состояния те же данные: параметры состояния (точка и уклон), величина критерия качества аппроксимации, номер вертикали начала элемента и номер точки на ней, если границы элементов неизвестны. Отличия возникают при восстановлении линии при обратном развороте, так как теперь конечный уклон элемента не обязательно совпадает с начальным уклоном следующего элемента. Придя в конечную точку В и выбрав наилучший вариант, вычисляем начальный уклон последнего элемента in, с использованием координаты точки В, уклона в точке В и координаты начала элемента. Но в начале последнего элемента могло и не быть такого уклона среди всех, которые запомнили, так как при построении вариантов последнего элемента допускались и другие значения начальных уклонов в пределах допустимого перелома касательной ?ь Но для каждого состояния хранится оценка критерия по наилучшему пути, что позволяет в допустимых пределах in- si< i< in+?i выбрать наилучший конечный уклон предпоследнего элемента. Теперь вместо точки В получаем новую точку и конечный уклон, что и позволяет двигаться дальше к началу линии вплоть до точки А, где выбора уже нет.

Если элементами аппроксимирующей кривой являются не параболы, а дуги окружностей и аппроксимирующая функция по-прежнему остаётся однозначной, то новых принципиальных сложностей не возникает. Усложняется только расчёт отклонений от исходной ломаной и уклона в конце элемента.

Действительно, зная абсциссы и ординаты концов дуги и уклон в начальной точке, можно найти радиус R и координаты центра окружности хо, уо и затем вычислить ординаты в промежуточных точках и уклон в конечной точке, (рис. 3.23).

У

Аппроксимация дугами окружностей

Рис.3.23. Аппроксимация дугами окружностей

Из уравнения окружности, на которой лежат точки А и С, следует:

так как iA это производная в точке А.

Из этой системы уравнений находим хо, уо.

и далее

Если в начале элемента касательная параллельна оси ординат, то

Уклон касательной в конце дуги окружности

Задача аппроксимации несколько усложняется, если аппроксимирующая функция не является однозначной. Однако, как и при кусочно-линейной аппроксимации в этом случае при расчёте отклонений исходной и аппроксимирующей кривой можно брать не разность ординат, а отклонения по нормали к исходной кривой. Вместо уклона в начальной точке iA для вычисления координат центра и радиуса очередной окружности удобно использовать а- угол касательной с осью OX (iA=tga).

Знак радиуса определяется условием ус -Уа>1а(хс -ха). Если оно выполнено, то R>0, если ус -уа<1а(хс -ха), то R<0. При ус ~Уа=1а(хс -ха) имеем отрезок прямой, а не окружности. Зная угол а (рис.3.24) и знак радиуса, находим угол между направлением к центру окружности и осью ОХ. При R>0 этот угол равен а+я/2, а при R<0 соответственно а-я/2. Далее находим угол р между направлением хорды АС и осью ОХ и, наконец, половину центрального угла у. | у |=| а - Р |, а знак у совпадает со знаком радиуса окружности. Через этот угол и расстояние АС вычисляем радиус и угол касательной в точке С с осью ОХ, который равен 2р - а (рис.3.24). |R|=|AC/(2siny)|, хо= XA-Rsina и yo=yA+Rcosa

К вычислению угла поворота

Рис. 3.24. К вычислению угла поворота.

Для вычисления отклонений по нормалям приходится решать задачу поиска точки пересечения окружности и прямой. Если и,у-координаты точки на исходной кривой, а ф- угол нормали в этой точке с осью ОХ, то для отклонения d получается формула

Знак перед корнем выбирается так, чтобы получить ту точку пересечения нормали и окружности, которая нужна по смыслу задачи.

Все эти вычисления приходится проделать для каждой дуги окружности, соединяющей две заданные точки на рассматриваемых вертикалях, при построении вариантов положения очередного элемента. Объём вычислений существенно больше, чем при аппроксимации однозначными функциями.

Эта задача аппроксимации неоднозначными функциями получается при проектировании плана трассы линейных сооружений, тогда как задача аппроксимации однозначными функциями возникает, как уже отмечалось, при проектировании продольного профиля различных линейных сооружений.

При известном числе элементов эти задачи аппроксимации решаются методами нелинейного программирования [24], так что при использовании методов динамического программирования нам требуется только найти число элементов и приближённое положение их границ. Поэтому нет смысла использовать малые значения дискретов поиска.

Кроме того, обычные приёмы повторных расчётов с последовательным уменьшением дискретов и сужением области поиска позволяют надеяться на успешное решение рассмотренных задач аппроксимации плоских кривых, включая трёхпараметрические, на доступных компьютерах в приемлемое время применительно не только к проектированию трасс линейных сооружений, но и в других практически важных случаях.

Задача аппроксимации заданной плоской кривой f(x) другой кривой g(x), состоящей из элементов заданного вида, может ставиться и следующим образом. Из всех допустимых кривых g(x) найти такую, для которой достигается min max | f(x)-g(x)| и при этом число элементов (п) минимально. Здесь max берётся по х, a min по всем допустимым кривым. В такой постановке это двухкритериальная задача, причём чем больше число элементов п, тем меньше максимальное отклонение. Если есть программа, которая выполняет поиск аппроксимирующей кривой в заданной полосе варьирования, то требование вписаться в эту полосу можно рассматривать как ограничения типа 1, а в качестве критерия принять число элементов. Задавая малое значение ширины полосы, в котором нет решения, удовлетворяющего ограничениям, и последовательно увеличивая это значение, можно получить набор допустимых решений. При сравнении вариантов, имеющих общую точку (или общий последний элемент), часто оказывается, что число элементов у них одно и то же. В этом случае остаётся вариант с меньшим значением максимального отклонения. Если увеличение ширины полосы допустимых отклонений даёт решение с тем же числом элементов, то это решение игнорируется. В итоге получим множество Парето для двухкритериальной задачи. Элементами этого множества являются кривые заданного вида. Каждая кривая из этого множества отличается от любой другой тем, что у нее либо число элементов меньше, но максимальное отклонение больше, либо наоборот максимальное отклонение меньше, но число элементов больше. Некоторые кривые из этого множества обычно не представляют интереса, например, кривая состоящая из одного элемента, при значительных отклонениях от исходной, или кривая, все элементы которой соответствуют lmin, то есть число элементов максимально. Среди всех остальных кривых с привлечением дополнительных данных и соображений может быть выбрано приемлемое решение.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >