in reply to Re^2: Placeing Tiles in a Circle
in thread Placeing Tiles in a Circle

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.

Replies are listed 'Best First'.
Re^4: Placeing Tiles in a Circle
by janDD (Acolyte) on Dec 02, 2013 at 07:49 UTC
    Dear BrowserUK,

    I am sorry if I expressed myself a bit clumsyly. Your last statement is exactly what I want:

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

    Best regards Jan

    P.S.: I know about the links but I had a strange error "permission denied" and I found a post in here that sourced this to the usage of links ... So I removed them ;)
[reply]
      Your last statement is exactly what I want:

      In that case, what you need to do is construct a circle from 3 points.

      But that just moves the problem to deciding which three points. I tried several heuristics to pick 3 suitable points, but despite that this is trivial by eye, I failed to find any one that would deal with all cases.

      So then you are left with finding the smallest enclosing circle.

      I've implemented the naive O(n3) algorithm, and if you feed it all the points for every populated tile, it works. Its not fast.

      There are O(n) algorithms out there, but finding either an algorithmic description that is intelligible; or an implementation that actually works when ported to Perl defeated me.

      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.
[reply]
        Hi BrowserUK,

        actually I think for my problem, constructing the circle from three points should work ... Thanks for this hint!

        However, I am also interested in the second way. I will not be dealing with more than 20.000 tiles, so I guess, speed is not a show stopper for the O(n^3) algorithm. Could you quickly describe or show how you implemented it?

        Best regards Jan
[reply]

In Section Seekers of Perl Wisdom