Сравнение двух кривых

Доброго времени суток. Не так давно у меня возникла задача по сравнению изолиний. Не двух конкретных, конечно, а множества. Я в процессе создания алгоритма, многое уже сделано, но осталась основная задача - наилучшим образом сравнить две конкретных кривых. Теперь подробнее)

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

Что я делаю. Беру конкретную кривую с первого участка, помещаю ее в новую систему координат с началом в середине кривой (примерно). Перевожу координаты каждой точки кривой в новые координаты. То же самое с кривой со второго участка.

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

Далее требуется для конкретно этой пары кривых выяснить насколько они совпадают. Что значит совпадают? Значит, если наложить одну прямую на другую (что в целом уже сделано ибо они в одной системе координат и с одинаковой начальной-конечной точкой), отклонения одной от другой будут минимальные.
Каким же образом сравнивать эти отклонения? Я не придумал ничего лучшего и простого как посчитать площадь между ними. Есть подозрение, что это не самый точный способ) И также для многих кривых положение полученное мною (концы совмещены) не самое оптимальное, т.е. мне нужно перемещать одну кривую отн-но второй по одной из осей?

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

0

тут наверное нужно больше про определение говорить

если кривые разной длины, то корректно ли их сравнивать?
т.е. две подобные кривые, например, дуги окружности радиуса 100 и 200 с одинаковым углом будут равны?

а сам способ как раз идеальный. минимальная площадь между кривыми. в пределе - ноль...

0

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

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

0

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

0

Упомянули океан, скорей всего изоуровень это карта высот дна?
Наверно сверять сами изоуровни не имеет смысла т.к. обычно это гладкие кривые которые суть стояться по не существующих данных(аппроксимация или интерполяция).
Сверять куски кривых тоже не имеет смысла т.к. это просто случайный шум.
Мне кажется сверять нужно класс поверхности. Т.е. брать точки в 3д сразу куска поверхности. И распознать что это? Это холмы, это уступы, это овраги и т.п.
Я бы гуглил “похожесть поверхностей” еще лучше “Классификация дна океана”.
http://www.activestudy.info/ob... go-relefa/
В дополн инфе:
“Принципы генетической классификации подводного рельефа
Методы изучения подводного рельефа
Генетические типы подводного рельефа” и т.д.

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

0

Сообщение от krapotkin тут наверное нужно больше про определение говорить

Сообщение от wingblack Тут многое зависит от того как бы вы сравнивали их самостоятельно, без компьютера, а так методов сравнения можно много понапридумывать

Думал, что достаточно объяснил(
Если взять две кривых, вырезать из листа бумаги одну и попробовать наложить на другую (как угодна перемещая, только без поворота на 180 градусов), то чем более они совпадут, тем лучше. Т.е. ни о каком подобие речи не идет, полное совпадение.

Сообщение от echs Попробуйте применить метод наименьших квадратов

Мне он кажется более сложным в реализации чем подсчет площади. Но в будущем сделаю и им - сравню рез-ты, хотя должны быть одинаковы.

Сообщение от Excalibur921 Упомянули океан, скорей всего изоуровень это карта высот дна?

Именно. Но в остальном немного не то) У меня задача именно сравнить изолинии, на этом строится вся работа, уже поздно менять подход. В плане того, что я пишу алгоритм только для того, чтобы убедиться, что выбраны нужные участки кривых. А выбраны они были уже давно руками.
У меня точки идут через каждые полмили, так что весьма точные данные. Для того, что я хочу.

А теперь пример что именно мне нужно сделать, надеюсь станет совсем понятно.
Довольно давно Фрэнсисом Бэконом было замечено совпадение берегов Африки и Южной Америки. Из этого выросла теория дрейфов материков. Именно о таком совпадение линий (только не берега, а подводных хребтов и иных образований) идет речь. То есть мне нужно найти уровни одной глубины (сами глубины могут быть разные), совпадающие наилучшем образом, как береговые линии некоторых материков.

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

0

Сообщение от qillous совпадение берегов Африки и Южной Америки.

Нужно было начать тему с этого.

1)зачем сверять то что сильно изменяет форму? (дно или берег)
Все давно посчитано…
https://books.google.com.ua/bo... B8&f=false
2) За 100 млн. лет эрозия и т.д. могли фундаментально поменять мелкие детали рельефа и дна.
Значит сверять их точно вообще бессмысленно.
3)Материки могли кроме сдвига еще и произвольно повернуться на некие 3 угла.
Значит сверять изолинии мне кажется тоже бессмысленно и вообще не корректно.

Наверно лучше поискать как исследователи сверяли их…
Как велосипед бы сделал примерно так:
Cтроил 2 поверхности в 3д по данным изолиний (рельеф Америки и Африки дальше обозначим A и B).
Одна поверхность неподвижна (например A), другой найти 6 неизвестных численно(XYZ координаты начала системы координат поверхности B, три угла поворота вокруг каждой оси).

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

Величина например среднего отклонения поверхностей (в км.) и будет ответ.

Суть расчета: грубый расчет затем уточнение. Основа расчета: расстояние от вершины в 3д до треугольника.
К примеру: есть данные изолинии высот от 0 до 5 км шаг 0.5 км.
A неподвижна для B найти 6 неизвестных.

1) строим поверхности A и B с шагом 2.5 км ищем 6 неизвестных поверхности B.
2)Нашли грубо 6 неизвестных, снова строим поверхности с более мелким шагом и т.д.

Или лучше поискать типа: Поиск совпадения поверхности. Скорей всего давно есть адекватные алгоритмы анализа совпадения двух поверхностей…
Изначально приблизить поверхности лучше визуально в 3д редакторе вручную. Может даже это быстрей всего и проще вообще как ответ.

0

Спасибо, Вы правы по поводу 3д модели, стало ясно как пришить сюда вычматы. Но это немного перебор для моей работы. Сравнение идет не только по изолиниям, но и по многим другим фактором (как то магнитные аномалии, состав грунта и т.д.). Совпадение изолинии только один из аргументов.
По поводу сдвигов. Сдвиг еще может быть и по вертикали (сползание) и это описывается схемой Вернике. Именно поэтому 3д модель необязательна, совпадение линий с глубиной 2000 и 3000 тоже хорошо.
Поворот по осям - да, конечно. Правда в моей случае только 2 оси. Я предполагаю, что решил эту проблему перемещением обеих изолиний в относительные системы координат. Видимо не прав( С поворотом возникли небольшие проблемы, может посоветует как лучше реализовать? Перейти в полярную систему координат правильно понимаю?

По поводу давно все сделано - это не так. Моя работа актуальна, для очень многих областей таких сравнений не проводилось. Хотя алгоритм для такого написан почти со 100% вероятностью. Но во-первых, не очень представляю как его найти, во-вторых, предпочитаю сделать сам, пусть и велосипед, всегда есть вероятность, что мой алгоритм будет лучше.

Да, вручную конечно проще для конкретного участка, но повторюсь, это уже сделано. Теперь хочется сравнить какие рез-ты даст алгоритм. И это работа на будущее. Если учесть, что мне нужно провести такое сравнение для 10 участков например, то проще один раз написать алгоритм, чем каждый раз сравнивать руками, ведь так?)

0

Сообщение от qillous Но это немного перебор для моей работы.

Почему? Ведь аналог задачи:
Некий цельный стержень из стекла. Разломили пополам, части откололись, остались две половинки.

Найти такие 6 неизвестных (координаты XYZ и 3 угла) одной половинки стержня чтобы их максимально приблизить. Удобно смотреть поверхности а не изолинии.

Сообщение от qillous Сравнение идет не только по изолиниям, но и по многим другим фактором (как то магнитные аномалии, состав грунта и т.д.).

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

И вообще: тип грунта это например цвет поверхности точки, величина магнитного поля- прозрачность точки.
Еще больше наглядность 3д модели. Аномалии состава грунта отличные метки для сопоставления. Можно выводить не всю карту а некие экстремумы точки.

Сообщение от qillous перемещением обеих изолиний в относительные системы координат. Видимо не прав

Относительная система координат и будет у поверхности с наглядным профилем в 3д.

Сообщение от qillous Перейти в полярную систему

Зачем? У вас 6 неизвестных, система координат тут не имеет значения обычно берут декартову.

Сообщение от qillous Правда в моей случае только 2 оси.

Какие 2 оси? У вас координаты глубин. Т.е. 3 координаты, XY точки и Z глубина. Так и строить поверхность в 3д.

Сообщение от qillous не очень представляю как его найти,

Пробовать разные запросы. Смотреть ссылки на что ссылается автор. Обычно книги поверхностно освещают и в них есть ссылки на исследования в которых детально описан метод. Глянуть книги по этой теме… Найти из какой области они.
Попробовать поискать спец форумы узкой направленности по геологии или что это…

Сообщение от qillous предпочитаю сделать сам, пусть и велосипед, всегда есть вероятность, что мой алгоритм будет лучше.

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

Сообщение от qillous проще для конкретного участка,

Какого участка? Строите всю поверхность и смотрите в 3д. Если потянет комп или кусками.

Сообщение от qillous чем каждый раз сравнивать руками, ведь так?)

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

0