Borders of overlapping circles
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))
This reads a set of circles as (x,y,r) tuples on stdin, and outputs an image in PGM format to stdout. It works roughly by computing a distance function of the diagram at each pixel, and shading each pixel less than one pixel away proportionally to its distance.
{(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)}
Here the distance function has been divided by 32 to make it visible:
{(7, 9, 7), (1, 3, 2), (4, 0, 4), (9, 2, 4), (0, 8, 5)}
C# ~2746
This is a solution in C#. Probably far from optimal but C# wont win this anyway. Just wanted myself to prove that i can do it.
Input via commandline by specifying the values seperated with a space in the order x y r Output is a file 'l.bmp' within the executing directory.
Program accepts any ammount of circles.
Test 1 : 10 10 10 25 12 8
Test 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);
}
All the Math involved here is based on this. The coordinates of the lines were easy to get using the formulars from the link. However they needed to be rotated by the angle between the two involved cricles centers.
To reduce the lines length i calculated their intersections. Then for that intersection i checked if the current lines end reaches into a circle that isnt the "parent of the line" and also contains the intersection itself. If that was the case, that end of the line was reduced to the location of the intersection.
The circles were simple to draw, the "notneeded" parts were difficult to remove, so i came up with a "rubber" solution, that removes the stuff that isnt needed anymore by painting it white again. Kind of brute forcing it. This is done by walking along each circles edge and checking if that pixel is within range of another circle.
Initially i wanted to roll my own circle-drawing method that only draws the circle withing specified angles but that didnt turn out well and took even more lines of code.
Really having a hard time explaining this if you havent noticed... English isnt my mother tounge so i am sorry for that.
Golfed
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);}
More Complex examples (top circle gets into negative y values)
