13
4
This is the second of two challenges about "pulling functions taut". Here is the slightly simpler Part I.
Let's drive m nails into a board at positions (x1, y1) to (xm, ym). Tie a rubber band to the first and last of those and stretch around the other nails, such that the band traverses all nails in order. Note that the rubber band now describes a piecewise linear parameterised function (x(t), y(t)) in 2D space.
Now drive another n nails into the board, at positions (x1, y1) to (xn, yn). If we now remove all of the original m nails except the first and last one (which the ends of the rubber is tied to), the rubber band will shorten until it's lying taut around the new nails, yielding another piecewise linear function.
As an example, take m = 12 initial nails at positions (0, 0), (2, -1), (3/2, 4/3), (7/2, 1/3), (11/2, 16/3), (1, 16/3), (0, 1), (7, -2), (3, 4), (8, 1), (3, -1), (11, 0), and n = 10 further nails at positions (1, 1), (3, 1), (4, 4), (1, 3), (2, 2), (5, -1), (5, 0), (6, 2), (7, 1), (6, 0). The following three plots show the process described above:
For larger version: Right-click --> Open in new tab
And here is an animation of the rubber band tightening if you have some difficulty visualising it:
The Challenge
Given two lists of "nails", plot the taut rubber band around the second list if it starts from the shape traversing all the nails in the first list.
You may write a program or function and take input via STDIN, ARGV or function argument. You can either display the result on the screen or save an image to a file.
If the result is rasterised, it needs to be at least 300 pixels on each side. The final rubber band and nails must cover at least 75% of the horizontal and vertical extent of the image. The length scales of x and y have to be the same. You need to show the nails in the second set (using at least 3x3 pixels) and the string (at least 1 pixel wide). You may or may not include the axes.
Colours are your choice, but you need at least two distinguishable colours: one for the background and one for the nails and the string (those may have different colours though).
You may assume that all nails in the second list are at least 10-5 units away from initial shape of the rubber band (so that you don't need to worry about floating-point inaccuracy).
This is code golf, so the shortest answer (in bytes) wins.
More Examples
Here are two more examples:
{{1, 1}, {3, 3}, {2, 4}, {1, 3}, {4, 0}, {3, -1}, {2, 0}, {4, 2}}
{{2, 1}, {3, 2}, {1, 2}, {4, 1}}
{{1, 1}, {3, 1}, {3, 3}, {1, 3}, {1, 5}, {3, 5}, {-1, 3}, {-1, 0}, {3, 4}, {5, 1}, {5, -1}, {7, -1}, {3, 7}, {7, 5}}
{{0, 0}, {0, 2}, {0, 4}, {0, 6}, {2, 0}, {2, 2}, {2, 4}, {2, 6}, {4, 0}, {4, 2}, {4, 4}, {4, 6}, {6, 0}, {6, 2}, {6, 4}, {6, 6}}
And here is one example that shows the significance of two of the initial nails remaining. The result should be b and not a:
{{0, 0}, {0, 1}, {-1, 1}, {-1, -1}, {1, -1}, {1, 0}}
{{-0.5, 0.5}}
Thanks to Ell for providing this example.
@laurencevs The string one is single-valued, which considerably simplifies things, because there's an obvious direction in which to process function and nails. This one may contain loops and zigzags, and the form of the function is considerably different (and variable), which means that the solutions should be considerably different. – Martin Ender – 2014-10-06T13:03:02.793
What's the output of this?
– Ell – 2014-10-10T15:31:46.790@Ell Ah, very nice test case. I suppose for consistency, it should be b, but I really need to clarify the question about that. Will do that soon. Thanks! – Martin Ender – 2014-10-10T15:44:04.283