Dadas as coordenadas de vários pontos em um plano e o raio de um círculo em torno de cada ponto, desenhe polígonos representando os círculos e as arestas onde os círculos se encontram. As arestas retas sempre caem ao longo das linhas de interseção círculo-círculo , mas podem não seguir o comprimento total dessas linhas.

Por sugestão do mbomb007 , imagine o comportamento das bolhas de sabão 2D. Isso é tecnicamente errado, porque as bolhas de sabão sempre se encontravam em ângulos de 120 ° para minimizar a energia, enquanto esses círculos podem se encontrar em qualquer ângulo.

Este é um diagrama de Voronoi, menos um plano de área definida. Obrigado Andreas . Esta é realmente uma generalização de um diagrama de Voronoi chamado diagrama de potência .

Exemplos

Por exemplo, dados dois pontos e dois raios, a saída pode ser assim:

Adicione outro ponto e raio e a saída poderá ser assim:

Entrada

Você pode estruturar a entrada da maneira que desejar. Poste os resultados com as seguintes entradas.

Teste 1

• x: 10, y: 10, r: 10
• x: 25, y: 12, r: 8

Teste 2

• x: 8, y: 10, r: 6
• x: 20, y: 8, r: 4
• x: 18, y: 20, r: 12

Saída

A saída deve ser gráfica e incluir bordas poligonais, mas nada mais é necessário. Pontos e interseções não precisam ser representados como estão nos exemplos.

Restrições

• Nenhum ponto existirá dentro do raio de outro círculo.
• Regras padrão do codegolf.
• Nenhuma resposta com brechas será aceita, mas fique à vontade para se divertir.

Python 2, 473 355 bytes

L=input()
m=min
a,b,c,d=eval('m(%s-r for u,v,r in L),'*4%('u','v','-u','-v'))
e=(-c-a)/499.
H=lambda x,y:x*x+y*y
I=500
J=int(2-(d+b)/e)
print'P2',I,J,255
i=I*J
P=lambda(u,v,r):H(c+i%I*e+u,b+i/I*e-v)-r*r
while i:i-=1;p,k=m((P(k)/[1,k[2]][P(k)>0],k)for k in L);u,v,r=k;print int(255*m(1,[m([-p/r]+[(P(l)-p)/H(u-l[0],v-l[1])**.5for l in L-{k}]),p][p>0]/2/e))

Isso lê um conjunto de círculos como (x,y,r)tuplas no stdin e gera uma imagem no formato PGM para o stdout. Ele funciona aproximadamente calculando uma função de distância do diagrama em cada pixel e sombreando cada pixel a menos de um pixel proporcionalmente à sua distância.

{(10,10,10),(25,12,8)}

{(8,10,6),(20,8,4),(18,20,12)}

{(6, 63, 4), (16, 88, 9), (64, 94, 11), (97, 96, 3), (23, 32, 13), (54, 14, 7), (41, 81, 3), (7, 7, 4), (77, 18, 8), (98, 55, 4), (2, 56, 7), (62, 18, 5), (13, 74, 2), (33, 56, 12), (49, 48, 4), (6, 76, 2), (82, 70, 9), (21, 71, 2), (27, 5, 10), (3, 32, 6), (70, 62, 6), (74, 46, 4), (21, 60, 7), (18, 47, 7), (94, 2, 4), (39, 97, 7), (62, 63, 2), (87, 29, 8), (19, 17, 4), (61, 23, 2), (73, 1, 8), (40, 17, 13), (99, 41, 4), (81, 57, 7), (1, 68, 5), (38, 3, 4), (46, 36, 9), (4, 39, 2), (73, 77, 3), (93, 19, 10), (67, 42, 3), (96, 65, 2), (2, 16, 3), (28, 92, 3), (54, 58, 2), (39, 86, 5), (84, 82, 5), (79, 43, 4), (5, 47, 1), (34, 41, 8), (65, 5, 2), (9, 44, 3), (53, 3, 6), (1, 12, 1), (81, 95, 7), (74, 31, 2), (63, 61, 1), (35, 72, 1), (44, 71, 2), (57, 35, 5), (46, 65, 6), (57, 45, 4), (93, 94, 1), (99, 81, 13), (13, 58, 4), (68, 32, 6), (11, 2, 6), (52, 98, 7), (51, 25, 5), (84, 2, 2), (44, 92, 3), (23, 72, 2), (32, 99, 7), (13, 19, 3), (97, 29, 8), (58, 80, 3), (67, 82, 5), (59, 60, 3), (86, 87, 5), (29, 73, 2), (5, 93, 4), (42, 74, 1), (75, 85, 8), (91, 53, 5), (23, 82, 4), (19, 97, 8), (51, 88, 3), (67, 12, 6), (60, 53, 1), (66, 72, 2), (57, 64, 2), (66, 49, 2), (44, 0, 4), (11, 69, 1), (93, 60, 5), (56, 50, 3), (19, 68, 3), (64, 75, 3), (6, 17, 2), (82, 5, 2)}

Aqui, a função de distância foi dividida por 32 para torná-la visível:

{(7, 9, 7), (1, 3, 2), (4, 0, 4), (9, 2, 4), (0, 8, 5)}

C # ~ 2746

Esta é uma solução em c #. Provavelmente longe do ideal, mas o C # não ganhará isso de qualquer maneira. Só queria provar que posso fazer isso.

Entrada via linha de comando, especificando os valores separados por um espaço na ordem xyr Output é um arquivo 'l.bmp' dentro do diretório em execução.

O programa aceita qualquer quantidade de círculos.

Teste 1: 10 10 10 25 12 8

Teste 2: 8 10 6 20 8 4 18 20 12

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Imaging;
using System.Linq;

class Program
{
    static void Main(params string[] args) => new Program().run(args);

    class Circle
    {
        public PointF P;
        public float R;
    }

    class Line
    {
        public PointF S;
        public PointF E;
        public Circle C1;
        public Circle C2;
        public Line(Circle c1, Circle c2, PointF s, PointF e)
        {
            S = s;
            E = e;
            C1 = c1;
            C2 = c2;
        }
    }


    List<Line> lines = new List<Line>();
    List<Circle> circles = new List<Circle>();

    void run(string[] args)
    {
        for (int i = 0; i < args.Length; i += 3)
            addcircle(args[i], args[i + 1], args[i + 2]);
        circles.Sort((c1, c2) => c1.P.X.CompareTo(c2.P.X));


        int mx = (int)circles.Max(c => c.P.X + c.R) + 1;
        int my = (int)circles.Max(c => c.P.Y + c.R) + 1;



        for (int i = 0; i < circles.Count; i++)
            for (int j = i + 1; j < circles.Count; j++)
            {
                var c1 = circles[i];
                var c2 = circles[j];

                var d = dist(c1.P, c2.P);
                var a = 1 / d * sqrt((-d + c1.R - c2.R) * (-d - c1.R + c2.R) * (-d + c1.R + c2.R) * (d + c1.R + c2.R));
                var x = (sqr(d) - sqr(c2.R) + sqr(c1.R)) / (2 * d);

                var ap = angle(c1.P, c2.P);
                var la = rotate(c1.P, new PointF(c1.P.X + x, c1.P.Y + a / 2), ap);
                var lb = rotate(c1.P, new PointF(c1.P.X + x, c1.P.Y - a / 2), ap);
                var l = new Line(c1, c2, la, lb);
                lines.Add(l);
            }
        foreach (Line l in lines)
            foreach (Line lo in lines)
            {
                if (l == lo) continue;
                var intersection = intersect(l, lo);

                if (intersection != null && online(intersection.Value, l) && online(intersection.Value, lo))
                {
                    foreach (Circle circle in circles)
                    {
                        if (l.C1 == circle || l.C2 == circle)
                            continue;
                        if (dist(intersection.Value, circle.P) >= circle.R)
                            continue;

                        if (dist(l.E, circle.P) < circle.R)
                            l.E = intersection.Value;

                        if (dist(l.S, circle.P) < circle.R)
                            l.S = intersection.Value;
                    }
                }
            }


        using (Bitmap bmp = new Bitmap(mx, my))
        {
            using (Graphics g = Graphics.FromImage(bmp))
            {
                g.Clear(Color.White);
                foreach (var c in circles)
                    draw(g, c);


                for (int i = 0; i < circles.Count; i++)
                {
                    var c1 = circles[i];
                    var p = new PointF(c1.P.X + c1.R, c1.P.Y);
                    for (int j = 0; j < circles.Count; j++)
                    {
                        if (i == j) continue;
                        var c2 = circles[j];
                        for (var f = 0f; f <= 360f; f += 0.1f)
                        {
                            var pl = rotate(c1.P, p, f);
                            if (dist(pl, c2.P) <= c2.R)
                            {
                                g.DrawRectangle(new Pen(Color.White), (int)pl.X, (int)pl.Y, 1, 1);
                            }

                        }
                    }
                }


                foreach (var l in lines)
                    draw(g, l);

            }
            bmp.Save("t.bmp");
        }
    }

    private float dist(PointF p1, PointF p2) => sqrt(sqr(p1.X - p2.X) + sqr(p1.Y - p2.Y));


    bool online(PointF p, Line l)
    {
        var lx = l.S.X < l.E.X ? l.S.X : l.E.X;
        var hx = l.S.X > l.E.X ? l.S.X : l.E.X;
        var ly = l.S.Y < l.E.Y ? l.S.Y : l.E.Y;
        var hy = l.S.Y > l.E.Y ? l.S.Y : l.E.Y;

        return p.X >= lx && p.X <= hx && p.Y >= ly && p.Y <= hy;
    }

    static PointF? intersect(Line l1, Line l2)
    {
        //Line1
        float A1 = l1.E.Y - l1.S.Y;
        float B1 = l1.S.X - l1.E.X;
        float C1 = A1 * l1.S.X + B1 * l1.S.Y;

        //Line2
        float A2 = l2.E.Y - l2.S.Y;
        float B2 = l2.S.X - l2.E.X;
        float C2 = A2 * l2.S.X + B2 * l2.S.Y;

        float det = A1 * B2 - A2 * B1;
        if (det == 0)
        {
            return null; //parallel lines
        }
        float x = (B2 * C1 - B1 * C2) / det;
        float y = (A1 * C2 - A2 * C1) / det;
        return new PointF(x, y);
    }

    void addcircle(string x, string y, string r)
    {
        var SCALE = 20f;
        Circle c1 = new Circle
        {
            P = new PointF(float.Parse(x) * SCALE, float.Parse(y) * SCALE),
            R = float.Parse(r) * SCALE
        };
        circles.Add(c1);
    }

    void draw(Graphics g, Line l) => g.DrawLine(new Pen(Color.Red), l.S.X, l.S.Y, l.E.X, l.E.Y);

    PointF rotate(PointF o, PointF p, float angle)
    {
        var sa = (float)Math.Sin(angle);
        var ca = (float)Math.Cos(angle);
        var dx = p.X - o.X;
        var dy = p.Y - o.Y;

        return new PointF((ca * dx - sa * dy + o.X), (sa * dx + ca * dy + o.Y));
    }

    float angle(PointF p1, PointF p2)
    {
        var dx = p2.X - p1.X;
        if (dx == 0)
            return 0f;
        return (float)Math.Atan((p2.Y - p1.Y) / dx);
    }


    void draw(Graphics g, Circle c)
    {
        g.DrawEllipse(new Pen(Color.Blue),
                      c.P.X - c.R,
                      c.P.Y - c.R,
                      c.R * 2,
                      c.R * 2);
    }

    float sqr(float d) => d * d;
    float sqrt(float d) => (float)Math.Sqrt(d);
}

Toda a matemática envolvida aqui é baseada nisso . As coordenadas das linhas eram fáceis de obter usando os formulários do link. No entanto, eles precisavam ser rotacionados pelo ângulo entre os dois centros envolvidos.

Para reduzir o comprimento das linhas, calculei suas interseções. Então, para essa interseção, verifiquei se o final das linhas atuais alcança um círculo que não é o "pai da linha" e também contém a própria interseção. Se fosse esse o caso, esse final da linha era reduzido ao local do cruzamento.

Os círculos eram simples de desenhar, as partes "desnecessárias" eram difíceis de remover, então eu vim com uma solução "de borracha", que remove as coisas que não são mais necessárias, pintando de branco novamente. Tipo de bruto forçando-o. Isso é feito caminhando pela borda de cada círculo e verificando se esse pixel está ao alcance de outro círculo.

Inicialmente, eu queria rolar meu próprio método de desenho de círculo que só desenha o círculo dentro de ângulos especificados, mas que não saiu bem e levou ainda mais linhas de código.

Realmente tendo dificuldade em explicar isso, se você ainda não percebeu ... Inglês não é minha língua materna, então sinto muito por isso.

Golfe

using System;using System.Collections.Generic;using System.Drawing;using System.Drawing.Imaging;using System.Linq;class P{static void Main(params string[]args)=>new P().R(args);class C{public PointF P;public float R;}class L{public PointF S;public PointF E;public C C1;public C C2;public L(C c1,C c2,PointF s,PointF e){S=s;E=e;C1=c1;C2=c2;}}List<L>_=new List<L>();List<C>c=new List<C>();void R(string[]args){for(int i=0;i<args.Length;i+=3)A(args[i],args[i+1],args[i+2]);c.Sort((c1,c2)=>c1.P.X.CompareTo(c2.P.X));int B=(int)c.Max(c=>c.P.X+c.R)+1;int e=(int)c.Max(c=>c.P.Y+c.R)+1;for(int i=0;i++<c.Count;)for(int j=i+1;j++<c.Count;){var f=c[i];var q=c[j];var d=D(f.P,q.P);var a=1/d*S((-d+f.R-q.R)*(-d-f.R+q.R)*(-d+f.R+q.R)*(d+f.R+q.R));var x=(F(d)-F(q.R)+F(f.R))/(2*d);var h=angle(f.P,q.P);var k=R(f.P,new PointF(f.P.X+x,f.P.Y+a/2),h);var m=R(f.P,new PointF(f.P.X+x,f.P.Y-a/2),h);var l=new L(f,q,k,m);_.Add(l);}foreach(L l in _)foreach(L o in _){if(l==o)continue;var n=I(l,o);if(n !=null && O(n.Value,l)&& O(n.Value,o)){foreach(C p in c){if(l.C1==p || l.C2==p)continue;if(D(n.Value,p.P)>=p.R)continue;if(D(l.E,p.P)<p.R)l.E=n.Value;if(D(l.S,p.P)<p.R)l.S=n.Value;}}}Bitmap r=new Bitmap(B,e);Graphics g=Graphics.FromImage(r);g.Clear(Color.White);foreach(var _ in c)D(g,_);for(int i=0;i++<c.Count;){var Q=c[i];var P=new PointF(Q.P.X+Q.R,Q.P.Y);for(int j=0;j++<c.Count;){if(i==j)continue;var G=c[j];for(var f=0f;f<=360f;f+=0.1f){var H=R(Q.P,P,f);if(D(H,G.P)<=G.R){g.DrawRectangle(new Pen(Color.White),(int)H.X,(int)H.Y,1,1);}}}}foreach(var l in _)D(g,l);r.Save("t.bmp");}float D(PointF p1,PointF p2)=>S(F(p1.X-p2.X)+F(p1.Y-p2.Y));bool O(PointF p,L l){var lx=l.S.X<l.E.X ? l.S.X : l.E.X;var hx=l.S.X>l.E.X ? l.S.X : l.E.X;var ly=l.S.Y<l.E.Y ? l.S.Y : l.E.Y;var hy=l.S.Y>l.E.Y ? l.S.Y : l.E.Y;return p.X>=lx && p.X<=hx && p.Y>=ly && p.Y<=hy;}static PointF? I(L l1,L l2){float a=l1.E.Y-l1.S.Y;float b=l1.S.X-l1.E.X;float d=a*l1.S.X+b*l1.S.Y;float e=l2.E.Y-l2.S.Y;float f=l2.S.X-l2.E.X;float g=e*l2.S.X+f*l2.S.Y;float h=a*f-e*b;if(h==0)return null;float x=(f*d-b*g)/h;float y=(a*g-e*d)/h;return new PointF(x,y);}void A(string x,string y,string r){var F=20f;C _=new C{P=new PointF(float.Parse(x)*F,float.Parse(y)*F),R=float.Parse(r)*F };c.Add(_);}void D(Graphics g,L l)=>g.DrawLine(new Pen(Color.Red),l.S.X,l.S.Y,l.E.X,l.E.Y);PointF R(PointF o,PointF p,float angle){var a=(float)Math.Sin(angle);var n=(float)Math.Cos(angle);var b=p.X-o.X;var x=p.Y-o.Y;return new PointF((n*b-a*x+o.X),(a*b+n*x+o.Y));}float angle(PointF p1,PointF p2){var a=p2.X-p1.X;if(a==0)return 0f;return(float)Math.Atan((p2.Y-p1.Y)/a);}void D(Graphics g,C c){g.DrawEllipse(new Pen(Color.Blue),c.P.X-c.R,c.P.Y-c.R,c.R*2,c.R*2);}float F(float d)=>d*d;float S(float d)=>(float)Math.Sqrt(d);}

Exemplos mais complexos (o círculo superior entra em valores y negativos)