Last active
April 11, 2021 03:50
-
-
Save danielslz/a49a4a2f176afb29c55e9e08e7f94572 to your computer and use it in GitHub Desktop.
Distância entre dois pontos no plano cartesiano por divisão e conquista implementado em Python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment