# Populate area with circles based on image no overlap

**URL:** <https://discourse.processing.org/t/populate-area-with-circles-based-on-image-no-overlap/14766>\
**Category:** Coding Questions\
**Created:** [October 17, 2019, 4:30pm UTC](https://discourse.processing.org/t/populate-area-with-circles-based-on-image-no-overlap/14766 "2019-10-17T16:30:49Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![TimoL](https://avatars.discourse-cdn.com/v4/letter/t/9fc29f/32.png) [@TimoL](https://discourse.processing.org/u/TimoL)\
**Post date:** [October 17, 2019, 4:30pm UTC](https://discourse.processing.org/t/populate-area-with-circles-based-on-image-no-overlap/14766/1 "2019-10-17T16:30:49Z")

</div>

I’m sure I saw someone with the same question on here not too long ago, but I can’t find it for the life of me.

I guess what Im trying to achieve is circle packing but with a more efficient way of filling the space rather than randomly waiting for a free space to be “picked” like in Daniel Shiffman’s coding challenge.

I’d also want to keep the circles all the same size.

thanks for any help

---

<div class="post-metadata">

**Author:** ![Chrisir](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/chrisir/32/45_2.png) [@Chrisir](https://discourse.processing.org/u/Chrisir)\
**Post date:** [October 17, 2019, 5:32pm UTC](https://discourse.processing.org/t/populate-area-with-circles-based-on-image-no-overlap/14766/2 "2019-10-17T17:32:57Z")

</div>

> [@Square with resizeable rectangles inside](https://discourse.processing.org/t/square-with-resizeable-rectangles-inside/14482):
>
> Hi Guys, i’m pretty new with processing and have a problem: I need a square with different squares in it. These should be changeable in size, but not smaller than a certain minimum size. I have tried different approaches, but always fail because of the minimum size. Do you have any idea how I can solve this problem? Unfortunately I lack the experience to abstract the problem in Java. If u will i can share my current state, but i think my code is to static to use a lot of it. Sorry about my …

> [@Random Circles in circles](https://discourse.processing.org/t/random-circles-in-circles/14360/3):
>
> A link to an example of this helpful. I apologize for not being specific, but I plan to tailor the base method of creating a circle at a random location in a circle without touching the edges of the larger circle to fit my needs. more information in case u are wondering: The larger circle is at a fixed position. the size of the smaller circles doesn’t matter as long as it is in the bigger circle the smaller circle can be as far as possible from the center of the circle assuming it does not …

---

<div class="post-metadata">

**Author:** ![solub](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/solub/32/333_2.png) [@solub](https://discourse.processing.org/u/solub)\
**Post date:** [October 17, 2019, 6:22pm UTC](https://discourse.processing.org/t/populate-area-with-circles-based-on-image-no-overlap/14766/3 "2019-10-17T18:22:36Z")

</div>

Hi @TimoL,

If I understand correctly, you would like to have:

- circles of **same size**
- **packed** (no overlapping)
- within a **specific area**
- almost **instantly**

One solution would be to display circles at each corner of a grid spreading all over the canvas. The unit size of that grid would be the desired diameter of your circles. You could then create/load a specific shape with the [Geomerative](http://www.ricardmarxer.com/geomerative/) library and only draw the circles whose location is in that shape.

Annotated example sketch (Python mode)

```auto
add_library('geomerative')

W, H = 1000, 600 #Dimensions of canvas
D = 8 #Desired diameter (circle)
w, h = W/D, H/D #Scaled dimensions

def setup():
    size(W, H, P2D)
    background(255)
    smooth(8)
    
    RG.init(this) #Intitialize the library
     
    rpoly = RPolygon() #Create an empty polygon
    
    #Adding vertices (heart formula)
    for i in xrange(360):
        x = 16 * pow(sin(radians(i)), 3) 
        y = 13 * cos(radians(i)) - 5 * cos(2 * radians(i)) - 2 * cos(3 * radians(i)) - cos(4 * radians(i))
        rpoly.addPoint(RPoint(width/2 + x*10, height/2 - y*10))
   
    #Create a RShape object from polygon
    heart = RShape(rpoly.toShape())
    
    #Display circles all over the canvas
    for i in xrange(w * h):
        x = (i%w) * D
        y = (i/w) * D
        
        #Only draws those within the heart shape
        if heart.contains(RPoint(x, y)):
            ellipse(x, y, D, D)

```

 ![SS202](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/f/f485e20f02cfc0dbf968a0332060ccc03d500796.png)

---

<div class="post-metadata">

**Author:** ![TimoL](https://avatars.discourse-cdn.com/v4/letter/t/9fc29f/32.png) [@TimoL](https://discourse.processing.org/u/TimoL)\
**Post date:** [October 17, 2019, 7:55pm UTC](https://discourse.processing.org/t/populate-area-with-circles-based-on-image-no-overlap/14766/4 "2019-10-17T19:55:08Z")

</div>

Thanks @solub  
Yea those are the requirements.  
The grid idea will work I suppose but I’m not sure if that’s optional packing.  
Also I think I’d prefer a more irregular arrangement.

I wonder if I add a bit of random to the grid arrangement perhaps?

---

<div class="post-metadata">

**Author:** ![solub](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/solub/32/333_2.png) [@solub](https://discourse.processing.org/u/solub)\
**Post date:** [October 17, 2019, 8:54pm UTC](https://discourse.processing.org/t/populate-area-with-circles-based-on-image-no-overlap/14766/5 "2019-10-17T20:54:00Z")

</div>

According to [Wikipedia](https://en.wikipedia.org/wiki/Circle_packing):

> the highest-density lattice arrangement of circles is the [hexagonal](https://en.wikipedia.org/wiki/Hexagon) packing arrangement,[[2]](https://en.wikipedia.org/wiki/Circle_packing#cite_note-ChangWang-2) in which the centres of the circles are arranged in a [hexagonal lattice](https://en.wikipedia.org/wiki/Hexagonal_lattice) (staggered rows, like a [honeycomb](https://en.wikipedia.org/wiki/Honeycomb)), and each circle is surrounded by 6 other circles.

So you could use the same sketch and just add an offset:

```auto
add_library('geomerative')

W, H = 1000, 600 #Dimensions of canvas
D = 8 #Desired diameter (circle)
w, h = W/D, H/D #Scaled dimensions

def setup():
    size(W, H, P2D)
    background(255)
    smooth(8)
    
    RG.init(this) #Intitialize the library
     
    rpoly = RPolygon() #Create an empty polygon
    
    #Adding vertices (heart formula)
    for i in xrange(360):
        x = 16 * pow(sin(radians(i)), 3) 
        y = 13 * cos(radians(i)) - 5 * cos(2 * radians(i)) - 2 * cos(3 * radians(i)) - cos(4 * radians(i))
        rpoly.addPoint(RPoint(width/2 + x*10, height/2 - y*10))
   
    #Create a RShape object from polygon
    heart = RShape(rpoly.toShape())
    
    #Display circles all over the canvas
    for i in xrange(w * h):
        x = (i%w) * D
        y = (i/w) * D
        
        if (i/w)%2 == 0:
            offset = D/2
        else:
            offset = 0
        
        #Only draws those within the heart shape
        if heart.contains(RPoint(x + offset, y)):
            ellipse(x + offset, y, D, D)

```

 ![ss205](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/a/a49473db2f85f27ccab66b1ee6bf699b3be5bd41.png)

If you prefer an irregular look, [Poisson-Disk Sampling](https://www.youtube.com/watch?v=flQgnCUxHlw) could also be an option, but the packing won’t be optimal.

EDIT: Java version without dependencies

```auto
int W = 1000, H = 600; //Dimensions of canvas
int D = 8; //Desired diameter (circle)
int w = W/D, h = H/D; //Scaled dimensions

PShape heart;
float offset;

void setup(){
  size(1000, 600, P2D);
  background(255);
  
  //Create heart shape (heart formula)
  heart = createShape();
  heart.beginShape();
  for (int i = 0; i < 360; i++){
    float x = 16 * pow(sin(radians(i)), 3);
    float y = 13 * cos(radians(i)) - 5 * cos(2 * radians(i)) - 2 * cos(3 * radians(i)) - cos(4 * radians(i));
    heart.vertex(width/2 + x*10, height/2 - y*10);
  }
  heart.endShape();
  
  //Grid coordinates
  for (int i = 0; i < w*h; i++){
    float x = (i%w);
    float y = (i/w);
    
    //Offset
    offset = (y%2 == 0) ? D/2 : 0;
    
    //Only draw circles within the heart shape
    if (contains(heart, x*D + offset, y*D)){
      ellipse(x*D + offset, y*D, D, D);
    }
    
  }
  
  noLoop();
  
  
}

  

//Function to determine whether a point is inside a shape/polygon or not
boolean contains(PShape shp, float x, float y){
    int N = shp.getVertexCount();
    boolean c = false;
    for (int i = 0; i < N-1; i++){
        PVector v1 = shp.getVertex(i+1);
        PVector v2 = shp.getVertex(i);
        if ((v2.y > y) != (v1.y > y)){
            if (x < (v1.x - v2.x) * (y - v2.y) / (v1.y - v2.y) + v2.x){
                c = !c;
             }
         }
    }
    return c;
}

```

---

<div class="post-metadata">

**Author:** ![TimoL](https://avatars.discourse-cdn.com/v4/letter/t/9fc29f/32.png) [@TimoL](https://discourse.processing.org/u/TimoL)\
**Post date:** [October 17, 2019, 9:21pm UTC](https://discourse.processing.org/t/populate-area-with-circles-based-on-image-no-overlap/14766/6 "2019-10-17T21:21:38Z")

</div>

This is exactly what I was looking for 🙂  
Thanks so much!