# Stretch Transform

Stretch Transform is a geometric transformation that distorts a plane in a rubbery way. Update 2020: Now it's also working in 3D space.

The story started when Benedikt Groß asked me to help with a project. He was working on MapMap Vauxhall and searched for a way to distort a map of London by moving a bunch of points to another location. The rest of the map should move accordingly without producing corners or overlappings. I did some experiments and got to the following algorithm which I will explain in detail.

But first, play around with it to get an impression of how it's behaving.

- Click and drag somewhere on the grid to add an anchor.
- Drag one of the ends of an existing anchor to move it and select it.
- Click "Delete Anchor" to remove it.

## Image morphing

Distorting a grid or maps is one thing you could do with Stretch Transform. But maps are just one kind of image. So, any other image might work as well. Below you'll see a demo where you can mess with my face. If I'll find any pictures of my distorted face in the web, I expect them to have a link to this page attached! :-)

## How to use this kind of transformation in your own project?

Download the StretchTransform class from Github. It's a standalone Javascript library which doesn't have any dependencies.

## How does this work?

The goal was to have a transformation where an arbitrary number of points (I call them anchors) *a _{i}* could be set on a plane (original position, Fig. 1) and after moving them to another position

*a*(destination position), the plane should be distorted as follows:

_{i}^{'}- The original point of an anchor should be translated exactly to its target position.
- All points between the anchors should be transformed in a way that the original plane is mapped with as little distorsion as possible and possibly without overlapping (Fig. 2).
- If distorsion is necessary it should be round and not angular.
- The transformation should be as close as possible to an affine transformation (Fig. 3).

The algorithm has two main steps:

First calculating a transformation matrix *M _{i}* for each anchor point, and then applying these matrices in a „weighted“ way to every point that should be transformed.

#### Step 1

Calculate a transformation matrix *M _{i}* for each anchor point.

Obviously the transfomation of an anchor point is mainly its translation from position

*a*to

_{i}*a*. In order to get such affine transformations as shown in Fig. 3, it is also necessary to calculate a rotation and scaling for the transformation matrix.

_{i}^{'}The rotation of an anchor *i* is calculated as follows:

- Calculate angle
*r*of the vector from_{i,j}*a*to_{i}*a*_{j} - Calculate angle
*r*of the vector from_{i,j}^{'}*a*to_{i}^{'}*a*_{j}^{'} - Calculate difference
*dr*of these two angles_{i,j} - Calculate weighted average of these delta angles. The weighting depends on the distance of the target positions (
*a*to_{i}^{'}*a*)._{j}^{'}

The scaling is done similarly:

- Calculate length
*l*of the vector from_{i,j}*a*to_{i}*a*_{j} - Calculate length
*l*of the vector from_{i,j}^{'}*a*to_{i}^{'}*a*_{j}^{'} - Calculate quotient
*q*of these two length_{i,j} - Calculate a weighted „average factor“ of these quotients

#### Step 2

Apply the anchor transformation matrices in a „weighted“ way to every point *p* that should be transformed.

- Calculate distances
*d*between_{i}*p*and all original anchor positions*a*_{i} - Calculate a weight
*w*from_{i}*d*so that_{i}*w*is high when_{i}*d*is low. I used this function:_{i}*1 / d*. If_{i}^{2}*d*is 0, the point is exactly at an anchor position. In that case, the weight for this anchor will be set to 1, for all other anchors to 0._{i} - „Normalize“
*w*so that the sum of all_{i}*w*is 1_{i} - Apply anchor transformation matrices
*M*to_{i}*p*as follows:- Calculate vector
*v*from_{i}*p*to*a*_{i} - Calculate
*v*by applying_{i}^{'}*M*to_{i}*v*_{i} - Calculate weighted difference vector
*v*_{i}^{*}= (v_{i}^{'}- v_{i}) * w_{i} - Add
*v*to_{i}^{*}*p*

- Calculate vector

## Acknowledgements

Many thanks to Benedikt for giving me this interesting task to think about.

And also many thanks to David Pritchard who helped me a lot at refining and improving my first version of this transformation. We had a very inspiring talk through email which brought me to new ideas. David also did the very good blog post The artfulness of maps in which he talks about Benedikt Groß' and Bertrand Clercs Metrography project which uses the transformation. There you'll find mainly the same description of the algorithm but expressed in a more mathematical way.

The library is using the great gl-matrix library for vector, matrix and quaternion calculations.