Distância entre muitos pontos??

[Vanessa Teixeira]

Oi gente, eu tenho 49 pontos

.        .        .        .        .        .        .

.        .        .        .        .        .        .

.        .        .        .        .        .        .

.        .        .        .        .        .        .

.        .        .        .        .        .        .

.        .        .        .        .        .        .

.        .        .        .        .        .        .

e a distância entre um ponto e o seguinte é de 2.5. Para cada ponto preciso calcular a distância até todos os outros pontos, estou me embolando toda aqui na hora de arrumar o código. Pra 2 pontos é fácil, tem q ter um jeito mais fácil de organizar as muitas distâncias do que indo de 2 em 2. Alguém pode me ajudar?

[Guilherme Medeiros]

Boa tarde Vanessa.

Vamos entender melhor o problema :D

Os pontos tem sempre a mesma distância entre si?

Os pontos são guardados em um array de duas dimensões ou de outra forma?

Como você identifica qual o ponto inicial e o ponto final?

Para calcular a distância entre esses dois pontos, podemos "andar na diagonal" ou sempre na horizontal e vertical?

Quanto a possíveis soluções, https://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra pode ser a resposta nesse caso.

Porém, dependendo das respostas q vc me der, talvez uma simples equação matemática resolva.

Boa sorte.

--
--
------------------------------------
Grupo Python-Brasil
https://wiki.python.org.br/AntesDePerguntar
 
<*> Para visitar o site do grupo na web, acesse:
http://groups.google.com/group/python-brasil
 
<*> Para sair deste grupo, envie um e-mail para:
python-brasi...@googlegroups.com
---
Você recebeu essa mensagem porque está inscrito no grupo "Python Brasil" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python-brasi...@googlegroups.com.
Para ver essa discussão na Web, acesse https://groups.google.com/d/msgid/python-brasil/f8e7a096-97aa-4096-8dd0-469b9c7748c1%40googlegroups.com.

[Vanessa Teixeira]

Isso daí são latitudes e longitudes. Está organizado assim:

longitude vai de -30º a -15º e para cada longitude as latitudes vão de -10 até -25º, tudo igualmente espaçado de 2.5º entre eles, tanto longitude quanto latitude.

Aí pra calcular as distâncias na mesma longitude (mesma linha vertical) é só ir somando 2.5º, assim como para a mesma latitude (linha horizontal). Agora pra longitudes diferentes é um triângulo retângulo onde a hipotenusa é a distância que eu quero.

Meu problema é otimizar isso, senão vou demorar mil anos pra fazer. Pra armazenar esses valores eu q tenho q escolher a melhor forma tbm

python...@googlegroups.com

---
Você recebeu essa mensagem porque está inscrito no grupo "Python Brasil" dos Grupos do Google.

Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python...@googlegroups.com.

[Henrique Pougy]

Faltou fechar o parênteses da função sqrt. Troca por isso:

dist = sqrt((x_2-x_1)**2 + (y_2-y_1)**2) 

Em qui, 16 de abr de 2020 22:02, Vanessa Teixeira <vteixe...@gmail.com> escreveu:

Fiz assim:

def distancia(x_1,y_1,x_2,y_2):

if x_1==x_2:

dist = y_2 - y_1

elif y_1==y_2:

dist = x_2 - x_1

else:

dist = sqrt((x_2-x_1)**2 + (y_2-y_1)**2

return dist

distancia(30,10,30,12.5)

distancia(30,10,27.5,12.5)

e deu erro de sintaxe:

  File "mai_pesado.py", line 185

    distancia(30,10,30,12.5)

            ^

SyntaxError: invalid syntax

Sabe me dizer o que fiz errado??

python-brasi...@googlegroups.com

---
Você recebeu essa mensagem porque está inscrito no grupo "Python Brasil" dos Grupos do Google.

Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python-brasi...@googlegroups.com.
Para ver essa discussão na Web, acesse https://groups.google.com/d/msgid/python-brasil/bd47dcfc-bcdb-49ae-bc72-00f7a669fdf9%40googlegroups.com.

[Sinval Júnior]

Vanessa, matematicamente vc pode usar Geometria Analítica, vetores. A forma mais simples será usando o Teorema de Pitagoras, assim será possível calcular a distancia inclusive em diagonal. Agora basta implemetar seu algoritimo em Python. Uma dica é procure montar uma matriz contendo o valor dos pontos.

Ao encaminhar esta mensagem, por favor:
1 - Apague meu endereço eletrônico;
2 - Encaminhe como Cópia Oculta (Cco ou BCc) aos seus destinatários. Dificulte assim a disseminação de vírus, spams e banners.

#=================================================================+
#!/usr/bin/env python
nome = 'Sinval Júnior'
email = 'sinvalju arroba gmail ponto com'
print nome
print email
#==================================================================+

Em qui., 16 de abr. de 2020 às 17:43, Vanessa Teixeira <vteixe...@gmail.com> escreveu:

--

--
------------------------------------
Grupo Python-Brasil
https://wiki.python.org.br/AntesDePerguntar
 
<*> Para visitar o site do grupo na web, acesse:
http://groups.google.com/group/python-brasil
 
<*> Para sair deste grupo, envie um e-mail para:
python-brasi...@googlegroups.com
---
Você recebeu essa mensagem porque está inscrito no grupo "Python Brasil" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python-brasi...@googlegroups.com.

Para ver essa discussão na Web, acesse https://groups.google.com/d/msgid/python-brasil/f8e7a096-97aa-4096-8dd0-469b9c7748c1%40googlegroups.com.

[Andre Emidio]

Discuti com amigo sobre esse problema uma vez, a solução que ele usou para um caso semelhante, foi usar insertion sort para recolher todos os pontos e depois aplicar distância euclidiana para saber as distâncias entre os pontos.

Para ver essa discussão na Web, acesse https://groups.google.com/d/msgid/python-brasil/CALatGPjefng9pvn0hVd%2BQghyDo_L5ewrXxn%3DcN%2Bi8wfHJvw8bg%40mail.gmail.com.

[Anderson Souza]

Olá.

Li por cima as questões.

Diante da sua questão, distância euclidiana resolve sua questão. Ainda, conforme um colega mencionou, tente montar uma matriz e aplicar os algorítimos.

Se for esse o caminho do que deseja, compartilho esse arquivo com os cálculos:

https://colab.research.google.com/drive/1neD5MK0j2knL4EMgjkU1xaEPbhTJtOLY

Anderson

[Linux - Junior Polegato]

Em 16/04/2020 18:03, Vanessa Teixeira escreveu:
> Isso daí são latitudes e longitudes. Está organizado assim:
> longitude vai de -30º a -15º e para cada longitude as latitudes vão de
> -10 até -25º, tudo igualmente espaçado de 2.5º entre eles, tanto
> longitude quanto latitude.
> Aí pra calcular as distâncias na mesma longitude (mesma linha
> vertical) é só ir somando 2.5º, assim como para a mesma latitude
> (linha horizontal). Agora pra longitudes diferentes é um triângulo
> retângulo onde a hipotenusa é a distância que eu quero.
> Meu problema é otimizar isso, senão vou demorar mil anos pra fazer.
> Pra armazenar esses valores eu q tenho q escolher a melhor forma tbm

Olá!

        De bate pronta, e verificando no Google rapidinho quanto
equivale aproximadamente um grau em km, fiz o código-sugestão abaixo:


import functools

lat_range = (-10, -25)
long_range = (-30, -15)
passo = 2.5

# Função para calcular distância entre dois pontos no plano cartesiano
(Pitágoras)
# Aproximando cada grau para 109 km
# Para calcular sobre uma esfera, a fóruma é outra, como por exemplo em:
# https://www.sunearthtools.com/pt/tools/distance.php#txtDist_1
# distância (A, B) = R * arccos (sin (lata) * sin (latB) + cos (lata) *
cos (latB) * cos (Lona-lonB))

dist_km = lambda p1, p2: functools.reduce(lambda w, z: (w**2 +
z**2)**(1/2), (map(lambda x: x[0] - x[1], zip(p1, p2)))) * 109

# Criando lista de valores de latitude (7 valores)
sentido = (-1, 1)[lat_range[1] > lat_range[0]]
lats = [x/100 for x in range(int(lat_range[0] * 100),
                             int((lat_range[1] + sentido * passo) * 100),
                             int(passo * 100) * sentido)]

# Criando lista de valores de longitude (7 valores)
sentido = (-1, 1)[long_range[1] > long_range[0]]
longs = [x/100 for x in range(int(long_range[0] * 100),
                              int((long_range[1] + sentido * passo) * 100),
                              int(passo * 100) * sentido)]

# Matris de pontos (latitude, longitude) (7 x 7 = 49 coordenadas)
pontos = functools.reduce(lambda w, z: w + z, map(lambda x:
list(map(lambda y: (x, y), longs)), lats))

# Combinando esses 49 pontos 2 a 2 (49!/(2!*(49-2)!) = 49!/(2*47!) =
1.176 distâncias)
# Calculando a distância entre eles e colocando numa lista de dicionários
dists = functools.reduce(lambda w, z: w + z, (list(map(lambda p2: {'p1':
p1, 'p2': p2, 'd': dist_km(p1, p2)}, pontos[x + 1:])) for x, p1 in
enumerate(pontos)))

--

[]'s

Junior Polegato

[José Luis Segatto Junior]

Vanessa,
Dependendo da precisão que você precisa, será necessário geometria esférica.

O primeiro problema que você colocou, com os pontos dispostos num plano, resolve-se fácil, com Pitágoras (hipotenusa=((horizontal^2)+(vertical^2))^(1/2)), os pontos diagonais.

Eu desconheço geometria esférica, mas sei que o resultado é diferente.

--
--
------------------------------------
Grupo Python-Brasil
https://wiki.python.org.br/AntesDePerguntar

<*> Para visitar o site do grupo na web, acesse:
    http://groups.google.com/group/python-brasil

<*> Para sair deste grupo, envie um e-mail para:

    python-brasi...@googlegroups.com
---
Você está recebendo esta mensagem porque se inscreveu no grupo "Python Brasil" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python-brasi...@googlegroups.com.
Para ver esta discussão na web, acesse https://groups.google.com/d/msgid/python-brasil/76e5b875-e3fe-eea4-5815-4ee75815ef7c%40juniorpolegato.com.br.

[Vanessa Teixeira]

Olá pessoal, obrigada pelas respostas. Então, eu não preciso de geometria esférica não e posso deixar tudo em grau msm. O que eu fiz e deu certo foi:

def distancia(x_1,y_1,x_2,y_2):

if x_1==x_2:

dist = abs(y_2 - y_1)

elif y_1==y_2:

dist = abs(x_2 - x_1)

else:

dist = sqrt((x_2-x_1)**2 + (y_2-y_1)**2)

return dist

print(distancia(30,10,30,12.5))

print(distancia(30,10,27.5,12.5))

#Distância do ponto (lon=-30,lat=-10) --> regiao R0 de todos os outros:

distR0 = asarray([distancia(30,10,30,12.5),distancia(30,10,30,15),distancia(30,10,30,17.5),distancia(30,10,30,20),distancia(30,10,30,22.5),distancia(30,10,30,25),distancia(30,10,27.5,10),distancia(30,10,27.5,12.5),distancia(30,10,27.5,15),distancia(30,10,27.5,17.5),distancia(30,10,27.5,20),distancia(30,10,27.5,22.5),distancia(30,10,27.5,25),distancia(30,10,25,10),distancia(30,10,25,12.5),distancia(30,10,25,15),distancia(30,10,25,17.5),distancia(30,10,25,20),distancia(30,10,25,22.5),distancia(30,10,25,25),distancia(30,10,22.5,10),distancia(30,10,22.5,12.5),distancia(30,10,22.5,15),distancia(30,10,22.5,17.5),distancia(30,10,22.5,20),distancia(30,10,22.5,22.5),distancia(30,10,22.5,25),distancia(30,10,20,10),distancia(30,10,20,12.5),distancia(30,10,20,15),distancia(30,10,20,17.5),distancia(30,10,20,20),distancia(30,10,20,22.5),distancia(30,10,20,25),distancia(30,10,17.5,10),distancia(30,10,17.5,12.5),distancia(30,10,17.5,15),distancia(30,10,17.5,17.5),distancia(30,10,17.5,20),distancia(30,10,17.5,22.5),distancia(30,10,17.5,25),distancia(30,10,15,10),distancia(30,10,15,12.5),distancia(30,10,15,15),distancia(30,10,15,17.5),distancia(30,10,15,20),distancia(30,10,15,22.5),distancia(30,10,15,25)])

ir chamando a função colocando todos os pontos. Só q dá um trabalho do cão fazer isso 49 vezes né. To pensando em como colocar um ciclo for no meio disso aí pra percorrer todos os pontos

    python...@googlegroups.com

---
Você está recebendo esta mensagem porque se inscreveu no grupo "Python Brasil" dos Grupos do Google.

Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python...@googlegroups.com.

[Sinval Júnior]

Muito bom Vanessa, 

Caso queira comparar com outra solução. Pode usar Grafo. 

Ao encaminhar esta mensagem, por favor:
1 - Apague meu endereço eletrônico;
2 - Encaminhe como Cópia Oculta (Cco ou BCc) aos seus destinatários. Dificulte assim a disseminação de vírus, spams e banners.

#=================================================================+
#!/usr/bin/env python
nome = 'Sinval Júnior'
email = 'sinvalju arroba gmail ponto com'
print nome
print email
#==================================================================+

python-brasi...@googlegroups.com
---
Você recebeu essa mensagem porque está inscrito no grupo "Python Brasil" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python-brasi...@googlegroups.com.
Para ver essa discussão na Web, acesse https://groups.google.com/d/msgid/python-brasil/913987c0-2139-4b04-9736-5c6252020322%40googlegroups.com.

[Vanessa Teixeira]

Começou a dar erro do nada!!

distR1 = asarray([distancia(30,12.5,30,10),distancia(30,12.5,30,15),distancia(30,12.5,30,17.5),distancia(30,12.5,30,20),distancia(30,12.5,30,22.5),distancia(30,12.5,30,25),distancia(30,12.5,27.5,10),distancia(30,12.5,27.5,12.5),distancia(30,12.5,27.5,15),distancia(30,12.5,27.5,17.5),distancia(30,12.5,27.5,20),distancia(30,12.5,27.5,22.5),distancia(30,12.5,27.5,25),distancia(30,10,25,10),distancia(30,10,25,12.5),distancia(30,10,25,15),distancia(30,10,25,17.5),distancia(30,10,25,20),distancia(30,10,25,22.5),distancia(30,10,25,25),distancia(30,10,22.5,10),distancia(30,12.5,22.5,12.5),distancia(30,12.5,22.5,15),distancia(30,12.5,22.5,17.5),distancia(30,12.5,22.5,20),distancia(30,12.5,22.5,22.5),distancia(30,12.5,22.5,25),distancia(30,12.5,20,10),distancia(30,12.5,20,12.5),distancia(30,12.5,20,15),distancia(30,12.5,20,17.5),distancia(30,12.5,20,20),distancia(30,12.5,20,22.5),distancia(30,12.5,20,25),distancia(30,12.5,17.5,10),distancia(30,12.5,17.5,12.5),distancia(30,12.5,17.5,15),distancia(30,12.5,17.5,17.5),distancia(30,12.5,17.5,20),distancia(30,12.5,17.5,22.5),distancia(30,12.5,17.5,25),distancia(30,12.5,15,10),distancia(30,12.5,15,12.5),distancia(30,12.5,15,15),distancia(30,12.5,15,17.5),distancia(30,12.5,15,20),distancia(30,12.5,15,22.5),distancia(30,12.5,15,25)])

         ^

SyntaxError: invalid syntax

Tava rodando antes e agora paro

python...@googlegroups.com

---
Você recebeu essa mensagem porque está inscrito no grupo "Python Brasil" dos Grupos do Google.

Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python...@googlegroups.com.

[Fabricio Michel Denes]

Olá Vanessa, 

para armazenar somente as distancias, você pode armazená-las em uma matriz

da seguinte forma:

P0 P1 P2 P3 ... P48

-------------------------------------------------

P0   | 0,00 2,50 2,50 5,00 ... 19,53

P1   | 2,50 0,00 5,00 7,50 ... 21,21

P2   | 2,50 5,00 0,00 2,50 ... 18,03

P3   | 5,00 7,50 2,50 0,00 ... 16,77

.      |         .              . .              .               . .

.      |         .              .               .              .               .                .

.      |         .              .               .              .               .                .

P48| 19,53 21,21 18,03 16,77 ...        0,00

se os seus dados estiverm ou puderam ser  salvos em formato .csv (Comma Separated Variable),

como exemplificado a seguir:

X;Y

30.0;12.5

30.0;10.0

30.0;15.0

30.0;17.5

30.0;20.0

30.0;22.5

30.0;25.0

27.5;10.0

27.5;12.5

27.5;15.0

27.5;17.5

27.5;20.0

27.5;22.5

27.5;25.0

25.0;10.0

25.0;12.5

25.0;15.0

25.0;17.5

25.0;20.0

25.0;22.5

25.0;25.0

22.5;10.0

22.5;12.5

22.5;15.0

22.5;17.5

22.5;20.0

22.5;22.5

22.5;25.0

20.0;10.0

20.0;12.5

20.0;15.0

20.0;17.5

20.0;20.0

20.0;22.5

20.0;25.0

17.5;10.0

17.5;12.5

17.5;15.0

17.5;17.5

17.5;20.0

17.5;22.5

17.5;25.0

15.0;10.0

15.0;12.5

15.0;15.0

15.0;17.5

15.0;20.0

15.0;22.5

15.0;25.0

o código a seguir salva a matriz de distancicas tanto no formato .csv quanto .xlsx (Excel)

import pandas as pd

import math 

def distancia(x_1,y_1,x_2,y_2):

    dist = math.sqrt((x_2-x_1)**2 + (y_2-y_1)**2)

    return dist

def cols_rows_names(qtd_pontos):

    names = []

    for i in range(0, qtd_pontos):

        names.append("P" + str(i))

    

    return names

#lê o arquivo com as coordenadas dos pontos

df = pd.read_csv("./pontos.csv",  sep=';')

#remove pontos duplicados (se houver)

df.drop_duplicates(inplace=True)

#ciar uma "matriz" (uma lista de listas) vazia

distancias = []

for indexP1, ponto1 in df.iterrows():

    

    #cria um vetor vazio

    distancias_entre_P1_e_demais_pontos = []

    

    for indexP2, ponto2 in df.iterrows():

        

        #Calcula as distancias e armazena no vetor

        distancias_entre_P1_e_demais_pontos.append(distancia(ponto1['X'],

            ponto1['Y'], ponto2['X'],  ponto2['Y']))

    

    #adiciona o vetor como linhas da matriz

    distancias.append(distancias_entre_P1_e_demais_pontos)

    

#converta a matriz para um dataframe da pandas

dfDistancias = pd.DataFrame.from_records(distancias)

#Cria um nome para as colunas do dataframe

dfDistancias.columns = cols_rows_names(len(df))

#Cria um nome para as linhas do dataframe

dfDistancias.index = cols_rows_names(len(df))

#Salva a matriz de distancias no formato csv

dfDistancias.to_csv("./Distancias.csv")

#Salva a matriz de distancias no formato excel (precisa do pacote openpyxl)

dfDistancias.to_excel("./Distancias.xlsx")

print("Finalizado")