Distância entre dois pontos no plano cartesiano por divisão e conquista implementado em Python

distancia_divisao_conquista.py

import sys
from math import sqrt
from random import uniform
from time import time


def imprime_lista_coordenadas(lista: [], titulo: str):
    print('=> {}:'.format(titulo))
    for c in lista:
        print(' - ({}, {})'.format(c[0], c[1]))


def gera_lista_coordenadas(qtd_pares: int):
    lista_coordenadas = []
    for i in range(qtd_pares):
        a = uniform(0, 360)
        b = uniform(0, 360)
        lista_coordenadas.append((a, b))
    return lista_coordenadas


def distancia_euclidiana(ponto_a, ponto_b):
    return sqrt((ponto_a[0] - ponto_b[0])**2) + ((ponto_a[1] - ponto_b[1])**2)


def distancia_minima_forca_bruta(coordenadas: []):
    menor_distancia = sys.float_info.max
    # identifica menor distancia
    for i, ponto_a in enumerate(coordenadas):
        start = i + 1
        for ponto_b in coordenadas[start:]:
            # calcula distancia
            distancia = distancia_euclidiana(ponto_a, ponto_b)
            # verifica menor distancia calculada
            if distancia < menor_distancia:
                menor_distancia = distancia
                pa = ponto_a
                pb = ponto_b

    # retorna lista de pontos com menor distancia
    return menor_distancia, pa, pb


def distancia_minima_divisao_conquista(coordenadas: []):
    ordenado_por_x = sorted(coordenadas, key=lambda x: x[0])
    ordenado_por_y = sorted(coordenadas, key=lambda x: x[1])

    # retorna lista de pontos com menor distancia
    return calcula_distancia(ordenado_por_x, ordenado_por_y)


def calcula_distancia(ord_x, ord_y):
    # se lista menor ou igual a 3 pontos resolve por forca bruta
    # dessa forma se impede que caia em um subproblema com apenas 1 ponto a verificar
    tamanho_lista = len(ord_x)
    if tamanho_lista <= 3:
        return distancia_minima_forca_bruta(ord_x)
    
    ## DIVISAO
    # divide lista x
    meio = tamanho_lista // 2
    x_esq = ord_x[:meio]
    x_dir = ord_x[meio:]

    # divide lista y pelo ponto central x
    ponto_x_central = ord_x[meio][0]  
    y_esq = list()
    y_dir = list()
    for p in ord_y:
        if p[0] <= ponto_x_central:
           y_esq.append(p)
        else:
           y_dir.append(p)

    ## CONQUISTA
    # chamada recursiva para verificar listas divididas
    dist_1, ponto_a1, ponto_b1 = calcula_distancia(x_esq, y_esq)
    dist_2, ponto_a2, ponto_b2 = calcula_distancia(x_dir, y_dir)

    # verifica menor distancia entre os pontos das duas listas
    if dist_1 <= dist_2:
        dist = dist_1
        ponto_ab = (ponto_a1, ponto_b1)
    else:
        dist = dist_2
        ponto_ab = (ponto_a2, ponto_b2)

    ## COMBINAR
    # chama funcao para calcular distancia dos pontos mais proximos da linha central
    dist_3, ponto_a3, ponto_b3 = distancia_pontos_mais_proximos_linha_central(ord_x, ord_y, dist, ponto_ab)
    
    # verifica se a distancia menor eh a da linha central ou dos pontos de uma das listas
    if dist <= dist_3:
        return dist, ponto_ab[0], ponto_ab[1]
    else:
        return dist_3, ponto_a3, ponto_b3


def distancia_pontos_mais_proximos_linha_central(ord_x, ord_y, distancia, pontos_mais_proximos):
    # pega ponto central da lista de pontos ordenados por x
    x_central = ord_x[len(ord_x) // 2][0]
    
    # cria arranjo de y eliminando pontos fora da faixa de distancia pelo ponto central x
    arranjo_y = [p for p in ord_y if x_central - distancia <= p[0] <= x_central + distancia]

    menor_distancia = distancia
    tamanho_arranjo_y = len(arranjo_y)
    # encontra menor distancia dos pontos
    for i in range(tamanho_arranjo_y - 1):
        # matematicamente somente 8 pontos podem estar dentro do retangulo 
        # formado pelo arranjo de y, de tamanho distancia x 2*distancia
        # dessa forma, somente precisam ser verificados no maximo ate 7 pontos 
        # da sequencia, se tamanho do arranjo for menor que 7 pontos o loop
        # so vai ate o tamanho do arranjo
        for j in range(i+1, min(i + 7, tamanho_arranjo_y)):
            a, b = arranjo_y[i], arranjo_y[j]
            dist = distancia_euclidiana(a, b)
            if dist < menor_distancia:
                menor_distancia = dist
                pontos_mais_proximos = a, b
    return menor_distancia, pontos_mais_proximos[0], pontos_mais_proximos[1]


# gera lista aleatoria de coordenadas
coordenadas_a_calcular = gera_lista_coordenadas(10000)

# lista coordenadas aleatorias
# imprime_lista_coordenadas(coordenadas_a_calcular, 'Coordenadas a calcular')

# chama funcao
inicio = time()
distancia, ponto_a, ponto_b = distancia_minima_divisao_conquista(coordenadas_a_calcular)
fim = time()

# exibe valores
print('=> Resultado:')
print('-  Ponto A = ({}, {})'.format(ponto_a[0], ponto_a[1]))
print('-  Ponto B = ({}, {})'.format(ponto_b[0], ponto_b[1]))
print('-  Distância = {}'.format(distancia))
print('=> Tempo de execução: {} segundos'.format(fim - inicio))