Tensão em um gráfico, parte II: um elástico

Este é o segundo de dois desafios sobre "puxar funções esticadas". Aqui está a parte I mais simples .

Vamos colocar m pregos em uma placa nas posições (x ₁ , y ₁ ) a (x _m , y _m ) . Amarre um elástico ao primeiro e ao último deles e estique-o em volta das outras unhas, de modo que a banda atravesse todas as unhas em ordem. Observe que o elástico agora descreve uma função parametrizada linear por partes (x (t), y (t)) no espaço 2D.

Agora, introduza mais n pregos no quadro, nas posições (x ₁ , y ₁ ) a (x _n , y _n ) . Se agora remover todos os originais m unhas , exceto a primeira e última (que as extremidades da borracha está ligada a), o elástico vai encurtar até que ele está mentindo esticada em torno dos pregos novos, produzindo outra linear por partes função.

Como exemplo, faça m = 12 pregos iniciais nas posições (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) , e n = 10 pregos adicionais nas posições (1, 1), (3, 1), (4, 4), (1, 3), (2, 2), (5, -1), (5, 0 ), (6, 2), (7, 1), (6, 0) . Os três gráficos seguintes mostram o processo descrito acima:

^{Para versão maior: Clique com o botão direito do mouse -> Abrir em uma nova guia}

E aqui está uma animação do aperto do elástico se você tiver alguma dificuldade para visualizá-lo:

O desafio

Dadas duas listas de "pregos", trace o elástico esticado em torno da segunda lista, se ele começar com a forma que atravessa todas as unhas da primeira lista.

Você pode escrever um programa ou função e receber entradas via STDIN, ARGV ou argumento de função. Você pode exibir o resultado na tela ou salvar uma imagem em um arquivo.

Se o resultado for rasterizado, ele precisará ter pelo menos 300 pixels de cada lado. O elástico final e as unhas devem cobrir pelo menos 75% da extensão horizontal e vertical da imagem. As escalas de comprimento de x e y devem ser as mesmas. Você precisa mostrar as unhas no segundo conjunto (usando pelo menos 3x3 pixels) e a corda (com pelo menos 1 pixel de largura). Você pode ou não incluir os eixos.

As cores são a sua escolha, mas você precisa de pelo menos duas cores distintas: uma para o fundo e outra para as unhas e a corda (essas podem ter cores diferentes).

Você pode supor que todas as unhas da segunda lista estão a pelo menos 10 a ⁵ unidades da forma inicial do elástico (para que você não precise se preocupar com a imprecisão do ponto flutuante).

Isso é código de golfe, então a resposta mais curta (em bytes) vence.

Mais exemplos

Aqui estão mais dois exemplos:

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

E aqui está um exemplo que mostra o significado de duas das unhas iniciais restantes. O resultado deve ser b e não um :

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

Agradecemos a Ell por fornecer este exemplo.

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

Lê duas listas de pontos de STDIN.

Exemplo

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

Como funciona

A chave da solução é trabalhar em pequenas etapas incrementais. Em vez de tentar descobrir o que acontece quando removemos todas as unhas de uma só vez, concentramo-nos nos efeitos diretos de remover apenas uma unha. Podemos então remover as unhas uma a uma em uma ordem arbitrária.

Trabalhar de forma incremental significa que devemos acompanhar o estado intermediário do elástico. Aqui está a parte complicada: apenas manter o controle de quais unhas a banda percorre não é suficiente. Durante o processo de remoção das unhas, a banda pode ser ferida e depois desenrolada em torno de uma unha. Portanto, quando a banda interage com uma unha, devemos acompanhar quantas vezes e em que direção ela a envolve. Fazemos isso atribuindo um valor a cada unha ao longo da banda da seguinte forma:

Observe que:

• Começamos a contar assim que a banda é tangente à unha, mesmo que a unha não afete estritamente sua forma. Lembre-se de que, diferentemente da ilustração, nossas unhas não têm dimensão. Portanto, se a banda se torna tangente a uma unha, não podemos dizer de que lado da banda a unha está, apenas pela sua posição - devemos acompanhar onde ela costumava ser relativa à banda.

• Mantemos as unhas com um valor zero, ou seja, unhas que costumavam, mas não seguram mais a banda, em vez de removê-las imediatamente. Se o fizéssemos, isso poderia desencadear uma reação em cadeia indesejada, enquanto tentamos manter os efeitos de cada etapa localizados. Em vez disso, unhas com valor zero são consideradas elegíveis para remoção como parte do processo maior.

Agora podemos descrever o que acontece em cada etapa:

• Selecionamos uma unha para remover do caminho atual da banda. Uma unha é elegível para remoção se fizer parte do primeiro conjunto de unhas (exceto os pontos finais) ou se seu valor for zero.

• Fingindo que as duas unhas vizinhas estão fixas, descobrimos quais unhas do segundo conjunto ou o par de pontos de extremidade pela qual a banda passará quando a unha selecionada for removida (não nos incomodamos com o restante das unhas da primeiro set, uma vez que vai finalmente ser todos removidos.) Fazemos isso de uma forma semelhante à da solução a Parte I . Todas essas unhas estão do mesmo lado da banda, portanto, atribuímos a todas elas um valor de 1 ou -1 , dependendo do lado.

• Atualizamos o valor das duas unhas vizinhas para refletir as mudanças no caminho da banda (facilmente a parte mais complicada!)

Esse processo é repetido até que não haja mais unhas para remover:

E aqui está um exemplo mais complicado que ilustra a banda envolvendo uma unha várias vezes:

Java - 1262 bytes

Eu sei que isso provavelmente não é jogado tanto quanto poderia ser.

No entanto, ninguém mais parece estar respondendo a essa pergunta, então eu irei.

Primeiro, a classe "T" - que é uma classe de pontos - 57 bytes

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

E a classe principal - 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);}}}}

Exemplo:

Para executar, chame a função "d" com uma lista de pontos e uma série de pregos (sim, eu sei, estranho). O que faz:

• cria uma lista de pontos que representam as linhas - ou seja, todos os pontos entre as linhas.
• repete um algoritmo repetidamente para esses pontos, de modo que cada ponto seja a média dos dois pontos ao seu redor.
• Quando os pontos não parecem mais se mover, eu desenho entre as unhas que eles estão tocando.

Não tenho certeza se eixos em pixels estão ok. Sempre ocupará mais de 75% do espaço, pode ser muito, muito pequeno.

Aqui está uma bela animação para demonstrar o que estou fazendo aqui:

Eventualmente, torna-se isso, no qual os pontos mal estão se movendo. É quando vejo quais unhas estão tocando:

Aqui está o código de animação não destruído:

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