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

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.

Replies are listed 'Best First'.
Re^8: Placeing Tiles in a Circle
by janDD (Acolyte) on Dec 09, 2013 at 10:48 UTC
    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]
      First find the convex hull of all tiles. Then, ... I calculate the minimum circle by doing it with brute force...The algorithm is fast enough for all practical examples, I checked.

      Indeed. As all your points live on a regular grid and large numbers of them will be 'inside'; and of the outermost, many will be eliminated by being co-linear, the convex hull should always reduce to a manageable number for brute force.

      For quite a while I thought that -- for the specific case of your regular grid -- the convex hull algorithm could be avoided by finding the 3 points 'by inspection'. Indeed, if your tiles were square, it is, but for the generality of rectangular tiles, I couldn't find a reliable way.

      I have to say, it offends me intellectually to know that there are several O(n) algorithms (for the {smallest/minimum/bounding} {enclosing/encircling/} {circle/disk/ball/sphere} problem) out there, and yet I found it impossible to find either a clear description; or a correct and usable implementation :(

      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

        So do you see any conceptual problems porting the java code from the miniball project to perl? I quickly went over it and, to be honest, I haven't understand it. But I guess, with some time, it should be possible to rewrite it (and learn how its done along the path ...)

        Best regards Jan
[reply]

In Section Seekers of Perl Wisdom