Length of arbitrary $2$D curve when transformed by simple skew

Question

This is a real-world problem that I can tackle by brute force but I'd like to know if there is a faster way to do it. I suspect there is.....

I have a dataset $d$ where $d(0)$ $d(1)$ $d(2)$ are an ordered set of data. Each of them contains an $x$ and $y$ coordinate, and the distance precalculated from the previous point. So typical data might be: $$\begin{align} &d(0): x=0,\ y=0,\ d=0\\ &d(1): x=3,\ y=0,\ d=3\\ &d(2): x=2,\ y=1,\ d=1.414\\ &\quad\vdots \end{align}$$

The real-world data has tens or hundreds of thousands of points, and the distance between points is small $O(10^{-5})$, but the principle is the same. The important figure is the total length of the path.

We then apply a simple linear skew +stretch to the plane, and to all the points: $x\rightarrow x - Ay$, $y \rightarrow By$, and need to calculate the new total length.

I need to create a lookup table of this for about $100,000$ combinations of $A$ and $B$, so that for any given $(A, B)$ in the set, I can find the length of the curve when transformed.

Clearly it's not that demanding computationally; also clearly the scale factor isn't constant for all curves and skews, it depends on the exact curve shape. I could iterate through each $(A, B)$, and for each, skew the $10$-$100$k points and recalculate the total new distance, but that seems inefficient. Its also about $10^{12}$ point recalculations and Pythagorases (is that a valid plural?).

So I wonder, is there any generalised faster way?

Answer 1

$T\mathbf x$ is a transformation that skews $\mathbf x$

You want to know $\|T\mathbf x\|$

and $\|T\mathbf x\|^2= \langle T\mathbf x, T\mathbf x \rangle = \mathbf x^TT^TT\mathbf x$

$T = \begin{bmatrix} 1&B\\A&1\end{bmatrix}$ would be the matrix that provides the skew described above.

$T^TT = \begin{bmatrix} 1+A^2&(A+B)\\(A+B)&1+B^2\end{bmatrix}$

$\|T(x,y)\| = \sqrt {(1+A^2)x^2 + 2(A+B) xy + (1+B^2)y^2}$

Answer 2

The solution of @Doug M is excellent.

I would like to attract your attention on a different feature.

• First of all, one can get rid of the enlargment (homothety) operation because this operation can be done at the end by multiplying the results by the enlargment ratio.

• Then, the stretch is either $S = \begin{bmatrix} 1&A\\0&1\end{bmatrix}$ (with your notations) or, in the general case of an affine transform with determinant 1, under the form of a "LU" product (https://en.wikipedia.org/wiki/LU_decomposition) of a lower and a upper triangular matrix:

$$S = \underbrace{\begin{bmatrix} 1&0\\B&1\end{bmatrix}}_{\text{skew in the Oy direction}} \ \ \times \ \ \underbrace{\begin{bmatrix} 1&A\\0&1\end{bmatrix}}_{\text{skew in the Ox direction}}$$

which means having simpler tables to manage.