1

I'm given a 2d binary array. Some of the dots are on, some are off (1 for on, 0 for off).

I know that the "on" dots were created before by putting circles on the 2d array. The circles are of the same radius, and each time a circle was put, the dots inside it changed to 1 instead of 0. All the circles are within the edges of the array and dot touching the edge of the circle is lit.

An illustration can be seen below. The circles are ordered randomly and may touch.

Notice that the dots inside the circles are 1 and all other are 0.

Can you find how many circles were there just by looking at the 2d array without the circles after I had put them? Is this problem solvable?

My attempt at solving this problem was:

First, I assumed that my circles can contain dots as in the figure (radius big enough to contain 4 to 7 dots. Then I tried to categorize what possible orientation can the circles have, however there are just a lot.

enter image description here

I would like to find these two circles. Notice that they can cannot overlap but can be just one near the other.

The Capacitor
  • 41
  • 7
  • by '2d array', do you mean something similar to the square grid graph in : https://en.wikipedia.org/wiki/Lattice_graph ? if so, then lattice, mesh, or grid would be more appropriate terms – Newton fan 01 Jul 23 '18 at 12:11
  • 1
    Yes, I mean a square grid – The Capacitor Jul 23 '18 at 12:14
  • can circles overlap? what is the radius? – Gijs Den Hollander Jul 23 '18 at 12:15
  • Is there any constraint that circles cannot overlap/intersect? Even with this constraint (suppose that each circle contains 9 points) , what does guarantee you that every 9th point is a center of a circle, such that there is a correspondance between the number of dots and the number of circles? what if i draw only one circle, how could you guess that by looking at the number of dots? – Newton fan 01 Jul 23 '18 at 12:17
  • circles cannot overlap. the radius is as I told in the text, 2 times the distance between the dots. About the question of newton - just draw it, it will be simpler. Ill add a picture later. – The Capacitor Jul 23 '18 at 12:55
  • I've added a picture – The Capacitor Jul 23 '18 at 16:54

2 Answers2

2

If your circles don't overlap, you can use connected component labeling algorithm and get number of circles:

NCircles = (NComponents - 1) / 2

(if inner empty regions of circles and outer empty place form separate components)

Edit: with these dots it is worth to select only connected conponents with size in some range to exclude dots and other false regions.

Simple kind of CCL suitable for this picture: 

scan image until black pixel is met   
do flood fill while possible, keep bounding box of scanned black pixels   
if  box corresponds to circle size, count it   
scan further from any unmarked pixel

One more possible approach: you can try Hough algorithm for circles of predefined radius.

For example, OpenCV library contains labeling function that works with images and arrays (and Hough transform too)

MBo
  • 77,366
  • 5
  • 53
  • 86
  • I find it a little bit hard to follow from wiki, can this find what I mentioned in the picture I've attached? – The Capacitor Jul 23 '18 at 16:55
  • Yes, but these dots change solution a bit: you have to count components with size in some range (to exclude dots) – MBo Jul 23 '18 at 18:13
  • I"m sorry, I think I actually didn't explain this well. I will edit the question again now, please see changes. – The Capacitor Jul 24 '18 at 09:41
  • So you have rasterization of small filled circles with non-integer coordinates of centers? If yes, CCL is still valid approach while touched figures might cause problems. Look here: http://stackoverflow.com/questions/11294859/ – MBo Jul 24 '18 at 13:52
0

Why not just generate randomly generate circles and count them?

When you insert a new circle, just check if they do not overlap. And stop inserting new circles after you tried a certain times and failed to insert a new circle. With this last value you probably need to play a bit.

You can probably repeat this a couple of times and average the result like that.

Gijs Den Hollander
  • 620
  • 4
  • 17