# Two-Coloring Overlapping Circles

Write a program or function that takes in the following input in a reasonable format of your choice:

• Two positive integers W and H that define the width and height of the image you'll be generating.

• Two RGB colors C1 and C2 that will be used to color the image.

• A list of 3-tuples of the form (r, x, y) that define circles with radius r and center x, y in the plane of the image. r is a positive integer and x and y are any integers. The top left pixel of the image is 0, 0 and the x-axis increases to the right and the y-axis increases downward.

Output an image with dimensions W by H that is colored with C1 and C2 such that no two neighboring regions defined by all the overlapping circles are the same color.

For example: If the input is

W = 300
H = 200
C1 = (255, 200, 0)
C2 = (128, 0, 255)
Circles = (25, 50, 80), (40, 80, 120), (300, -100, 6), (17, 253, 162)


then the circle boundaries look like this:

There are six distinct, contiguous regions in the image created by the circles. Each region must be colored with C1 (yellow) or C2 (purple) such that no two neighboring regions are the same color.

There are two ways to do this, their only difference being that the colors are swapped:

Thus, either of these two images would be valid output for the example input.

Something like this would be invalid output since two yellow regions neighbor each other.

• Besides C1 and C2, a third, neutral color such as black or white may be used for circle boundaries as long as they are no more than 5 pixels thick. (Black, 1-pixel thick boundaries are present in the example above.)

• Circles boundaries are not required, however. The regions may neighbor each other directly:

Both of these is another valid output to the example above.

• Circles should be as accurate as reasonably possible, using circle drawing algorithms or whatever your graphics library provides.

• In general, pixel-perfection is not required, but if the input parameters are scaled equally larger and larger, the resulting image should become more and more accurate.

• Anti-aliasing is allowed but not required.

• Gridlines or axis labels etc. in the background are not allowed.

The shortest code in bytes wins.

# More Examples

All using these inputs with different sets of circles:

W = 100
H = 60
C1 = (255, 0, 0)
C2 = (0, 0, 255)


In any example the colors can be swapped and remain valid.

Circles =
A. empty list
B. (13, 16, 20)
C. (30, 16, 20)
D. (200, 16, 20)
E. (42, 50, 20)
F. (42, 50, 20), (17, 40, 30)
G. (42, 50, 20), (17, 20, 30)
H. (42, 50, 20), (17, 10, 30), (10, 50, 30)
I. (42, 50, 20), (17, 10, 30), (35, 50, 20)
J. (18, 36, 40), (18, 63, 40), (18, 50, 20)
K. (100, -10, -20), (60, 50, -10)
L. (18, 36, 40), (18, 63, 40), (18, 50, 20), (14, 50, 20), (5, 50, 18), (20, 0, 0), (70, 22, 0), (10000, -9970, 0), (135, 100, -80)


A. B. C. D.
E. F. G. H.
I. J. K. L.

Make sure your output behaves similar to all these examples.

• It looks nice, can we output in ascii, for example C1 is 1 and C2 is 0? – lol Mar 12 '17 at 5:45
• @MatthewRoh No. I know that would be convenient but images are required. – Calvin's Hobbies Mar 12 '17 at 5:48
• Ok then I guess I can count out tikz – Sriotchilism O'Zaic Mar 12 '17 at 6:56
• @MatthewRoh, netpbm is a commonly used image format on this site. – Peter Taylor Mar 12 '17 at 7:26
• @Luis Ok. Small input variations like that or having the y axis go up are alright. – Calvin's Hobbies Mar 12 '17 at 13:14

# Mathematica, 165 bytes

ContourPlot[Cos@Tr[Boole[Norm[{x,y}-#2]<#]Pi&@@@#4],{x,0,#},{y,0,#2},PlotPoints->5!,AspectRatio->Automatic,Frame->False,ContourShading->RGBColor@@@#3,Contours->{0}]&


Pure function taking four arguments: the width, the height (both integers), an ordered pair of triples of numbers between 0 and 1 (representing the two RGB colors), and a list of items of the form {r, {x, y}} to record the radii and centers of the circles. For example, the first example in the OP would be called with the arguments [300, 200, {{1, 0.784, 0}, {0.5, 0, 1}}, {{25, {50, 80}}, {40, {80, 120}}, {300, {-100, 6}}, {17, {253, 162}}}]. The positive y-axis points upwards in Mathematica.

Norm[{x,y}-#2]<# detects whether a point is inside a given circle; Boole[...]Pi converts that True or False to π or 0. After computing those πs/0s over all the input circles, Tr adds them up and Cos converts even multiples of π to 1, odd multiples of π to –1. ContourPlot[...,Contours->{0}] then colors the appropriate region of the plane in two colors depending on whether the value is greater or less than 0. AspectRatio->Automatic makes circles look like circles; PlotPoints->5! gives a decent accuracy (boost it to 9! if you really want an amazing picture, far in the future!); Frame->False gets rid of the axes; and ContourShading->RGBColor@@@#3 uses the input colors for the contours.

Sample output, with the first pair of colors (since they're nice) but the last set of circles:

## JavaScript/SVG/HTML5, 219 bytes

f=// for demo
(w,h,b,f,a)=><svg width=${w} height=${h}><rect width=${w} height=${h} fill=rgb(${b}) /><path fill=rgb(${f}) fill-rule=evenodd d=${a.map(([r,x,y])=>[M+x,y-r+a+r,r,0,0,0,0,r+r+a+r,r,0,0,0,0,-r-r]).join} /></svg> ;//demo [[A, []], [B, [[13, 16, 20]]], [C, [[30, 16, 20]]], [D, [[200, 16, 20]]], [E, [[42, 50, 20]]], [F, [[42, 50, 20], [17, 40, 30]]], [G, [[42, 50, 20], [17, 20, 30]]], [H, [[42, 50, 20], [17, 10, 30], [10, 50, 30]]], [I, [[42, 50, 20], [17, 10, 30], [35, 50, 20]]], [J, [[18, 36, 40], [18, 63, 40], [18, 50, 20]]], [K, [[100, -10, -20], [60, 50, -10]]], [L, [[18, 36, 40], [18, 63, 40], [18, 50, 20], [14, 50, 20], [5, 50, 18], [20, 0, 0], [70, 22, 0], [10000, -9970, 0], [135, 100, -80]]] ].forEach(([c, a])=>document.write(<nobr><tt>&nbsp;${c}.&nbsp;</tt>${f(100, 60, [255, 0, 0], [0, 0, 255], a)}</nobr><wbr>)); # BBC Basic, 120 117 bytes Download interpreter at http://www.bbcbasic.co.uk/bbcwin/bbcwin.html I.w,h,R,G,B,r,g,b:V.22,4,19;16,r,g,b,275;16,R EORr,G EORg,B EORb,24,0;0;w;h;16 5I.r,x,y:V.25,4,x;h-y;25,154,r;0;:G.5  BBC Basic has a range of colour modes allowing you to plot raster graphics according to basic logic operations: OR, AND, XOR etc. It also supports pallete reprogramming, meaning that for example here a 2 colour image can have its colours reprogrammed to any of 4096 colours. The implementation used here has some (undocumented) differences from the original BBC implementation, in which the EOR operators would not be necessary. Ungolfed  INPUTw,h,R,G,B,r,g,b: :REM Input size and colours VDU22,4 :REM Change to MODE 4 (2 colours) as the default mode gives odd behaviour VDU19,0,16,r,g,b,19,1,16,R EORr,G EORg,B EORb :REM Reprogram the colours to R,G,B and R^r,G^g,B^b VDU24,0;0;w;h;16 :REM Setup a graphics viewport of the right size, and "clear" it to change background colour 5 INPUTr,x,y :REM take input coordinates VDU25,4,x;h-y; :REM move to x,y (h-y required as BBC BASIC y axis increases upward, reverse of spec) VDU25,154,r;0; :REM draw circle in "logical inverse colour" of existing pixels (this implementation seems however to XOR with colour 1 instead) GOTO5 :REM repeat infinitely until user presses escape  Typical output screen Example image scaled up by a factor of 10 in units / factor of 5 in pixels (BBC basic uses 1 pixel = 2 units.) # MATL, 3029 25 bytes 2ZG:i:!J*+2&!-|i<so2&!1YG  Input format: • Colormap as a matrix of values between 0 and 255, where each row defines a color • W • H • Column vector of 1-based center coordinates as complex values (x is the real part, y is the imaginary part) • Column vector of radii. Try at MATL Online! Or verify the last test case. (The interpreter is still experimental. You may need to refresh the page and try again if it doesn't work). ### Explanation The code uses complex numbers to define the grid of points and to compute distances, and makes heavy use of array operations with broadcasting. 2ZG % Implicitly input matrix of colors. Set as colormap : % Implicitly input W. Push [1 2 ... W] i: % Input H. Push [1 2 ... H] !J* % Transpose, multiply by 1i + % Add element-wise with broadcast. Gives H×W grid of points as % complex numbers, 1-based 2&! % Permute first dimension with the third. Gives a 1×W×H array -| % Implicitly input center coordinates. Subtract grid from them, % element-wise with broadcast. Gives a C×H×W array, where C is the % number of circles i % Input column vector of circle radii < % Less than, element-wise with broadcast so % Sum along first dimension, modulo 2. Gives a 1×W×H array 2&! % Permute first dimension with the third. Gives a a H×W array 1YG % Display as scaled image  • I say Save Those Bytes! :D – Greg Martin Mar 12 '17 at 19:55 • @GregMartin You are right. Who cares about elegance when 4 bytes can be saved! :-) Done – Luis Mendo Mar 12 '17 at 22:19 • @LuisMendo The shorter the better with codegolf, no matter how ugly it becomes. ;) – Kevin Cruijssen Mar 13 '17 at 16:07 # Python using pypng, 140 138 bytes import png f=lambda W,H,c,d,C:png.from_array([[[c,d][sum(abs(x-X+1j*(y-Y))<r for r,x,y in C)%2]for X in range(W)]for Y in range(H)],'RGB')  Example usage: W = 100 H = 60 C1 = (255, 0, 0) C2 = (0, 0, 255) Circles = (18, 36, 40), (18, 63, 40), (18, 50, 20), (14, 50, 20), (5, 50, 18), (20, 0, 0), (70, 22, 0), (10000, -9970, 0), (135, 100, -80) f(W, H, C1, C2, Circles).save('test.png')  Thanks to xnor for saving 2 bytes. • Welcome to code golf! For checking if a point lies in a circle, one trick is to use complex norm: abs(x-X+1j*(y-Y))<r. – xnor Mar 12 '17 at 20:29 # Math (non-competiting) (idk how to do LaTeX in PPCG, so I used a LaTeX to png tool) ## Explanation The product of multiple circle equations ((x-a)^2+(y-b)^2-r^2) >= 0 will make a graph which this question needs. In the equation, n is the size of the array, and (x, y or r)_k is the kth (x, y, or r) element. ## Example (0,0,2),(2,2,2) (Inequality plot by WolframAlpha) # Get/Run equation for WolframAlpha Getting script : Complete <input id="in" placeholder="input, with () changed to []"> <br> <input type="color" id="c1" value="#ff0000"> <input type="color" id="c2" value="#00ff00"> <br> <input id="w" placeholder="width"> <input id="h" placeholder="height"> <br> <button onclick="change()"> Convert! </button> <br> <input id="res" placeholder="result"> <script> function change() { var a = document.getElementById("in").value; document.getElementById("res").value = ""; var arr = JSON.parse("[" + a + "]"); document.getElementById("res").value += "plot "; for (var i = 0; i < arr.length; i++) { document.getElementById("res").value += "((x-(" document.getElementById("res").value += arr[i][1]; document.getElementById("res").value += "))^2+(y-("; document.getElementById("res").value += arr[i][2]; document.getElementById("res").value += "))^2-("; document.getElementById("res").value += arr[i][0]; document.getElementById("res").value += ")^2)"; } document.getElementById("res").value += ">=0"; document.getElementById("res").value += " from x=0 to x="; document.getElementById("res").value += document.getElementById("w").value; document.getElementById("res").value += " and y=0 to y="; document.getElementById("res").value += document.getElementById("h").value/2; document.getElementById("res").value += "> color "; document.getElementById("res").value += document.getElementById("c1").value; document.getElementById("res").value += " background color "; document.getElementById("res").value += document.getElementById("c2").value; } </script> Running script : Not done yet Now make it work with Mathematica... • I wonder if this is valid? – lol Mar 22 '17 at 11:27 • You'd need to list a specific pre-existing interpreter that would plot the output in the form you wanted given that input. That'd make it possible to count the bytes in it. At present, the issue is that because it's not tied to an interpreter, it's not tied to a specific format for representing the equation, and thus the notation is informal and impossible to count objectively. There are plenty of programs for plotting graphs of equations around, so it might be worth trying to find one with a terse input format. – user62131 Mar 23 '17 at 15:20 • @ais523 Ohh. I'll try to make it work with WolframAlpha. – lol Mar 23 '17 at 15:21 # Common Lisp + Quicklisp + ZPNG 260 + 20 = 280 chars This is some of the widest code I've ever written in CL, and if I weren't doing a code golf I would've restructured this to make it much easier to read... Prelude (20 chars) (ql:quickload 'zpng)  Golfed (260 chars) (lambda(w h g b c)(make-instance'zpng:png :image-data(coerce(loop :for j :below h :nconc(loop :for i :below w :append(if(evenp(count t(mapcar(lambda(c)(<(abs(complex(-(cadr c)i)(-(caddr c)j)))(car c)))c)))g b)))'(array(unsigned-byte 8)(*))):width w :height h))  Ungolfed: (Uses defun to allow testing and longer variable names for readability) (defun mk-png (width height color1 color2 circles) (make-instance 'zpng:png :image-data (coerce (loop :for j :below height :nconc (loop :for i :below width :append (if (evenp (count t (mapcar (lambda (circ) (< (abs (complex (- (cadr circ) i) (- (caddr circ) j))) (car circ))) circles))) color1 color2))) '(array (unsigned-byte 8) (*))) :width width :height height))  Example Usage: (let ((png (mk-png 300 200 '(255 200 0) '(128 0 255) '((25 50 80) (40 80 120) (300 -100 6) (17 253 162))))) (zpng:write-png png #p"path/to/file.png"))  ### Explaination (lambda (circ) (< (abs (complex (- (cadr circ) i) (- (caddr circ) j))) (car circ)))  Returns true if the point (i, j) falls within the given circle circ. Euclidean distance is calculated by taking the absolute value of the complex number which represents the vector from (i, j) to the center of circ. (evenp (count t (mapcar ___ circles)))  Map that function across the circles list and check if the given point (i, j) falls within an even number of circles. (if ____ color1 color2)  Select color based on that test. (loop :for j :below height :nconc (loop :for i :below width :append ____))  Collect together a flat list of all the rgb bytes by looping over each (i, j) in the image and appending the resulting lists together. (coerce ____ '(array (unsigned-byte 8) (*)))  Convert that list of bytes into a proper array of bytes, so zpng can ingest it properly. (make-instance 'zpng:png :image-data ____ :width width :height height)  Create the png object. (defun mk-png (width height color1 color2 circles) ___)  Create the function to take the width, height, two colors, and list of circles and return the created png object. # Python 2.x, 166 158 import re;def f(W,H,c,d,C):print'P3',W,H,255,re.sub('[^0-9]',' ',repr([[d,c][sum([abs(x-X+1j*(y-Y))<r for r,x,y in C])%2]for Y in range(H)for X in range(W)]))  The function generates a PPM file on the standard output. # example: W = 300 H = 200 C1 = (255, 200, 0) C2 = (128, 0, 255) Circles = [(25, 50, 80), (40, 80, 120), (300, -100, 6), (17, 253, 162)] f(W, H, C1, C2, Circles)  # JavaScript (ES6), 224 bytes I saw the JS + SVG solution, but I just had to create a canvas-based solution ;-) This is a function which returns a canvas element. If an existing canvas element can be provided, remove 40 bytes. Call like f(width, height, [[r1, g1, b1], [r2, g2, b2]], [[r1, x1, y1], [r2, x2, y2], ...]) let f = (w,h,a,c,O=document.createElementcanvas)=>{O.width=w;O.height=h;C=O.getContext2d;for(y=0;y<h;y++)for(x=0;x<w;x++)C.fillStyle=rgb(${a[c.filter(([R,X,Y])=>(X-x)**2+(Y-y)**2<R**2).length%2]}),C.fillRect(x,y,1,1);return O}

let tests = A.innerHTML.match(/.+/g);
A.innerHTML = "";
for (let i of tests) {
let p = document.createElement("span");
p.innerHTML = "<br>" + i.slice(0, 3);
p.style["font-family"] = "monospace";
A.append(p);
A.append(f(100, 60, [[255,0,0], [0,0,255]],
eval([\${ i.slice(3).replace(/$$/g, "[").replace(/$$/g, "]") }])
));
}
<div id=A>
A.
B. (13, 16, 20)
C. (30, 16, 20)
D. (200, 16, 20)
E. (42, 50, 20)
F. (42, 50, 20), (17, 40, 30)
G. (42, 50, 20), (17, 20, 30)
H. (42, 50, 20), (17, 10, 30), (10, 50, 30)
I. (42, 50, 20), (17, 10, 30), (35, 50, 20)
J. (18, 36, 40), (18, 63, 40), (18, 50, 20)
K. (100, -10, -20), (60, 50, -10)
L. (18, 36, 40), (18, 63, 40), (18, 50, 20), (14, 50, 20), (5, 50, 18), (20, 0, 0), (70, 22, 0), (10000, -9970, 0), (135, 100, -80)
</div>

Example output:

# Löve2D, 353 Bytes.

o=love.graphics
a=arg
w,h,r,g,b,R,G,B=...c={}for i=9,#a,3 do
c[#c+1]={a[i],a[i+1],a[i+2]}end
C=o.newCanvas(w,h)o.setCanvas(C)o.clear(R,G,B)for k,v in pairs(c)do
o.stencil(function()o.circle("fill",v[2],v[3],v[1],9^3)end,"invert",1,true)end
o.setStencilTest("greater",0)o.setColor(r,g,b)o.rectangle("fill",0,0,w,h)local
C:newImageData():encode("png","c")