How would I algorithmically "stretch" polygons on a plane by re-scaling the distances between interior points?

Question

I've been thinking about a computational problem and could use some guidance for how to go about developing an algorithm to solve it.

On a Euclidean plane, I have a polygon A, a set of points A* bounded by A, another polygon B (that does not intersect A), and another set of points B* bounded by B. What I want is to create a mapping between points in A* and B* (not necessarily one-to-one or onto), re-scale the distances between mapped points (the rescaling can be different for each pair of points), and then "stretch" A and B so that mapped points are still contained within their bounding polygon but are the new distances away from each other. The polygons should maintain their shape to the greatest extent possible.

As a simple example, if A and B were squares of equal size centered along the X axis, A* consisted of the center point of A, B* consisted of the center point of B, and I wanted to halve the distance between those two points, I would stretch each polygon along the X axis towards the other by horizontally extending the top and bottom edges, horizontally shift the inner edges towards each other, and leave the outer edge unchanged. The new polygons would look like rectangles that are still centered along the X axis but with each of their center points and inner edges moved a quarter of the original distance towards one another.

Another way of visualizing the transformation is to use the raisin-in-bread analogy https://www.wwu.edu/skywise/hubble_pudding.html commonly used to explain the expansion of the universe. If the points in A* and B* were raisins, the algorithm would show how shapes around those points are distorted if space-time were expanding or contracting between pairs of points.

Ideally, a solution would generalize to any number of polygons with any number of mapped interior points.

Thanks

Answer 1

You might try using the spring model: https://en.wikipedia.org/wiki/Force-directed_graph_drawing. Or, you could use optimization methods. Build an objective function $\Psi$ that is a sum of penalty terms. For each pair of mapped points $a^*,b^*$ that you are hoping will be at distance $c_{a^*,b^*}$, you have a penalty term $(d(a^*,b^*) - c_{a^*,b^*})^2$. Also, for each point $a^*$, add a penalty term that is zero throughout most of the interior of $A$, but increases when you get close to the boundary of $A$ and rises to $+\infty$ for all points outside $A$. Finally, find an arrangement of points that minimizes this objective function. You could then apply any of a number of optimization methods to do this, such as gradient descent or others. Stress majorization may be useful.