The stupid question is the question not asked PerlMonks

### Placeing Tiles in a Circle

by janDD (Acolyte)
 on Nov 29, 2013 at 15:27 UTC Need Help??
janDD has asked for the wisdom of the Perl Monks concerning the following question:

Hi, I am currently struggeling with the task to place rectangular tiles "nicely" in a circle with radius = 100 ....

Starting point is a hash %hash{\$x}{\$y}=\$color which associates a color to a coordinate.

My current approach is to calculate the distinct number of x and y and determine the tile size for a square 100x100. Then I walk through the coordinates and determine the outermost point with respect to the center of the square. I then calculate the shrinkage factor so that this outermost point fits in the circle. After that, I can resize each tile using this factor and the tiles fit in the circle.

This approach works nicely with regular tile arrays, see for instance this picture: http://www.myimg.de/?img=tile136472.png

If the tile array is irregular, however, the algorithm fails. The problem is that the algorithm always implies that the tile array is a square. This leads to different distances of the tile points to the circle in the following picture: http://www.myimg.de/?img=tile2a1863.png

The algorithm calculates assuming the presence of the blue tiles: http://www.myimg.de/?img=tile316d1d.png"

With these few tiles, one might argue that this still looks ok. If there are really many tiles, no inter-tile distance and the arrangement is asymmetric, it looks strange, see this picture: http://www.myimg.de/?img=tile417dd5.png

I can't really think of an algorithm that somehow puts the tiles in the "middle" of the circle, meaning that in average all outer points of a tile have the same distance to the circle. I want to achieve, that the tiles "look" centered.

I thought of walking through the coordinates row-wise and calculate the outermost points for each row. with some geometry it is easy the get the distance to the circle. i then have an array of distances of the outermost point/tile for each row. the tricky part (where i am stuck) is, how to move/resize the tiles now ... ;(

maybe you guys have an idea

Best regards Jan

Replies are listed 'Best First'.
Re: Placeing Tiles in a Circle
by BrowserUk (Pope) on Nov 29, 2013 at 17:22 UTC

There are only four positions to consider. If you view this image, you see that there are 4 circles drawn over a grid of squares:

1. The green circle, is centered at the green dot, which aligns with a crossover point of the grid.

It contains 4 full tiles.

2. The blue circle, is centered at the blue dot, which is aligned with the grid in the y-axis and misaligned by half a tile in the x-axis.

It encompasses 6 full tiles in a 3 x 2 arrangement.

3. The yellow circle, is centered at the yellow dot, which is aligned with the grid in the x-axis and misaligned by half a tile in the y-axis.

It also encompases 6 full tiles, this time in a 2 x 3 arrangement.

4. And the magenta circle, is centered at the magenta dot, which is the center of a tile.

It encompasses 5 full times.

Whether you need full tetrameric (quadrilateral) symmetry (green or magenta) or will settle for bilateral symmetry (blue or yellow), those really are the only 4 points to consider regardless the proportions of the tiles.

How you choose between them is really just a case of deciding upon your criteria and a little math.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Hi BrowserUK, your analysis is perfectly true and you are describing the algorithm I just implemented. The magenta circle is essentially picture 1 of my post.

But lets consider again this picture: http://www.myimg.de/?img=tile2a1863.png - how would you achieve that the distance of the uppermost green tile has the same distance to the circle as the lower left green tile? I don't think that this can be achieved by placing the center of the circle to any of the four points you mention ...

The tricky think is to move the center of the circle such that the beholder "thinks", the tiles are centered. Please look at my last pic (http://www.myimg.de/?img=tile417dd5.png) where the optical glitch of a nonsymmetric tile array becomes obvious ...

Best regards Jan
I don't think that this can be achieved by placing the center of the circle to any of the four points you mention ...

Let me re-state this. If you want symmetry, then positioning the circle at one of those 4 points will ensure that. No other point will give you symmetry. Full stop.

The problem with this (please learn to use the links), is that you are comparing eggs with oranges. That is to say why are you comparing the 'gap' of the bottom square in column 1 with a 'gap' of the top square in column 2? It doesn't make any sense at all.

If you fill in the rest of the tiles, you'll see that once you compare like with like (ie. caps top and bottom of the same columns), that "problem" goes away.

And you'll also see that once like for like gaps are equalised, the circle is centered at the half-tile offset in both x-axis and y-axis (the magenta circle on my plot). And for a full grid, it will always be one of those 4 positions.

### Only now, having typed that last sentence does the word "irregular" from your OP ring alarms in my head....

#### What you real want is an algorithm to evenly encircle any pattern of tiles on a grid, partial or full. Yes?

(Assuming so, I'll let my brain mull that completely different problem to the one I was solving and get back to you if I come up with anything :)

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Re: Placeing Tiles in a Circle
by BrowserUk (Pope) on Nov 29, 2013 at 15:37 UTC

Are all the tiles in any given circle the same size & shape? Same orientation?

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Yes, all tiles have the same size (width and height) and orientation
Re: Placeing Tiles in a Circle
by GrandFather (Sage) on Nov 30, 2013 at 23:07 UTC

Why? Why are you doing this? BrowserUK has given you the hint you need if we understand what you are asking correctly, but the terms you use ("regular" and "irregular" in particular) and the mention of calculating a "shrinkage factor" suggests that maybe we don't have any idea what the actual constraints on your problem are. If you tell us what you want to do this for it may give enough context that we can give the answer you are looking for.

True laziness is hard work
Re: Placeing Tiles in a Circle
by oiskuu (Hermit) on Nov 30, 2013 at 18:50 UTC
You are looking for a circle drawing algorithm then, one that runs on a rectangular grid?

Update. More precisely, it seems you want a filled ellipse, which, because of the "stretched" grid, appears as a circle. (Ahh. Memories of BASIC resurfacing.)

Create A New User
Node Status?
node history
Node Type: perlquestion [id://1064972]
Approved by Corion
help
Chatterbox?
and the grasshoppers chirp...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (5)
As of 2018-06-19 11:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Should cpanminus be part of the standard Perl release?

Results (113 votes). Check out past polls.

Notices?