Ich schaue aus meinem Dachfenster in den Hof meines Nachbarn. Sie haben einen Hund in der Mitte des Hofes an einen Pfosten gekettet. Der Hund rennt um den Hof, ist aber immer am Ende seiner Kette und hinterlässt am Ende eine Spur im Dreck. Normalerweise wäre diese Spur vollkommen kreisförmig, aber meine Nachbarn haben einige andere Stangen in ihrem Hof, an denen sich die Kette des Hundes verfängt. Jedes Mal, wenn die Hundekette auf eine Stange trifft, beginnt sich der Hund um die neue Stange zu drehen, wobei die Länge der Kette als Radius übrig bleibt. Da die Stangen, der Hund und die Kette alle null breit sind (meine Nachbarn sind Mathematiker), kann sich die Kette auf unbestimmte Zeit um eine Stange wickeln, ohne dass sich der Radius des Kreises verkürzt. Der Hund kann auch die Kette passieren (nur nicht das Halsband), wenn sich die Kette im Weg befindet. Nachdem ich diese Kuriosität eine Weile beobachtet habe, entscheide ich mich, einen Code zu schreiben, um den Hund meines Nachbarn zu simulieren. Der Code nimmt die Positionen eines Mittelpfostens, an den der Hund angekettet ist, die Positionen der anderen Pfosten in meinem Nachbarhof, die Länge der Kette und die Startposition des Hundes und gibt ein Diagramm aus, in dem die Weg, wo der Hund das Gras abgenutzt hat. Sie können davon ausgehen, dass eine beliebige Kombination der folgenden Elemente konstant ist (und sie daher nicht als Eingabe verwendet):

• Position der Stange, an die der Hund angekettet ist

• Länge der Kette

• Startort des Hundes

Die Sonne geht auf, so dass der Raum auf dem Boden meines vom Fenster beleuchteten Dachbodens kleiner wird und ich immer weniger Platz habe, um meinen Code zu schreiben. Bitte versuchen Sie, die Byteanzahl Ihres Codes so gering wie möglich zu halten, damit ich auf meinem Dachboden Platz zum Zeichnen habe.

Testfälle

Hier gehe ich davon aus, dass der Hund 3 Einheiten südlich von der Stange beginnt, an der er angekettet ist (der rote Punkt) 0,0. Ich habe aus Gründen der Klarheit angegeben, wo sich die Pole mit Punkten befinden. Sie müssen sie nicht in Ihre Ausgabe einbeziehen.

Poles at 1,2 -1,2

Poles at 0,.5

Poles at 0,1 1,1 -2,1 -1,-.5

Poles at 0,1 1,1

Python 3 mit matplotlib, 457 Bytes

from cmath import*
from matplotlib import pyplot as g,patches as i
def x(p):
 p+=[0];d=180/pi;a=2;h=g.gca();h.set_xlim(-5,5);h.set_ylim(-5,5)
 while a:
  a-=1;c=0;y=3;z=-pi/2
  while 1:
   s=[n for n in p if abs(n-c)<=y and n!=c]
   if not s:h.add_patch(i.Arc((c.real,c.imag),y*2,y*2));break
   n=[max,min][a](s,key=lambda n:(z-phase(n-c))%(2*pi));l,r=polar(n-c);h.add_patch(i.Arc((c.real,c.imag),y*2,y*2,[z,r][a]*d,0,[r-z,z-r][a]*d));y-=l;z=r;c=n
 g.show()

Da Ihre Nachbarn Mathematiker sind, habe ich angenommen, dass der Garten Ihres Nachbarn den komplexen Bereich einnimmt und alle Koordinaten von Objekten im Garten daher komplexe Zahlen sind. Um diese Funktion nutzen zu können, müssen Sie ihm eine Liste komplexer Zahlen übergeben, die die Positionen der Pole im Garten Ihres Nachbarn angeben. Die Standarddarstellung des Koordinatensystems wurde gewählt, wobei rechts positive reelle Zahlen und aufwärts positive imaginäre Zahlen stehen. Das heißt, die Beispiele werden:

x([2j+1,2j-1])
x([.5j])
x([1j,1+1j,-2+1j,-1-.5j])
x([1j,1+1j])

Außerdem geht das Programm von folgenden Dingen aus: Die Leine ist an den Punkt 0 gebunden, die Leine ist 3 Einheiten lang und die Plotfläche ist 10 mal 10 um 0 zentriert. Für diese Parameter stimmen die Ergebnisse genau mit den Beispielen überein. Und so sieht das Ergebnis aus (für das letzte Beispiel):

Der Algorithmus ist recht einfach und erfordert nur eine Bedingung, um die Suche im Uhrzeigersinn und gegen den Uhrzeigersinn zu unterscheiden. Der Status des Algorithmus wird durch den aktuellen Rotationspunkt und die Ausrichtung / verbleibende Länge der Leine beim Auftreffen auf den aktuellen Rotationspunkt definiert. Es funktioniert wie folgt:

• Filtern Sie Punkte aus dem Kollisionssatz heraus, die weiter vom aktuellen Rotationspunkt entfernt sind als die verbleibende Leinenlänge sowie den aktuellen Rotationspunkt.
• Wenn dieser Satz leer ist, zeichnen Sie einen Kreis mit dem Radius der verbleibenden Gurtlänge um diesen Punkt, wenn das Ende dieses Arms erreicht ist.
• Bestimmen Sie den Punkt, an dem die Phasendifferenz zwischen dem Differenzvektor und der Leinenorientierung minimal / maximal ist. Dies ist der nächste Punkt, an dem die Leine im Uhrzeigersinn bzw. gegen den Uhrzeigersinn schlägt.
• Zeichnen Sie den Bogen basierend auf diesen Vektoren, nehmen Sie die Länge der Leine, subtrahieren Sie die Größe der Distanz und stellen Sie die Ausrichtung der Leine auf die Ausrichtung des Differenzvektors ein. Aktualisieren Sie den Rotationspunkt und fahren Sie von Anfang an fort.

Dieser Algorithmus wird dann zuerst im Uhrzeigersinn ausgeführt, wonach der Zustand zurückgesetzt und im Gegenuhrzeigersinn ausgeführt wird. Die Einfachheit des Algorithmus bedeutet, dass ungefähr die Hälfte des Programms bytecount für die Zeichenfunktionen aufgewendet wird. Wenn die Zeichenroutinen entfernt würden, würden 218 Bytes aus der Programmgröße entfernt.

Das Folgende ist eine ungolfed-Version, die auch Debug-Code enthält, der auch Punkte und Leinen-Kollisionen anzeigt:

from cmath import pi, rect, polar, phase
from matplotlib import pyplot, patches
def x_ungolfed(points):
    degrees = 180/pi # conversions

    # add the center point to the collision points
    points.append(0.0)

    # configure plot area
    axes=pyplot.gca()
    axes.set_xlim(-5,5)
    axes.set_ylim(-5,5)

    # plot the points
    x, y =zip(*((p.real, p.imag) for p in points))
    axes.scatter(x, y, 50, "b")

    # first iteration is clockwise, second counterclockwise
    clockwise = 2
    while clockwise:
        clockwise -= 1

        # initial conditions
        center = 0 + 0j;
        leash_size = 3
        leash_angle = -pi / 2

        # initial leash plot
        leash_start = rect(leash_size, leash_angle)
        axes.plot([center.real, leash_start.real], [center.imag, leash_start.imag], "r")

        # search loop
        while 1:
            # find possible collission candidates
            candidates = [n for n in points if abs(n - center) <= leash_size and n != center]
            # if we reached the end, draw a circle
            if not candidates:
                axes.add_patch(patches.Arc(
                    (center.real, center.imag), 
                    leash_size*2, leash_size*2
                ))
                break
            # find the actual collision by comparing the phase difference of the leash angle vs the difference between the candidate and the current node
            new = (min if clockwise else max)(candidates, key=lambda n: (leash_angle - phase(n - center)) % (2 * pi))

            # convert the difference to polar coordinates
            distance, new_angle = polar(new - center)
            # draw the arc
            if clockwise:
                axes.add_patch(patches.Arc(
                    (center.real, center.imag),
                    leash_size * 2, leash_size * 2,
                    new_angle * degrees,
                    0,
                    (leash_angle-new_angle) * degrees
                ))
            else:
                axes.add_patch(patches.Arc(
                    (center.real, center.imag),
                    leash_size * 2, leash_size * 2,
                    leash_angle * degrees,
                    0,
                    (new_angle - leash_angle) * degrees
                ))
            # draw intermediate lines
            edge = rect(leash_size, new_angle) + center
            axes.plot([center.real, edge.real], [center.imag, edge.imag], "g")

            # perform updates: decrease remaining leash size, set new leash angle, move rotation center to the collision
            leash_size -= distance
            leash_angle = new_angle
            center = new

    # show the graph
    pyplot.show()

Die Ausgabe sieht folgendermaßen aus:

Verarbeitung 3, 815 833 835 876 879 Bytes

Dank @ZacharyT konnten zwei Bytes gespart werden, indem unnötige Klammern entfernt wurden

void settings(){size(600,600);}int i,w,x,n;float l,d,t,a,f,g,m,R,U;float[][]N,T;float[]S,p;void s(float[][]t){N=new float[t.length+1][2];N[0][0]=N[0][1]=i=0;for(float[]q:t)N[++i]=q;translate(w=300,w);noFill();pushMatrix();f(N,0,-w,w,1,0);popMatrix();f(N,0,-w,w,0,0);}float p(float a,float b){for(a+=PI*4;a>b;)a-=PI*2;return a;}void f(float[][]P,float x,float y,float L,int c,int I){l=2*PI;d=i=0;S=null;for(;i<P.length;i++){float[]p=P[i];g=atan2(y,x);m=atan2(p[1],p[0]);if(p(f=(c*2-1)*(g-m),0)<l&(t=dist(0,0,p[0],p[1]))<=L&I!=i){l=p(f,0);S=new float[]{g,m};d=t;n=i;}}if(S==null)ellipse(0,0,2*(L-d),2*(L-d));else{arc(0,0,L*2,L*2,p(S[c],S[1-c]),S[1-c]);R=cos(a=S[1]);U=sin(a);translate(d*R,d*U);T=new float[P.length][2];for(int i=0;i<T.length;T[i][1]=P[i][1]-d*U,i++)T[i][0]=P[i][0]-d*R;f(T,(L-d)*R,(L-d)*U,L-d,c,n);}}

Führen Sie dieses Programm folgendermaßen aus:

void setup() {
    s(new float[][]{{0,100},{100,100},{-200,100},{-100,-50}});
}

(Die Funktion snimmt in a float[][]). Dies ist im Wesentlichen Testfall Nr. 3, wird jedoch mit 100 multipliziert, um das Fenster anzupassen.

Einige Dinge zu beachten:

• Das Programm zeichnet KEINE Stangen
• Die Bilder werden verkehrt herum angezeigt, da im Koordinatensystem von Processing die positive y-Achse nach unten zeigt
• Da bei der Verarbeitung Floats verwendet werden, sind die Berechnungen nicht sehr genau, sodass Sie dies möglicherweise in den Bildern sehen. Ich habe das OP gefragt, ob diese Gleitkommafehler von Bedeutung sind.
• Die Größe des Fensters beträgt 600 x 600 Pixel
• Sehr kleine Eingabekoordinaten sprengen das Programm, weil der Stapel pushMatrix()undpopMatrix() Operation nur 32 Matrizen aufnehmen können.
• Der Hund beginnt bei (0, -300) und die Kette beginnt bei 300 Pixel Länge
• Die folgenden Bilder wurden zur Vereinfachung verkleinert

Beispielausgabe für den obigen Testfall.

Wenn Sie die hübsche Ausgabe sehen möchten, fügen Sie diese Zeile direkt nach der translate(w,w);In-Funktion hinzu s.

background(-1);scale(1,-1);fill(255,0,0);ellipse(0,0,25,25);fill(0);for(float[]q:N)ellipse(q[0],q[1],25,25);

Und das gibt uns dieses Ergebnis:

Ungolfed f() und Erklärung

(enthält auch Debug-Code)

void f(float[][]points, float x, float y, float len, int c, int pindex) {
    print(asd+++")");
    float closest = 2*PI;
    float d=0,t;
    float[]stuff = null;
    int index = 0;
    for(int i=0;i<points.length;i++) {
        if(pindex != i) {
            float[]p = points[i];
            float originAngle = atan2(y, x);
            float tempAngle = atan2(p[1], p[0]);
            //println(x,y,p[0],p[1]);
            float diff = c<1?tempAngle-originAngle:originAngle-tempAngle;
            println("@\t"+i+"; x=\t"+x+"; y=\t"+y+"; tx=\t"+p[0]+"; ty=\t",p[1], diff, originAngle, tempAngle);
            if(p(diff) < closest && (t=dist(0,0,p[0],p[1])) < len) {
                println("+1");
                closest = p(diff);
                stuff = new float[]{originAngle, tempAngle};
                d=t;
                index = i;
            }
        }
    }
    if(stuff == null) {
        ellipse(0,0,2*(len-d),2*(len-d));
        println("mayday");
    } else {
        println("d angles",d,p(stuff[c],stuff[1-c],c), stuff[1-c]);
        //println(points[0]);
        arc(0, 0, len*2, len*2, p(stuff[c],stuff[1-c],c), stuff[1-c]);
        float angle = stuff[1];
        translate(d*cos(angle), d*sin(angle));
        println("Translated", d*cos(angle), d*sin(angle));
        println("angle",angle);
        float[][]temp=new float[points.length][2];
        for(int i=0;i<temp.length;i++){
            temp[i][0]=points[i][0]-d*cos(angle);
            temp[i][1]=points[i][1]-d*sin(angle);
            println(temp[i]);
        }
        println(d*sin(angle));
        pushMatrix();
        println();
        f(temp, (len-d)*cos(angle), (len-d)*sin(angle), (len-d), c, index);
        popMatrix();
        //f(temp, (len-d)*cos(angle), (len-d)*sin(angle), (len-d), 0, index);
    }
}

Kurz gesagt, das Programm sendet zwei "Sucher", einer gegen den Uhrzeigersinn und der andere im Uhrzeigersinn. Jeder dieser Sucher findet den nächsten Pol und zeichnet einen Bogen, wenn die Kette lang genug ist, andernfalls zeichnet er einen Kreis. Sobald es einen Bogen gezeichnet hat, schickt es einen anderen Sucher an diesen Pol und der Prozess wird fortgesetzt. f()enthält den Prozess jedes Suchers. Eine ausführlichere Erklärung wird kommen, sobald ich mehr Golf spiele.

LOGO, 305 298 297 293 Bytes

Probieren Sie den Code auf FMSLogo.

Definieren Sie eine Funktion draw(golfen als d), die als Liste der Polkoordinaten (zum Beispiel) eingegeben wirddraw [[0 100] [100 100] [-200 100] [-100 -50][0 0]] das Ergebnis auf dem Bildschirm .

Bedarf:

1. Anfangsseillänge = 300 Pixel. (da 3 Pixel zu klein sind)
2. [0 0]muss in die Poleliste aufgenommen werden. Wenn der Debug-Code (Zeichnen von Polen) aktiviert ist, dann[0 0] muss dies das letzte Element sein.
3. Der Hund beginnt an der Koordinate x=0, y=-300(wie in der Problembeschreibung)

Mögliche Optimierungen:

1. -1 Byte, wenn ausnahmsweise (wenn der Hund gegen eine Stange rennt) nicht durch Ersetzen mathematisch korrekt sein muss >= mit>

Golf Code:

to f
op(if ?=pos 360 modulo :m*(180+heading-towards ?)360)
end
to x :m[:1 300]
home
forever[make 2 filter[:1>=u ?](sort :p[(u ?)<u ?2])invoke[pd
arc -:m*f :1
pu
if 360=f[stop]make 1 :1-u ?
lt :m*f
setpos ?]reduce[if f<invoke[f]?2[?][?2]]:2]
end
to d :p
copydef "u "distance
foreach[1 -1]"x
end

Ungolfed Code ( ;startet einen Inline-Kommentar (zur Erklärung) und :startet einen Variablennamen):

to f
    op ifelse ? = pos 360 modulo :m*(180 + heading - towards ?) 360
end

to x
    home
    foreach :poles [pu setpos ? pd circle 5] ; debug code
    make "length 300 ; initial length of rope
    forever [
        make "tmp filter [:length >= distance ?] ; floating point error makes > and >= similar,  ~
            ; but >= is correct mathematically ~
            (sort :poles [(distance ?) < distance ?2])
         ; the last = longest element will be rotated
        invoke [
            pd
            arc -:m*f :length
            pu
            if 360=f [stop]
            make "length :length - distance ?
            lt :m*f
            setpos ?
        ] reduce [
            if f < invoke[f]?2 [?] [?2]
        ] :tmp ; apply to use ? instead of :pos
    ]
end

to draw :poles
    foreach [1 -1] [[m]
        x
    ]
end

Python 2 + PIL, 310 Bytes

from PIL import Image
from cmath import*
I,_,X,P=Image.new('1',(300,300),'white'),abs,polar,input()
def r(s):
 a,C,l=0,0,3
 while _(a)<99:
  c=C+l*exp(1j*a);I.load()[c.real*30+150,150-c.imag*30]=0
  for p in P+[0]:
   N,E=X(C-c);n,e=X(C-p)
   if n<=N and _(E-e)<.1:l-=_(p-C);C=p
  a+=s
r(.01)
r(-.01)
I.show()

Das Skript liest die Liste der Punkte von stdin als Liste komplexer Zahlen.

printf '[complex(0,0.5)]' | python2 snippet.py

printf '[complex(0,1), complex(1,1)]' | python2 snippet.py