There is a question on Zhihu, the content is known the coordinates of three points in space, find the coordinates of the center of the circle formed by three points (programming implementation)?

According to the definition of a circle, the core of the problem is to find a point that is equal to the three known points, using mathematical knowledge can be solved as follows:

For example: given a (x1,y1) b (x2,y2) c (x3,y3) find the coordinates O (x,y) (x1-x)*(x1-x)+(y1-y)*(y1-y)=(x2-x)*(x2-x)+(y2-y)*(y2-y); (x2-x)+(y2-y)*(y2-y); (x2-x)*(x2-x)+(y2-y)*(y2-y)=(x3-x)*(x3-x)+(y3-y)*(y3-y); 2. Jane got: 2 * (x2 – x1) * x + 2 * (y2 – y1) y = x2 y2 ^ ^ 2 + 2 – x1 ^ 2 – y1 ^ 2; 2*(x3-x2)*x+2*(y3-y2)y=x3^2+y3^2-x2^2-y2^2; Make: A1 = 2 * (x2 – x1); B1 = 2 * (y2 – y1); C1=x2^2+y2^2-x1^2-y1^2; A2 = 2 * (x3 – x2); B2 = 2 * (y3 – y2); C2=x3^2+y3^2-x2^2-y2^2; Namely: A1 * x + B1y = C1; A2*x+B2y=C2; 3. At last, according to the laws: the kramer, x = (* B2 (C1) – (C2 * B1))/(B2) (A1 * – * B1) (A2); Y = (C2) (A1 * – * C1) (A2)/(B2) (A1 * – * B1) (A2);

Of course, we’re not here today to study mathematical formulas and mathematical derivations. Tensorflow is an open source deep learning tool from Google. In fact, we can use Tensoflow to provide powerful mathematical computing power to solve similar mathematical problems.

In this case, we can use the gradient descent algorithm, because the center of the circle is an optimal solution, and no other point is satisfied. (If these three points are not on a straight line, otherwise there is no solution.)

All right, let’s look at the code first and then explain.

Import tensorflow as tf import numpy # Parameters Learning_rate = 0.1 training_epochs = 3000 display_step = 50 # Training Data, 3 points that form a triangel train_X = numpy.asarray([3.0,6.0,9.0]) train_Y = numpy.asarray([7.0,9.0,7.0]) # tf Graph Input X = tf.placeholder("float") Y = tf.placeholder("float") # Set vaibale for center cx = tf.Variable(3, name="cx",dtype=tf.float32) cy = tf.Variable(3, name="cy",dtype=tf.float32) # Caculate the distance to the center and make them as equal as possible distance = Tf. Pow (tf. The add (tf. The pow ((X - cx), 2), tf, pow ((Y - cy), 2)), 0.5) mean = tf. Reduce_mean cost = (short) tf.reduce_sum(tf.pow((distance-mean),2)/3) # Gradient descent optimizer = tf.train.GradientDescentOptimizer(learning_rate).minimize(cost) # Initialize the variables (i.e. assign their default value) init = tf.global_variables_initializer() # Start training with tf.Session() as sess: sess.run(init) # Fit all training data for epoch in range(training_epochs): sess.run(optimizer, feed_dict={X: Train_X, Y:train_Y}) c = sess.run(cost, feed_dict={X: train_X, Y:train_Y}) if (c-0) < 0.0000000001: break #Display logs per epoch step if (epoch+1) % display_step == 0: c = sess.run(cost, feed_dict={X: train_X, Y:train_Y}) m = sess.run(mean, feed_dict={X: train_X, Y:train_Y}) print "Epoch:", '%04d' % (epoch+1), "cost=", "{:.9f}".format(c), \ "CX=", sess.run(cx), "CY=", sess.run(cy), "Mean=", "{:.9f}".format(m) print "Optimization Finished!" training_cost = sess.run(cost, feed_dict={X: train_X, Y: train_Y}) print "Training cost=", training_cost, "CX=", round(sess.run(cx),2), "CY=", round(sess.run(cy),2), "R=", round(m,2), '\n'Copy the code

Running the python code above results in the following:

Epoch: 0050 cost= 0.290830940 CX= 5.5859795 CY= 2.6425467 Mean= 5.657848835
Epoch: 0100 cost= 0.217094064 CX= 5.963002 CY= 3.0613017 Mean= 5.280393124
Epoch: 0150 cost= 0.173767462 CX= 5.997781 CY= 3.5245996 Mean= 4.885882378
Epoch: 0200 cost= 0.126330480 CX= 5.9999194 CY= 4.011508 Mean= 4.485837936
Epoch: 0250 cost= 0.078660280 CX= 5.9999976 CY= 4.4997787 Mean= 4.103584766
Epoch: 0300 cost= 0.038911112 CX= 5.9999976 CY= 4.945466 Mean= 3.775567770
Epoch: 0350 cost= 0.014412695 CX= 5.999998 CY= 5.2943544 Mean= 3.535865068
Epoch: 0400 cost= 0.004034557 CX= 5.999998 CY= 5.5200934 Mean= 3.390078306
Epoch: 0450 cost= 0.000921754 CX= 5.999998 CY= 5.6429324 Mean= 3.314131498
Epoch: 0500 cost= 0.000187423 CX= 5.999998 CY= 5.7023263 Mean= 3.278312683
Epoch: 0550 cost= 0.000035973 CX= 5.999998 CY= 5.7292333 Mean= 3.262284517
Epoch: 0600 cost= 0.000006724 CX= 5.999998 CY= 5.7410445 Mean= 3.255288363
Epoch: 0650 cost= 0.000001243 CX= 5.999998 CY= 5.746154 Mean= 3.252269506
Epoch: 0700 cost= 0.000000229 CX= 5.999998 CY= 5.7483506 Mean= 3.250972748
Epoch: 0750 cost= 0.000000042 CX= 5.999998 CY= 5.749294 Mean= 3.250416517
Epoch: 0800 cost= 0.000000008 CX= 5.999998 CY= 5.749697 Mean= 3.250178576
Epoch: 0850 cost= 0.000000001 CX= 5.999998 CY= 5.749871 Mean= 3.250076294
Epoch: 0900 cost= 0.000000000 CX= 5.999998 CY= 5.7499437 Mean= 3.250033140
Optimization Finished!
Training cost= 9.8869656e-11 CX= 6.0 CY= 5.75 R= 3.25 Copy the code

After more than 900 iterations, the center position is (6.0, 5.75) and the radius is 3.25.

# Parameters
learning_rate = 0.1
training_epochs = 3000
display_step = 50Copy the code
  • Learning_rate is the rate of gradient descent. The larger the value is, the faster the convergence will be, but the optimal solution may be missed
  • Training_epochs is the number of learning iterations
  • Display_step is how many iterations to display the current calculation
# Training Data, 3 points that form a triangel
train_X = numpy.asarray([3.0,6.0,9.0])
train_Y = numpy.asarray([7.0,9.0,7.0])

# tf Graph Input
X = tf.placeholder("float")
Y = tf.placeholder("float")

# Set vaibale for center
cx = tf.Variable(3, name="cx",dtype=tf.float32)
cy = tf.Variable(3, name="cy",dtype=tf.float32)Copy the code
  • Train_X,train_Y is the x and y coordinates of the three points. Here, we choose (3,7), (6,9) and (9,7)
  • X and Y are the input of calculation, and we will use training data to input X and Y during calculation
  • Cx, cy is the center of the circle that we want to find, and the initial value is (3,3), and a normal learning algorithm would use a random initial value, so I picked a point in the triangle, and that would reduce the number of iterations.
# Caculate the distance to the center and make them as equal as possible distance = Tf. Pow (tf. The add (tf. The pow ((X - cx), 2), tf, pow ((Y - cy), 2)), 0.5) mean = tf. Reduce_mean cost = (short) tf.reduce_sum(tf.pow((distance-mean),2)/3) # Gradient descent optimizer = tf.train.GradientDescentOptimizer(learning_rate).minimize(cost)Copy the code

These few lines of code are the heart of the algorithm.

  • Distance is the distance between three points and the center of a circle by using the formula for the distance between two points
  • Mean is the average of the three distances
  • Cos (t) is the variance of the three distances, and our goal is to have the same distance from the center of the circle, which is to minimize the variance.
  • Optimizer is a gradient descent training function whose goal is to minimize cost

Here’s how it works:

# Start training with tf.Session() as sess: sess.run(init) # Fit all training data for epoch in range(training_epochs): sess.run(optimizer, feed_dict={X: train_X, Y: train_Y}) c = sess.run(cost, feed_dict={X: Train_X, Y:train_Y}) if (C-0) < 0.0000000001: break #Display logs per epoch step if (epoch+1) % display_step == 0: c = sess.run(cost, feed_dict={X: train_X, Y:train_Y}) m = sess.run(mean, feed_dict={X: train_X, Y:train_Y}) print "Epoch:", '%04d' % (epoch+1), "cost=", "{:.9f}".format(c), \ "CX=", sess.run(cx), "CY=", sess.run(cy), "Mean=", "{:.9f}".format(m) print "Optimization Finished!" training_cost = sess.run(cost, feed_dict={X: train_X, Y: train_Y}) print "Training cost=", training_cost, "CX=", round(sess.run(cx),2), "CY=", round(sess.run(cy),2), "R=", round(m,2), '\n'Copy the code
  • Initialize the TF session
  • Start the iteration
  • Calculate the cost value, when the cost is less than a certain value, deduce the iteration, indicating that we have found the center of the circle
  • Finally, print the results of the training

The original problem was a point in space, and my example is a point on a plane, but there’s no difference. I can add a z-axis. This problem, three-dimensional is actually redundant, can be solved by projecting three points on the space onto the plane.

I have implemented another algorithm in JS, but it does not always converge. We can refer to take a look:

Among them, the green three conditional points, the red circle is the final learning result, and the yellow center point is the learning track.

Using this example, I would like to say:

  • Tensorflow is more than just a deep learning tool. It provides powerful data computing power and can be used to solve many mathematical problems
  • The essence of machine learning is to find answers through a set of data, which is also the role of mathematics, so many mathematical problems can be solved by machine learning ideas.