Mapear coordenadas 2D en coordenadas normalizadas que definen un cuadrilátero

Question

Tengo una serie de puntos 2D $q_i$ . También tengo un cuadrilátero convexo definido por $P =(p_1,p_2,p_3,p_4)$ . Me gustaría encontrar una manera de mapear estos puntos en el espacio de coordenadas definido por $P$ de manera que el nuevo $\hat{q}_i$ estaría en el rango $\{0,1\}$ donde $\{0,0\}$ es la esquina inferior izquierda del cuadrante, $\{0,1\}$ es la esquina superior izquierda, $\{1,1\}$ es la esquina superior derecha, y tal.

$q_i$ se supone que se encuentran dentro de $P$ y $P$ se supone que está relativamente orientado con los ejes x-y, de modo que podemos afirmar sin ambigüedad "esquina superior izquierda de $P$ ". De hecho, podemos suponer $p_i$ representan, por orden, $\{0,0\},\{0,1\},\{1,0\},\{1,1\}$

Espero que esta pregunta sea lo suficientemente clara, es la primera vez que pregunto aquí así que, por favor, hazme saber si necesito aclarar algo.

Answer 1

Dejemos que $(a,c)=p_3 - p_1, (b,d)=p_2-p_1$ y $\Delta = ad-bc$ . Si $\Delta \neq 0$ (lo que significa que los vectores $p_3 - p_1$ y $p_2-p_1$ no son paralelos) este problema tiene solución.

Dejemos que $(x_i,y_i) = q_i - p_1$ . Entonces $q_i$ mapas a $\frac{1}{\Delta}(d x_i - b y_i, a y_i - c x_i)$ .

---

¿De dónde viene eso?

Nos dicen que $p_1$ mapas a $(0,0)$ , por lo que deberíamos traducir a todo el mundo por $p_1$ para que los orígenes coincidan.

Se nos dice que $p_2 - p_1$ corresponde a un desplazamiento unitario a lo largo del $y$ -y que $p_3 - p_1$ corresponde a un desplazamiento unitario a lo largo del $x$ -eje. Considere $M = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ . Este $M$ toma el vector $\begin{pmatrix}1 \\ 0\end{pmatrix}$ un desplazamiento unitario a lo largo del $x$ -eje a $\begin{pmatrix}a \\ c\end{pmatrix}$ y toma $\begin{pmatrix}0 \\ 1\end{pmatrix}$ un desplazamiento unitario a lo largo del $y$ -eje, a $\begin{pmatrix}b \\ d\end{pmatrix}$ . Así que si $(a,c)=p_3 - p_1$ y $(b,d)=p_2-p_1$ esta matriz lleva el cuadrado unitario al paralograma (trasladado al origen) $P - p_1$ .

Queremos ir por el otro lado, así que queremos $M^{-1}$ . Primero encontramos el discriminante de $M$ que es $ad-bc$ . Si es distinto de cero, $M$ puede invertirse. (Esto equivale a $\begin{pmatrix}a \\ c\end{pmatrix}$ y $\begin{pmatrix}b \\ d\end{pmatrix}$ no ser paralelos. La inversa es $M^{-1} = \begin{pmatrix} d/\Delta & -b/\Delta \\ -c/\Delta & a/\Delta \end{pmatrix}$ .

A continuación, escribimos cada $q_i - p_1$ en coordenadas, $(x_i, y_i)$ y aplicar $M^{-1}$ para que obtenga el punto de la imagen $\frac{1}{\Delta}(d x_i - b y_i, a y_i - c x_i)$ .

Answer 2

Básicamente, estás buscando formas de mapear un cuadrilátero plano convexo en el cuadrado unitario. Hay, por supuesto, muchos mapas de este tipo, así que tendrás que decidir qué otras propiedades quieres que tenga el tuyo para seleccionar uno. Una opción bastante sencilla de implementar es la transformación de perspectiva plana, también conocida como homografía plana. Una razón de peso para utilizar este mapa es que en muchas APIs de gráficos por ordenador se dispone de una función para construir este mapa, por lo que es posible que no tengas que hacer ningún trabajo.

Un método general para construir esta transformación para un par arbitrario de cuadriláteros convexos se da en esta respuesta . Suponiendo que el cuadrado no es degenerado -no hay tres puntos colineales- y tomando $p_1$ , $p_2$ y $p_3$ como puntos de base, la matriz $A$ es entonces $P\operatorname{diag}(P^{-1}p_4)$ , donde $$P = \begin{bmatrix}p_1&p_2&p_3\\1&1&1\end{bmatrix}.$$ (The homogeneous coordinates of $p_4$ are used in the above formula.) A similar calculation for the unit square produces $$B = \begin{bmatrix}0&1&0\\0&0&1\\-1&1&1\end{bmatrix}.$$ El mapa de perspectiva viene dado entonces por la matriz $$M = BA^{-1} = B \operatorname{diag}(P^{-1}p_4)^{-1}P^{-1}.$$ La expresión siguiente $B$ representa dividir el filas de $P^{-1}$ por los factores de escala obtenidos al resolver $P(\lambda,\mu,\tau)^T=p_4$ por lo que sólo hay que realizar una única multiplicación matricial. Además, la multiplicación a la izquierda por $B$ corresponde a desplazar las filas de la otra matriz hacia arriba y sustituir la última fila por la suma de la segunda y la tercera, menos la primera.

Es poco probable que esta matriz tenga una fila de unos en la parte inferior, por lo que la tercera componente de las coordenadas homogéneas resultantes no suele ser igual a $1$ y tendrás que volver a convertir en coordenadas cartesianas no homogéneas dividiendo por este valor.

Otro mapa relativamente sencillo de implementar se basa en la interpolación bilineal, como sugiere Eric Towers. La idea es dibujar una cuadrícula en el cuadrado de manera que el espacio de la cuadrícula sea uniforme a lo largo de cada borde. El punto $(\xi,\eta)$ en el cuadrado unitario corresponde entonces a la intersección de las líneas (de nuevo utilizando coordenadas homogéneas) $\mathbf l_\xi = ((1-\xi)p_1+\xi p_2)\times((1-\xi)p_3+\xi p_4)$ y $\mathbf l_\eta=((1-\eta)p_1+\eta p_3)\times((1-\eta)p_2+\eta p_4)$ . Por lo tanto, el mapeo de un punto $p = \mathbf l_\xi \times \mathbf l_\eta$ en el cuadrado de la unidad es una cuestión de encontrar $\xi$ y $\eta$ tal que $\mathbf l_\xi\cdot p = \mathbf l_\eta\cdot p = 0$ . Este mapa tiene un aspecto más uniforme que el mapa en perspectiva, pero el mapa inverso del cuadrado unitario al cuadrado implica términos en $\xi\eta$ por lo que el cálculo de este mapeo desde el cuadrado a la unidad cuadrada implicará el cálculo de una raíz cuadrada.