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

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

Simen Kvaal wrote:
>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.

Yes.

>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.

Yes, where sphere N is one specific circle, not any circle.

>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).

I don't think so. If there's holes in the area covered by the spheres there
will be more points, I think.

Besides, How do I find out which intersection points are on the perimeter of
the union? I guess testing all the points are the only way?

One more question: How do I find these points where the circles intersect?

Thanks for your help!

Greetings,

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

Rune wrote:

> I don't think so. If there's holes in the area covered by the spheres there
> will be more points, I think.

But you said the point is inside *all* of the circles. I am only hypothesizing
here, but I believe if such a point does exist there can be no holes.

--
___     ______________________________________________________
 | \     |_                 <dav### [at] faricynet> <ICQ 55354965>
 |_/avid |ontaine               http://www.faricy.net/~davidf/

"Sitting on a cornflake, waiting for the van to come" -Beatles

Post a reply to this message

Just assume that Q lies on a circle of radius 2 centered at P.

Rune wrote:

> 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

>But you said the point is inside *all* of the circles. I am only
hypothesizing
>here, but I believe if such a point does exist there can be no holes.
>


That was my point too. If such a hole exist, then at least two circles
doesn't overlap, thus no common point for _all_ the circles exist.

5k.

Post a reply to this message

"Simen Kvaal" <sim### [at] studentmatnatuiono> writes:
> 
> 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. 

No. Without loss of generality we assume that all circles are pairwise
different. (If two circles are identical, we remove one of them.)
Since there exists a point that lies inside all circles, two of them
intersect in two points. There are N circles and therefore N*(N-1)/2
unordered pairs of circles. This may lead to up to N*(N-1) intersections.

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

The closest intersection point may not be the correct solution. It may
lie inside another (third) circle.

A simple but time consuming algorithm may work like this:

1. For every pair of circles find the two intersection points and collect
   them in a list L.
2. For every circle C
3.     For every intersection point P in L
4.        If P is inside C 
5.           Remove P from the list L
6. Find the closest point in L

Thomas

-- 
http://thomas.willhalm.de/ (includes pgp key)

Post a reply to this message

>No. Without loss of generality we assume that all circles are pairwise
>different. (If two circles are identical, we remove one of them.)
>Since there exists a point that lies inside all circles, two of them
>intersect in two points. There are N circles and therefore N*(N-1)/2
>unordered pairs of circles. This may lead to up to N*(N-1) intersections.
>

But most of these intersections are not interesting, because they are
obscured by other circles. On the _perimeter_ of the big buch of circles,
there are a maximum og N+1 points to check.


Try to draw circles on a paper so that all of them overlap at some point,
and see what happens. How many points around the edge of the figure do you
need to count?

>> It sould not be difficult to locate those points, checking the distance
to P
>> and chose the one(s) closest.
>
>The closest intersection point may not be the correct solution. It may
>lie inside another (third) circle.
>

No, because all the intersection points in question are outside all the
circles. (See above.)

Post a reply to this message

Simen Kvaal wrote:
>>But you said the point is inside *all*
>>of the circles. I am only hypothesizing
>>here, but I believe if such a point does
>>exist there can be no holes.
>
>That was my point too. If such a hole
>exist, then at least two circles doesn't
>overlap, thus no common point for _all_
>the circles exist.

Oops... you're right.
I mixed some thoughts together...

Greetings,

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

Simen Kvaal wrote:
>But most of these intersections are not
>interesting, because they are obscured
>by other circles. On the _perimeter_ of
>the big buch of circles, there are a
>maximum og N+1 points to check.

Why N+1? Why not just N?

If N=5, there would be 5 circles and
thus 5 of these points.

Please explain :-)

Greetings,

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

Here we go, I did a little testcase.

I don't know if it is as bad as can be, but it gives some hints on error
cases for algorithms.

The point Q is close to P. (P is not depicted, but just choose one). It
is closer as 2 and even closer as 1/2 (that was a bug in my mind :-))

Not all intersections are outside of circles. And I got N+1 outer
intersections. I don't know if I can have more.

So much for the test case.

Oh and take care in your algos, that you don't know the order of the
circles.

Axel

Post a reply to this message

Attachments:
Download 'circle1.png' (3 KB)

Preview of image 'circle1.png'

>
>Why N+1? Why not just N?
>
>If N=5, there would be 5 circles and
>thus 5 of these points.
>


Thinking about it, I realize that it is N number of points; you're
absolutely right! For some reason I counted wrong... :O.

Simen.

Post a reply to this message

Serge LAROCQUE wrote:
>Ok, so now, calculate all the points of intersection,
>store in a list somehow. Check them for being
>interior points with the inequality
>(x-xi)^2+ (y-yi)^2 < 1 for each circle, where (xi,yi)
>is the centre of circle i. Discard any points that
>satisfy the the inequality. You are left with all the
>exterior points. Calculate their distance from P and
>pick the nearest one.

Yes, I too have found that that's the only way.
Now I just need to know how to calculate all the
points of intersection. How do I do that?

Greetings,

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

Given two circles with centres c1 and c2, both radius 1, the points of
intersection is the points p that satisfy:
(Note that vectors and points are essentially the same, so we can for
example take the dot product of two points by summing the products of the
components (i.e. coordinates.))

||p-c1|| + ||p-c2|| = 2


This should be fairly straightforward, i think.

5k.

Post a reply to this message

On Sun, 13 Feb 2000 14:19:32 +0100, "Rune" <run### [at] inamecom>
wrote:

>Yes, I too have found that that's the only way.
>Now I just need to know how to calculate all the
>points of intersection. How do I do that?
>
>Greetings,
>
>Rune

For each two circles, solve the system:

(X-X1)^2+(Y-Y1)^2=R1^2
(X-X2)^2+(Y-Y2)^2=R2^2

where the two circles have centers (X1,Y1) and (X2,Y2) and radii R1
and R2, respectively. The system will have no real roots if they do
not intersect, one double real root if they touch, two distinct real
roots if they intersect and infinitely many solutions if they
coincide.


Peter Popov
pet### [at] tagpovrayorg
ICQ: 15002700

Post a reply to this message

On Sat, 12 Feb 2000 13:04:57 +0100 Axel Hecht <ah### [at] numerikuni-kielde>
wrote:

>Here we go, I did a little testcase.

  Hi, Axel. Can you please cancel the post with the binary attachment
(image)? This is a text group. The preferred method is to post text in
this group and mention where to find the image in p.binaries.images.

  Thanks for your help in keeping some organization to the articles on
this server.

-- 
Alan - ako### [at] povrayorg - a k o n g <at> p o v r a y <dot> o r g
http://www.povray.org - Home of the Persistence of Vision Ray Tracer

Post a reply to this message

Aha! Simen has found a solution to this part of the problem.

Concider the two circles, whose radi are1 and centres c1 and c2.

Now, translate and rotate the system so that c1 lies at <0, 0> and c2 lies
on <x, 0>, simply by letting c1' = 0 and c2' = c2 - c1, and rotating
with -theta, where tan theta = c2'.y/c2'.x.

Now, there are two points of intersection if the circles overlap (or one if
they are just "kissing".) By simple geometric judgement and using the
Pythagorean Theorem, we obtein the two intersections:

<x/2, sqrt(1-x^2/4)> and <x/2, sqrt(1-x^2/4)>

Now, rotate these points with +theta, and add c1, and you have the points of
intersection between the two circles.

5k.

>
>Yes, I too have found that that's the only way.
>Now I just need to know how to calculate all the
>points of intersection. How do I do that?
>

Post a reply to this message

"Simen Kvaal" <sim### [at] studentmatnatuiono> writes:

> >No. Without loss of generality we assume that all circles are pairwise
> >different. (If two circles are identical, we remove one of them.)
> >Since there exists a point that lies inside all circles, two of them
> >intersect in two points. There are N circles and therefore N*(N-1)/2
> >unordered pairs of circles. This may lead to up to N*(N-1) intersections.
> >
> 
> But most of these intersections are not interesting, because they are
> obscured by other circles. On the _perimeter_ of the big buch of circles,
> there are a maximum og N+1 points to check.
> 
> 
> Try to draw circles on a paper so that all of them overlap at some point,
> and see what happens. How many points around the edge of the figure do you
> need to count?

The problem is that you don't know in advance which intersection points
are on the boundary. You must have a look at all intersection points and
decide whether it is inside another circle. Such a brute force algorithm
requires cubic run time.

However in this case, there is a better way than a brute force algorithm:
Since all circles have the same perimeter, it should be enough to have 
a look at intersection points of consecutive circles, thus considering 
only N intersection points.

Sorting the circles is possible in O(n log n) time. This dominates the
(asymptotic) run time.

Thomas

-- 
http://thomas.willhalm.de/ (includes pgp key)

Post a reply to this message

Hi Rune and Peter

Peter Popov wrote:

> On Sun, 13 Feb 2000 14:19:32 +0100, "Rune" <run### [at] inamecom>
> wrote:
>
> >Yes, I too have found that that's the only way.
> >Now I just need to know how to calculate all the
> >points of intersection. How do I do that?
> >
> >Greetings,
> >
> >Rune
>
> For each two circles, solve the system:
>
> (X-X1)^2+(Y-Y1)^2=R1^2
> (X-X2)^2+(Y-Y2)^2=R2^2
>
> where the two circles have centers (X1,Y1) and (X2,Y2) and radii R1
> and R2, respectively. The system will have no real roots if they do
> not intersect, one double real root if they touch, two distinct real
> roots if they intersect and infinitely many solutions if they
> coincide.
>
> Peter Popov
> pet### [at] tagpovrayorg
> ICQ: 15002700

I just had to see if I could solve the problem of finding these points
of
intersections without having to solve the above equation system.
(or maybe I did solve it without knowing it ? ;-)

Here is my graphical (and numerical) POV-Ray solution.

It can be used to solve the problem for intersection of spheres
(3D-problems)
or intersection of circles (2D-problems).

Best regards,
Tor Olav Kristensen

mailto:tor### [at] hotmailcom
http://www.crosswinds.net/~tok/tokrays.html

// ===================================================================
// Finding the points where two spheres (or circles) meet. By Tor Olav
Kristensen.
// ===================================================================

#version 3.1;
#include "colors.inc"

// ===================================================================

// Data for the spheres (3D) or circles (2D)
// The z co-ordinate in the sphere centres can be set to zero for a
// 2D-problem/solution in the XY-plane.
// If such an 2D solution is needed: Also select UpVector = z
//
// Note: If you choose the two spheres to have the same centre, then
// my solution will not work. If they also have the same radius, there
// will have infinitely many "intersections", else they will have none.
// It would however be simple to test for these cases before my code
// is used.

#declare Radius1 = 3.5;
//#declare Center1 = <-3, -2, 0>; // 2D-problem
#declare Center1 = <-3, -2, 2>; // 3D-problem

#declare Radius2 = 3;
//#declare Center2 = <1, -5, 0>; // 2D-problem
#declare Center2 = <1, -5, 1>; // 3D-problem

// ===================================================================

// My attempt to solve the problem

#declare Vector1to2 = Center2 - Center1;
#declare Distance = vlength(Vector1to2);
#declare C = (Radius1*Radius1 - Radius2*Radius2 + Distance*Distance)/
             (2*Distance);
#declare BetweenPoint = Center1 + C*vnormalize(Vector1to2);
#declare TR = Radius1*Radius1 - C*C;
//#declare UpVector = z; // for 2D-problem
#declare UpVector = <1, 3, -2>; // example for 3D-problem
// Note: Do not choose an UpVector that is parallel to Vector1to2
#declare SideVector = vcross(Vector1to2, UpVector);

#if (TR > 0)
  #declare SideVector = sqrt(TR)*vnormalize(SideVector) // Resizing
  #declare InterSection1 = BetweenPoint + SideVector;
  #declare InterSection2 = BetweenPoint - SideVector;
#else
  #if (TR = 0)
    #declare InterSection = BetweenPoint;
  #end
#end

#declare NewUpVector = vcross(SideVector, Vector1to2);
// I use this NewUpVector instead of UpVector just to make sure
// that I have an "Up"-vector that is perpendicular to the line
// between the two spherecentres.
// Should I have used vcross(Vector1to2, SideVector) instead?
// Maybe not: The numerical results seems to be the same.
// But the graphical view changes to "the other side"

// ===================================================================

// Graphical illustration of the problem

sphere { Center1, Radius1 pigment { color Green } }
sphere { Center2, Radius2 pigment { color Cyan  } }

plane {
  NewUpVector, 0
  translate BetweenPoint
  pigment { color Yellow }
}

// ===================================================================

// Graphical illustration of my proposed solution

#if (TR > 0)
  sphere { InterSection1, 0.8 pigment { color Red  } }
  sphere { InterSection2, 0.8 pigment { color Blue } }
#else
  #if (TR = 0)
    sphere { InterSection, 0.8 pigment { color Magenta } }
  #end
#end

// Note: A more correct graphical solution for a the 3D-problem
// would be to put a torus along the "circle of intersection" of
// the two spheres. Its major radius would then equal sqrt(TR)
// It's center should be at BetweenPoint. You can find an image here:
// http://www.crosswinds.net/~tok/Sphere2Sphere04.jpg

// ===================================================================

// Text output of the proposed solution to the debug window
// Press Alt M when parsing to view this text output

#macro PrintVector(Vector)

  #debug concat("<", str(Vector.x, 0, -1), ", ",
                     str(Vector.y, 0, -1), ", ",
                     str(Vector.z, 0, -1), " >")

#end // macro PrintVector


#if (TR > 0)
  #debug concat("\nFirst  intersection: ")
  PrintVector(InterSection1)
  #debug concat("\nSecond intersection: ")
  PrintVector(InterSection2)
#else
  #if (TR = 0)
    #debug concat("\nIntersection: ")
    PrintVector(InterSection)
  #else
    #debug "\nThere are no intersections"
  #end // if
#end // if

#debug "\n"

// ===================================================================

// Just my macros for axes
// X-axis is red
// Y-axis is green
// Z-axis is blue

#macro Arrow(StartPoint, EndPoint, Radius)

  #local a = Radius*3;
  #local b = Radius*2;
  #local c = Radius;
  #local Dirv = vnormalize(EndPoint-StartPoint);

  merge {
    difference {
      cone {
        EndPoint, 0,
        EndPoint-(a+b)*Dirv, Radius+c
      }
      cone {
        EndPoint-a*Dirv, Radius,
        EndPoint-(a+2*b)*Dirv, Radius+2*c
      }
    }
    cylinder {
      StartPoint, EndPoint-a*0.999*Dirv, Radius
    }
  }

#end // macro Arrow


#macro Axes(Size)

  #local Thickness = Size/40;

  union {
    object {
      Arrow(-Size*x, Size*x, Thickness)
      pigment { color Red }
    }
    object {
      Arrow(-Size*y, Size*y, Thickness)
      pigment { color Green }
    }
    object {
      Arrow(-Size*z, Size*z, Thickness)
      pigment { color Blue }
    }
  }

#end // macro Axes


Axes(5)

// ===================================================================

#declare CameraPosition = BetweenPoint + 3*(Radius1+Radius2)*
                          vnormalize(NewUpVector);

#if (TR > 0)
  light_source { CameraPosition + (Radius1+Radius2)*SideVector, White }
  light_source { CameraPosition - (Radius1+Radius2)*SideVector, White }
#else
  light_source { CameraPosition, White }
  light_source { CameraPosition, White }
#end

camera {
  location CameraPosition
  look_at BetweenPoint
}

// ===================================================================

Post a reply to this message