branch14.org

 1 module SOLE
       2   
       3   def self.circle_of(*three_points)
       4     m = sole_matrix_for_circle(three_points)
       5     solve_sole!(m)
       6     x = m[1].last
       7     y = m[2].last
       8     r = Math.sqrt(x*x + y*y - m[0].last)
       9     Circle.new(Point.new(x, y), r)
      10   end
      11   
      12   private
      13 
      14   def self.sole_matrix_for_circle(points)
      15     matrix = []
      16     c = 0
      17     points.each do |p|
      18       matrix[c] = [1]
      19       matrix[c] << -2 * p.x
      20       matrix[c] << -2 * p.y
      21       matrix[c] << -p.x**2 - p.y**2
      22       c += 1
      23     end
      24     matrix
      25   end
      26   
      27   # solve system of linear equations
      28   def self.solve_sole!(matrix) 
      29     num_equations = matrix.size
      30     num_variables = matrix.first.size
      31     (num_variables-1).times do |j|
      32       q = matrix[j][j]
      33       if q == 0
      34         for i in j+1..num_equations-1 do
      35           if matrix[i][j] != 0
      36             for k in 0..num_variables-1 do
      37               matrix[j][k] += matrix[i][k]
      38             end
      39             q = matrix[j][j]
      40             break
      41           end
      42         end
      43       end
      44       if q != 0
      45         for k in 0..num_variables-1
      46           matrix[j][k] = matrix[j][k] / q
      47         end
      48       end
      49       for i in 0..num_equations-1
      50         if i != j
      51           q = matrix[i][j]
      52           for k in 0..num_variables-1
      53             matrix[i][k] -= matrix[j][k] * q
      54           end
      55         end
      56       end
      57     end
      58   end
      59   
      60 end