преобразование координат из одной искаженной системы координат в другую

Question

проблему лучше всего объяснить на примере:

http://dl.dropbox.com/u/1013446/distortedcoordinatespace.exe

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

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

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

Итак, учитывая 4 абсолютные координаты каждого из 2 неправильных четырехугольников, A и B, как я могу преобразовать координаты точки C, учитывая ее абсолютные координаты?

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

хорошо, я пытаюсь реализовать решение btilly, и вот что у меня есть:

   #include<complex>
#define cf complex<float>

cf i=sqrt(complex<float>(-1));

cf GetZ(float x,float y)
{
    return cf(x)+(cf(y)*i);
}

cf GetPathIntegral(cf p1,cf p2,cf q1,cf q2, int n)
{
    cf sum;
    for (int index=0;index<=n;index++)
    {
        cf s=cf(float(index)/float(n));
        cf weight;
        if (index==0||index==n)
            weight=1;
        else if(index%2)
            weight=4;
        else weight =2;


        sum+=(((cf(1)-s)*q1)+(s*q2))*(p2-p1)*weight;
    }
    return sum/cf((3.0*(n-1.0)));
}

прежде чем я уеду отсюда, я хочу убедиться, что я прав пока ...

также, этот параграф немного смутил меня:

Хорошо, мы можем делать интегралы по путям. Какие ценность этого? Ну предположим мы взять случайную точку z0 = x + iy где-то в нашем регионе. Предположим, что f (z) определяется на пути. Тогда Интегральная формула Коши говорит, что неотъемлемой частью нашего региона (который сумма 4 кусочных интегралов, которые мы знаем как это сделать) из f (z) / (2 * π * i * (z - z0)) действительно хорошая функция, которая будет соответствовать нашей оригинальной функция на границе.

что именно делает функция?

Answer 1

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

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

Достаточно шумихи.Как ты делаешь это?Я объясню это, предполагая, что вы абсолютно ничего не знаете о сложном анализе.Я буду использовать некоторые термины исчисления, но вы сможете следовать моим указаниям, даже если вы вообще не знаете исчисления.Поскольку я предполагаю, что так мало, объяснение должно быть довольно длинным.Я прошу прощения за это.

Каждая точка (x, y) в реальной плоскости может рассматриваться как комплексное число z = x + iy.Мы можем сложить и умножить комплексные числа, используя обычные правила алгебры и тот факт, что i * i = -1.Кроме того, обратите внимание, что 1 = (x + iy) * (x - iy)/(x<sup>2</sup> + y<sup>2</sup>), поэтому мы можем делить, если мы допустим 1/z = (x - iy)/(x<sup>2</sup> + y<sup>2</sup>)Поэтому у нас есть все обычные правила арифметики.

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

Предположим, что начальная область имеет углы P<sub>1</sub>, P<sub>2</sub>, P<sub>3</sub>, P<sub>4</sub>.Путь вокруг области определяется четырьмя отрезками (P<sub>1</sub>, P<sub>2</sub>), (P<sub>2</sub>, P<sub>3</sub>), (P<sub>3</sub>, P<sub>4</sub>), (P<sub>4</sub>, P<sub>1</sub>).Я расскажу о том, как обрабатывать первый отрезок.Остальные похожи.

Интеграл пути от f(z) по (P<sub>1</sub>, P<sub>2</sub>) - это интеграл от 0 до 1 из f((1-s)P<sub>1</sub> + sP<sub>2</sub>)(P<sub>2</sub> - P<sub>1</sub>).Чтобы оценить этот интеграл, проще всего сделать числовую интеграцию, используя правило Симпсона .Для этого выберите нечетное число n и для значений s = 0, 1/n, 2/n, ..., (n-1)/n, 1 присвойте им весовые коэффициенты в шаблоне 1, 4, 2, 4, 2, ..., 2, 4, 1.(Конечные точки - 1, все остальное чередуется между 4 и 2.) Теперь для каждой точки вычислите f((1-s)P<sub>1</sub> + sP<sub>2</sub>)(P<sub>2</sub> - P<sub>1</sub>), умножьте на вес и сложите их все вместе.Затем разделите на магическое значение 3 * (n-1).Результат примерно ваш интеграл.(По мере роста n ошибка в этом приближении составляет O(1/n<sup>4</sup>). В вашем случае, если вы возьмете n = 21, то приближение должно получиться достаточно хорошим, чтобы отобразить пиксели на нужный пиксель, за исключением некоторых пикселей вблизи границы.Сделайте его немного больше, и проблемная область уменьшится. По краю вам понадобится кратное число пикселей на стороне, чтобы уменьшить ошибку.)

ОК, так что мы можемсделать интегралы по путям.Какова ценность этого?Хорошо, предположим, что мы берем случайную точку z<sub>0</sub> = x + iy где-нибудь в нашем регионе.Предположим, что f(z) определено на пути.Тогда Интегральная формула Коши говорит, что интеграл вокруг нашей области (который является суммой 4-х кусочных интегралов, которые мы знаем, как сделать) из f(z)/(2 * π * i * (z - z<sub>0</sub>)) - это действительно хорошая функция, которая будет соответствовать нашей оригинальнойфункция на границе.Я не буду вдаваться во все «действительно приятные» вещи об этом, но то, что я говорил выше о конформных , является частью этого.

Теперь, какую функцию f делаем мыиспользовать?Хорошо предположим, что наш регион отображается на регион с углами Q<sub>1</sub>, Q<sub>2</sub>, Q<sub>3</sub>, Q<sub>4</sub>.Мы хотим, чтобы первый фрагмент пути отображался на второй фрагмент пути.Поэтому мы хотим, чтобы f((1-s)P<sub>1</sub> + sP<sub>2</sub>) было (1-s)Q<sub>1</sub> + sQ<sub>2</sub>.Это говорит нам о том, как вычислить f во всех точках, которые нам нужны для нашего интеграла.

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

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

Answer 2

нашел решение. Я должен сказать, что это намного сложнее, чем я ожидал:

при условии, что квадрат или четырехугольник имеет четыре угла:

AB
CD

вам нужен коэффициент интерполяции: xt для оси x и yt для оси y, так что

если вы определяете формулу линейной интерполяции:

lerp(j,k,t)
{
     return (t*(k-j))+j;
}

точка p в квадре ABCD определяется как:

p.x=lerp(lerp(a.x,b.x,xt),lerp(c.x,d.x,xt),yt)

и

p.y=lerp(lerp(a.y,c.y,yt),lerp(b.y,d.y,yt),xt)

тогда значения, которые вам нужно определить, это xt и yt

xt = ((2 * c.x * a.y) - (d.x * a.y) - (2 * a.x c.y) + (b.x c.y) - (c.x * b.y) + (a.x * d.y) - (a.y * p.x) + (c.y * p.x) + (b.y p.x) - (d.y p.x) + (a.x p.y) - (b.x p.y) - (c.x * p.y) + (d.x * p.y) - Sqrt (-4 * ((c.x * a.y) - (d.x * a.y) - (a.x * c.y) + (b.x * c.y) - (c.x * b.y) + (d.x * b.y) + (a.x d.y) - (b.x d.y)) * ((c.x * a.y) - (a.x * c.y) - (ay * px) + (cy * px) + (ax * py) - (cx * py)) + ((-2 * cx ay) + (dx ay) + (2 * ax cy) - (bx c.y) + (c.x * b.y) - (a.x * d.y) + (a.y * p.x) - (c.y * p.x) - (b.y * p.x) + (d.y * p.x) - (a.x * p.y) + (b.x * p.y) + (c.x * p.y) - (d.x p.y)) ^ 2)) / (2 ((c.x * a.y) - (d.x * a.y) - (a.x * c.y) + (b.x * c.y) - (c.x * b.y) + (d.x * b.y) + (a.x * d.y) - (b.x * d.y)))

и когда у вас есть это

yt=(p.x-lerp(a.x,b.x,('xt')))/(lerp(c.x,d.x,('xt'))-lerp(a.x,b.x,('xt')))