CODEWITHSUNDEEP
geometry
Md. Ikramul Murad
Md. Ikramul Murad

Reputation: 199

How to find centers of two circle when their intersecting points and corresponding radius is given?

I was reading chapter 7 of "Competitive Programming 3" by Steven and Felix Halim. I then found this problem, given in picture:

enter image description here

Here two intersecting points of two circles and corresponding radius are also given. I have to find centres of two circles. They have given the solution code. But I didn't understand the technique behind it. The given code is:

enter image description here

I have searched many times, but I didn't find. Can anyone explain the technique?

Anyway, thanks in advance :)

Upvotes: 1

Views: 1950

Answers (2)

Leandro Caniglia
Leandro Caniglia

Reputation: 14843

Let's first visualize variables d2 and h defined in the code: enter image description here

As we can see, d2 stands for the square of the distance between p1 and p2. Let's put d = sqrt(d2). Then d^2 = d2.

Using Pythagoras: r^2 = h^2 + d^2/4. Hence, h^2 = r^2 - d^2/4.

The unitary (norm = 1) vector in the direction of the line joining p1 and p2 is:

v := (p2 - p1)/d = (p2.x - p1.x, p2.y - p1.y)/d.

its perpendicular is

w := (p2.y - p1.y, p1.x - p2.x)/d

Now we can express c1 as a point in the perpendicular direction:

c1 = q + w*h = (p1 + p2)/2 + w*h,

because w has norm 1 and h is precisely the distance between c1 and q. Therefore,

c1 = (p1.x + p2.x, p1.y + p2.y)/2 + (p2.y - p1.y, p1.x - p2.x)*h/d

where

h/d = sqrt(r^2 - d^2/4)/d = sqrt(r^2/d2 - 1/4)

which explains the code.

Notes

  1. From the picture that r is always ge than d/2. Thus, r^2 ≥ d^2/4 or (r/d)^2 ≥ 1/4 and there is no need to check whether det < 0, because it never is (provided the circles intersect).

  2. The derivation above will actually produce two solutions for c1, one to the right of the blue line from p1 to p2, which is the one in the drawing, and another on the left of said line. In fact, these correspond to the equations

    c1 = q ± w*h = q + w*(±h)

    In order to decide whether we should use +h or -h, we can apply one of the well-known criteria for establishing whether a point lies on the left or the right of a directed segment. For example, we could compute the sign of the determinant

         | 1 p1.x p1.y |
 D = | 1 p2.x p2.y | = (p2.x-p1.x)(c1.y-p1.y) - (p2.y-p1.y)(c1.x-p1.x)
     | 1 c1.x c1.y |

which will have a sign for +h and the opposite for -h. The value of h that makes D < 0 is the one that leaves c1 on the right of the segment from p1 to p2.

Upvotes: 1

user1196549
user1196549

Reputation:

Apply Pythagoras in the right triangles. This gives you the distances between the midpoint of p1p2 and the centers.

From unit vectors parallel then orthogonal to p1p2, the offset vectors are easily obtained.

Upvotes: 0

Related Questions