Algo/code to cover a rectangular area using circles

[iPrank]

Hi !

This is a problem like the puzzle - "find minimum number of coins to completely cover a piece of paper".

The difference is:
in my case RADIUS of the coins is variable (but all coins should have same radius).

Real scenario:
1. I need to draw circular shapes on a rectangular image.
2. Number of circles (N) is CONSTANT/ User input
3. Size of image (S) is CONSTANT/ User input
4. The program should find the MINIMUM RADIUS (R) that is needed to draw N number of circles on an image of size S, so that, the image is completely hidden behind the circles.

Please Note
This is NOT a puzzle/assignment that I'm trying to solve.
This is part of a larger project that I'm working on.

I don't need any drawing code. I just need the code/algo to find the radius.

Any help is appreciated.

Thanks.

Edit: My project is in VB.Net 2008. But if you have code in any other language or just have a pseudo-code, kindly post them too.

[stanav]

Easiest way is to cover the paper with rows/columns of coins.
You'll need to find the width/height ratio of the paper. For example, a letter size (8.5x11) piece of paper has the ratio of 0.77...
Let's x be the number of coins that fit the width of the paper (or # of columns)
Let's y be the number of coins that fit the height of the paper (or # of rows)
Then you have
x*y = N
x = 0.77*y
Solve for x and y and you have the number of columns and rows of coins that fit in the piece of paper.
Take width of the paper (or the height) and divide it by x (or by y) and you have the diameter of the coin. Divide that by 2 to get the radius.

[iPrank]

Sorry, after reading your post, I realized I didn't give enough details of the problem.

The software will be like a HeatMap generator.

1. The full program is a GIS/Map Plotting software. No 3rd party library is used. I'm using my own (modified) Mercator projection to plot the map.
2. The data is in (near) WGS84 format.
3. The map is drawn perfectly.
[You DON'T need to understand #1 and #2 to solve THIS problem.]

4. You get a BITMAP image generated by step #3.
5. User supplies you a list of x,y coordinates and their corresponding Temperature value. (Example- X:150,Y:200,T:40C)
6. Now you draw the heatmap using the above linked code.
7. My problem is, I have too few data-points to completely fill the map. So, currently user selects the (common minimum) radius of data-points by dragging a slider and checks when the map is completely filled by the gradient circles. (see the linked page for the idea of gradient circles)
8. I want step #7 to be automatic.
9. The data-points can occur anywhere in the map.

Think it like this way,

You have 3 circles in locations: (100,200), (500,800), (1000,1200)
Radius of each circle is same.
Now you gradually increasing the radius until the whole image is covered.
I want to determine that radius.

[Shaggy Hiker]

The problem doesn't sound solvable as it stands, but it clearly is, so I am clearly misunderstanding something. If you were to take the three circles in your example, you could easily figure out the distance between each of them. If the radius for all three are the same, then once the radius exceeds half the minimum distance between the points, it is certain that one circle will be overlapping another, however, it is also certain that the third circle is not touching the other two, so the map certainly can't be filled.

Since circles can't fill a rectangle unless the circle extends outside of the rectangle, and since multiple circles can't cover a rectangle unless they overlap, there is a trivial solution, which is the case where the most central circle is expanded to overlap the whole rectangle (and both of the other circles), but that would be kind of silly.

The thing that really has me baffled is that you talk about circles, yet show a link to a heatmap (and describe this like a heat map), which doesn't show circles, but topography. The lines are points of equal value (whether the value is equal height, heat, or anything else). That seems kind of subjective, since you can't really know a topography based on a few scattered reference points.

[iPrank]

Thanks for your reply.

You are correct. I don't understand much about how to solve this.

The linked page uses a gradient circle to draw the heatpoints.

One thing I would like to talk about in this method is the FOR loop. The reason for it's existence is to allow the GDI to produce a radial gradient, because unfortunately there is no easy way to produce a variable radial gradient using the GDI in .NET 2.0. The way my method works is by creating a new polygon object and adding points to it that fall along the circumference of heat point. The circumference is calculated using the radius passed to the DrawHeatPoint method. The rest of the code in the method is used to adjust the ratio of white and black in the gradient brush that we use to fill the polygon generated in the FOR loop.

Since circles can't fill a rectangle unless the circle extends outside of the rectangle, and since multiple circles can't cover a rectangle unless they overlap, there is a trivial solution, which is the case where the most central circle is expanded to overlap the whole rectangle (and both of the other circles), but that would be kind of silly.

Yes. I understand. But I want something similar to this.
(Not only the most central circle, I want all circles to expand)
Actually the reference points are lot more than 3. But they are not enough to fill a map (which can go greater than 3000x3000px)

[dday9]

I'm terrible at math, and I don't quite understand the question. However I think it could be as simple as taking the width of the rectangle and dividing it by twice the amount of circle's something like this:

Dim rect As New Rectangle(0, 0, 15, 15)
        Dim wid As Integer = rect.Width
        Dim numOfCircles As Integer = 4
        Dim radius As Integer = CInt(wid / (4 * 2))
        MessageBox.Show(radius.ToString)

Edit - with the size of the rectangle be user inputed as well as the number of circles

[iPrank]

@dday9: The 'data-points' are NOT in any sequence.
I can have a datapoint at (200,300) another at (200,400), another at (100,400), another at (31,43)...
Do you think your idea still work ?

PS: I'm also terrible at math.

Edit: Currently the datapoints are location of weather stations from across the world. But later they can be changed to anything that has coordinate+value.

[iPrank]

Here is the C# project of the linked page.
If you want, I can change it to VB.Net.

Edit: This generates random 500 data points.
Default radius is 15 - which is good for the regular image.
But maximize the window and you'll nderstand the problem.

[dday9]

Basically my idea works like this: Imagine your datapoint's width as the size of a line, I'm simply dividing that number by double the amount of circles wanted; that gives me the radius(if I just divided by the number of circles it would give me the diameter.). So it would work with any rectangle.

Edit - It would work with any rectangle... So long as you have the size of the rectangle and how many circles you want.

[iPrank]

Imagine your datapoint's width as the size of a line

May be I'm missing something.
The datapoint is a POINT. It does not have ANY width.
The default radius (15) was set by the original programmer for the original small image.

I think first I'll need to I'll check your idea and confirm.

[dday9]

Like I said I could be missing your question entirely. I was under the assumption that you had a rectangle(pointx, pointy, width, hieght), but it sounds like you just have point and not the size, in which case my suggestion wouldn't work.

[jcis]

I don't need any drawing code. I just need the code/algo to find the radius.

iPrank! long time no see

Posting this in the math forum would also be a good idea. jemidiah goes there often and he's very good for these sort of questions.

[boops boops]

If I've understood the question, it shouldn't be too hard to do it iteratively. I assume your original radius of 15 is in pixel units, though it doesn't have to be.

Imagine you start with a solid red rectangle the same size as your actual map. You paint circles on it centred on the weather stations. Are there any red pixels left? If so, expand the radius in steps of, say, 2 pixels until there are no red pixels left.

I don't mean it actually has to be done visually. The solid red rectangle could just be a List(Of Point) representing red pixels on the screen. You could add all the circles to a Drawing2D.GraphicsPath, and then use the GraphicsPath.IsVisible(Point) to check what points are covered. Those that are can be removed from the List, until the list count reaches zero.

Anyway, am I getting warm? Does it sound like the kind of thing you need?

BB

[namrekka]

Hmm.....
I don't get the idea of using circels. For example if you use a 1D map, just a graph, with some data points, you use a curve fitting algo to create a continues curve.
So I quess you need a 2D curve fitting algo.

[iPrank]

iPrank! long time no see

Posting this in the math forum would also be a good idea. jemidiah goes there often and he's very good for these sort of questions.

Hi! It is nice to see old friens like you and Shaggy. Ah! Those good old days! :sigh:
Last few years I got real busy with my day job. After returning home, didn't have time & energy to do VBF.
Recently I've quit my job and started full-time freelanceing/consulting. Hopefully now I'll have time to spam VBF once again.

I HATE math. (Imagine 'HATE' in Arial Black, 100pt, Bold)
But, I think this might be a good idea.

If I've understood the question, it shouldn't be too hard to do it iteratively. I assume your original radius of 15 is in pixel units, though it doesn't have to be.

Imagine you start with a solid red rectangle the same size as your actual map. You paint circles on it centred on the weather stations. Are there any red pixels left? If so, expand the radius in steps of, say, 2 pixels until there are no red pixels left.

I don't mean it actually has to be done visually. The solid red rectangle could just be a List(Of Point) representing red pixels on the screen. You could add all the circles to a Drawing2D.GraphicsPath, and then use the GraphicsPath.IsVisible(Point) to check what points are covered. Those that are can be removed from the List, until the list count reaches zero.

Anyway, am I getting warm? Does it sound like the kind of thing you need?

BB

Excellent. I LIKE your idea.
Instead of checking each pixel/list menber, can you suggest a faster idea to check unique colors in a image / Graphics ?
(NOT using GetPixel and LockBits - they will be very slow for this job.)
Probably some way to get the colormap ?

Hmm.....
I don't get the idea of using circels. For example if you use a 1D map, just a graph, with some data points, you use a curve fitting algo to create a continues curve.
So I quess you need a 2D curve fitting algo.

I don't understand. Please explain.

[jcis]

To tell the truth i don't even think this has a mathematical solution because you don't know the distance between circles and also they don't follow a pattern, they could be anywhere in the rectangle. Shaggy was the only one who used the word "distance" in this thread, if you don't have distances and you don't have a pattern (see this) then it's gonna be very hard to get a solution comming from pure math. So i would go with boops boops idea, some "by pixel" calculations actually run pretty fast, something like converting the image to bytearray(), specify a color as "null pixel" (ensure this pixel color is not present in your color scale) then there should exist something like ByteArrayName.Contains(pixel), while it returns True you keep making circles bigger, or something like that.

[iPrank]

some "by pixel" calculations actually run pretty fast, something like converting the image to bytearray(), specify a color as "null pixel" (ensure this pixel color is not present in your color scale) then there should exist something like ByteArrayName.Contains(pixel), while it returns True you keep making circles bigger, or something like that.

Thanks for the link. Saved for possible future use.

About byte array: I think thats what LockBits does. If I follow Boop's idea, then I'll need to check the color in every iteration. LockBits is faster than GetPixel, but IMHO running it in a loop for a large image will be slow.

[jcis]

It will run once right? there are different ways to optimize this process, appart from the pixel proccesing stuff itself you could optimize how many of these comparations are needed, for example using a Binary search algorithm, each time you search using this algo you can exclude from the search half the possible values (solutions). For example you have your min and max size for circles, your first guess goes in the middle, if the rectangle is covered then you know the answer is between small and middle size, if not it's between middle size and max size, and so on, then at most log2 N checks are required to determine the number.

Just one detail: There is a little difference in the common implementation of a Binary search like the one explained in the link above and the one you need here: You won't be looking for the exact match, because you're not searching a value you already have, I mean you need the minimum radio but you may find it in the first search and you wouldn't still know if it's the value you want or not, then you're forced to run this algorith until you reach the unit and that's the value you want, still this will be much faster than simply incresing circle radius one by one for each pixel check.

[iPrank]

Thanks everyone for your suggestions.
I think I'll use Boop's idea and AForge library for calculating colors.

I'm not marking this thread 'resolved' yet. I'll try the code tomorrow and let you know how it goes.

[boops boops]

Forget my idea of using GraphicsPath.IsVisible to check whether the pixels are covered, and deleting them from a list. It turns out to be far too slow for practical use.

I'm now convinced that literally painting circles (say white) on a bitmap of uniform colour and checking if there are any pixels left will be the simplest and most efficient way to do it.

Suppose your map is 1000 x 1000 pixels. Using my FastPix LockBits wrapper (see my signature) each iteration could be something like this:

Private Function CirclesNotBigEnough_TryAgain(radius As Integer) As Boolean
    Dim bmp As New Bitmap(1000, 1000)
    'each pixel has the color Color.Empty, which is ARGB [0,0,0,0] = integer 0 
    Using g As Graphics = Graphics.FromImage(bmp)
      For each p As Point in WeatherSations
         g.FillEllipse(Brushes.White, p.X - radius, p.Y - radius, 2*radius, 2*radius)
      Next
   End Using
   Using fp As New FastPix(bmp)
      Dim pixels() As Integer = fp.PixelArray
      For Each pix As Integer in pixels
         If pix = 0 Then Return True 'pixel found with Color.Empty
      Next
   End Using
   Return False
End Function

I haven't tried this yet but I would expect an iteration time of the order of 100 ms. per iteration. You could use a binary search approach to increasing/decreasing the radius until you get the minimum radius needed.

BB

[iPrank]

I was thinking about drawing a 2-bit monochrome bitmap.
The bmp will have white background.
I'll draw black circle on that.
Then I'll use AForge libraty to determine non-black pixel count. (very fast)

Thanks for the 'FastPix' wrapper. I'll use both of them and see which one works best.

[boops boops]

I just tested the function I posted above with a bitmap of 1000*1000 pixels, a radius of 50 and 16 data points. Time: 20 milliseconds. Varying the radius and number of points gave results in the region of 15 - 40 milliseconds. This is on a humdrum supermaket twincore. Better than I expected!

In principle there's no need to make the background white since a New Bitmap (by size) has uniform ARGB = 0. There's no need to count the unchanged pixels since finding one of them is enough to decide if the circles are big enough. Still, I wouldn't be surprised AForge has a few tricks up its sleeve.

It might be faster to use a Pinned Array instead of LockBits (or my FastPix wrapper version). Then it wouldn't be necessary to declare a new LockBits/FastPix on each iteration, since you could address the bytes of the bitmap directly. More about that another time, or if asked nicely.

BB

[namrekka]

A better explaination what I mean, hmm... my english, is:

http://en.wikipedia.org/wiki/Surface_fitting

and:

http://www.vbforums.com/showthread.php?t=599801