Какие простые методы существуют для адаптивной выборки 2D-функции?

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

Какие хорошие методы есть, чтобы сделать это?

Что у меня пока

• Я начинаю с существующего набора точек, где я уже вычислил значение функции (это может быть квадратная решетка точек или что-то еще).

• Затем я вычисляю триангуляцию Делоне этих точек.

• Если две соседние точки в триангуляции Делоне достаточно далеко ( ) и значение функции отличается достаточно в них ( > Δ F ), а затем вставить новую точку на полпути Inbetween них. Я делаю это для каждой соседней пары точек.$> \Delta X$$> \Delta f$

Что не так с этим методом?

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

Это дает такие результаты (если разрешение исходной точечной сетки достаточно грубое):

На приведенном выше графике показаны точки, где вычисляется значение функции (на самом деле ячейки Вороного вокруг них).

Этот график выше показывает линейную интерполяцию, сгенерированную из тех же точек, и сравнивает ее со встроенным в Mathematica методом выборки (для примерно одинакового начального разрешения).

Как это улучшить?

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

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

Вопрос

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

Или какие другие простые способы можно рассчитать положение точек уточнения оптимальным образом?

Я собираюсь реализовать это в Mathematica, но этот вопрос в основном о методе. Для бита «легко реализовать» считается, что я использую Mathematica (т.е. это было легко сделать до сих пор, потому что у него есть пакет для выполнения триангуляции Делоне)

К какой практической проблеме я применяю это

Я рассчитываю фазовую диаграмму. Он имеет сложную форму. В одном регионе его значение равно 0, в другом - от 0 до 1. Между двумя регионами наблюдается резкий скачок (он прерывистый). В области, где функция больше нуля, есть как плавное изменение, так и пара разрывов.

Значение функции рассчитывается на основе симуляции Монте-Карло, поэтому иногда следует ожидать неправильного значения функции или шума (это очень редко, но для большого числа точек это происходит, например, когда устойчивое состояние не достигается из-за какой-то случайный фактор)

_{Я уже спрашивал об этом на Mathematica.SE, но не могу дать ссылку на него, потому что он все еще находится в частной бета-версии. Этот вопрос здесь о методе, а не о реализации.}

Ответить @suki

Вы предлагаете этот тип деления, то есть ставите новую точку в середине треугольников?

Меня беспокоит то, что, по-видимому, требуется особая обработка на краях региона, иначе это даст очень длинные и очень тонкие треугольники, как показано выше. Вы исправили это?

ОБНОВИТЬ

Проблема, возникающая как в описанном мною методе, так и в предложении @ suki поместить подразделение на основе треугольников и поместить точки разделения в треугольник, состоит в том, что при наличии разрывов (как в моей задаче) повторный расчет триангуляции Делоне после шага может вызвать изменение треугольников и, возможно, появление больших треугольников, которые имеют разные значения функций в трех вершинах.

Вот два примера:

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

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

Я работал над проблемой, похожей на эту, некоторое время назад.

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

У меня есть ощущение, что добавление точек внутри треугольников сделает его более эффективным, если немного увеличить среднее расстояние от старых точек до новых.

В любом случае, еще одна приятная вещь, связанная с использованием треугольников вместо ребер, состоит в том, что они дают оценку вектора градиента, а не наклона вдоль этого конкретного ребра.

В своем коде Matlab я использовал базовый класс для заботы о большинстве машин, используя несколько абстрактных методов:

• weight(self) решить приоритет, на какие треугольники поделить дальше.
• choosePoints(self,npoints = "auto") определить новые точки для оценки на основе веса каждого треугольника.

Я нашел эту настройку очень гибкой:

• установка функции подкласса weight()в область треугольника дает постоянную плотность сетки.
• установка weight()для вычисления среднего значения функции, умноженного на площадь треугольника, дает своего рода квазислучайную выборку вероятности.
• Использование var(triangle.zs)может сделать для функций, которые имеют двоичный вывод, что я считаю обобщением поиска по разделам на более чем 1 измерение.
• использование area + var(triangle.zs)было довольно эффективным при размещении постоянной плотности повсюду и увеличенной плотности вдоль любого склона (почти то, что у вас есть сейчас).

Я использовал дисперсию значений z, чтобы приблизить важность эффектов первого порядка (уклон), потому что дисперсия никогда не уйдет в бесконечность, как уклон.

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

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

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

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

Это будет содержать достаточно информации, чтобы получить оценку полной гессианской матрицы. Вы можете получить его, выполнив подгонку наименьших квадратов z = c1*x + C2*y c11*x^2+c12*x*y+c22*y^2по всем вершинам в интересующих треугольниках (сначала отцентрируйте систему координат на треугольнике).

Я бы не использовал градиент или гессиан (эти константы) напрямую, потому что они будут уходить в бесконечность с перерывами.

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

Обновлено:

Это выглядит разумно для меня.

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

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

Но поскольку вы не ожидаете, что основная часть сетки будет иметь треугольники с высоким соотношением сторон, вы можете использовать такую ​​функцию, как функция свободной границы Matlab, чтобы найти границу, а затем запустить тот же алгоритм в одном измерении на границе. Если все сделано правильно, например, в кубе, вы можете получить одинаковую плотность сетки по краям, граням и внутри куба. Интересный.

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

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

Одним из быстрых решений было бы рассмотреть наборы из четырех точек, взяв их центр тяжести и приблизив | dfdx | + | dfdy | используя эти четыре пункта. Другая альтернатива - взять три точки (то есть треугольник) и взять максимальный градиент поверхности над ними.