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

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.

Replies are listed 'Best First'.
Re^6: Placeing Tiles in a Circle
by janDD (Acolyte) on Dec 02, 2013 at 11:45 UTC
    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]
      I think for my problem, constructing the circle from three points should work

      I'd love to see how you will pick the 3 points?

      For your case, it should be trivial to vastly reduce the points set by excluding all those points that do not lie on the outer extremes of the grid. Eg.

              *---*
        |   | 
        +   +
        |   |
        +   +
        |   |
*---+---+   +---+---*
|                   |
*---+---+---+---+---*
    
    
*---+---+---+---*
|               |
+   +---+---+---+
|   |
+   +---+---+---+---*
|                   |
*---+---+---+---+---*

      [download]

      Picking out the *s and eliminating the +s is fairly easy, which reduces the points vastly. But picking just (the right) three of those is much harder.

      However, I am also interested in the second way. I will not be dealing with more than 20.000 tiles,

      My crude, naive implementation of SEC takes ~17 microseconds per 3-point trial. With 20,000 points and an O(n3) algorithm, you'd be looking at 20,000^3 * 0.000017 = 136e6 seconds or around 4.5 years! Its a non-starter.

      Again, it is probably fairly trivial to vastly reduce the point set for consideration, but you'd be better to go looking at one of the implementations of the O(n) algorithms like: miniball and others.

      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]
[d/l]
        Hi BrowserUK,

        I need to thank you again for bringing me on the right path. I implemented the algorithm as follows: First find the convex hull of all tiles. Then, depending of the quadrant, take one of the four points of a given tile as "outermost point" => Should be a small number.

        With these outermost points, I calculate the minimum circle by doing it with brute force i.e., take all pairs and triple of points.

        The algorithm is fast enough for all practical examples, I checked. One example: example

        Again: Thanks alot and best regards
        Jan
[reply]

In Section Seekers of Perl Wisdom