Hi everybody, given all vertices of an n-sided (maybe concave) polygon and the radius of a circle. How can i find the position for the circle to fit best on the polygon? Fit best means a position where most parts of the circle lie on the polygon. The method doesen''t have to be very accurate but it must be fast. eloso

Well, the more i think about it i come to the consideration that the size of the circle doesn''t really matter. For a bigger circle more parts of it will lie outside the polygon but i think the best position keeps the same.

So i have to change my question to how to find the position of the point where the distances to all sides of the polygon are at their maximum. Or more exactly: Find a point inside the polygon where the distance to the nearest side is maximal.

eloso

wow. quite a tricky task indeed.

Well, the exact math solution is fairly complex.

For a quick and dirty solution you can choose the gravity center of the polygon. But it won''t work in some cases: small circle with large concave polygon (like letter ''C'').

I''m not sure that this would be the best way, but I suppose looking at the vertices would be easier. Just try to reduce the sum of the distances from the centre to all the vertices. I would have thought that the sum of the distances would produce better results than the sum of the distances squared, but I could be wrong. Also it''s likely that it will be quicker using the squared, although I can already think of some situations in which an anomalous case would occur using the distance squared.

Looking at it this way is more an exercise in statistics than the way you proposed. Take a look at how the formulae for the best fit line is achieved for a set of points. The best point could be similar.

The quickest way I can see is just use the average of all the x coords and the average of all the y coords. But that is one big approximation. But if you think that elephants can be modelled as smooth hard spheres with inelastic trunks, then that''s the way to go.

Okay... so this is what I''ve come up with so far. Please feel free to comment on

Since I think that a strictly mathematical approach is just too damn hard, I went for a much-less-than-optimal, yet perhaps-good-enough-to-try thing. When doing this, I supposed that the vertices lie on a plane (and, actually, some other things that will become apparent later).

1. Enclose the polygon in a bounding square (if you were drawing this on a sheet of paper, you''d make a square just big enough for the polygon to fit in).

2. Fill the square with points, preferably distributed in some intelligent, non-random way.

3. For each of these points, check if it''s in the polygon. If not, do nothing with that point. If in the polygon, find the nearest "wall". Store the distance to the wall in some way so that you can easily retrieve it later and...

4. ...get the point that scored the highest distance to its nearest wall. This is the Sacred Point, which is the point at which you will place the centre of the circle. Ah....

NOTES
* I have no idea how efficient this is, or how it compares to any other method (that will most likely surface if you search the net). Using a large number of points will improve the chances of finding a good spot. It will also make the search go slower, of course.

* I have no idea of how to find the closest "wall" (line between vertices, branch, whatever) or the answer to any other geomethrical conundrums involved (Tips: Orthogonal distance to walls is not a good thing to go by, I guess).

* There are surely pitfalls.

Thanks guys. I will try some of your solutions (or a mixture of them ;-)

eloso