How to detect what are the common points between two circles?

Question

I need assistance for the following program:

Receive from the keyboard the equations of two circles:

c1= X^2+y^2+ax+by+c=0
c2= X^2+y^2+a2=x+by+c=0

and show if the circles have points in common, intersections.

I am a student of chemical engineering, I understand almost nothing of programming (it is not my area), before that if someone can give me a "light".

Answer 1

The problem here is classic Analytical Geometry, where you find a way to deal with geometry without using compasses or rulers. It differs greatly from classical geometry because you represent Geometry through Algebra, uniquely and uniquely Algebra.

Defining a circle

A circle is the set of points equidistant to a fixed point; this fixed point is the center of the circumference and the distance is its thunderbolt. This allows you to draw circles from 1 dimension to N dimensions. In this case, the special interest is with 2 dimensions, the Cartesian plane.

You need three pieces of information to know if a point belongs to a specific circumference (besides, of course, the point in question):

• the centre of the circumference
• the radius of the circumference
• how to calculate the distance between any two points

The following formula condenses all this information into a single equation:

(p.x - c.x)^2 + (p.y - c.y)^2 - r^2 = 0

Which can be expanded as follows:

p.x^2 + p.y^2 - 2*c.x *p.x - 2*c.y*p.y + c.x^2 + c.y^2 - r^2 = 0

As the center c is a coordinate in the plane, it is a constant in the equation. Therefore, c.x and c.y are also. The same goes for lightning r. So I’m gonna play c.x^2 + c.y^2 - r^2 with the arbitrary constant K. The constants that multiply p.x and p.y will be replaced by mx and my. This then is the final form of the equation:

p.x^2 + p.y^2 - mx*p.x - my*p.y + K = 0

Previously I said that it needs two factors, but in this last equation appear only the terms of the center and radius (compensated and hidden behind constants). But where does the necessary third element enter? , the one that says it is necessary to know how to calculate the distance between two arbitrary points?

Enter the general form of the formula. If you notice, the distance in a Cartesian plane follows the Pythagorean theorem. Classic example of classical geometry. But we can define other values to calculate distance. With this, we also obtain very peculiar forms of "circles" for each new "geometry", based on this idea of distance (see this Infinite Series video for more details).

What if the distance were given by the Manhattan distance formula? Then the circle would obey the following equation:

|p.x - c.x| + |p.y - c.y| - r = 0

I can safely assume that your problem occurs in circles that follow a geometry in which distances are calculated in a very traditional way, because otherwise it would be much explicit that this is not the case.

Relative position classification of two circles

There are some possible positions that two circles may be relative to each other. And these possible positions depend on the relative size of the radius of these two circles.

To compare the radius, we only have two possibilities:

• the radius of the two is distinct, where the smallest radius is the circumference o1 and the largest o2
• the radius of both is the same size

It is always possible to assume in the first case that o2 will be the circumference with greater radius. This does not reduce at all the generalization of what is found.

Let’s assume here that o2 has the center coincident with the center of our coordinate system and that o1 cannot move on the Y-axis, being attached to the X-axis. Not only to the X-axis, but with o1.c.x >= 0. In the first sections I will talk about the possible relative positions, and then (and only then) demonstrate that assuming these restrictions does not imply loss of generality, that in fact all other variations are only symmetric forms of this base case:

Relative positioning with different radii

At first, o1.c = o2.c, then the two circumferences are centered at the origin. In this case, they will not touch. Their positioning is "non-drying interior".

I can move o1 even before the position o1.c.x + o1.r < o2.r that the relative position will remain the same. That interval is:

0 <= o1.c.x < o2.r - o1.r

At a time when o1.c.x + o1.r = o2.r, the two circles shall be "internal tangents".

If I go a little beyond the tangentially internal, then I will have the circumferences to be "boring" with each other. This means that the meeting between them is a section (hence the name "secante"). This interval is given by:

o2.r - o1.r < o1.c.x < o2.r + o1.r

There is no distinction between secant classification.

When you reach the boundary of this interval (but still within it), the two circles will barely be in contact with each other. When the distance of the centers of the circles is the sum of the rays, I will have extrapolated this interval and they will be only "external tangents". The formula is:

o1.c.x = o1.r + o2.r

Anything beyond that, they become "external nondryers", where they no longer touch each other:

o1.c.x > o1.r + o2.r

Recapping:

• non-drying
  distance from the centers less than the radius difference
  d < r2 - r1
• internal tangent
  distance between centres equal to the difference between radii
  d = r2 - r1
• secant
  distance between the centers greater than the difference between the radii, but less than the sum
  r2 - r1 < d < r2 + r1
• external tangent
  distance between centres equal to the sum of radii
  d = r2 + r2
• external non-drying
  distance between the centres greater than the sum of the radii
  r2 + r1 < d

The gif below summarizes these 5 types:

Relative positioning with identical radii

In this case, the beginning with o1.c.x = 0 shall produce the same circumference as o2. So they’re "overlapping circles".

After that, until the distance is twice the radius (or the sum of the rays, as in the case of different rays), they will be drying:

o1.c.x < o1.r*2

When they reach twice the radius, they will be external tangents:

o1.c.x = o1.r*2

In addition, they will be non-drying:

o1.c.x > o1.r*2

Recapping:

• superimposed
  distance from zero centres
  d = 0
• secant
  distance from the centres
  0 < d < 2*r
• external tangents
  centre distance equal to twice the radius
  d = 2*r
• unending
  distance from the centres beyond two radii
  d > 2*r

Proof of symmetry

The names o1 and o2 are not inherent to the objects of study, so I can put any label on any object without mischaracterizing it. Therefore, I can define my labeling system without losing generality.

On the case in which o2 not being in the center. I can do the translation of all objects in the plane until o2.c = (0,0). As I am translating all objects at the same time, they maintain their relative positions with each other. So the plan translation operation still does not interfere with the overall solution.

Now, imagine that o1 is not exactly on the x-axis. But rather moved 47º counterclockwise. If I rotate the 47º plane clockwise, the center of o1 would be in the new X axis. And as the rotation was done in the plane, the properties remained.

With this, we can see that the above cases, in which the following truths happen:

o1.r <= o2.r
o2.c = (0,0)
o1.c = (x, 0) | x >= 0

classify all the infinite possible cases of relative positioning of two circles.

Checking whether a given formula is a circle

If you have a guarantee that past data is data controlled, that’s fine. Now, what if it’s wild data? Data that has not been normalized? Data provided by people who can type erroneously?

For this, we must worry whether the data makes sense. Perhaps for the specific question it is not the case to worry about it. But someone might need to know that, and it’s also fun to check.

For a circle to be valid, in the case of distances given by the Pythagorean theorem, it can accept any center, but the radius must be non-negative. If the radius is 0, the circumference is only one point in the plane. There are those who consider it a circumference, there are those who think it is not, but for simplicity we can consider it is.

Let’s take the formula again. As the only parameter provided is p, we can ignore him and directly his fields:

x^2 + y^2 - mx*x - my*y + K = 0

Because of the way we create mx, we know that, in this formula, the value of c.x = mx/2. The same goes for c.y.

So to find out if the value is valid, we need to replace in K these values and find r^2:

K = c.x^2 + c.y^2 - r^2

Multiplying by 4 on both sides:

4*K = 4*c.x^2 * 4*c.y^2 - 4*r^2 = mx^2 + my^2 - 4*r^2

Therefore, isolating 4*r^2:

4*r^2 = mx^2 + my^2 - 4*K

To r take on a real value, we have to be all non negative:

mx^2 + my^2 - 4*K >= 0

If that is not true, or the form treated is not a circle, or is a circle with imaginary radius (I do not know what geometric interpretation for this, but is what in fact it would be).

Other checks

It is implicit in the problem that the given form is always with the factor that multiplies x^2 and the factor that multiplies y^2 is 1. This value can be any arbitrary value as long as it is the same for x^2 and y^2.

Take the equation:

x^2 + y^2 - mx*x - my*y + K = 0

Multiply by a on both sides:

a*x^2 + a*y^2 - a*mx*x - a*my*y + a*K = 0

Continues to describe a circumference.

Finding the intersection

Given two distinct formulas of circumferences, we can first verify in which situation they fit. We can verify whether or not the rays are the same and thus determine whether they are tangent, secant, or nonsecant according to the distance from their centers. Only with this, then, we will know how many solutions to expect. The possibilities are:

• infinite (concentric and of the same radius)
• 2 (secant)
• 1 (tangent, external or internal)
• 0 (non-drying, external or internal)

If, algebraically, we subtract the two equations from the given circles, we get the following:

x^2 + y^2 - mx1*x - my1*y + K1 = 0      -
x^2 + y^2 - mx2*x - my2*y + K2 = 0
_________________________________________

x^2 - x^2 + y^2 - y^2 - mx1*x + mx2*x - my1*y + my2*y + K1 - K2 = 0 - 0

x*(mx2 - mx1) + y*(my2 - my1) + K1 - K2 = 0

That’s a straight line. I don’t particularly know what that straight line is, what it represents, but I know it’s a straight line. If by chance my1 = my2, then I know that the validity of this equation is independent of y, so it’s a vertical line. In this case, I can get the value of x. The same goes for the x, with mx1 = mx2 having a horizontal line.

Well, in the previous paragraph I said I didn’t know what that line was, right? Well, partially just. I can get the same results when I make equation 1 equal to equation 2. To pass equation 2 to the other side, so that only 0 is on the right side of the equation, is to do this subtraction. Then, this line obtained by this "algebraic subtraction" of the formulas is, for the case of secants and tangents, the line that touches the common points of the two circles. In the case of the tangent, it is a line tangent to both circumferences, in the case of secants, it is a drying line.

In the case of nonsecants? I do not know. This segment is perpendicular to the segment that unites the two centers. I didn’t find any specific relation about the reason in which it divides this segment.

What I do have is that I know this line and I also know how many intersections there are between o1 and o2. From this line, I can decrease in 1 the degree of freedom of the system (therefore returning to 1), either by finding a constant for one of the variables (cases of horizontal/vertical lines), or by putting y as a function of x. Applying this reduction of the degrees of freedom, replacing the value obtained in the equation referring to o1, we will obtain the values of y (or of x in the case of a horizontal line) through the second degree equation. These points intersect at the same time the two circles.

You can see that when there is intersection, the obtained line always passes at the intersection. For the case of internal non-setters the interpretation of what this line means is something strange (it was not represented for concentric because this line would be in infinity in all directions):

Case of inclined line

This is the most general case. With this, I get a function of y datum x:

y = - x*(mx2 - mx1) - K1 + K2
    --------------------------
           my2 - my1

Since they are all known constants, I can simplify to:

y = -a*x + b

Then, replacing the value of y in any of the circles, we obtain an equation of the second degree that depends only on x:

x^2 + (-a*x + b)^2 - mx1*x - (-a*x + b)*x + K1 = 0

Algebra, algebra, algebra:

(1 + a^2 + a)*x^2 + (-2*a*b - mx1 - b)*x + K1 + b^2 = 0

With this, we can apply the Bhaskara solution and find the two or a root of this equation. To get the intersection then, just get the values of y for the x found.

Case of the horizontal line

When the line is horizontal, we have to:

y*(my2 - my1) = K2 - K1

So we get the value of y:

y =  K2 - K2
    ---------
    my2 - my1

So we get a constant value for y. We substitute in the equation of one of the circles and obtain an equation of the second degree in x. Bhaskara again.

Case of the vertical line

Identical to the previous one, but the constant value found is x and we must resolve Bhaskara to y.

Recapping

It is possible to determine, in that order:

1. Classify whether the four forms provided are circumferences or not
2. Determine how many points of intersection there are between the circles
3. If secant or tangent, what are the points of intersection of these circles

Through the indices of the formula, we have a magical inequality that ensures this:

mx^2 + my^2 - 4*K >= 0

The identification of the amount of intersections (which varies between values { 0, 1, 2, infinito }) define whether we will try to find these intersections or not. We identify how many intersections it has according to the relative positioning between the two circles. However, our definition of relative positioning depends on finding the following constructs of the circles:

1. Its center
2. Your lightning

The center is easy to get:

c = (mx/2 ; my/2)

Already the ray is given by:

r = (c.x^2 + c.y^2 - K)^0.5

With these four pieces of information in our hands, we first check whether the rays are the same size or not. If it is of different sizes, then we already know that there is no intersection of infinite points, but we must worry about whether one circumference will be internal to another without touching or just touching tangentially. These cases are given by (i.e. d the distance between the centres):

• non-drying
  d < r2 - r1
• internal tangent
  d = r2 - r1
• secant
  r2 - r1 < d < r2 + r1
• external tangent
  d = r2 + r1
• external non-drying
• r2 + r1 < d

When the circles have the same radius, the possibility of being encountered at all infinite points is with d = 0. Any distance value greater than this to the external tangent value implies secant: 0 < d < 2*r, but it can also be rewritten as r2 - r1 < d < r2 + r1. Therefore, the only special case is with infinite points of intersection, zero distance. All others are identical to those provided by the inequalities above.

Knowing if there is an intersection or not, if it is a finite number of intersections, we can try to find the points of that intersection.

We find this from the following equation:

x*(mx2 - mx1) + y*(my2 - my1) + K1 - K2 = 0

With that, we can get y for a value of x, or a constant value for x , or a constant value for y. We substitute what we find in the equation of one of the circles generating an equation of the second degree and then we obtain the value/values for one of the variables. If we have y as a function of x, then we need to find out what those would be ys.

later I put the programmatic resolution