0

For start I have 3 points : A,B,C
The points are placed in a grid. The grid is actually an ImageView in a FrameLayout and both of them are inside a RelativeLayout
The 3 points are places on RelativeLayout, on top of the grid.
Now the 3 points represent the center of a circle with different radius each time(doesn't matter), so when I place the 3 points I draw a circle around each of them.
The circles are drawn like this : 

            Drawable drawable = getResources().getDrawable(R.drawable.circle);
            GradientDrawable gradientDrawable = (GradientDrawable) drawable;
            gradientDrawable.setColor(getResources().getColor(android.R.color.transparent));
            gradientDrawable.setShape(GradientDrawable.OVAL);
            //Then scale it 
            gradientDrawable.setStroke(stroke,color);
            circles[i].setImageDrawable(gradientDrawable);

Now I now both the (x,y) of the 3 points as well as their radius
Is there a way to find if the 3 cirlces intersect in one or more pixels?
EDIT:
Example of 3 circles that intersect in a point

BOSAnonym
  • 9
  • 1
  • 1
    adding some figure helps your explanation. I can't understand your problem – beigirad Apr 22 '20 at 16:42
  • You can use answers at [circle-circle intersection](https://stackoverflow.com/questions/3349125/circle-circle-intersection-points). You can solve by pairs (circles A & B, circles A & C, circles B & C) and compare the intersections found. – Ripi2 Apr 22 '20 at 18:57

1 Answers1

0

You have the following data, representing your 3 circles:

For each circle i=1,2,3:
Center: Ci = (ai, bi)
Radius: ri > 0

For three circles to have a common intersection point (x, y) that point has to be a solution to the system of quadratic equations:

(x - a1)^2 + (y - b1)^2 = r1^2
(x - a2)^2 + (y - b2)^2 = r2^2
(x - a3)^2 + (y - b3)^2 = r3^2

Expand each equation and rearrange the terms:

x^2 + y^2 - 2*a1*x - 2*b1*y = r1^2 - a1^2 - b1^2
x^2 + y^2 - 2*a2*x - 2*b2*y = r2^2 - a2^2 - b2^2
x^2 + y^2 - 2*a3*x - 2*b3*y = r1^2 - a3^2 - b3^2

One trick is to rewrite the system as follows:

z - 2*a1*x - 2*b1*y = r1^2 - a1^2 - b1^2
z - 2*a2*x - 2*b2*y = r2^2 - a2^2 - b2^2
z - 2*a3*x - 2*b3*y = r1^2 - a3^2 - b3^2
x^2 + y^2 = z

It is an over-determined system of three linear equations and three unknown variables (x, y, z), plus one extra quadratic equation between these three variables x^2 + y^2 = z.

So, solving linear systems is easy, therefore run the following algorithm:

Step 1: Reduce the linear system 

z - 2*a1*x - 2*b1*y = r1^2 - a1^2 - b1^2
z - 2*a2*x - 2*b2*y = r2^2 - a2^2 - b2^2
z - 2*a3*x - 2*b3*y = r1^2 - a3^2 - b3^2

by subtracting the first equation from the second and the third:

z = 2*a1*x + 2*b1*y + r1^2 - a1^2 - b1^2
2*(a1-a2)*x + 2*(b1-b2)*y = r2^2 - a2^2 - b2^2 - r1^2 + a1^2 + b1^2
2*(a1-a3)*x + 2*(b1-b3)*y = r1^2 - a3^2 - b3^2 - r1^2 + a1^2 + b1^2

Step 2: Solve the two by two linear system for (x, y):

2*(a1-a2)*x + 2*(b1-b2)*y = r2^2 - a2^2 - b2^2 - r1^2 + a1^2 + b1^2
2*(a1-a3)*x + 2*(b1-b3)*y = r1^2 - a3^2 - b3^2 - r1^2 + a1^2 + b1^2

and find the solution (or solutions, in some degenerate cases, but generally there should be exactly one solution) (x, y).

Step 3: Calculate z by substituting every solution (x, y) from Step 2 in the formula:

z = 2*a1*x + 2*b1*y + r1^2 - a1^2 - b1^2

Step 4: Check if 

x^2 + y^2 = z

If it is, then the three circles intersect at the point (x, y). If none of the solutions (x, y, z) from Step 3 satisfy the quadratic equation, then the three circles do not intersect.

Futurologist
  • 1,874
  • 2
  • 7
  • 9