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(n³) 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.

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

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.