Имеется карта высот N*N. Есть некоторая программа построения на этой карте высот прямолинейного пути (отрезок от начальной точки А и до конечной Б) и соответственно профиля вдоль этого пути.
Профиль представляет собой массив значений высот длины M, значения берутся вдоль пути через одинаковые интервалы. 

Задача: по карте высот и профилю найти положение профиля на карте высот, т.е. найти начальную и конечную точки пути.
Известны также параметры профиля: общая длина пути (от точки А до Б), количество точек на нем для взятия профиля.

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

•  находить профиль без знания направления пути, или знания направления с ошибкой +\- 40 градусов
•  находить профиль если имеется небольшая постоянная ошибка между картами высот и точками профиля, т.е. высоты профиля смещены на скажем 2 метра вверх. Величину смещения и знак мы не знаем
•  на карту высот или на профиль добавлен шум
•  давать оценку надежности, например 10% - "это скорее всего тут, но не обязательно", 90% - "тут и только тут без сомнения"

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

Может кто-то встречался с этим, просто укажите куда рыть.

Т.е. координаты точек A и B неизвестны, только расстояние между ними и профиль?
Наверное, все таки перебор: найти все возможные точки A (по высоте), затем для каждой точки A мысленно построить окружность и найти на ней возможные точки B. Далее проверить профиль. Но не каждую точку (сначала), а, скажем, только в середине, если высоты совпадают, то еще раз пополам и т.д. - пока либо не совпадет все, либо не нарвешься на разницу, которая не укладывается в допуск... Допуски здесь тоже можно учесть. А как интерполировать высоту - без разницы, лишь бы одинаково (при построении профиля и при проверке). Вероятность можно оценивать по некоей мере отклонения найденного профиля от заданного...

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

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

Я бы делал по принципу, описанному Earnest, но шел бы вдоль профиля, хотя это и не принципиально. Примерно так (для того, чтобы не было путанцы точки профиля я буду называть значениями, а точки на карте точками:
1. Берем первое значение профиля (не обязательно крайнее, как выбрать первое значение - потом) и находим на карте изогипсу, соответстующую этой высоте.
2. Берем точку на изогипсе и временно привязываем к ней первое значение профиля.
3. На расстоянии шага профиля ищем точку, соответстующую второму значению (мысленное рисование круга в описании Earnest). Отметим, что здесь может быть найдено несколько "вторых" точек и проверять надо каждую.
4. Если такой точки нет - сдвигаемся вдоль изогипсы на один шаг, т.е возвращаемся к п.2 этого алгоритма.
5. Если вторая точка найдена, ищем третью, соответствующую третьему значению. На этот раз ищем не вокруг, а уже строго в направлении прямой идущей от первой точки к второй.
6. Если такой точки нет - сдвигаемся вдоль изогипсы на один шаг, т.е возвращаемся к п.2 этого алгоритма.
7. И так далее вдоль всего профиля.

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

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

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

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

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

Это сообщение отредактировал(а) _Y_ - 21.4.2011, 02:52