Find the shortest distance between two dots in two dimension 【Ruby】
May 5, 2023
Studied an algorithm. A solution for O(N²) was known but I wanted to find O(N). It’s below. If you know better one, please tell me.
dots = [[11, 22], [3, 4], [50, 60], [5, 5]] # [x, y]
def vector(first_dot, second_dot)
minus = [first_dot[0] - second_dot[0], first_dot[1] - second_dot[1]]
Math.sqrt(minus[0]**2 + minus[1]**2)
end
def compare(dots)
number = 0
compared = 1
result = vector(dots[number], dots[compared])
while 1 < dots.size
temp_result = vector(dots[number], dots[compared])
if temp_result < result
result = temp_result
end
compared += 1
if compared > (dots.size - 1)
dots.delete_at(number)
compared = number + 1
end
end
result
end
p compare(dots) #=> 2.23606797749979
