In as few characters of code as you can, create an algorithm which will pack the least number of rectangles necessary to completely fill a rasterized circle with integer radius r and return the parameters necessary to create each rectangle.

I don't like cyan or pink, but here they are.

In the above image, the cyan portion is the "idealized" circle. The darkened cells have been selected by a rasterization algorithm. The area to be filled in is within the black line around the cyan circle.

Here's one way to fill that circle:

Transformers!

Here's another:

Robots in disguise.

The fine print:

  • All units will/must be centimeters.
  • Rectangles should be in the format [x y width height], where x and y is the position of the upper left corner and width and height are positive numbers for the width and height from that point.
    • Example: [10 20 40 20][-10 -20 20 40] ...
  • Rectangles may overlap each other, but their bounds must be within or coincident to the rasterized circle. Rectangles must not extend past those bounds.
  • The algorithm's results must match what would be expected from the bounds given by the Midpoint Circle Algorithm with parameters x = 0, y = 0, r = radius.
  • While there might be a minimum number of rectangles needed to fill the circle, finding them might make your code longer than it's worth with respect to the length of the code. (see scoring system below)
  • It isn't necessary to actually draw anything. Just return the rectangles needed.
  • Coordinate system should be Cartesian, so not display graphics definition. Eg. (+x, +y) quadrant is north-east of (0, 0), (+x, -y) is south-east, (-x, -y) is south-west, and (-x, +y) is north-west.

To test for correctness, use your chosen rasterization method to draw a circle. Draw the rectangles from your rectangle packing algorithm. Check for gaps inside the circle or pixels outside the circle.

Expected signature of function:

(ℕ radius) → {(ℤ x, ℤ y, ℕ width, ℕ height), ...}

The very complex scoring system:

[code characters]*([rectangles for radius of 10]/10
                   + [rectangles for radius of 100]/100
                   + [rectangles for radius of 1000]/1000)

Lowest score wins. In the event of a tie, winner will be the most popular.

Winner will be selected at midnight GMT, January 16th 2014.

  • 2
    10 / 100 / 1000 what?? px, cm, em, raster squares ?? also what kind of coordinate system / scala do you want for the raster? also please specify format of output.. – Vogel612 Jan 8 '14 at 5:57
  • What is the output? The number of rectangles? An image file? Anything? – Kendall Frey Jan 8 '14 at 17:15
  • Amended to answer your questions. – jzx Jan 8 '14 at 17:22
  • 1
    Perhaps you had better specify the rasterization algorithm yourself. :) – Kendall Frey Jan 8 '14 at 17:27
  • Oh, alright. =P – jzx Jan 8 '14 at 17:38
up vote 4 down vote accepted

Mathematica (105)

  • 63 characters
  • 1.665 multiplier (5/10+58/100+585/1000)

Function:

f={-#,#}&/@Last/@{n+1,⌈√(#^2-n^2)⌉}~Table~{n,#-1}~SplitBy~Last&

For r=10 its output is

f[10]

{{{-5, -10}, {5, 10}}, {{-6, -9}, {6, 9}}, 
{{-8, -8}, {8, 8}}, {{-9, -6}, {9, 6}}, {{-10, -5}, {10, 5}}}

It is coordinates of left-bottom and right-top corners of rectangles (it's native for Mathematica's rectangles)

The number of rectangles for r=10,100,1000

Length@f@# & /@ {10, 100, 1000}

{5, 58, 585}

Visualization:

Graphics[{EdgeForm[Black], EdgeForm@Thickness[0.005], Blue, Opacity[0.3], Rectangle@@@f[10],
 Disk[{0, 0}, 10]}, Axes -> True, GridLines -> {#, #} &@Range[-10, 10]]

enter image description here

Update: it seems that the theoretical limit is

enter image description here

Pre-rule-change answer:

C# / ECMAScript 6 - 12

r=>r

Because overlapping rectangles are allowed, we need at most r rectangles.

Proof:

I did not make this a gif. You're welcome.

With a circle of radius 10, it can be filled with 10 rectangles. Each rectangle has been highlighted in a distinct colour.


Older pre-rule-change answer:

C# / ECMAScript 6 - 0.444

r=>1

I believe this meets all the rules as of the time of this writing.

It evaluates to the number of rectangles required to fill a circle, rasterized with this algorithm:

inCircle = max(|x|,|y|) <= radius

This algorithm doesn't yield very high-quality results, but it can still be useful. The popular video game Minecraft uses this algorithm.

  • As of 1 min ago you have to use the Midpoint Circle Algorithm – Cruncher Jan 8 '14 at 17:43
  • So for "r=>r", that's 4*(10/10+100/100+1000/1000), so 12 points. Maybe we should make it more interesting? – jzx Jan 8 '14 at 19:11
  • 1
    @jzx Change the rules if you must, but it appears I'm winning. :) – Kendall Frey Jan 8 '14 at 19:18
  • Heheh, alright. – jzx Jan 8 '14 at 19:34

C#: 514.892 479.298

  • Characters: 254
  • Number of rectangles: 7, 60, and 587. Rectangle multiplier = 1.887

Method takes a single integer as parameter, and returns a List<Int32Rect> as the result. Could probably shave a few more characters off by searching for another rectangle class with a shorter name, but Int32Rect is probably the most correct one to use here.

You didn't specify which coordinate system we should be using. I'm assuming Cartesian coordinates (X & Y increase toward the top & right), as opposed to the more standard in computer graphics, where Y increases toward the bottom.

using System.Collections.Generic;using R=System.Windows.Int32Rect;
class G{List<R>A(int r){var z=new List<R>();int x=r,y=0,e=1-x;while(x>=y)
if(e<0)e+=2*++y+1;else{z.Add(new R(-x,y,2*x,2*y));if(x!=y)z.Add(new R(-y,x,2*y,2*x));
e+=2*(++y- --x+1);}return z;}}

Edit

  • Removed namespace.
  • In the 10 and 1000 circles, the last two rectangles were exactly the same. As x decreases and y increases, sometimes they meet, sometimes they're one off from each other on the last iteration. On the 100 circle, the last iteration is with x=70,y=71, so there's no duplicate. On the 10 circle, the last iteration is x=y=7, so checking for x!=y eliminates that duplicate rectangle. On the 1000 circle, the last iteration is x=y=707.

Results with 10:

enter image description here

Results with 100:

enter image description here

  • I've added a rule for the coordinates, no change needed. – jzx Jan 9 '14 at 13:10
  • Not sure if I'm missing something, but your first output contains 7 rectangles, not 8. – Griffin Jan 9 '14 at 14:57
  • Yeah, the last two rectangles were equal. I wasn't sure if leaving out the if(x!=y) would give a better score than eliminating the duplicate, turns out eliminating the duplicate is a better score. – David Yaw Jan 9 '14 at 16:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.