Перенос точек

The DEADman · 27/08/10 32

Здравствуйте!
Будучи программистом, я столкнулся с задачей переноса вершин некоторого многоугольника (площадь и длина ребер в результате переноса может меняться)

Хотелось бы, чтобы этот перенос однозначно определялся двумя векторами $a$ и $b$
с координатами $(x_1, y_1), \quad(x_2,y_2)$ соответственно. Преобразование переводит первый вектор во второй. На вход функции, выполняющей перенос, подаются координаты обоих векторов.

(возможно, с точками, от которых вектора отложены, если это необходимо)

В верную ли сторону я смотрю: накопал что-то про аффинное преобразование на плоскости и его матрицу. Определится ли она в данном случае однозначно? И что делать, если нет, какой дополнительный параметр функции будет естественнее ввести?

Если да, то верно ли, что новые координаты вершины $(x^*, y^*)$ будут получены умножением строки первоначальных координат и единицы $(x, y, 1)$ на матрицу аффинного преобразования?

Заранее спасибо!

JMH · 25/02/10 687

The DEADman в сообщении #419093 писал(а):

я столкнулся с задачей переноса вершин некоторого многоугольника (площадь и длина ребер в результате переноса может меняться)

Если длина ребер может меняться, то это уже не перенос - присутствует либо гомотетия, либо вращение, либо и то и др.

The DEADman в сообщении #419093 писал(а):

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

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

The DEADman в сообщении #419093 писал(а):

В верную ли сторону я смотрю: накопал что-то про аффинное преобразование на плоскости и его матрицу. Определится ли она в данном случае однозначно?

Да

The DEADman в сообщении #419093 писал(а):

В Если да, то верно ли, что новые координаты вершины $(x^*, y^*)$ будут получены умножением строки первоначальных координат и единицы $(x, y, 1)$ на матрицу аффинного преобразования?

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

The DEADman · 27/08/10 32

Спасибо!
И прошу прощения. Не совсем удобовразумительно сформулировал задачу.

Мне нужно такое преобразование плоскости, которое переводит вектор $a(x_1,y_1)$ в вектор $b(x_2,y_2)$ .

Однозначно ли определяется матрица такого преобразования?
(И если нет, то поправит ли ситуацию указание точек, от которых вектора отложены)?

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

Буду благодарен любой помощи в возможности и способе разрешения этого вопроса!

ИСН · 18/05/06 13438 с Территории

Уже лучше. Но не у всех преобразований есть матрица (у $x\to xy,\;y\to\sqrt{y^2-x^2}$ , например, нифига нету). Наверное, Вам нужно преобразование какого-то конкретного вида. Какого?

The DEADman · 27/08/10 32

Я надеялся на как можно более общий случай...
Вектора $(x_1;y_1); \quad (x_2; y_2)$ с заранее известными координатами и точками начала $(x_1^s; y_1^s); \quad (x_2^s; y_2^s)$ .

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

На вопрос, какого вида нужно преобразование... Пока мысли такие:

1. Растяжение первого вектора с тем, чтобы он приобрел длину второго.
2. Поворот первого вектора с тем, чтобы он стал коллинеарен второму.
3. Перенос точки начала первого вектора с тем, чтобы он совпал со вторым.

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

Проблема именно в математической формализации решения :(

ИСН · 18/05/06 13438 с Территории

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

The DEADman · 27/08/10 32

Ну, насколько я понял из того, что накопал в интернете, аффинное преобразование на плоскости может быть выполнено при помощи матрицы 3x3:

$\begin{pmatrix} a & d & 0 \\ b & e & 0 \\ c & f & 1 \end{pmatrix}$

Представляем векторы в виде $(x_1,y_1,1) and (x_2,y_2,1)$
В условии $a*M = b$ имеем:

$\begin{eqnarray} ax_1 + by_1 + c = x_2 \\ dx_1 + ey_1 + f = y_2 \\ 1 = 1 \end{eqnarray}$

Шесть штук неизвестных.
Если я прав.
Начальные точки векторов как-то могут помочь избавиться от неопределенности?

ИСН · 18/05/06 13438 с Территории

Ага, шесть неизвестных. Теперь: что нам дадут начальные точки? Ещё какие-то уравнения? Какие? Сколько? Сколько всего тогда получится уравнений?

The DEADman · 27/08/10 32

Кажется, еще плюс два уравнения.
Начальная точка вектора $(x_1^s; y_1^s)$ должна перейти в $(x_2^s; y_2^s)$ .

$\begin{eqnarray} ax_1 + by_1 + c = x_2 \\ dx_1 + ey_1 + f = y_2 \\ 1 = 1 \\ ax_1^s + by_1^s + c = x_2^s \\ dx_1^s + ey_1^s + f = y_2^s \\ 1 = 1 \end{eqnarray}$

Верно?
И еще два надо брать откуда-то.
Хотя, в общем, можно положить c и f равными нулю, но не наложит ли это какие-то сильные ограничения на преобразование - можно ли обойтись без переноса, одними поворотами/растяжениями?

ИСН · 18/05/06 13438 с Территории

Меня несколько настораживает зачем-то дважды упомянутое Вами бесполезное равенство 1=1, но выводы верные.
Да, уравнений не хватает, надо что-то делать. Да, можно этих двоих положить нулю. Да, обычно можно обойтись без них.

The DEADman · 27/08/10 32

Равенство 1 = 1 выходит из равенства $(x,y,1)*(0,0,1)^T = 1$ , матрица-то 3 на 3. Да, может, я и излишне его написал :)

Благодарю Вас!
После вычисления матрицы мне достаточно будет умножить на нее координаты (приняв третью за единицу) вершин моего многоугольника, чтобы получить преобразованную фигуру?

Но ведь есть какая-то разница для точности вычислений?
Есть ли какой-то способ подбирать $c$ и $f$ , чтобы она была как можно больше?

ИСН · 18/05/06 13438 с Территории

Похоже, так.
Насчёт точности - не помню, вероятно, что-то есть; надо сидеть и выводить.

The DEADman · 27/08/10 32

Спасибо!
Пожалуй, последний вопрос.
Предположим, $c$ и $f$ уже заранее кем-то заданы.
Вот что вышло у меня:

$\begin{pmatrix} x_1 & y_1 & 0 & 0 &|& x_2 - c \\ 0 & 0 & x_1 & y_1 &|& y_2 - f \\ x_1^s & y_1^s & 0 & 0 &|& x_2^s - c \\ 0 & 0 & x_1^s & y_1^s &|& y_2^s - f \\ \end{pmatrix}$

Из этой матрицы коэффициентов путем обращения находится вектор $(a, b, c, d)$ ?

ИСН · 18/05/06 13438 с Территории

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

The DEADman · 27/08/10 32

Да, прошу прощения, обращается именно левая (квадратная) часть :)

Она, кажется, невырожденна только в том случае, если $x_1*y_1^s \neq y_1*x_1^s$ .
Выходит, это непоправимый недостаток метода?

Научный форум dxdy

Правила форума

Перенос точек

Кто сейчас на конференции