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