Estou olhando pela janela do sótão para o quintal do meu vizinho. Eles têm um cachorro acorrentado a um poste no centro do quintal. O cachorro corre pelo quintal, mas está sempre no final de sua cadeia, por isso acaba deixando uma trilha na terra. Normalmente essa pista seria perfeitamente circular, mas meus vizinhos têm outros postes em seu quintal nos quais a corrente do cachorro é presa. Cada vez que a corrente do cão atinge um poste, o cão começa a girar em torno do novo poste, independentemente do comprimento da corrente que resta como raio. Como os pólos, o cachorro e a corrente têm largura zero (meus vizinhos são matemáticos), a corrente pode enrolar indefinidamente em torno de um poste sem que o raio do círculo diminua. O cão também pode passar pela corrente (e não pelo colarinho) se a corrente estiver em seu caminho. Depois de observar essa estranheza por um tempo, decido escrever um código para simular o cão do meu vizinho. O código pegará as localizações de um poste central, ao qual o cão está acorrentado, as localizações dos outros postes no quintal dos meus vizinhos, o comprimento da corrente e a localização inicial do cachorro, e exibirá um diagrama indicando a caminho onde o cachorro se desgastou na grama. Você pode assumir que qualquer combinação do seguinte é constante (e, portanto, não as aceita como entrada):

• Localização do poste ao qual o cão está acorrentado

• Comprimento da corrente

• Localização inicial do cão

O sol está nascendo, então o espaço no chão do meu sótão iluminado pela janela está encolhendo, me dando cada vez menos espaço para escrever meu código. Tente minimizar a contagem de bytes do seu código para que eu tenha espaço para redigitá-lo no meu sótão.

Casos de teste

Aqui, eu suponho que o cão comece 3 unidades ao sul do pólo em que está acorrentado (o ponto vermelho), localizado em 0,0. Eu indiquei onde os pólos estão com pontos para maior clareza, você não precisa incluí-los em sua saída.

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

Como seus vizinhos são matemáticos, assumi que o jardim de seu vizinho ocupa o domínio complexo e, portanto, quaisquer coordenadas de objetos no jardim são números complexos. Para usar esta função, você deve, portanto, passar uma lista de números complexos, indicando a localização dos pólos no jardim do seu vizinho. A representação padrão do sistema de coordenadas foi escolhida, onde à direita há números reais positivos e acima são números imaginários positivos. Isso significa que os exemplos se tornam:

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

Além disso, o programa assume o seguinte: a trela está ligada ao ponto 0, a trela tem 3 unidades e a área de plotagem é 10 por 10, centrada em torno de 0. Para esses parâmetros, os resultados correspondem exatamente aos exemplos, e é assim que o resultado se parece (para o exemplo final):

O algoritmo é bastante simples, exigindo apenas uma condição para diferenciar a pesquisa no sentido horário e no sentido anti-horário. O estado do algoritmo é definido pelo ponto de rotação atual e pela orientação / comprimento restante da trela quando atinge o ponto de rotação atual. Funciona da seguinte maneira:

• Filtre os pontos do conjunto de colisões que estão mais distantes do ponto de rotação atual do que o comprimento restante da trela, bem como o ponto de rotação atual.
• Se este conjunto estiver vazio, desenhe um círculo com o raio do comprimento restante da correia em torno deste ponto quando o final deste braço for atingido.
• Determine o ponto em que a diferença de fase entre o vetor de diferença e a orientação da trela é mínima / máxima. Este é o próximo ponto que a trela atingirá no sentido horário / anti-horário, respectivamente.
• Desenhe o arco com base nesses vetores, pegue o comprimento da guia, subtraia a magnitude da distância e defina a orientação da guia como a orientação do vetor de diferença. Atualize o ponto de rotação e continue desde o início.

Esse algoritmo é então executado primeiro no sentido horário, após o qual o estado é redefinido e é executado no sentido anti-horário. A simplicidade do algoritmo significa que cerca da metade do programa pelo valor gasto é gasto nas funções de desenho. Se as rotinas de desenho fossem removidas, removeria 218 bytes do tamanho do programa.

A seguir, é apresentada uma versão não destruída que também contém código de depuração, que também exibe pontos e colisões de trelas:

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

A saída que ele produz se parece com isso:

Processamento 3, 815 833 835 876 879 bytes

Salvou dois bytes graças a @ZacharyT removendo parênteses desnecessários

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

Execute este programa da seguinte maneira:

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

(a função srecebe a float[][]). Este é essencialmente o caso de teste nº 3, mas multiplicado por 100 para caber na janela.

Várias coisas a serem observadas:

• o programa NÃO desenha postes
• as imagens aparecem viradas de cabeça para baixo, porque no sistema de coordenadas do Processing, o eixo y positivo desce
• como o Processing usa flutuadores, os cálculos não são muito precisos; portanto, você pode ver isso nas imagens. Perguntei ao OP se esses erros de ponto flutuante são importantes.
• o tamanho da janela é de 600 pixels por 600 pixels
• coordenadas de entrada muito pequenas iniciarão o programa porque a pilha pushMatrix()e a popMatrix()operação podem conter apenas 32 matrizes.
• o cão começa em (0, -300) e a cadeia começa em 300 pixels de comprimento
• as imagens abaixo foram minificadas por conveniência

Exemplo de saída para o caso de teste acima.

Se você quiser ver a saída prettificada, adicione esta linha logo após a translate(w,w);função in 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);

E isso nos dá este resultado:

Ungolfed f()e explicação

(também contém código de depuração)

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

Em poucas palavras, o programa envia dois "buscadores", um no sentido anti-horário e o outro no sentido horário. Cada um desses buscadores encontra o pólo mais próximo e desenha um arco se a corrente for longa o suficiente, caso contrário, desenha um círculo. Depois de desenhar um arco, envia outro buscador para esse polo e o processo continua. f()contém o processo de cada candidato. Uma explicação mais detalhada virá assim que eu jogar mais isso.

LOGO, 305 298 297 293 bytes

Experimente o código no FMSLogo.

Defina uma função draw(golfed as d) que, dada a entrada como uma lista de coordenadas do pólo (por exemplo draw [[0 100] [100 100] [-200 100] [-100 -50][0 0]], irá desenhar na tela o resultado).

Requisitos:

1. Comprimento inicial da corda = 300 pixels. (como 3 pixels é muito pequeno)
2. [0 0]deve ser incluído na lista de pólos. Se o código de depuração (polos de desenho) estiver ativado, [0 0]o último item deverá ser esse.
3. O cão começa na coordenada x=0, y=-300(como na descrição do problema)

Otimizações possíveis:

1. -1 byte se não for necessário que o caso excepcional (o cão colidir com um poste) seja matematicamente correto substituindo >=por>

Código de golfe:

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

Código não-bloqueado ( ;inicia um comentário embutido (usado para explicação) e :inicia um nome de variável):

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

O script lê a lista de pontos do stdin como uma lista de números complexos.

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

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