Есть четыре точки в 2D пространстве, образующие непрямоугольную область.
В каждой точке задано значение. (Для простоты пусть будет Z)
Есть точка заданная координатами X,Y заведомо попадающая в эту область.

Задача:
Найти значение Z в заданной точке.

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

Интересуют именно вариации билинейной интерполяции.

Здравствуйте, Ev., Вы писали:

Ev.>Есть четыре точки в 2D пространстве, образующие непрямоугольную область.
Ev.>В каждой точке задано значение. (Для простоты пусть будет Z)
Ev.>Есть точка заданная координатами X,Y заведомо попадающая в эту область.

Ev.>Задача:
Ev.>Найти значение Z в заданной точке.

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

Ev.>Интересуют именно вариации билинейной интерполяции.

http://ru.wikipedia.org/wiki/Билинейная_интерполяция
Вид интерполянта:


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

Здравствуйте, Ev., Вы писали:

Ev.>Для упрощения задачи, примем нашу область выпуклой.
Ev.>Интересуют именно вариации билинейной интерполяции.

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

Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, Ev., Вы писали:

Ev.>>Для упрощения задачи, примем нашу область выпуклой.
Ev.>>Интересуют именно вариации билинейной интерполяции.

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

чушь. ключевое слово апперцепция! и далее по тексту!

Здравствуйте, McSeem2, Вы писали:

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

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

Здравствуйте, Ev., Вы писали:

Ev.>Есть четыре точки в 2D пространстве, образующие непрямоугольную область.
Ev.>В каждой точке задано значение. (Для простоты пусть будет Z)
Ev.>Есть точка заданная координатами X,Y заведомо попадающая в эту область.

Ev.>Задача:
Ev.>Найти значение Z в заданной точке.

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

Ev.>Интересуют именно вариации билинейной интерполяции.
Билинейная интерполяция имеет вид f(x,y) = summ c_i(x,y) * f(x_i,y_i), p_i = (x_i,y_i) -- узловые точки.
c_i(x,y) равно отношению площадей треугольников c_i(x,y) = |S(p_i-1,(x,y),p_i+1)| / |S (p_i-1,p_i,p_i+1)|. Их достаточно просто посчитать в случае выпуклого четырехугольника, в случае невыпуклого это ведет к граблям, поэтому проще восстановить билинейную форму в лоб решив систему 4*4

Чувствую себя идиотом, нао разве возможна билинейная интерполяция дя 2х значений по одному измерению ?

Здравствуйте, minorlogic, Вы писали:

M>Чувствую себя идиотом, нао разве возможна билинейная интерполяция дя 2х значений по одному измерению ?

тьху ... перепутал с бикубической.

Здравствуйте, minorlogic, Вы писали:

M>Здравствуйте, minorlogic, Вы писали:

M>>Чувствую себя идиотом, нао разве возможна билинейная интерполяция дя 2х значений по одному измерению ?

M>тьху ... перепутал с бикубической.

совсем все перепутал

Здравствуйте, Ev., Вы писали:

Ev.>Вы похоже совершенно не в теме. Прежде чем что-то постить, попытайтесь хотя бы немного вникнуть в суть проблемы, "Если есть хоть минимум мозга"

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

Здравствуйте, McSeem2, Вы писали:

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

Этого делать нельзя, т.к. мы имеем дело с седловой поверхностью.

Здравствуйте, Ev., Вы писали:

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

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

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

Для получения чего-то "седловидного" можно предложить на плоском 4-угольнике построить 4 отрезка, проходящих через искомую точку и каждую из вершин. Далее, находим точки пересечения каждого из отрезков с противоположной стороной и линейной интерполяцией вычисляем значения в этих точках, после чего, опять-же, линейной интерполяцией — в искомой точке. Полученные 4 значения усредняем.

Здравствуйте, McSeem2, Вы писали:

MS>рубаем четырехугольник на два треугольника и внутри одного из них делаем интерполяцию.

И значение из оставшейся 4-ой вершины не используем вообще?

Здравствуйте, Ev., Вы писали:

Ev.>Есть четыре точки в 2D пространстве, образующие непрямоугольную область.
Ev.>В каждой точке задано значение. (Для простоты пусть будет Z)
Ev.>Есть точка заданная координатами X,Y заведомо попадающая в эту область.

Ev.>Задача:
Ev.>Найти значение Z в заданной точке.

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

Ev.>Интересуют именно вариации билинейной интерполяции.

Аналогично тому, как для прямоугольной области — найти сначала значения в точках E и F, а потом в искомой. Как проводятся "разделяющие" линии, понятно из рисунка:

Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, Ev., Вы писали:

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

MS>В таком случае мы имеем дело с взаимоисключающими параграфами. Если мы имеем дело с седловой поверхностью, то интерполяция не является билинейной. А если билинейная — то это по определению должна быть плоскость.

Билинейная — это не плоскость.по крайне мере так утверждает википедия. и тут в ветке есть уравнение. возможно плоскость частный случай этого определения, но тогда давайте определимся чего мы определяем.

24>Аналогично тому, как для прямоугольной области — найти сначала значения в точках E и F, а потом в искомой. Как проводятся "разделяющие" линии, понятно из рисунка:
24>

Билинейная — она линейна по x и по y ПО ОТДЕЛЬНОСТИ. т.е. вычислять линейную интерполяцию можно только по вертикальным и горизонтальным прямым. поэтому возникает вопрос — чему равно значение функции в точке E?

Здравствуйте, Ev., Вы писали:

Ev.>Для упрощения задачи, примем нашу область выпуклой.
Ev.>Интересуют именно вариации билинейной интерполяции.

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

Другой способ. Сначала вспомним, что такое билинейная интерполяция на квадратной сетке:


Это просто взвешенная сумма цветных площадей, считая, что у нас значения заданы в синей сетки, а посчитать надо значение в красной точке.
Теперь предположим, что у нас не квадраты, а произвольные четырехугольники. Тогда надо:
1. Найти четырехугольник, внутри которого находится точка
2. Вычислить центр тяжести этого четырехугольника
3. Сдвинуть четырехугольник так, чтобы его центр тяжести совпадал с искомой точкой.
4. Вычислить и взвешенно просуммировать площади кусочков аналогично интерполяции на квадратной сетке.

Здравствуйте, McSeem2, Вы писали:

MS>Да, признаю, метод с триангуляцией груб, хотя и может дать приемлемый результат — зависит от задачи.

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

Здравствуйте, Аноним, Вы писали:


24>>

А>Билинейная — она линейна по x и по y ПО ОТДЕЛЬНОСТИ. т.е. вычислять линейную интерполяцию можно только по вертикальным и горизонтальным прямым. поэтому возникает вопрос — чему равно значение функции в точке E?

Вместо вертикальных и горизонтальных прямых здесь используются стороны четырёхугольника (для вычисления значений в точках E и F), и линии, показанные на рисунке зелёным цветом (для вычисления значения в точке Z (искомой) для интерполяции между E и F.) Z на рисунке не показана, считаем что это красная точка.

f(E) = f(A) * AE/AB + f(B) * BE/AB, где AE, BE, AB — длины соответствующих отрезков.
f(F) = f(D) * DF/CD + f(C) * CF/CD,
f(Z) = f(E) * EZ/EF + f(F) * FZ/EZ.

PS. Я это строго не доказывал, но судя по всему отношение AE/BE такое же, как DF/CF, поэтому вдоль EF идёт плавная интерполяция между гранями AD и BC с одинаковым коеффициентом вдоль всей длины. По крайней мере при использовании такого способа на практике получался вполне вменяемый результат.

Здравствуйте, 24, Вы писали:

24>f(E) = f(A) * AE/AB + f(B) * BE/AB, где AE, BE, AB — длины соответствующих отрезков.
24>f(F) = f(D) * DF/CD + f(C) * CF/CD,
24>f(Z) = f(E) * EZ/EF + f(F) * FZ/EZ.

В последней формуле опечатка, должно быть
f(Z) = f(E) * EZ/EF + f(F) * FZ/EF.