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

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

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.

---

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.