Tension on a Graph, Part II: A Rubber Band

Question

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 (x₁, y₁) to (x_m, y_m). 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 (x₁, y₁) to (x_n, y_n). 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.

Answer 1

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)>=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<=0)*(x*z<0 or y*z>0)*(x!=0 or d*W[k]<=0)*(y!=0 or d*W[k]>=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:

Answer 2

Java - 1262 bytes

I know this is probably not golfed as much as it could be.

However, no one else seems to be stepping up to the plate and answering this question, so I will.

First, class "T" - which is a point class - 57 bytes

class T{double x,y;public T(double a,double b){x=a;y=b;}}

And the main class - 1205 bytes

import java.awt.Color;import java.awt.Graphics;import java.util.*;import javax.swing.*;class Q extends JPanel{void d(List<T>a,T[]z){JFrame t=new JFrame();int m=0;int g=0;for(T v:a){if(v.x>m)m=(int)v.x;if(v.y>g)g=(int)v.y;}for(T v:z){if(v.x>m)m=(int)v.x;if(v.y>g)g=(int)v.y;}t.setSize(m+20,g+20);t.setVisible(true);t.getContentPane().add(this);double r=9;while(r>1){r=0;for(int i=0;i<a.size()-1;i+=2){T p1=a.get(i),p2=new T((p1.x+a.get(i+1).x)/2,(p1.y+a.get(i+1).y)/2);a.add(i+1,p2);if(y(p1,p2)>r){r=y(p1,p2);}}}double w=15;List<T>q=new ArrayList<T>();while(w>3.7){w=0;q.clear();for(int e=0;e<a.size()-2;e++){T p1=a.get(e),u=a.get(e+1),p3=a.get(e+2),p2=new T((p1.x+p3.x)/2,(p1.y+p3.y)/2);w+=y(u,p2);int k=0;if(y(p1,a.get(e+1))<.5){a.remove(e);}for(T n:z){if(y(n,p2)<1){k=1;q.add(n);}}if(k==0){a.set(e+1,p2);}}}q.add(a.get(a.size()-1));q.add(1,a.get(0));p=z;o=q.toArray(new T[q.size()]);repaint();}T[]p;T[]o;double y(T a,T b){return Math.sqrt(Math.pow(b.x-a.x,2)+Math.pow(b.y-a.y,2));}public void paintComponent(Graphics g){if(o!=null){for(int i=0;i<o.length-1;i++){g.drawLine((int)o[i].x,(int)o[i].y,(int)o[i+1].x,(int)o[i+1].y);}g.setColor(Color.blue);for(T i:p){g.fillOval((int)i.x-3,(int)i.y-3,6,6);}}}}

Example:

To run, call the "d" function with a List of points and an array of nails (yeah, I know, weird). What it does:

• creates a list of points that represent the lines - that is, all the points in between the lines.
• repeats an algorithm repeatedly to these points so that the each point is the average of the two points around it.
• When the points don't seem to be moving much anymore, I draw between any nails that they are touching.

I am not sure if axes in pixels is ok. It will always take up more than 75% of the space, it might just be really, really small.

Here is a nice animation to demonstrate what I'm doing here:

Eventually, it becomes this, in which the points are barely moving. This is when I see what nails it is touching:

Here is the ungolfed, animation code:

import java.awt.Color;
import java.awt.Graphics;
import java.util.ArrayList;
import java.util.List;

import javax.swing.JFrame;
import javax.swing.JPanel;

public class Q extends JPanel{
    List<Point>points=new ArrayList<Point>();
    List<Point>n=new ArrayList<Point>();
    public Q() throws InterruptedException{
        double[][]rawPoints={{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}};
        double[][]rawNails={{1, 1}, {3, 1}, {4, 4}, {1, 3}, {2, 2}, {5, -1}, {5, 0}, {6, 2}, {7, 1}, {6, 0}};
        List<Point>p=new ArrayList<Point>(),nails = new ArrayList<Point>();
        double factor = 50;
        for(double[]rawP:rawPoints){p.add(new Point(rawP[0]*factor+100,rawP[1]*factor+100));}
        for(double[]rawN:rawNails){nails.add(new Point(rawN[0]*factor+100,rawN[1]*factor+100));}
        n=nails;
        JFrame frame=new JFrame();
        frame.setSize(700,500);
        frame.setVisible(true);
        frame.getContentPane().add(this);
        d(p,nails);
    }
    public static void main(String[]a) throws InterruptedException{
        new Q();
    }
    void d(List<Point>a,List<Point>nails) throws InterruptedException{
        //add midpoint every iteration until length of 1 is achieved
        //begin algorithm
        //stop points that are within a small amount of a nail
        double distance=20;
        while(distance>1){
            distance=0;
            for (int i=0;i<a.size()-1;i+=2){
                double fir=a.get(i).x;
                double sec=a.get(i).y;
                double c=(fir+a.get(i+1).x)/2;
                double d=(sec+a.get(i+1).y)/2;
                a.add(i+1,new Point(c,d));
                double dist=distBP(new Point(fir,sec),new Point(c,d));
                if(dist>distance){distance=dist;}
            }
        }
        for(Point p:a){a.set(a.indexOf(p), new Point(p.x,p.y));}
        //algorithm starts here:
        setEqual(a);
        repaint();
        invalidate();
        System.out.println(a);
        int count=0;
        while(true){
            count++;
            for(int index=0;index<a.size()-2;index++){
                double x2=(a.get(index).x+a.get(index+2).x)/2;
                double y2=(a.get(index).y+a.get(index+2).y)/2;
                int pointStable=0;
                if(distBP(a.get(index),a.get(index+1))<.5){a.remove(index);}
                for(Point n:nails){
                    if(distBP(n,new Point(x2,y2))<1){pointStable=1;}
                }
                if(pointStable==0){a.set(index+1, new Point(x2,y2));}
            }
            if(count%10==0){
            setEqual(a);
            invalidate();
            repaint();
            Thread.sleep(5);
            }
        }
        //System.out.println(a);
    }
    void setEqual(List<Point>a){
        points = new ArrayList<Point>();
        for(Point p:a){points.add(p);}
    }
    double distBP(Point a,Point b){
        return Math.sqrt(Math.pow(b.x-a.x, 2)+Math.pow(b.y-a.y, 2));
    }
    @Override
    public void paintComponent(Graphics g){
        g.setColor(Color.white);
        g.fillRect(0,0,getWidth(),getHeight());
        g.setColor(Color.black);
        for(Point p:points){
            g.drawRect((int)p.x, (int)p.y, 1, 1);
        }
        for(Point nail:n){
            g.drawOval((int)nail.x-2, (int)nail.y-2, 4, 4);
        }
    }
}