Two-Coloring Overlapping Circles

Question

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.

Your output images should follow these guidelines:

• 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.

Answer 1

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:

Answer 2

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

Answer 3

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

Answer 4

MATL, 30 29 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

Answer 5

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.

Answer 6

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

Answer 7

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.

Answer 8

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)

Answer 9

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.createElement`canvas`)=>{O.width=w;O.height=h;C=O.getContext`2d`;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:

Answer 10

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