Borders of overlapping circles Given the coordinates of several points on a plane, and the radius of a circle surrounding each point, draw polygons representing the circles and the edges where the circles meet. Straight edges will always fall along circle-circle intersection lines, but might not follow the full length of these lines.

Per mbomb007's suggestion, imagine the behavior of 2D soap bubbles. That's technically wrong, because soap bubbles would always meet at 120° angles to minimize energy, while these circles may meet at any angle.

This is a Voronoi diagram, minus a defined area plane. Thanks Andreas. This is actually a generalization of a Voronoi diagram called a power diagram.

Examples

For example, given two points and two radii, the output might look like this:



Add another point and radius and the output might look like this:



Input

You can structure the input however you wish. Please post results with the following inputs.

Test 1


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


Test 2


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


Output

Output should be graphical and should include polygon borders, but nothing else is required. Points and intersections do not need to be represented like they are in the examples.

Constraints


No point will exist within the radius of another circle.
Standard codegolf rules.
No answers with loopholes will be accepted, but feel free to have fun with it.
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)&gt;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&gt;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)}