Reputation: 199
I was reading chapter 7 of "Competitive Programming 3" by Steven and Felix Halim. I then found this problem, given in picture:
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:
I have searched many times, but I didn't find. Can anyone explain the technique?
Anyway, thanks in advance :)
Upvotes: 1
Views: 1950
Reputation: 14843
Let's first visualize variables d2
and h
defined in the code:
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
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).
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
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