help: circle filling question

I tried hard but still can't get this piece of code work.

I was trying to modified a code by Tobias Schwinn regarding circle filling in a predefined poly line. Here is my pseudo code:

define a closed polyline
generate many dots randomly inside it
create circles based on following requests:
1. circle can't intersect with polyline edge
2. circle can't intersect with each other

currently, my problem is there are some circles still can intersect with other, see attached. I really can't find where the problem is.

So I surrender, the glory is yours if you can find. Much thx.

Attachments:

circlePackingPoly_modifiedByCmrhm.ghx, 88 KB
VBNET_circlePackingPoly_modifiedByCmrhm.3dm, 27 KB

▶ Reply to This

Replies to This Discussion

Permalink Reply by Tobias Schwinn on June 21, 2010 at 11:41am

hello cmrhn,

would this definition help?
http://wp.me/p64zU-dy

T

▶ Reply

Permalink Reply by cmrhm on June 21, 2010 at 9:45pm

Hi, Tobias:

I actually modified your code to fit my needs. By checking your code again, I found there are some differences. I think here is your pseudo code:

For 0 to N
find one point
find radius for this point
make a circle
repeat

This is a very clear and clever algorithm. How did you get this?

▶ Reply

Permalink Reply by Tobias Schwinn on June 22, 2010 at 8:07am

ok, let me give it a try a some pseudo code:

do the following until the number of circles equals some number
create a point within the boundary (this might already require some thinking)
check if the point is inside an existing circle
if yes skip the rest and repeat (we are looking for points outside existing circles)
if no then
find the distance to the closest existing circle and make that distance the radius of the new circle (so that they become tangent)
double-check if maybe the polyline boundary is closer if yes make that the radius
bingo
repeat

i hope that doesn't sound to convoluted.

T

▶ Reply

Permalink Reply by cmrhm on June 22, 2010 at 8:51am

I understand your code. Thanks for the confirmation.

I am extremely interested in following parts and appreciated at its simplicity:

' define the radius of the current circle such that it is tangent to its closest neighbor
' Step 1: define a radius for my_pt that is tangent to the boundary
' Step 2: find the closest neighbor and adjust the radius if necessary

My idea is using the uniform size of circles to fill a closed polyline. The post is my first step to do it. If you do, what is your algorithm?

▶ Reply

Permalink Reply by Daniel Piker on June 22, 2010 at 9:42am

I mentioned a simple 'brute force' approach to filling a polyline with equal radius circles a while back:
http://www.grasshopper3d.com/xn/detail/2985220:Comment:50831
I attached a definition.
The circles won't come right up to all the edges - to do that you'd probably need something force based to let them jiggle about into a good arrangement.

Attachments:

CircPack.ghx, 132 KB

▶ Reply

Permalink Reply by cmrhm on June 22, 2010 at 10:03am

Hi, Daniel:

I don't know what is wrong. But when I tried to open the file, there is message window coming up. And
the results isn't what it should be.
Also, it seems you didn't write VB.NET script for this definition, am I correct?

▶ Reply

Permalink Reply by Daniel Piker on June 22, 2010 at 10:48am

Hmm, seems something dodgy happened when I saved it.
I've resaved and uploaded the file again.
The only VB used here is inside the dupPts component.
(You do need Kangaroo for this to work btw.)

Attachments:

CircPack.ghx, 153 KB

▶ Reply

Permalink Reply by cmrhm on June 22, 2010 at 11:18am

I will try to install the kangaroo and see how it works. Thx for sharing!

▶ Reply

Permalink Reply by Tobias Schwinn on June 22, 2010 at 10:32am

sorry, i missed the part that said you wanted uniform circles. ok, how about this:

create a circle at a random location inside the polyline boundary with the defined radius
do the following until the number of circles equals some number
create a new circle at a random location within the boundary
check if that location is inside of any of the existing circles
if yes then skip the rest and repeat
if no then
find the distance to the closest existing circle
create the vector between the center of the closest circle and the center of your new circle
if the length of the vector is more than twice the defined radius R then move the new circle closer to the existing one by the delta between the vector length and 2*R
else if the length is less then 2*R then move the new circle away by the delta between the vector length and 2*R
after you moved the new circle double-check if the distance between the new circle center point and the polyline boundary is less than R
if yes (the circle is overlapping the boundary) then you should probably discard the new circle for simplicity's sake
repeat

what do you think?

BTW, the whole exercise really lends itself perfectly to an object-oriented approach where radius and location are properties of a circle object.

T

▶ Reply

Permalink Reply by cmrhm on June 22, 2010 at 11:17am

Thx. You use Move to arrange the uniformed circle. Let me try on this. I properly will try to do one or two small tests first. My original formal idea is to offset the curve, then put the center of circles on it.