2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I don't think there is a faster exact method, because as you know arc length does not transform nicely under general affine transformations. You could precompute the arc length for a sparser set of $(A,B)$ pairs and then interpolate between them. $\endgroup$ – user856 May 24 '17 at 20:51
4
$\begingroup$

$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}$

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.