Tension on a Graph, Part II: A Rubber Band 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.
Python + matplotlib, 688

from pylab import*
C=cross
P,M=eval("map(array,input()),"*2)
P,N=[[P[0]]+L+[P[-1]]for L in P,M]
W=[.5]*len(P)
def T(a,c,b):
 I=[(H[0]**2,id(n),n)for n in N for H in[(C(n-a,b-a),C(n-b,c-b),C(n-c,a-c))]if(min(H)*max(H)&gt;=0)*H[1]*H[2]]
 if I:d=max(I)[2];A=T(a,c,d);B=T(d,c,b);return[A[0]+[d]+B[0],A[1]+[sign(C(c-a,b-c))]+B[1]]
 return[[]]*2
try:
 while 1:
    i=[w%1*2or w==0for w in W[2:-2]].index(1);u,a,c,b,v=P[i:i+5];P[i+2:i+3],W[i+2:i+3]=t,_=T(a,c,b);t=[a]+t+[b]
    for p,q,j,k in(u,a,1,i+1),(v,b,-2,i+len(t)):x=C(q-p,c-q);y=C(q-p,t[j]-q);z=C(c-q,t[j]-q);d=sign(j*z);W[k]+=(x*y&lt;=0)*(x*z&lt;0 or y*z&gt;0)*(x!=0 or d*W[k]&lt;=0)*(y!=0 or d*W[k]&gt;=0)*d
except:plot(*zip(*P))
if M:scatter(*zip(*M))
show()


Reads two lists of points from STDIN.

Example

[(0, 0), (2, -1), (3.0/2, 4.0/3), (7.0/2, 1.0/3), (11.0/2, 16.0/3), (1, 16.0/3), (0, 1), (7, -2), (3, 4), (8, 1), (3, -1), (11, 0)]
[(1, 1), (3, 1), (4, 4), (1, 3), (2, 2), (5, -1), (5, 0), (6, 2), (7, 1), (6, 0)]




How it works

The key to the solution is to work in small, incremental steps.
Instead of trying to figure out what happens when we remove all the nails at once, we concentrate on the direct effects of removing just a single nail.
We can then remove the nails one by one in an arbitrary order.

Working incrementally means that we must keep track of the intermediate state of the rubber band.
Here's the tricky part: merely keeping track of which nails the band runs through is not enough.
During the process of removing nails the band can get wound and later unwound around a nail.
Therefore, when the band interacts with a nail we must keep track of how many times and in what direction it wraps around it.
We do it by assigning a value to each nail along the band like so:



Note that:


We start counting as soon as the band is tangent to the nail, even though the nail doesn't strictly affect its shape.
Recall that, unlike the illustration, our nails are dimensionless.
Therefore, if the band becomes tangent to a nail we can't tell which side of the band the nail is on by its position alone---we must keep track of where it used to be relative to the band.
We keep around nails with a value of zero, that is, nails that used to, but no longer hold the band, instead of removing them right away.
If we did, it could trigger an unwelcomed chain reaction, while we're trying to keep the effects of each step localized.
Instead, nails with a value of zero are considered eligible for removal as part of the bigger process.


Now we can describe what happens at each step:


We select a nail to remove from the band's current path.
A nail is eligible for removal if it's part of the first set of nails (save for the endpoints) or if its value is zero.
Pretending that the two neighboring nails are fixed, we figure out which nails from the second set or the pair of endpoints the band is going to run through once the selected nail is removed (we don't bother with the rest of the nails from the first set, since they'll eventually all be removed.)
We do it in a similar fashion to the solution to Part I.
All these nails are on the same side of the band, hence we assign to all of them a value of 1 or -1, depending on the side.
We update the value of the two neighboring nails to reflect the changes to the band's path (easily the trickiest part!)


This process is repeated until there are no more nails to remove:



And here's a more complicated example illustrating the band wrapping around a nail several times: