How to resolve the algorithm Problem of Apollonius step by step in the Java programming language

Published on 12 May 2024 09:40 PM
#Java

How to resolve the algorithm Problem of Apollonius step by step in the Java programming language

Table of Contents

Problem Statement

Implement a solution to the Problem of Apollonius   (description on Wikipedia)   which is the problem of finding the circle that is tangent to three specified circles   (colored black in the diagram below to the right). There is an   algebraic solution   which is pretty straightforward.

The solutions to the example in the code are shown in the diagram   (below and to the right). The red circle is "internally tangent" to all three black circles,   and the green circle is "externally tangent" to all three black circles.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Problem of Apollonius step by step in the Java programming language

The provided code is an implementation of the Apollonius solver in Java. It takes three circles as input and returns a circle that is tangent to all three of them. The solution is based on the theory of Apollonius, which states that there are at most eight circles that are tangent to three given circles. The code uses a series of transformations to reduce the problem to a quadratic equation, which is then solved to find the center and radius of the solution circle.

The code first defines the Circle class, which represents a circle in the plane. The circle is defined by its center point and its radius. The Circle class includes a toString() method that returns a string representation of the circle.

The ApolloniusSolver class contains the solveApollonius() method, which takes three circles and three signs as input and returns a circle that is tangent to all three of them. The signs indicate whether the solution circle should be externally or internally tangent to each of the input circles.

The solveApollonius() method first converts the input circles to a set of linear equations. It then solves the system of equations to find the center and radius of the solution circle. The solution circle is then returned as a new Circle object.

The main() method of the ApolloniusSolver class creates three circles and then calls the solveApollonius() method to find a circle that is tangent to all three of them. The results are then printed to the console.

Here is a more detailed explanation of the code:

  • The Circle class defines a circle in the plane. The circle is defined by its center point and its radius. The Circle class includes a toString() method that returns a string representation of the circle.
  • The ApolloniusSolver class contains the solveApollonius() method, which takes three circles and three signs as input and returns a circle that is tangent to all three of them. The signs indicate whether the solution circle should be externally or internally tangent to each of the input circles.
  • The solveApollonius() method first converts the input circles to a set of linear equations. It then solves the system of equations to find the center and radius of the solution circle. The solution circle is then returned as a new Circle object.
  • The main() method of the ApolloniusSolver class creates three circles and then calls the solveApollonius() method to find a circle that is tangent to all three of them. The results are then printed to the console.

Source code in the java programming language

public class Circle
{
 public double[] center;
 public double radius;
 public Circle(double[] center, double radius)
 {
  this.center = center;
  this.radius = radius;
 }
 public String toString()
 {
  return String.format("Circle[x=%.2f,y=%.2f,r=%.2f]",center[0],center[1],
		       radius);
 }
}

public class ApolloniusSolver
{
/** Solves the Problem of Apollonius (finding a circle tangent to three other
  * circles in the plane). The method uses approximately 68 heavy operations
  * (multiplication, division, square-roots). 
  * @param c1 One of the circles in the problem
  * @param c2 One of the circles in the problem
  * @param c3 One of the circles in the problem
  * @param s1 An indication if the solution should be externally or internally
  *           tangent (+1/-1) to c1
  * @param s2 An indication if the solution should be externally or internally
  *           tangent (+1/-1) to c2
  * @param s3 An indication if the solution should be externally or internally
  *           tangent (+1/-1) to c3
  * @return The circle that is tangent to c1, c2 and c3. 
  */
 public static Circle solveApollonius(Circle c1, Circle c2, Circle c3, int s1,
				      int s2, int s3)
 {
  float x1 = c1.center[0];
  float y1 = c1.center[1];
  float r1 = c1.radius;
  float x2 = c2.center[0];
  float y2 = c2.center[1];
  float r2 = c2.radius;
  float x3 = c3.center[0];
  float y3 = c3.center[1];
  float r3 = c3.radius;

  //Currently optimized for fewest multiplications. Should be optimized for
  //readability
  float v11 = 2*x2 - 2*x1;
  float v12 = 2*y2 - 2*y1;
  float v13 = x1*x1 - x2*x2 + y1*y1 - y2*y2 - r1*r1 + r2*r2;
  float v14 = 2*s2*r2 - 2*s1*r1;

  float v21 = 2*x3 - 2*x2;
  float v22 = 2*y3 - 2*y2;
  float v23 = x2*x2 - x3*x3 + y2*y2 - y3*y3 - r2*r2 + r3*r3;
  float v24 = 2*s3*r3 - 2*s2*r2;

  float w12 = v12/v11;
  float w13 = v13/v11;
  float w14 = v14/v11;

  float w22 = v22/v21-w12;
  float w23 = v23/v21-w13;
  float w24 = v24/v21-w14;

  float P = -w23/w22;
  float Q = w24/w22;
  float M = -w12*P-w13;
  float N = w14 - w12*Q;

  float a = N*N + Q*Q - 1;
  float b = 2*M*N - 2*N*x1 + 2*P*Q - 2*Q*y1 + 2*s1*r1;
  float c = x1*x1 + M*M - 2*M*x1 + P*P + y1*y1 - 2*P*y1 - r1*r1;

  // Find a root of a quadratic equation. This requires the circle centers not
  // to be e.g. colinear
  float D = b*b-4*a*c;
  float rs = (-b-Math.sqrt(D))/(2*a);
  float xs = M + N * rs;
  float ys = P + Q * rs;
  return new Circle(new double[]{xs,ys}, rs);
 }
 public static void main(final String[] args)
 {
  Circle c1 = new Circle(new double[]{0,0}, 1);
  Circle c2 = new Circle(new double[]{4,0}, 1);
  Circle c3 = new Circle(new double[]{2,4}, 2);
  // Expects "Circle[x=2.00,y=2.10,r=3.90]" (green circle in image)
  System.out.println(solveApollonius(c1,c2,c3,1,1,1));
  // Expects "Circle[x=2.00,y=0.83,r=1.17]" (red circle in image)
  System.out.println(solveApollonius(c1,c2,c3,-1,-1,-1));
 }
}

You may also check:How to resolve the algorithm Pig the dice game step by step in the Racket programming language
You may also check:How to resolve the algorithm Bitmap/Write a PPM file step by step in the PHP programming language
You may also check:How to resolve the algorithm Greatest subsequential sum step by step in the Haskell programming language
You may also check:How to resolve the algorithm Integer overflow step by step in the Pike programming language
You may also check:How to resolve the algorithm First-class functions step by step in the Python programming language