Circle Packing. Trying to implement on my project

#1

Hi,
Came here from below youtube discussion,
I am working on my final thesis and I watched your video related to circle packing (https://www.youtube.com/watch?v=pF0cadg2mg0). I have some question on my mind.

Github link of this discussion where you can find more info. and picturesi,

I need some help or some idea. This circle packing part is 2nd phase of my project.

Brief description:
I have approximately 300 images about sheepskin and my aim is to pack specific size circle as much as possible in efficient way. After implementing edge detection (right image) I want to nest circles to this image which includes white boundaries of sheepskin, black inside of boundaries and black background.
I want to do circle packing just inside of these white boundaries in an optimum way. Basically, I have many irregular shapes. Example of 2017 you did inside 0, 1, 2 , 7 seems to me very similar to my problem; so, I asked you about this.

Is that possible for you to do one example of image which is not rectangular but irregular shape?

Thank for your help. :slight_smile:

0 Likes

Running a circle pattern inside a given shape
#2

just a random response and maybe not what you are looking for but it’s a fair approximation imo. you would have to do some preprocessing to your input (as i use the alpha to judge the area) but nothing that couldn’t be automated. anyways have a look and see what you think.

https://www.openprocessing.org/sketch/669632

0 Likes

#3

What is Alpha? What is fair approximation ? Do you think that I should calculate area first ?
Can you be more specific ?
I basically want to pack circles into irregular shapes …

0 Likes

#4

basically i just check if the possible position for a circle is empty or in other words if the alpha of the pixel is more than zero i know that it is a position within or at least on the edge of the shape. if you look at the link and just add “image(img,0,0)” in draw you can see the image is just an irregular shape with a transparent background.

have you seen this link there is a good explanation of a good circle packing algorithm (as what i have shown is a really bad approximation and doesn’t distribute the circles well at all) just a bit down the page. i just wanted to give an idea of how it might be done.

0 Likes

#5

besides a math way to define/add new elements
a other way
is to generate random elements and add them ONLY after they
passed a collision test with all other existing elements.

it turned out to be tricky as we needed to break loops on timeout.

we play something like this with rectangles here.

the restriction by the outer shape must be added,
also change rect with circle collision.

0 Likes

#6

I did a search and I got some hits from previous posts

https://www.youtube.com/watch?v=QHEQuoIKgNE

https://forum.processing.org/two/discussion/23637/circle-packing-problem

https://gist.github.com/brysonian/235705

https://forum.processing.org/two/discussion/comment/90483/#Comment_90483

The task is divided in few parts:

  1. Can you detect the irregular edges? (Sorry, I did not inspect your project you provided)
  2. Can you placed circles in a regular shape, as demonstrated by Shiffman?
  3. Focus less in code and more in concept: What strategy would you use to do the packing? In other words, what strategy would you use to avoid circle overlapping?

A couple of notes.

  1. You need to implement your own code. You can use any other code as a reference. Implementing your own code will give you more confidence to improve it and adapt it to your project.

  2. If you are stuck in the implementation at any stage, provide your code. Your code shows your approach and it help find bugs easily. A code snippet is a thousand words…

  3. Github is not a place to discuss use cases or coding problems. Github is to document bugs with Processing or submit feature request. *****EDIT: I noticed you posted in CodingTrain’s Github. I initially thought you posted in the Processing’s Github. Nevertheless, I doubt Shiffman is able to keep up with all the issues there. This forum is a better place for your inquiry.

Kf

0 Likes

#7

I do not have idea that how can I constraint with outer shape. Basically, How can I make this rectrangle or circles inside of a shape ? Do you have any idea about that.

BTW, I tried your code with different and same color. It looked and worked very well.
The one with different shapes did not change when I clicked mouse while the other one with green colors rect. changed.

Thank you a lot.

0 Likes

#8

possibly, after you give us your shape!
check Running a circle pattern inside a given shape

0 Likes

#9

I was looking for SVG file but I did not get the idea behind. After doing this, my image will convert to the just a shape _?

For example what will happen if I convert that image to svg? I tried but result is the same
RLeather1After

Could you do that for me ? or Can you give advices how to do it ?

Thanks, Sorry if I bother you :frowning:

0 Likes

#10

Can you give an example? Is the white-line-on-black image at the bottom of this thread what all the images in your image set look like?

If so, you might want to flood-fill the outside of the image to create your mask.

0 Likes

#11

All images looks like these twos below. The image that I mentioned on post was edge detection of one of them. But, I did not get what you told :slight_smile:

Could you explain again :slight_smile: ?

image

0 Likes

#12

Well, your images already have a dark background.

A basic naive method is to spawn circles on white (shape), and grow until they touch another circle or dark (mask). So, you could threshold your image into a mask – for example, by looping over pixels and setting each to 1 (255) or 0 based on a threshold. You will probably need to do some cleanup such as eroding or annealing to remove mess on the edges and get a clean mask region.

Another alternative is to create a complex polygon, then spawn circles inside the polygon and grow until they cross outside. Your shape is concave, which is a pain. For a polygon approach, one method is to begin by finding points along the edges. Here is a really simple way of doing that – it works on your example skin, but might not work on ones that have highly concave regions.

PImage img = loadImage("proc-sheepskin.jpeg");
size(557, 462);
image(img, 0, 0);
ArrayList<PVector> points = new ArrayList<PVector>();
int grain = 10;
int thresh = 64;

for (int x=0; x<width; x=x+grain) {
  for (int y=0; y<height; y++) {
    if (brightness(get(x, y))>thresh) {
      points.add(new PVector(x, y));
      break;
    }
  }
  for (int y=height; y>0; y--) {
    if (brightness(get(x, y))>thresh) {
      points.add(new PVector(x, y));
      break;
    }
  }
}

for (int y=0; y<height; y=y+grain) {
  for (int x=0; x<width; x++) {
    if (brightness(get(x, y))>thresh) {
      points.add(new PVector(x, y));
      break;
    }
  }
  for (int x=width; x>0; x--) {
    if (brightness(get(x, y))>thresh) {
      points.add(new PVector(x, y));
      break;
    }
  }
}

for (int i=0; i<points.size(); i++) {
  PVector pt = points.get(i);
  ellipse(pt.x, pt.y, grain, grain);
}

sheepCirclePack

Once you have a set of edge points you can try to find the polygon that they define in various ways. For example: try to walk the edge from an arbitrary starting point in an arbitrary direction, finding the next closest point. Or you could try radial sorting from the center of the bounding box. Or you could use the mesh library to get a Delaunay triangulation, then prune long exterior edges from the convex hull to get a concave hull – from there, the concave hull is a polygon.

Note that concave hulls are hard. There are lots of approaches:

https://community.esri.com/blogs/dan_patterson/2018/03/11/concave-hulls-the-elusive-container

If you have a lot of complicated shapes then at some point you may need to test regions between points to see if they are white or not to guess whether those regions should be connected. There is no perfect geometric solution – just mesh up your points and then test. This might be one reason to consider a raw threshold and flood fill approach rather than a polygon – if you have to check all points anyway, you could just use a magic wand tool approach at the pixel level.

Just as an example of the polygon approach, here is a very crude example that takes the Dalaunay diagram and then simply ignores lines that are less than a threshold distance. It almost sort of works at giving you a list of points / lines for your polygon.

import megamu.mesh.Delaunay;

int sz = points.size();
float[][] pointsArray = new float[sz][];
for (int i=0; i<sz; i++) {
  PVector pt = points.get(i);
  pointsArray[i] = new float[]{pt.x, pt.y};
}

Delaunay myDelaunay = new Delaunay( pointsArray );

float[][] myEdges = myDelaunay.getEdges();

for (int i=0; i<myEdges.length; i++) {
  float startX = myEdges[i][0];
  float startY = myEdges[i][1];
  float endX = myEdges[i][2];
  float endY = myEdges[i][3];
  if (dist(startX, startY, endX, endY)<3*grain) {
    stroke(255, 0, 0);
  } else {
    stroke(32);
  }
  line( startX, startY, endX, endY );
}

sheepCirclePack

Once you actually have an irregular polygon, I recommend checking out this discussion and paper:

1 Like

#13

Thank you very much,

I will try to understand concepts that you mentioned about and I will read what you sent to me in advance. Then, I would like to keep in touch with you. I am very glad about your helping.

I have a code about circle packing which I will try to implement with those.
In my code, firstly one circle is packed then other is being packed around it.(I shared the circle packing code which I found on online)

I want to tell you some issues which I encountered with during the implementation my code to the image I mentioned on last senteces;

I was trying to improve my approach. I also tried to pack circles inside of white area and when black area comes I want to avoid packing then keep packing to the white ones.

I could pack inside of white area but due to each white pixels, which are near to the black area, circles are exceeding to the black area as well.
If the first circle packs corner white pixel others are packed around it then they exceed (e.g. half of them on black area and half of them on white area OR exceeding area depends on which white pixels circles pack.)

I could not manage how to avoid exceeding circles.
I want to make circles not to pack when they see the black pixels.

I would like to keep in touch with you :slight_smile: Could you help me if I am stuck.
Thank you again.

Shape that mentioned is below. I can use either this or the one that you also used.
(Image after edge detection and was filled inside of it with white color)
Image after edge detection and was filled inside of it with white color

Code of circle packing:( works in processing )

int circle_count = 100;
Circle[] circles;
int min_radius = 0;
int max_radius = 2;
int[] possibleRadiuses = new int[] { 10 };
int w = 800;
int h = 600;
int cx;
int cy;

void setup () {
  size(600, 600);
  background(255);
  smooth();
  cx = w/2;
  cy = h/2;
  
  int i;
  
  int[] c = new int[circle_count];
  
  circles = new Circle[circle_count];
  for (i=0; i<circle_count; i++)
  {
    c[i] = possibleRadiuses[int(random(0, 1))];
  }
  c = sort(c);
  for (i=0; i<circle_count; i++)
  {
    circles[i] = new Circle(c[circle_count-1-i]);
  }
  circles[0].x = cx;
  circles[0].y = cy;
  circles[0].computed = true;
  
  for (i=1; i<circle_count; i++)
  {
    circles[i].computePosition(circles);
  }
}

void draw () {
  /**/
  background(0);
  
  int i;
  
  for (i=0; i<circle_count; i++)
  {
    circles[i].display();
  }
  /**/
}

class Circle {
  int x, y;
  int radius;
  boolean computed = false;
  
  Circle (int r) {
    radius = r;
  }
  
  void computePosition (Circle[] c) {
    int i, j;
    boolean collision;
    Point[] openPoints = new Point[0];
    int ang;
    Point pnt;
    
    if (computed) { return; }
    
    //Loops below, looking circles if they collide to each other or not 
    for (i=0; i<c.length; i++)
    {
      if (c[i].computed)
      {
        ang = 0;
        for (ang=0; ang<360; ang+=1)
        {
          collision = false;
          pnt = new Point();
          pnt.x = c[i].x + int(cos(ang*PI/180) * (radius+c[i].radius+1));
          pnt.y = c[i].y + int(sin(ang*PI/180) * (radius+c[i].radius+1));
          
          for (j=0; j<c.length; j++)
          {
            if (c[j].computed && !collision)
            {
              //Check wheter two circles intersect or not
              if (dist(pnt.x, pnt.y, c[j].x, c[j].y) < radius + c[j].radius)
              {
                collision = true;
              }
            }
          }
          
          if (!collision)
          {
            openPoints =  (Point[]) expand(openPoints, openPoints.length+1);
            openPoints[openPoints.length-1] = pnt;
          }
        }
      }
    }
    
    float min_dist = -1;
    int best_point = 0;
    for (i=0; i<openPoints.length; i++)
    {
      if (min_dist == -1 || dist(cx, cy, openPoints[i].x, openPoints[i].y) < min_dist)
      {
        best_point = i;
        min_dist = dist(cx, cy, openPoints[i].x, openPoints[i].y);
      }
    }
    if (openPoints.length == 0)
    {
      println("no points?");
    } else
    {
      println(openPoints.length + " points");
      x = openPoints[best_point].x;
      y = openPoints[best_point].y;
    }
    
    computed = true;
  }
  
  void display () {
    int i;
    for (i=0; i<circles.length; i++)
    {
      ellipseMode(CENTER);
      ellipse(circles[i].x, circles[i].y, circles[i].radius*2, circles[i].radius*2);
    }
  }
}

class Point {
  int x, y;
  
  Point () {
    
  }
}
0 Likes

#14

One test for when to stop growing is circle-line collision. So if you have a pool of random start points (your white region) then you can start growing circles and check for collision against the list of red lines (the “fence”) to prevent growing out-of-bounds

0 Likes

#15

Hi again,

I am trying to do it but could not manage.
I will try again then keep in touch with you if I get stuck.
If it is possible ?

Thank you again . :slight_smile:

0 Likes

#16

Good luck. If you are stuck on your sketch, post a simple version and explain what part you are stuck on.

0 Likes