Spannung auf einer Grafik, Teil II: Ein Gummiband

Dies ist die zweite von zwei Herausforderungen zum Thema "Funktionen straffen". Hier ist die etwas einfachere Teil I .

Lassen Sie uns m Nägel an den Positionen (x ₁ , y ₁ ) bis (x _m , y _m ) in ein Brett treiben . Binden Sie ein Gummiband an das erste und letzte Band und spannen Sie es um die anderen Nägel, sodass das Band alle Nägel der Reihe nach durchquert. Beachten Sie, dass das Gummiband nun eine stückweise linear parametrisierte Funktion (x (t), y (t)) im 2D-Raum beschreibt.

Fahren Sie nun an den Positionen (x ₁ , y ₁ ) bis (x _n , y _n ) weitere n Nägel in die Platine . Wenn wir jetzt alle ursprünglichen entfernen m Nägel mit Ausnahme der ersten und letzten (die die Enden des Gummis gebunden), das Gummiband verkürzt , bis sie straff um die neuen Nägel liegend ist, wodurch man eine andere stückweise lineare Funktion.

Nehmen Sie als Beispiel m = 12 Anfangsnägel an den Positionen (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) und n = 10 weitere Nägel an den Positionen (1, 1), (3, 1), (4, 4), (1, 3), (2, 2), (5, -1), (5, 0) ), (6, 2), (7, 1), (6, 0) . Die folgenden drei Darstellungen zeigen den oben beschriebenen Prozess:

^{Für größere Version: Rechtsklick -> In neuem Tab öffnen}

Und hier ist eine Animation der Gummibandstraffung, wenn Sie Schwierigkeiten haben, sie zu visualisieren:

Die Herausforderung

Zeichnen Sie bei zwei Listen mit "Nägeln" das gespannte Gummiband um die zweite Liste, wenn es von der Form ausgeht, die alle Nägel in der ersten Liste durchläuft.

Sie können ein Programm oder eine Funktion schreiben und Eingaben über STDIN, ARGV oder Funktionsargument vornehmen. Sie können das Ergebnis entweder auf dem Bildschirm anzeigen oder ein Bild in einer Datei speichern.

Wenn das Ergebnis gerastert wird, müssen mindestens 300 Pixel pro Seite vorhanden sein. Das endgültige Gummiband und die Nägel müssen mindestens 75% der horizontalen und vertikalen Ausdehnung des Bildes bedecken. Die Längenskalen von x und y müssen gleich sein. Sie müssen die Nägel im zweiten Satz (mit mindestens 3x3 Pixel) und den String (mindestens 1 Pixel breit) anzeigen. Sie können die Achsen einschließen oder nicht.

Sie haben die Wahl zwischen Farben, aber Sie benötigen mindestens zwei unterscheidbare Farben: eine für den Hintergrund und eine für die Nägel und die Schnur (diese können jedoch unterschiedliche Farben haben).

Sie können davon ausgehen, dass alle Nägel in der zweiten Liste mindestens 10 ^-5 Einheiten von der ursprünglichen Form des Gummibands entfernt sind (damit Sie sich nicht um Gleitkommaungenauigkeiten sorgen müssen).

Dies ist Codegolf, daher gewinnt die kürzeste Antwort (in Bytes).

Mehr Beispiele

Hier sind zwei weitere Beispiele:

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

Und hier ist ein Beispiel, das die Bedeutung von zwei verbleibenden Anfangsnägeln zeigt. Das Ergebnis sollte b und nicht a sein :

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

Vielen Dank an Ell für dieses Beispiel.

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

Liest zwei Punktelisten aus STDIN.

Beispiel

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

Wie es funktioniert

Der Schlüssel zur Lösung besteht darin, in kleinen, inkrementellen Schritten zu arbeiten. Anstatt herauszufinden, was passiert, wenn wir alle Nägel auf einmal entfernen, konzentrieren wir uns auf die direkten Auswirkungen des Entfernens nur eines einzigen Nagels. Wir können dann die Nägel einzeln in einer beliebigen Reihenfolge entfernen.

Inkrementelles Arbeiten bedeutet, dass wir den Zwischenzustand des Gummibands im Auge behalten müssen. Hier ist der schwierige Teil: Es reicht nicht aus, nur nachzuverfolgen, durch welche Nägel die Band läuft. Während des Entfernens von Nägeln kann das Band um einen Nagel gewickelt und später abgewickelt werden. Wenn das Band mit einem Nagel interagiert, müssen wir daher verfolgen, wie oft und in welche Richtung es sich darum wickelt. Dazu weisen wir jedem Nagel entlang des Bandes einen Wert zu, und zwar wie folgt:

Beachten Sie, dass:

• Wir fangen an zu zählen, sobald das Band den Nagel berührt, obwohl der Nagel seine Form nicht stark beeinflusst. Denken Sie daran, dass unsere Nägel im Gegensatz zur Abbildung dimensionslos sind. Deshalb, wenn die Band Tangente an einen Nagel wird können wir nicht sagen , welche Seite der Band der Nagel auf durch seine Position allein ist --- wir die Spur halten müssen , wo sie verwendet wird, um das Band zu sein relativ.

• Wir behalten Nägel mit dem Wert Null bei, d. H. Nägel, die früher das Band gehalten haben, aber nicht mehr, anstatt sie sofort zu entfernen. Wenn wir dies tun, könnte dies eine unerwünschte Kettenreaktion auslösen, während wir versuchen, die Auswirkungen jedes Schritts lokalisiert zu halten. Stattdessen können Nägel mit dem Wert Null im Rahmen des größeren Prozesses entfernt werden.

Nun können wir beschreiben, was bei jedem Schritt passiert:

• Wir wählen einen Nagel aus, der aus dem aktuellen Pfad der Band entfernt werden soll. Ein Nagel kann entfernt werden, wenn er Teil des ersten Satzes von Nägeln ist (abgesehen von den Endpunkten) oder wenn sein Wert Null ist.

• Wir tun so, als wären die beiden benachbarten Nägel fixiert, und finden heraus, durch welche Nägel des zweiten Satzes oder der beiden Endpunkte das Band laufen wird, sobald der ausgewählte Nagel entfernt ist (wir kümmern uns nicht um den Rest der Nägel des zuerst gesetzt, da sie schließlich alle entfernt werden werden.) Wir tun es in ähnlicher Weise auf die Lösung zu Teil I . Alle diese Nägel befinden sich auf derselben Seite des Bandes, daher weisen wir ihnen je nach Seite einen Wert von 1 oder -1 zu .

• Wir aktualisieren den Wert der beiden benachbarten Nägel, um die Änderungen auf dem Pfad der Band widerzuspiegeln (einfach der schwierigste Teil!)

Dieser Vorgang wird wiederholt, bis keine Nägel mehr entfernt werden müssen:

Und hier ist ein komplizierteres Beispiel, das zeigt, wie sich das Band mehrmals um einen Nagel wickelt:

Java - 1262 Bytes

Ich weiß, dass dies wahrscheinlich nicht so viel ist, wie es sein könnte.

Es scheint jedoch niemand anderes an die Tafel zu treten und diese Frage zu beantworten, also werde ich es tun.

Erstens, Klasse "T" - das ist eine Punktklasse - 57 Bytes

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

Und die Hauptklasse - 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);}}}}

Beispiel:

Rufen Sie zum Ausführen die "d" -Funktion mit einer Liste von Punkten und einer Reihe von Nägeln auf (ja, ich weiß, seltsam). Was es macht:

• Erstellt eine Liste von Punkten, die die Linien darstellen, dh alle Punkte zwischen den Linien.
• wiederholt einen Algorithmus wiederholt auf diese Punkte, so dass jeder Punkt der Durchschnitt der zwei Punkte um ihn herum ist.
• Wenn sich die Punkte nicht mehr viel zu bewegen scheinen, zeichne ich zwischen die Nägel, die sie berühren.

Ich bin mir nicht sicher, ob Achsen in Pixeln in Ordnung sind. Es wird immer mehr als 75% des Platzes einnehmen, es könnte wirklich sehr, sehr klein sein.

Hier ist eine nette Animation, um zu demonstrieren, was ich hier mache:

Schließlich wird es dies, in dem sich die Punkte kaum bewegen. Dies ist, wenn ich sehe, welche Nägel es berührt:

Hier ist der ungolfed, Animationscode:

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