Tension sur un graphique, partie II: une bande élastique

Il s'agit du deuxième des deux défis liés à la "traction des fonctions". Voici la partie I légèrement plus simple .

Insérons m clous dans une planche aux positions (x ₁ , y ₁ ) à (x _m , y _m ) . Attachez une bande de caoutchouc au premier et au dernier de ceux-ci et étirez-vous autour des autres ongles, de sorte que la bande traverse tous les ongles dans l'ordre. Notez que l'élastique décrit maintenant une fonction paramétrée linéaire par morceaux (x (t), y (t)) dans l'espace 2D.

Maintenant , un autre disque n clous dans la plaque, à des positions (x ₁ , y ₁ ) à (x _n , y _n ) . Si nous retirons maintenant tous les originaux m clous , sauf le premier et le dernier (dont les extrémités du caoutchouc est liée à), la bande de caoutchouc raccourcira jusqu'à ce qu'il soit allongé tendu autour des nouveaux clous, ce qui donne une autre linéaire par morceaux fonction.

Par exemple, prenez m = 12 clous initiaux aux 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) , et n = 10 autres clous aux positions (1, 1), (3, 1), (4, 4), (1, 3), (2, 2), (5, -1), (5, 0 ), (6, 2), (7, 1), (6, 0) . Les trois graphiques suivants montrent le processus décrit ci-dessus:

^{Pour une version plus grande: clic droit -> Ouvrir dans un nouvel onglet}

Et voici une animation du serrage de l'élastique si vous avez du mal à le visualiser:

Le défi

Étant donné deux listes de "clous", tracez l'élastique tendu autour de la deuxième liste s'il part de la forme traversant tous les clous de la première liste.

Vous pouvez écrire un programme ou une fonction et prendre une entrée via STDIN, ARGV ou un argument de fonction. Vous pouvez soit afficher le résultat à l'écran, soit enregistrer une image dans un fichier.

Si le résultat est tramé, il doit être d'au moins 300 pixels de chaque côté. L'élastique final et les clous doivent couvrir au moins 75% de l'étendue horizontale et verticale de l'image. Les échelles de longueur de x et y doivent être les mêmes. Vous devez montrer les clous dans le deuxième ensemble (en utilisant au moins 3x3 pixels) et la chaîne (au moins 1 pixel de large). Vous pouvez ou non inclure les axes.

Les couleurs sont votre choix, mais vous avez besoin d'au moins deux couleurs distinctes: une pour l'arrière-plan et une pour les ongles et la chaîne (celles-ci peuvent cependant avoir des couleurs différentes).

Vous pouvez supposer que tous les clous de la deuxième liste sont à au moins 10 à ⁵ unités de la forme initiale de l'élastique (de sorte que vous n'avez pas à vous soucier de l'inexactitude en virgule flottante).

Il s'agit du code golf, donc la réponse la plus courte (en octets) l'emporte.

Plus d'exemples

Voici deux autres exemples:

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

Et voici un exemple qui montre l'importance de deux des premiers clous restants. Le résultat doit être b et non a :

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

Merci à Ell d'avoir fourni cet exemple.

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

Lit deux listes de points depuis STDIN.

Exemple

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

Comment ça fonctionne

La clé de la solution est de travailler par petites étapes incrémentielles. Au lieu d'essayer de comprendre ce qui se passe lorsque nous retirons tous les ongles à la fois, nous nous concentrons sur les effets directs de la suppression d'un seul ongle. Nous pouvons ensuite retirer les clous un par un dans un ordre arbitraire.

Travailler progressivement signifie que nous devons garder une trace de l'état intermédiaire de l'élastique. Voici la partie délicate: il ne suffit pas de garder une trace des clous traversés par le groupe. Pendant le processus de retrait des ongles, la bande peut être enroulée et ensuite enroulée autour d'un ongle. Par conséquent, lorsque le groupe interagit avec un clou, nous devons garder une trace du nombre de fois et dans quelle direction il s'enroule autour de lui. Nous le faisons en attribuant une valeur à chaque ongle le long de la bande comme suit:

Notez que:

• Nous commençons à compter dès que la bande est tangente à l'ongle, même si l'ongle n'affecte pas strictement sa forme. Rappelons que, contrairement à l'illustration, nos ongles sont sans dimension. Par conséquent, si la bande devient tangente à un clou, nous ne pouvons pas dire de quel côté de la bande le clou est sur sa seule position --- nous devons garder une trace de l'endroit où il était par rapport à la bande.

• Nous gardons autour des ongles avec une valeur de zéro, c'est-à-dire des ongles qui autrefois, mais ne tiennent plus la bande, au lieu de les retirer tout de suite. Si nous le faisions, cela pourrait déclencher une réaction en chaîne indésirable, alors que nous essayons de garder les effets de chaque étape localisés. Au lieu de cela, les clous d'une valeur de zéro sont considérés comme éligibles à être retirés dans le cadre d'un processus plus vaste.

Nous pouvons maintenant décrire ce qui se passe à chaque étape:

• Nous sélectionnons un clou à retirer du chemin actuel du groupe. Un clou peut être retiré s'il fait partie du premier ensemble de clous (sauf pour les points de terminaison) ou si sa valeur est nulle.

• Prétendant que les deux clous voisins sont fixes, nous déterminons quels clous du deuxième ensemble ou la paire de points d'extrémité que la bande traversera une fois le clou sélectionné retiré (nous ne nous soucions pas du reste des clous du premier set, car ils finiront par être tous supprimés.) Nous le faisons de façon similaire à la solution à la partie I . Tous ces clous sont du même côté de la bande, nous attribuons donc à chacun d'eux une valeur de 1 ou -1 , selon le côté.

• Nous mettons à jour la valeur des deux clous voisins pour refléter les changements de chemin du groupe (facilement la partie la plus délicate!)

Ce processus est répété jusqu'à ce qu'il n'y ait plus de clous à retirer:

Et voici un exemple plus compliqué illustrant plusieurs fois la bande enroulée autour d'un clou:

Java - 1262 octets

Je sais que ce n'est probablement pas autant joué au golf.

Cependant, personne d'autre ne semble intervenir et répondre à cette question, alors je le ferai.

Tout d'abord, la classe "T" - qui est une classe de points - 57 octets

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

Et la classe principale - 1205 octets

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

Exemple:

Pour exécuter, appelez la fonction "d" avec une liste de points et un tableau de clous (ouais, je sais, bizarre). Ce qu'il fait:

• crée une liste de points qui représentent les lignes, c'est-à-dire tous les points entre les lignes.
• répète un algorithme à plusieurs reprises à ces points de sorte que chaque point soit la moyenne des deux points qui l'entourent.
• Lorsque les points ne semblent plus bouger, je dessine entre les ongles qu'ils touchent.

Je ne sais pas si les axes en pixels sont corrects. Il occupera toujours plus de 75% de l'espace, il pourrait être vraiment très petit.

Voici une belle animation pour montrer ce que je fais ici:

Finalement, cela devient cela, dans lequel les points bougent à peine. C'est à ce moment-là que je vois quels ongles il touche:

Voici le code d'animation non 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);
        }
    }
}