Napięcie na wykresie, część II: gumka

To drugie z dwóch wyzwań dotyczących „napinania funkcji ciągnięcia”. Oto nieco prostsze Część I .

Let jazdy m gwoździ w płycie w pozycji (X ₁ , Y ₁ ) do (x _m y _m ) . Przywiąż gumkę do pierwszego i ostatniego z nich i rozciągnij wokół innych gwoździ, tak aby pasek przecinał wszystkie gwoździe w kolejności. Zauważ, że gumka opisuje teraz częściowo sparametryzowaną liniową funkcję (x (t), y (t)) w przestrzeni 2D.

Teraz wbij kolejne n gwoździ do tablicy, w pozycjach (x ₁ , y ₁ ) do (x _n , y _n ) . Jeśli teraz usuniemy wszystkie oryginalne gwoździe m, z wyjątkiem pierwszego i ostatniego (do którego są przywiązane końce gumy), gumka skróci się, dopóki nie będzie napięta wokół nowych gwoździ, dając kolejną funkcję liniową.

Jako przykład weź m = 12 początkowych gwoździ w pozycjach (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) i n = 10 kolejnych gwoździ w pozycjach (1, 1), (3, 1), (4, 4), (1, 3), (2, 2), (5, -1), (5, 0) ), (6, 2), (7, 1), (6, 0) . Poniższe trzy wykresy pokazują proces opisany powyżej:

^{W przypadku większej wersji: kliknij prawym przyciskiem myszy -> Otwórz w nowej karcie}

A oto animacja zaciśnięcia gumki, jeśli masz trudności z jej wizualizacją:

Wyzwanie

Biorąc pod uwagę dwie listy „gwoździ”, narysuj napięty gumowy pasek wokół drugiej listy, jeśli zaczyna się od kształtu przechodzącego przez wszystkie gwoździe na pierwszej liście.

Możesz napisać program lub funkcję i przyjąć dane wejściowe za pomocą argumentu STDIN, ARGV lub funkcji. Możesz wyświetlić wynik na ekranie lub zapisać obraz w pliku.

Jeśli wynik jest zrasteryzowany, musi on mieć co najmniej 300 pikseli z każdej strony. Końcowa gumka i gwoździe muszą pokrywać co najmniej 75% poziomego i pionowego zasięgu obrazu. Waga długości z X i Y mają być takie same. Musisz pokazać paznokcie w drugim zestawie (używając co najmniej 3x3 pikseli) i sznurku (co najmniej 1 piksel szerokości). Możesz włączyć lub nie osie.

Kolory są twoim wyborem, ale potrzebujesz co najmniej dwóch wyróżniających się kolorów: jednego dla tła i jednego dla paznokci i sznurka (te mogą mieć różne kolory).

Możesz założyć, że wszystkie gwoździe na drugiej liście znajdują się w odległości co najmniej 10 ^-5 jednostek od początkowego kształtu gumki (abyś nie musiał się martwić niedokładnością zmiennoprzecinkową).

To jest kod golfowy, więc wygrywa najkrótsza odpowiedź (w bajtach).

Więcej przykładów

Oto dwa kolejne przykłady:

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

A oto jeden przykład, który pokazuje znaczenie dwóch pozostałych gwoździ początkowych. Wynik powinien być b i nie :

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

Dzięki Ellowi za ten przykład.

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

Czyta dwie listy punktów ze STDIN.

Przykład

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

Jak to działa

Kluczem do rozwiązania jest praca w małych, przyrostowych krokach. Zamiast próbować dowiedzieć się, co się dzieje, gdy usuwamy wszystkie paznokcie naraz, koncentrujemy się na bezpośrednich efektach usunięcia tylko jednego paznokcia. Następnie możemy usuwać gwoździe jeden po drugim w dowolnej kolejności.

Praca przyrostowa oznacza, że ​​musimy śledzić stan pośredni gumki. Oto trudna część: samo śledzenie gwoździ, przez które przebiega zespół, nie wystarczy. Podczas usuwania paznokci opaska może się zranić, a następnie rozwinąć wokół paznokcia. Dlatego gdy zespół wchodzi w interakcję z gwoździem, musimy śledzić, ile razy i w jakim kierunku owija się wokół niego. Robimy to, przypisując wartość do każdego gwoździa wzdłuż zespołu w następujący sposób:

Uwaga:

• Zaczynamy liczyć, gdy tylko opaska przylegnie do gwoździa, mimo że gwóźdź nie wpływa ściśle na jego kształt. Przypomnij sobie, że w przeciwieństwie do ilustracji nasze paznokcie są bezwymiarowe. Dlatego jeśli opaska staje się styczna do gwoździa, nie jesteśmy w stanie stwierdzić, po której stronie gwoździa znajduje się sam po swojej pozycji --- musimy śledzić, gdzie kiedyś był względem opaski.

• Trzymamy gwoździe o wartości zerowej, to znaczy gwoździe, które kiedyś miały, ale nie trzymają już opaski, zamiast natychmiast je usuwać. Gdybyśmy to zrobili, mogłoby to wywołać niepożądaną reakcję łańcuchową, podczas gdy staramy się utrzymać efekty każdego kroku zlokalizowane. Zamiast tego paznokcie o wartości zero są uważane za kwalifikujące się do usunięcia w ramach większego procesu.

Teraz możemy opisać, co dzieje się na każdym kroku:

• Wybieramy gwóźdź do usunięcia z bieżącej ścieżki zespołu. Gwóźdź kwalifikuje się do usunięcia, jeśli jest częścią pierwszego zestawu gwoździ (z wyjątkiem punktów końcowych) lub jeśli jego wartość wynosi zero.

• Udając, że dwa sąsiednie gwoździe są nieruchome, ustalamy, które gwoździe z drugiego zestawu lub pary punktów końcowych będzie przebiegać przez zespół po usunięciu wybranego gwoździa (nie zawracamy sobie głowy resztą gwoździ z pierwszy set, ponieważ wszystko będzie ostatecznie zostać usunięte). Robimy to w sposób podobny do roztworu do części I . Wszystkie te gwoździe znajdują się po tej samej stronie opaski, dlatego przypisujemy im wartość 1 lub -1 , w zależności od strony.

• Aktualizujemy wartość dwóch sąsiednich gwoździ, aby odzwierciedlić zmiany na ścieżce zespołu (łatwo najtrudniejsza część!)

Ten proces powtarza się, aż nie będzie już więcej paznokci do usunięcia:

A oto bardziej skomplikowany przykład ilustrujący zespół owijający się wielokrotnie wokół gwoździa:

Java - 1262 bajtów

Wiem, że to prawdopodobnie nie gra w golfa tak bardzo jak mogłoby być.

Wydaje się jednak, że nikt inny nie podchodzi do talerza i nie odpowiada na to pytanie, więc zrobię to.

Po pierwsze, klasa „T” - która jest klasą punktową - 57 bajtów

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

I główna klasa - 1205 bajtów

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

Przykład:

Aby uruchomić, wywołaj funkcję „d” z listą punktów i zestawem gwoździ (tak, wiem, dziwne). Co to robi:

• tworzy listę punktów, które reprezentują linie - to znaczy wszystkie punkty między liniami.
• powtarza algorytm wielokrotnie do tych punktów, tak aby każdy punkt był średnią z dwóch punktów wokół niego.
• Kiedy wydaje się, że punkty już się nie poruszają, rysuję między paznokciami, których dotykają.

Nie jestem pewien, czy osie w pikselach są w porządku. Zawsze zajmie więcej niż 75% miejsca, może być naprawdę bardzo małe.

Oto ładna animacja pokazująca, co tu robię:

W końcu staje się tym, w którym punkty ledwo się poruszają. Właśnie wtedy widzę, jakich paznokci dotyka:

Oto niepoddany golfowi kod animacji:

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