Tensión en un gráfico, Parte II: Una banda elástica

Este es el segundo de dos desafíos sobre "tensar las funciones de tracción". Aquí está la Parte I, un poco más simple .

Pongamos m clavos en una tabla en las posiciones (x ₁ , y ₁ ) a (x _m , y _m ) . Ate una banda de goma al primero y al último de ellos y estírese alrededor de las otras uñas, de modo que la banda atraviese todas las uñas en orden. Tenga en cuenta que la banda elástica ahora describe una función parametrizada lineal por partes (x (t), y (t)) en el espacio 2D.

Ahora inserte otros n clavos en el tablero, en las posiciones (x ₁ , y ₁ ) a (x _n , y _n ) . Si ahora eliminamos todos los clavos m originales, excepto el primero y el último (al que están unidos los extremos de la goma), la banda elástica se acortará hasta que quede tensa alrededor de las nuevas uñas, produciendo otra función lineal por partes.

Como ejemplo, tome m = 12 clavos iniciales en las posiciones (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) , yn = 10 clavos adicionales en las posiciones (1, 1), (3, 1), (4, 4), (1, 3), (2, 2), (5, -1), (5, 0 ), (6, 2), (7, 1), (6, 0) . Los siguientes tres gráficos muestran el proceso descrito anteriormente:

^{Para una versión más grande: haga clic con el botón derecho -> Abrir en una pestaña nueva}

Y aquí hay una animación del ajuste de la banda elástica si tiene alguna dificultad para visualizarla:

El reto

Dadas dos listas de "clavos", trace la banda elástica tensa alrededor de la segunda lista si comienza desde la forma que atraviesa todas las uñas en la primera lista.

Puede escribir un programa o función y recibir información a través de STDIN, ARGV o argumento de función. Puede mostrar el resultado en la pantalla o guardar una imagen en un archivo.

Si el resultado está rasterizado, debe tener al menos 300 píxeles en cada lado. La banda elástica final y los clavos deben cubrir al menos el 75% de la extensión horizontal y vertical de la imagen. Las escalas de longitud de x y y tienen que ser las mismas. Debe mostrar las uñas en el segundo conjunto (usando al menos 3x3 píxeles) y la cadena (al menos 1 píxel de ancho). Puede incluir o no los ejes.

Los colores son su elección, pero necesita al menos dos colores distinguibles: uno para el fondo y otro para las uñas y la cuerda (aunque pueden tener colores diferentes).

Puede suponer que todas las uñas en la segunda lista son al menos ^10-5 unidades de distancia de la forma inicial de la banda elástica (para que no tenga que preocuparse por la inexactitud de punto flotante).

Este es el código de golf, por lo que gana la respuesta más corta (en bytes).

Más ejemplos

Aquí hay dos ejemplos más:

{{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}}

Y aquí hay un ejemplo que muestra la importancia de dos de las uñas iniciales restantes. El resultado debe ser b y no a :

{{0, 0}, {0, 1}, {-1, 1}, {-1, -1}, {1, -1}, {1, 0}}
{{-0.5, 0.5}}

Gracias a Ell por proporcionar este ejemplo.

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()

Lee dos listas de puntos de STDIN.

Ejemplo

[(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)]

Cómo funciona

La clave de la solución es trabajar en pequeños pasos incrementales. En lugar de tratar de descubrir qué sucede cuando quitamos todas las uñas a la vez, nos concentramos en los efectos directos de quitar solo una uña. Luego podemos quitar las uñas una por una en un orden arbitrario.

Trabajar de forma incremental significa que debemos realizar un seguimiento del estado intermedio de la banda elástica. Aquí está la parte difícil: simplemente no es suficiente hacer un seguimiento de las uñas que atraviesa la banda. Durante el proceso de extracción de las uñas, la banda puede lastimarse y luego desenrollarse alrededor de una uña. Por lo tanto, cuando la banda interactúa con un clavo, debemos realizar un seguimiento de cuántas veces y en qué dirección se envuelve. Lo hacemos asignando un valor a cada clavo a lo largo de la banda de la siguiente manera:

Tenga en cuenta que:

• Comenzamos a contar tan pronto como la banda es tangente a la uña, a pesar de que la uña no afecta estrictamente su forma. Recordemos que, a diferencia de la ilustración, nuestras uñas no tienen dimensiones. Por lo tanto, si la banda se vuelve tangente a un clavo, no podemos decir en qué lado de la banda se encuentra el clavo solo por su posición --- debemos hacer un seguimiento de dónde solía estar en relación con la banda.

• Mantenemos alrededor de las uñas con un valor de cero, es decir, las uñas que solían, pero ya no sostienen la banda, en lugar de quitarlas de inmediato. Si lo hiciéramos, podría desencadenar una reacción en cadena no deseada, mientras intentamos mantener localizados los efectos de cada paso. En cambio, las uñas con un valor de cero se consideran elegibles para la eliminación como parte del proceso más grande.

Ahora podemos describir lo que sucede en cada paso:

• Seleccionamos un clavo para eliminar del camino actual de la banda. Un clavo es elegible para su eliminación si es parte del primer conjunto de clavos (salvo para los puntos finales) o si su valor es cero.

• Fingiendo que los dos clavos vecinos están fijos, descubrimos qué clavos del segundo conjunto o el par de puntos finales por los que pasará la banda una vez que se retire el clavo seleccionado (no nos molestamos con el resto de los clavos del establecer en primer lugar, ya que con el tiempo todos estarán eliminados.) lo hacemos de una manera similar a la solución de la Parte I . Todos estos clavos están en el mismo lado de la banda, por lo tanto, les asignamos a todos un valor de 1 o -1 , dependiendo del lado.

• Actualizamos el valor de las dos uñas vecinas para reflejar los cambios en el camino de la banda (¡fácilmente la parte más difícil!)

Este proceso se repite hasta que no haya más uñas que quitar:

Y aquí hay un ejemplo más complicado que ilustra la banda envolviendo un clavo varias veces:

Java - 1262 bytes

Sé que esto probablemente no se juegue tanto como podría ser.

Sin embargo, nadie más parece estar dando un paso al frente y respondiendo esta pregunta, así que lo haré.

Primero, la clase "T", que es una clase de punto, 57 bytes

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

Y la clase principal - 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);}}}}

Ejemplo:

Para ejecutar, llame a la función "d" con una Lista de puntos y una serie de clavos (sí, lo sé, raro). Que hace:

• crea una lista de puntos que representan las líneas, es decir, todos los puntos entre las líneas.
• repite un algoritmo repetidamente en estos puntos para que cada punto sea el promedio de los dos puntos a su alrededor.
• Cuando los puntos ya no parecen moverse mucho, dibujo entre las uñas que están tocando.

No estoy seguro si los ejes en píxeles están bien. Siempre ocupará más del 75% del espacio, podría ser muy, muy pequeño.

Aquí hay una buena animación para demostrar lo que estoy haciendo aquí:

Finalmente, se convierte en esto, en el que los puntos apenas se mueven. Esto es cuando veo qué uñas está tocando:

Aquí está el código de animación sin golf:

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);
        }
    }
}