@Igor3D

Здравствуйте

Есть ф-ция Которая принимает 2 целых числа и возвращает значение высоты (z-координату)
И дана точка P как 3 float числа (xf, yf, zf)

Нужно найти такие xi, yi для которых расстояние до точки P минимально
Min((xf - xi)^2 + (yf - yi)^2 + (zf - GetZ(xi, yi))^2)

Можно кэшировать Z, создавать любые доп данные, деревья и.т.п. Если вещь известная - буду благодарен за ссылки на теорию

Спасибо

0

@monochromer

Вам нужно посмотреть литературу по численным методам оптимизации.
В математическом виде Ваша задача есть задача минимизации функции многих переменных без ограничений.
Есть так называемые методы нулевого порядка - методы Нелдера-Мида, Хука-Дживса и др., методы первого порядка - градиентный спуск и пр.

0

@Igor3D

Меня интересует не сам "факт нахождения" а скорость его выполнения, т.е. создание эффективных структур данных для поиска. Если "просто найти" - мне достаточно перебрать все значения ф-ции в "окне" по x/y (размер окна легко вычисляется). Однако это неприемлемо медленно.

Обратите внимание что xi, yi - целые числа, значения ф-ции в узлах может быть предрасчитано.

0

@monochromer

Я, конечно, не вчитывался, но есть, например, монография Хохлюк "ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ЦЕЛОЧИСЛЕННОЙ
ОПТИМИЗАЦИИ".

0

@Igor3D

Ага, целые числа - вот книжка с подходящим названием Было бы конечно прекрасно если бы порылся в книжках/гугле - и нужный алгоритм нашелся. Но вот почему-то так бывает не всегда...

0

@Mysterious Light

Мне не понятно, почему эта задача не может решаться так же, как задача минимизации функцииЕсли функция GetZ является тяжелой, то вычисление F будет занимать столько же времени, сколько и GetZ. Тогда ведь уже не будет так принципиально, какой вид имеет функция F(xi,yi), кроме, может быть, того факта, что
F(x,y) > R^2 при (x-xf)^2 + (y-yf)^2 > R^2, где R = zf - GetZ(xf,yf),
посему можно искать минимум только в R-окрестности точки (xf,yf).

Если R мало (~10 точек), то можно рассчитать значение F в каждом из (2R)^2 точек около (xf,yf) и выбрать наименшую. Просто, не очень напряжно.

А если R велико, то тогда лучше сделать упор на минимизации числа точек, в которых производится рассчёт F (или GetZ). Тогда, как я понимаю, вся существенная оптимизация будет заключена в выборе наиболее оптимального метода поиска минимума. Я не прав?

0

@Igor3D

Лучше искать не в окрестности, а начиная от (int(xf), int(yf)). Тогда находя меньший радиус можно сужать окно. Впрочем проблему это не решает

Не сказал бы (400 вызовов GetZ). Это было бы просто и хорошо для единичного расчета. Но этот поиск - базовая операция которая должна выполняться миллионы раз (для разных точек P). Да и начальный радиус может быть не 10 а напр 100.

Неясно в чем эта оптимальность (откуда Вы ее возьмете). Попытки получить какую-то аналитику GetZ ни к чему не ведут - эта ф-ция не аналитическая. Очевидно надо как-то кешировать, но пока не знаю как

0

@Mysterious Light

Под R понимается zf-GetZ(xf,yf).
Уточню: Вам необходимо для каждой пары целых чисел (xf,yf) найти пару целых чисел (xi,yi), минимизирующих расстояние F(xi,yi)?

Пусть известно, что GetZ(x,y) от y не зависит, тогда расстояние есть функция одного аргумента F(x) = x^2 + (zf-GetZ(x,yf))^2.
Пусть к тому же R=zf-GetZ(xf,yf) >> 1000 и пусть известно, что производная GetZ меняется слабо на расстояниях порядка R.
Для такой одномерной задачи можно применить метод дихотомии:
Берём точки x1=xf-R и x2=xf+R в качестве опорных, считаем значение в них, а также значение в xm=(x1+x2)/2=xf. Выбираем один из двух отрезков, в котором минимум.
Повторяем шаг: берём среднюю точку, считаем GetZ и F, выбираем один из 2 отрезков, где лежит минимум.
Для точности 1, которой нам достаточно, чтоб определить целое xi, достаточно совершить log2(R) шагов, то есть вычислить всего log2(R) раз функцию GetZ на разных аргументах. Это лучше, чем считать R точек Вашим методом, то есть вызывать GetZ R раз.
Условие на производную накладнываются для того, чтобы не попасть в локальный минимум, что является характерной проблемой дихотомии. Я не знаю, с какими поверхностями Вы работаете, но нарушения этого правила может быть для сильно волнистых и искаженных поверхностей.

0

@Igor3D

Аттач: постановка в виде картинки. К какой вершине (вертексу) ближе всего красный шарик?

Модель гор (карта высоты) создана с постоянным шагом по x, y и фиксирована. Для каждого запроса своя точка флоты (xf, yf. zf). Однако предположения о том что высота (z) меняется достаточно медленно, имеет известное кол-во максимумов и.т.п. - ничего этого нет

Миниатюры

 

0

@Igor3D

Дополнительные детали

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

0