Как построить уравнение кривой по точкам

Written on 04 Июля 2013 .

Построение кривой по множеству точек P с помощью интерполяционного многочлена Лагранжа.

Видео:Как написать уравнения касательной и нормали | МатематикаСкачать

Введение

В данной статье объясняется построение кривой по точкам с помощью интерполяционного многочлена Лагранжа. Построение кривой по точкам используется в широком спектре технических применений, таких как проектирование машин и поверхностей самолетов. Главная проблема, учитывая множество точек в плане, в том, что надо построить по ним гладкую кривую, проходящую через эти точки. Порядок кривой f(x) зависит от количества заданных точек. Например, если задано две точки, функция будет иметь первый порядок, и кривая будет линией, проходящей через эти две точки, тогда как если задано три точки, функция будет иметь второй порядок f(x) = x2 . Сначала разберем многочлен Лагранжа, затем перейдем к алгоритму и реализации. В этой статье код написан на C#.

Видео:Уравнения касательной и нормали к кривой, заданной в неявном видеСкачать

Основы

Многочлен Лагранжа

Интерполяция на двух точках, (x0, y0) и (x1, y1), дает линейное уравнение или прямую линию. Стандартная форма линейного уравнения задается y = mx +c, где m – градиент линии, а c — отрезок, отсекаемый на оси Y.

Линейное уравнение переписано, чтобы две полученные интерполяцией точки, (x0, y0) и (x1, y1), были непосредственно представлены.

Поэтому линейное уравнение переписывается в виде:

где a0 и a1 — константы. Точки x0 и x1 в множителях вышеприведенного уравнения называются центрами. Применив уравнение в (x0, y0), получаем:

В (x1, y1) получаем:

Следовательно, линейное уравнение становится:

Квадратичная форма многочлена Лагранжа интерполирует три точки, (x0, y0), (x1, y1), and (x2, y2). Многочлен имеет вид:

с центрами в x0, x1, и x2. В (x0, y0):

В целом, многочлен Лагранжа степени n является многочленом, полученным путем интерполяции по множеству точек, (xi , yi ) для i = 0, 1, . . ., n, следующим образом:

Видео:Математика без Ху!ни. Кривые второго порядка. Эллипс.Скачать

Использование кода

Алгоритм

Заданы интерполяционные точки (xi , yi ) для i =0, 1, . . . ,n;

Скачайте исходники из верха этой страницы, чтобы изучить код.

Видео:Математика Без Ху!ни. Полярные координаты. Построение графика функции.Скачать

Интересные моменты

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

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

Видео:Как составить уравнение прямой, проходящей через две точки на плоскости | МатематикаСкачать

Интерполяция данных: соединяем точки так, чтобы было красиво

Как построить график по n точкам? Самое простое — отметить их маркерами на координатной сетке. Однако для наглядности их хочется соединить, чтобы получить легко читаемую линию. Соединять точки проще всего отрезками прямых. Но график-ломаная читается довольно тяжело: взгляд цепляется за углы, а не скользит вдоль линии. Да и выглядят изломы не очень красиво. Получается, что кроме ломаных нужно уметь строить и кривые. Однако тут нужно быть осторожным, чтобы не получилось вот такого:

Немного матчасти

Восстановление промежуточных значений функции, которая в данном случае задана таблично в виде точек P₁&nbsp. &nbspP_n, называется интерполяцией. Есть множество способов интерполяции, но все они могут быть сведены к тому, что надо найти n&nbsp–&nbsp1 функцию для расчёта промежуточных точек на соответствующих сегментах. При этом заданные точки обязательно должны быть вычислимы через соответствующие функции. На основе этого и может быть построен график:

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

В разных инструментах для построения графиков — редакторах и библиотеках — задача «красивой интерполяции» решена по-разному. В конце статьи будет небольшой обзор существующих вариантов. Почему в конце? Чтобы после ряда приведённых выкладок и размышлений можно было поугадывать, кто из «серьёзных ребят» какие методы использует.

Ставим опыты

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

Результат линейной интерполяции этих точек выглядит так:

Однако, как отмечалось выше, иногда хочется получить в итоге гладкую кривую.

Что есть гладкость? Бытовой ответ: отсутствие острых углов. Математический: непрерывность производных. При этом в математике гладкость имеет порядок, равный номеру последней непрерывной производной, и область, на которой эта непрерывность сохраняется. То есть, если функция имеет гладкость порядка 1 на отрезке [a;&nbspb], это означает, что на [a;&nbspb] она имеет непрерывную первую производную, а вот вторая производная уже терпит разрыв в каких-то точках.
У сплайна в контексте гладкости есть понятие дефекта. Дефект сплайна — это разность между его степенью и его гладкостью. Степень сплайна — это максимальная степень использованных в нём полиномов.
Важно отметить, что «опасными» точками у сплайна (в которых может нарушиться гладкость) являются как раз P_i, то есть точки сочленения сегментов, в которых происходит переход от одного полинома к другому. Все остальные точки «безопасны», ведь у полинома на области его определения нет проблем с непрерывностью производных.
Чтобы добиться гладкой интерполяции, нужно повысить степень полиномов и подобрать их коэффициенты так, чтобы в граничных точках сохранялась непрерывность производных.

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

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

Другое традиционное решение, кроме кубических сплайнов дефекта 1 — полиномы Лагранжа. Это полиномы степени n&nbsp–&nbsp1, принимающие заданные значения в заданных точках. То есть членения на сегменты здесь не происходит, вся последовательность описывается одним полиномом.
Но вот что получается:

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

В компьютерной графике очень широко применяются кривые Безье, представленные полиномами k-й степени.
Они не являются интерполирующими, так как из k&nbsp+&nbsp1 точек, участвующих в построении, итоговая кривая проходит лишь через первую и последнюю. Остальные k&nbsp–&nbsp1 точек играют роль своего рода «гравитационных центров», притягивающих к себе кривую.
Вот пример кубической кривой Безье:

Как это можно использовать для интерполяции? На основе этих кривых тоже можно построить сплайн. То есть на каждом сегменте сплайна будет своя кривая Безье k-й степени (кстати, k&nbsp=&nbsp1 даёт линейную интерполяцию). И вопрос только в том, какое k взять и как найти k&nbsp–&nbsp1 промежуточную точку.
Здесь бесконечно много вариантов (поскольку k ничем не ограничено), однако мы рассмотрим классический: k&nbsp=&nbsp3.
Чтобы итоговая кривая была гладкой, нужно добиться дефекта 1 для составляемого сплайна, то есть сохранения непрерывности первой и второй производных в точках сочленения сегментов (P_i), как это делается в классическом варианте кубического сплайна.
Решение этой задачи подробно (с исходным кодом) рассмотрено здесь.
Вот что получится на нашем тестовом наборе:

Стало лучше: ложные экстремумы всё ещё есть, но хотя бы не так сильно отличаются от реальных.

Думаем и экспериментируем

Можно попробовать ослабить условие гладкости: потребовать дефект 2, а не 1, то есть сохранить непрерывность одной только первой производной.
Достаточное условие достижения дефекта 2 в том, что промежуточные контрольные точки кубической кривой Безье, смежные с заданной точкой интерполируемой последовательности, лежат с этой точкой на одной прямой и на одинаковом расстоянии:

В качестве прямых, на которых лежат точки C_{i&nbsp–&nbsp1} (2) , P_i и C_i (1) , целесообразно взять касательные к графику интерполируемой функции в точках P_i. Это гарантирует отсутствие ложных экстремумов, так как кривая Безье оказывается ограниченной ломаной, построенной на её контрольных точках (если эта ломаная не имеет самопересечений).

Методом проб и ошибок эвристика для расчёта расстояния от точки интерполируемой последовательности до промежуточной контрольной получилась такой:

Первая и последняя промежуточные контрольные точки равны первой и последней точке графика соответственно (точки C₁ (1) и C_{n&nbsp–&nbsp1} (2) совпадают с точками P₁ и P_n соответственно).
В этом случае получается вот такая кривая:

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

К текущему варианту мы пришли, уменьшив гладкость на один порядок. Можно сделать это ещё раз: пусть сплайн будет иметь дефект 3. По факту, тем самым формально функция не будет гладкой вообще: даже первая производная может терпеть разрывы. Но если рвать её аккуратно, визуально ничего страшного не произойдёт.
Отказываемся от требования равенства расстояний от точки P_i до точек C_{i&nbsp–&nbsp1} (2) и C_i (1) , но при этом сохраняем их все лежащими на одной прямой:

Эвристика для вычисления расстояний будет такой:

Результат получается такой:

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

Результат следующий:

На этом было принято решение признать цель достигнутой.
Может быть, кому-то пригодится код.

А как люди-то делают?

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

MS Excel

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

LibreOffice Calc

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

Есть там ещё один тип интерполяции, который мы тут не рассматривали: B-сплайн. Но для нашей задачи он явно не подходит, так как даёт вот такой результат 🙂

Highcharts, одна из самых популярных JS-библиотек для построения диаграмм

Тут налицо «метод касательных» в варианте равенства расстояний от точки интерполируемой последовательности до промежуточных контрольных. Ложных экстремумов нет, зато есть сравнительно большая ошибка относительно линейной интерполяции (седьмой сегмент).

amCharts, ещё одна популярная JS-библиотека

Картина очень похожа на экселевскую, те же два ложных экстремума в тех же местах.

Coreplot, самая популярная библиотека построения графиков для iOS и OS X

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

aChartEngine, вроде как самая популярная библиотека построения графиков для Android

Больше всего похоже на кривую Безье степени n&nbsp–&nbsp1, хотя в самой библиотеке график называется «cubic line». Странно! Как бы то ни было, тут не только присутствуют ложные экстремумы, но и в принципе не выполняются условия интерполяции.

Видео:Составляем уравнение прямой по точкамСкачать

Кривые второго порядка

Видео:§31.1 Приведение уравнения кривой к каноническому видуСкачать

Видео:Построение кривой в полярной системе координатСкачать

Кривая второго порядка — это некоторая линия на плоскости, которая в декартовой системе координат задается общим уравнением:

Видео:Математика без Ху!ни. Уравнения прямой. Часть 1. Уравнение с угловым коэффициентом.Скачать

Видео:Математика без Ху!ни. Уравнения прямой. Часть 2. Каноническое, общее и в отрезках.Скачать

Имеем дело с уравнением второй степени, в котором коэффициенты при старших членах — при вторых степенях одновременно не нули.

Видео:Математика без Ху!ни. Уравнение плоскости.Скачать

или можно встретить следующую форму записи:

Видео:Математика без Ху!ни. Уравнение касательной.Скачать

К кривым второго порядка относятся окружность, эллипс, гипербола и парабола.

Покажем на примере определение значений коэффициентов.

Рассмотрим кривую второго порядка:

Видео:Математика без Ху!ни. Нахождение асимптот, построение графика функции.Скачать

Вычислим определитель из коэффициентов:

Если Δ = 0, кривая второго порядка параболического типа,

если Δ > 0, кривая второго порядка эллиптического типа,

если Δ F₁ и F₂ — фокусы.

с — фокальное расстояние,

Каноническое уравнение эллипса с центром симметрии в начале координат:

2а — большая ось эллипса, 2b — малая ось эллипса.

а — большая полуось эллипса, b — малая полуось эллипса.

Если a = b, то имеем окружность с радиусов R = a = b:

Если центр эллипса находится не в начале координат, а в некоторой точке C(x₀;y₀), оси эллипса параллельны осям координат, то каноническое уравнение эллипса имеет вид:

Эксцентриситет — число, равное отношению фокального расстояния к большей полуоси:

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

Гипербола — множество точек на плоскости для каждой из которых абсолютная величина разности расстояний до двух данных точек F₁ и F₂ есть величина постоянная, меньшая расстояния между этими точками.

с — фокальное расстояние,

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

Каноническое уравнение гиперболы с центром симметрии в начале координат:

x — действительная ось, y — мнимая ось.

а — действительная полуось, b — мнимая полуось.

Если центр гиперболы находится в некоторой точке C(x₀;y₀), оси симметрии параллельны осям координат, то каноническое уравнение имеет вид:

Эксцентриситет гиперболы — число, равное отношению фокусного расстояния к действительной полуоси.

Чем эксцентриситет меньше, тем гипербола более вытянута, сплюшена вдоль оси Ох.

Директриса гиперболы — прямые, параллельные мнимой оси гиперболы и отстоящая от нее на расстоянии a/Ε.

f₁ — правая директриса, f₂ — левая директриса.

Порядок построения гиперболы :

1. Строим прямоугольник со сторонами 2a и 2b.

2. Провести асимптоты гиперболы — диагонали построенного прямоугольника.

3. Строим гиперболу с вершинами в точках А 1 (-а;0), А 2 (а;0).

Парабола — множество точек на плоскости для каждой из которых расстояние до данной точки F равно расстоянию до данной прямой f.

F — фокус параболы, f — директриса параболы.

💡 Видео

Уравнения стороны треугольника и медианыСкачать

Видеоурок "Гипербола"Скачать

9 класс, 7 урок, Уравнение прямойСкачать

Аналитическая геометрия, 7 урок, Линии второго порядкаСкачать

Аналитическая геометрия, 5 урок, Уравнение плоскостиСкачать

Уравнение касательной в точке. Практическая часть. 1ч. 10 класс.Скачать

Точки пересечения графика линейной функции с координатными осями. 7 класс.Скачать