3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's an interesting way of thinking about it, I can see how this would lead to a solution although I think there's a more direct method. Another way of thinking about the problem is like the raisins-in-bread analogy commonly used to visualize the expansion of the universe. If each raisin was a point in A* or B* and space-time was either contracting or expanding between each of then, the algorithm would output the distorted shapes of polygons in this new fabric. $\endgroup$ – Thuy Guevarra Sep 16 '18 at 6:42
  • $\begingroup$ @ThuyGuevarra, if you find a more direct method, I hope you'll post it as an answer -- I look forward to seeing it! I don't think you should expect to find a simpler solution; in the special case where the polygons A,B cover all of the plane, this reduces to the graph drawing problem. So basically you have a graph drawing problem with extra constraints. $\endgroup$ – D.W. Sep 16 '18 at 18:09

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.