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:


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


#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 …


#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.


#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.


#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


#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.


#8

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


#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: