Кубический сплайн

@almazsr · Регистрация: 13.11.2010

Студворк — интернет-сервис помощи студентам

Для отбора на собеседование (вакансия математик-программист C++) мне дали такую задачу:

Разработать программный модуль, позволяющий строить два двумерных кубических сплайна и определять для этих сплайнов ближайшие точки.
Использовать параметрическое представление сплайнов. Каждый сплайн должен быть построен по заданному массиву опорных точек на плоскости.
Если заданные сплайны пересекаются, то необходимо найти все точки пересечения, если заданные сплайны не пересекаются, то необходимо найти ближайшие точки на сплайнах.
Положение искомых точек найти с точностью 1E-09.
Задание реализовать на языке программирования С++. Использовать объектно-ориентированный подход.

С построением кубических сплайнов никаких проблем. Но, подскажите, как при такой высокой точности найти наиболее близкие друг к другу точки сплайнов??? Тут нужен какой-то хитрый алгоритм - чтобы вычисления 2 дня не проводились, но никак не пойму какой... Может кто знает?

Евгений М. · 19.07.2011, 21:23

Не по теме:

Сообщение от almazsr

вакансия математик-программист C++

Если не секрет это где?

Сообщение от almazsr

определять для этих сплайнов ближайшие точки.

Что такое ближайшая точка для сплайнов?

@almazsr · 19.07.2011, 21:42 **[ТС]**

Евгений М., вот.

Сообщение от Евгений М.

Что такое ближайшая точка для сплайнов?

тоже самое что и для любых двух линий, я так понимаю.

@Eugeniy · 19.07.2011, 21:52

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

Евгений М. · 19.07.2011, 21:56

Сообщение от almazsr

тоже самое что и для любых двух линий

Что такое ближайшая точка для двух линий?
К примеру есть функции F1(x)=(x-1)^2 и F2(x)=-(x+2)^2 на отрезке [-4;4]
Какая точка для них ближайшая?

Добавлено через 2 минуты
Имеется ввиду при каком x abs(F1(x)-F2(x))=min ?

@Eugeniy · 19.07.2011, 21:56

almazsr, кстати, насчет первого метода. Каждый узел сплайна - есть суть кубический многочлен. Разница двух кубических многочленов - это многочлен степени не более три.
Надо перебирать каждый случай. Если многочлен степени три, тогда минимумов может быть не более двух. Если степень два тогда тем более не больше двух минимумов. Ну а если 1 тогда все ясно.
almazsr, удачи!

@almazsr · 19.07.2011, 22:05 **[ТС]**

Евгений М., точно не могу сказать, примерно -0.5.

Добавлено через 3 минуты

Сообщение от Евгений М.

Имеется ввиду при каком x abs(F1(x)-F2(x))=min ?

но ведь это необязательно наиближайшие точки.

Евгений М. · 19.07.2011, 22:11

Понял, что имелось ввиду.
По теме - не знаю

@Eugeniy · 19.07.2011, 22:29

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

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод Сайт называется reddit: The Thinkpad X220 Tablet is the best budget school laptop period. Это. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

@Eugeniy 3132 / 1325 / 156 Регистрация: 19.12.2009 Сообщений: 1,808
	19.07.2011, 21:52
	almazsr, насколько я понял Ваши сплайны апроксимируют некоторую поверхность. В принципе какой-то явный метод мне в голову не приходит. Но можно реализовать два подхода. Первый. В принципе функционально Вы можете представить каждый узел Вашего сплайна. Каждый узел является гладкой функцией. По-этому если сплайны апроксимируют два разных процесса, но на одинаковых компактах, Вы можете взяв разницу сплайнов на каждом узле и вычислив их частные производные, можете попробовать найти глобальный минимум. Плюс надо проверять границу компакта. Второй метод по-проще. Проектируйте Ваши сплайны на разные координатные плоскости и попробуйте находить минимумы уже для границ - это значительно проще. Собственно далее надо запоминать все эти точки минимумов и в дальнейшем проверять их на глобальный минимум. Плюс всегда надо проверять границы компактов. Так что работы здесь - хоть отбавляй! 1

@Eugeniy 3132 / 1325 / 156 Регистрация: 19.12.2009 Сообщений: 1,808
	19.07.2011, 21:56
	almazsr, кстати, насчет первого метода. Каждый узел сплайна - есть суть кубический многочлен. Разница двух кубических многочленов - это многочлен степени не более три. Надо перебирать каждый случай. Если многочлен степени три, тогда минимумов может быть не более двух. Если степень два тогда тем более не больше двух минимумов. Ну а если 1 тогда все ясно. almazsr, удачи! 1

Евгений М. 1080 / 1007 / 107 Регистрация: 28.02.2010 Сообщений: 2,889
	19.07.2011, 22:11
	Понял, что имелось ввиду. По теме - не знаю 0

@Eugeniy 3132 / 1325 / 156 Регистрация: 19.12.2009 Сообщений: 1,808
	19.07.2011, 22:29
	almazsr, кстати насчет вычисления минимумов. Если сплайны заданы на одном компакте. Тогда есть такая интересная веща. Зная достаточно много точек, Вы можете найти в каждой точке в каждом направлении ее прирост - это фактически будет линеаризация сплайна, а также множеством касательных векторов - в простонародье касательным пространством. Таким образом зная прирост Ваших сплайнов в каждой точке, можно смело утверждать, что приросты разницы сплайнов на каждом узле будут равны разнице приростов Ваших сплайнов вдоль одного направления - это следует из линейности касательного пространства. По-этому для каждого узла Вы достаточно точно можете найти локальный минимум - под подозрениям будут точки где разница приростов равна нулю. Конечно это потребует достаточно много операций, но по-крайней это менее хлопотно, нежели просто брать циклически каждую точку и считать ее расстояние ко всем остальным 0