I can imagine he solution. I write this as I think, and cannot guarantee a
working solution; only a thorough (?) analysis of the problem.

Preliminary analysis: By a circle we mean not the 2d curve, but the 2d space
_enclosed_ by this curve, but not _including_ the curve. Thus, any point
_inside_ a circle with radius 1 lies _closer_ than 1 units from the centre
of the circle. The point _just outside_, however, will lie exactly one unit
away from the centre.

If you have N circles (not spheres, but the 2d counterpart) in the plane,
with radius 1, you can see this:

We are seeking a point _no farther_ than 1 units away from one well chosen
circle. This, because there are a finite number of circles, and there will
always exist a point that is outside them all.

the vector a_n which points from the centre of circle number n to the point
P (insode) in question, has an absolute value _less_ than 1. The vector b_n,
pointing to the point Q _outside_all of the circles, however, has an
absolute value _equal_ to one.

Examining the perimeter of the union of the circles, we find m candidates to
the point Q, and these lie in the corners where circles meet. There are a
maximum of N+1 such points, but it can be less. (I cannot prove this easily,
but see for yourself; it must be true). Thus we have reduced the amount of
possible solutions from one zillion to N+1, and that's not bad.

It sould not be difficult to locate those points, checking the distance to P
and chose the one(s) closest.

In fact, I think there might be a connection between the closes point and
the vector sum of the vectors b_n and the sum a_n, but I'm not sure.

Hope this was useful/laughable/fun.

Simen.

Rune skrev i meldingen <38a31d99@news.povray.org>...
>I have N number of circles, all with a radius of 1.
>A point P is located *inside* *all* the circles.
>How do I find the point Q that is as close as
>possible to P, but which is located *outside* *all*
>the circles?
>
>Thanks in advance,
>
>Rune
>
>---
>Updated January 24: http://rsj.mobilixnet.dk
>Containing 3D images, stereograms, tutorials,
>The POV Desktop Theme, 350+ raytracing jokes,
>miscellaneous other things, and a lot of fun!
>
>
>

Post a reply to this message