Dengan koordinat beberapa titik pada pesawat, dan jari-jari lingkaran yang mengelilingi setiap titik, gambar poligon yang mewakili lingkaran dan tepi tempat lingkaran bertemu. Tepi lurus akan selalu jatuh di sepanjang garis persimpangan lingkaran-lingkaran , tetapi mungkin tidak mengikuti panjang penuh dari garis-garis ini.

Per saran mbomb007 , bayangkan perilaku gelembung sabun 2D. Itu secara teknis salah, karena gelembung sabun akan selalu bertemu pada sudut 120 ° untuk meminimalkan energi, sementara lingkaran ini dapat bertemu di sudut manapun.

Ini adalah diagram Voronoi, minus bidang luas yang ditentukan. Terima kasih Andreas . Ini sebenarnya adalah generalisasi dari diagram Voronoi yang disebut diagram kekuatan .

Contohnya

Misalnya, diberi dua titik dan dua jari-jari, output mungkin terlihat seperti ini:

Tambahkan titik dan jari-jari lain dan hasilnya mungkin terlihat seperti ini:

Memasukkan

Anda dapat menyusun input sesuai keinginan Anda. Silakan kirim hasil dengan input berikut.

Tes 1

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

Tes 2

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

Keluaran

Keluaran harus grafis dan harus mencakup batas poligon, tetapi tidak ada lagi yang diperlukan. Poin dan persimpangan tidak perlu direpresentasikan seperti pada contoh.

Kendala

• Tidak ada titik di dalam jari-jari lingkaran lain.
• Aturan codegolf standar.
• Tidak ada jawaban dengan celah yang akan diterima, tetapi jangan ragu untuk bersenang-senang dengannya.

Python 2, 473 355 byte

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

Ini membaca satu set lingkaran sebagai (x,y,r)tupel pada stdin, dan menampilkan gambar dalam format PGM ke stdout. Ini bekerja kira-kira dengan menghitung fungsi jarak diagram pada setiap piksel, dan menaungi setiap piksel kurang dari satu piksel secara proporsional dengan jaraknya.

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

Di sini fungsi jarak telah dibagi dengan 32 untuk membuatnya terlihat:

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

C # ~ 2746

Ini adalah solusi dalam C #. Mungkin jauh dari optimal tetapi C # tidak akan memenangkan ini. Hanya ingin diriku membuktikan bahwa aku bisa melakukannya.

Input melalui commandline dengan menentukan nilai-nilai yang dipisahkan dengan spasi dalam urutan xyr Output adalah file 'l.bmp' di dalam direktori eksekusi.

Program menerima jumlah lingkaran apa pun.

Tes 1: 10 10 10 25 12 8

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

Semua Matematika yang terlibat di sini didasarkan pada ini . Koordinat garis mudah diperoleh menggunakan formulars dari tautan. Namun mereka perlu diputar dengan sudut antara dua pusat cricles yang terlibat.

Untuk mengurangi panjang garis saya menghitung persimpangan mereka. Kemudian untuk persimpangan itu saya memeriksa apakah garis saat ini mencapai menjadi lingkaran yang bukan "induk dari garis" dan juga berisi persimpangan itu sendiri. Jika itu yang terjadi, ujung garis itu dikurangi menjadi lokasi persimpangan.

Lingkarannya sederhana untuk digambar, bagian yang "tidak perlu" sulit untuk dihilangkan, jadi saya menghasilkan solusi "karet", yang menghilangkan hal-hal yang tidak diperlukan lagi dengan mengecatnya lagi putih. Agak kasar memaksanya. Ini dilakukan dengan berjalan di sepanjang setiap tepi lingkaran dan memeriksa apakah piksel tersebut berada dalam jangkauan lingkaran lain.

Awalnya saya ingin menggulung metode menggambar lingkaran saya sendiri yang hanya menggambar lingkaran dengan sudut tertentu tetapi tidak berhasil dengan baik dan mengambil lebih banyak baris kode.

Benar-benar mengalami kesulitan menjelaskan ini jika Anda tidak memperhatikan ... Bahasa Inggris bukan ibuku bicara jadi aku minta maaf untuk itu.

Golf

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

Lebih banyak contoh kompleks (lingkaran atas masuk ke nilai y negatif)