Dans un réseau de points, supprimer points trop proches

Version imprimable

Bonjour,

J'ai un réseau de latitudes/longitude ci-dessous:

Code:

1
2
3
4
 
latitude_degres_init=[50.90778, 51.19047, 50.75686, 51.17059, 50.2414, 50.90233, 51.11861, 50.57397, 51.34806, 50.87667, 50.45392, 50.74944, 51.09472, 50.65397, 50.58583, 51.165, 50.51472, 51.18767, 50.897, 50.90828, 50.91139, 50.89, 50.46269, 50.82058, 50.63175, 50.64431, 51.19683, 50.96472, 50.92028, 50.82403, 50.48953, 51.22031, 51.16742, 50.478, 50.74722, 50.29917, 50.60222, 51.00306, 50.64917, 50.70944, 50.77933, 50.87997, 51.1825, 50.59278, 50.72306, 51.37083, 51.29131, 50.13, 50.63667, 50.87944, 51.23611, 49.52333, 49.83194, 50.63917, 51.195, 50.83806, 51.16667, 50.9125, 50.75194, 50.25389, 50.94528, 49.74167, 50.3725, 50.92694, 50.14389, 50.59306, 50.44278, 50.83306, 50.66278, 51.26944, 49.97861, 50.71957, 50.69389, 50.49694, 50.3775, 50.69583, 50.68917, 51.36585, 50.66222, 49.77583, 50.07778, 50.47333, 50.41778, 50.61806, 50.80639, 51.19056, 50.25278, 50.46944, 50.36722, 50.66958, 50.28278, 49.60111, 50.6825, 49.60833, 50.26667, 50.73944, 51.18944, 50.75783, 51.16833, 50.90139, 51.34083, 49.89167, 50.15278, 50.46, 50.57591, 51.09033, 50.24333, 50.94861, 50.75556, 51.30528, 51.18083, 50.81722, 51.12, 50.63639, 50.90139, 50.85278, 50.48806, 51.19889, 50.4575, 50.03583, 50.9475, 50.4825, 50.79194, 50.03417, 50.78167, 50.5525, 50.52972, 51.14417, 51.39417, 50.97, 51.26472, 51.01528]
 
longitude_degres_init=[4.13889, 4.47258, 4.76874, 5.46609, 4.65326, 4.53808, 4.84222, 3.83287, 3.35528, 5.13444, 4.44139, 4.64167, 2.65167, 5.47042, 5.71028, 4.18389, 5.62361, 4.46828, 4.51964, 4.50189, 4.49472, 4.49442, 4.46653, 3.21822, 5.43281, 5.44844, 2.86161, 3.49611, 4.61617, 3.22486, 4.55539, 3.01161, 4.56622, 5.91303, 3.71861, 6.13222, 6.25194, 4.17167, 5.84889, 3.21444, 4.28136, 4.36214, 5.44889, 5.25139, 4.60111, 3.36694, 4.27945, 4.37278, 6.20722, 4.02778, 3.6575, 6.35861, 5.33139, 5.90611, 4.99861, 5.50611, 4.57139, 3.63694, 4.77417, 5.54139, 3.61583, 5.86972, 6.285, 3.9925, 5.37361, 6.23806, 5.79417, 4.15861, 5.15361, 3.40667, 6.16639, 4.96746, 4.29083, 5.7625, 6.34833, 6.13639, 6.14028, 4.33761, 4.91417, 5.02111, 5.80694, 3.63333, 5.10194, 4.05667, 5.04528, 4.83833, 5.77389, 6.33639, 6.36611, 4.84704, 6.28861, 5.42056, 5.66556, 5.58417, 6.25, 3.48611, 4.46028, 4.767, 5.46972, 4.48444, 4.50417, 5.22389, 4.38722, 4.45278, 3.83098, 2.65283, 4.64583, 4.39194, 3.86389, 4.39056, 5.22083, 3.20444, 5.30722, 5.44278, 4.48444, 3.14722, 4.76889, 2.86222, 3.82028, 5.40417, 5.59056, 5.91028, 5.20167, 5.44, 4.95778, 5.855, 3.49444, 3.47556, 4.95917, 5.375, 4.75333, 5.52639]

Chaque [latitude_degres_init[i],longitude_degres_init[i]] représente un point donné sur la planète.
Or certains points sont très très proches.
Je souhaiterais donc éliminer tous les points qui sont trop proches. Je ne souhaite pas calculer la distance entre les points.
Un critère serait donc pas exemple:
si il y a moins de 0.5 d'écart dans la latitude et la longitude entre deux points, alors ne pas prendre le deuxième point.

Exemple:
point A (50.0, 3.4)
point B (50.1, 4)
--> les latitudes n'ont pas l'écart souhaité, on ne prends que A mais pas B

point A (50.0, 3.4)
point B (50.9, 3.5)
--> les longitudes n'ont pas l'écart souhaité, on ne prends que A mais pas B

point A (50.0, 3.4)
point B (50.4)
--> les latitudes et longitudes ont l'écart souhaité, on prend A et B

point A (50.0, 3.4)
point B (50.1, 3.5)
--> les longitudes et latitudes n'ont pas l'écart souhaité, on ne prend ni A ni B

Quand je dis "on prend", ça veut dire on stocke dans des variables latitudes_degres et longitude_degres.

Merci d'avance pour votre aide

02/06/2014, 15h13
wiztricks
Salut,

Je ne suis pas certain de comprendre la question.

Côté algo. à vous de voir ce que vous voulez.
Côté programmation, ce sont des tests basiques à écrire:
Code:

1 2 3 4 5 >>> a = (50.0, 3.4) >>> b=(50.1, 4) >>> if abs(a[0] - b[0]) < 0.5: print (a) ... (50.0, 3.4)
- W
02/06/2014, 15h21
Invité

Bonjour et merci pour cette réponse,

Le test est correct mais je voudrais tester aussi la deuxième coordonnée (longitude): faire un

Code:

and abs(a[1]-b[1])<0.5

Mon problème n'est pas dans le test mais plutôt dans le fait que je veux tester tous les points entre eux: le 1 er et le 2ème, le 1er et le 3ème, ..., le 1er et le dernier, le 2ème et le 3ème, le 2ème et le 4ème, ..., le 2ème et le dernier.... etc. (sans re-tester les même: ex: le 4ème et le 2ème que j'ai déjà testé via le 2ème et le 4ème)

Et ensuite, il faut remplir deux listes (latitude_degres et longitude_degres) avec les seuls points qui vérifient ces conditions.
Donc les listes finales doivent contenir des points tous au moins éloignés de 0.5 en latitude ET en longitude pour éviter les points trop rapprochés.

Je n'arrive pas à créer ces listes finales.
Avez-vous une idée?
02/06/2014, 16h43
wiztricks
Salut,

Vous pouvez regarder le générateur combination du module itertools:
Code:

1 2 3 4 >>> import itertools >>> list(itertools.combinations([1,2,3,4], 2)) [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] >>>
Il vous génère les paires 2 a 2 sans répétitions.

Après il faut adapter cela à votre cas, mais vous devriez pouvoir vous en sortir seul.

- W

Citation:

Envoyé par mp0777236

Bonjour,

J'ai un réseau de latitudes/longitude ci-dessous:

Code:

1
2
3
4
 
latitude_degres_init=[50.90778, 51.19047, 50.75686, 51.17059, 50.2414, 50.90233, 51.11861, 50.57397, 51.34806, 50.87667, 50.45392, 50.74944, 51.09472, 50.65397, 50.58583, 51.165, 50.51472, 51.18767, 50.897, 50.90828, 50.91139, 50.89, 50.46269, 50.82058, 50.63175, 50.64431, 51.19683, 50.96472, 50.92028, 50.82403, 50.48953, 51.22031, 51.16742, 50.478, 50.74722, 50.29917, 50.60222, 51.00306, 50.64917, 50.70944, 50.77933, 50.87997, 51.1825, 50.59278, 50.72306, 51.37083, 51.29131, 50.13, 50.63667, 50.87944, 51.23611, 49.52333, 49.83194, 50.63917, 51.195, 50.83806, 51.16667, 50.9125, 50.75194, 50.25389, 50.94528, 49.74167, 50.3725, 50.92694, 50.14389, 50.59306, 50.44278, 50.83306, 50.66278, 51.26944, 49.97861, 50.71957, 50.69389, 50.49694, 50.3775, 50.69583, 50.68917, 51.36585, 50.66222, 49.77583, 50.07778, 50.47333, 50.41778, 50.61806, 50.80639, 51.19056, 50.25278, 50.46944, 50.36722, 50.66958, 50.28278, 49.60111, 50.6825, 49.60833, 50.26667, 50.73944, 51.18944, 50.75783, 51.16833, 50.90139, 51.34083, 49.89167, 50.15278, 50.46, 50.57591, 51.09033, 50.24333, 50.94861, 50.75556, 51.30528, 51.18083, 50.81722, 51.12, 50.63639, 50.90139, 50.85278, 50.48806, 51.19889, 50.4575, 50.03583, 50.9475, 50.4825, 50.79194, 50.03417, 50.78167, 50.5525, 50.52972, 51.14417, 51.39417, 50.97, 51.26472, 51.01528]
 
longitude_degres_init=[4.13889, 4.47258, 4.76874, 5.46609, 4.65326, 4.53808, 4.84222, 3.83287, 3.35528, 5.13444, 4.44139, 4.64167, 2.65167, 5.47042, 5.71028, 4.18389, 5.62361, 4.46828, 4.51964, 4.50189, 4.49472, 4.49442, 4.46653, 3.21822, 5.43281, 5.44844, 2.86161, 3.49611, 4.61617, 3.22486, 4.55539, 3.01161, 4.56622, 5.91303, 3.71861, 6.13222, 6.25194, 4.17167, 5.84889, 3.21444, 4.28136, 4.36214, 5.44889, 5.25139, 4.60111, 3.36694, 4.27945, 4.37278, 6.20722, 4.02778, 3.6575, 6.35861, 5.33139, 5.90611, 4.99861, 5.50611, 4.57139, 3.63694, 4.77417, 5.54139, 3.61583, 5.86972, 6.285, 3.9925, 5.37361, 6.23806, 5.79417, 4.15861, 5.15361, 3.40667, 6.16639, 4.96746, 4.29083, 5.7625, 6.34833, 6.13639, 6.14028, 4.33761, 4.91417, 5.02111, 5.80694, 3.63333, 5.10194, 4.05667, 5.04528, 4.83833, 5.77389, 6.33639, 6.36611, 4.84704, 6.28861, 5.42056, 5.66556, 5.58417, 6.25, 3.48611, 4.46028, 4.767, 5.46972, 4.48444, 4.50417, 5.22389, 4.38722, 4.45278, 3.83098, 2.65283, 4.64583, 4.39194, 3.86389, 4.39056, 5.22083, 3.20444, 5.30722, 5.44278, 4.48444, 3.14722, 4.76889, 2.86222, 3.82028, 5.40417, 5.59056, 5.91028, 5.20167, 5.44, 4.95778, 5.855, 3.49444, 3.47556, 4.95917, 5.375, 4.75333, 5.52639]

Bonjour,

Je me suis amusé à bidouiller ceci :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
# merge: fusionne des valeurs proches
 
def merge (vlist, radius):
    """
        merges values in vlist lower than radius
    """
    values = sorted(vlist)
    merged = list()
    index = 0
    while index < len(values):
        value = values[index]
        merged.append(value)
        index += 1
        while index < len(values):
            next_value = values[index]
            # TRON console
            print(
                "value:", value,
                "next_value:", next_value,
                "delta:", round(next_value - value, 3)
            )
            if abs(next_value - value) > radius:
                break
            # end if
            index += 1
        # end while
    # end while
    return merged
# end def
 
 
latitude_degres_init = [
    50.90778, 51.19047, 50.75686, 51.17059, 50.2414, 50.90233,
    51.11861, 50.57397, 51.34806, 50.87667, 50.45392, 50.74944,
    51.09472, 50.65397, 50.58583, 51.165, 50.51472, 51.18767,
    50.897, 50.90828, 50.91139, 50.89, 50.46269, 50.82058, 50.63175,
    50.64431, 51.19683, 50.96472, 50.92028, 50.82403, 50.48953,
    51.22031, 51.16742, 50.478, 50.74722, 50.29917, 50.60222,
    51.00306, 50.64917, 50.70944, 50.77933, 50.87997, 51.1825,
    50.59278, 50.72306, 51.37083, 51.29131, 50.13, 50.63667,
    50.87944, 51.23611, 49.52333, 49.83194, 50.63917, 51.195,
    50.83806, 51.16667, 50.9125, 50.75194, 50.25389, 50.94528,
    49.74167, 50.3725, 50.92694, 50.14389, 50.59306, 50.44278,
    50.83306, 50.66278, 51.26944, 49.97861, 50.71957, 50.69389,
    50.49694, 50.3775, 50.69583, 50.68917, 51.36585, 50.66222,
    49.77583, 50.07778, 50.47333, 50.41778, 50.61806, 50.80639,
    51.19056, 50.25278, 50.46944, 50.36722, 50.66958, 50.28278,
    49.60111, 50.6825, 49.60833, 50.26667, 50.73944, 51.18944,
    50.75783, 51.16833, 50.90139, 51.34083, 49.89167, 50.15278,
    50.46, 50.57591, 51.09033, 50.24333, 50.94861, 50.75556,
    51.30528, 51.18083, 50.81722, 51.12, 50.63639, 50.90139,
    50.85278, 50.48806, 51.19889, 50.4575, 50.03583, 50.9475,
    50.4825, 50.79194, 50.03417, 50.78167, 50.5525, 50.52972,
    51.14417, 51.39417, 50.97, 51.26472, 51.01528
]
 
longitude_degres_init = [
    4.13889, 4.47258, 4.76874, 5.46609, 4.65326, 4.53808, 4.84222,
    3.83287, 3.35528, 5.13444, 4.44139, 4.64167, 2.65167, 5.47042,
    5.71028, 4.18389, 5.62361, 4.46828, 4.51964, 4.50189, 4.49472,
    4.49442, 4.46653, 3.21822, 5.43281, 5.44844, 2.86161, 3.49611,
    4.61617, 3.22486, 4.55539, 3.01161, 4.56622, 5.91303, 3.71861,
    6.13222, 6.25194, 4.17167, 5.84889, 3.21444, 4.28136, 4.36214,
    5.44889, 5.25139, 4.60111, 3.36694, 4.27945, 4.37278, 6.20722,
    4.02778, 3.6575, 6.35861, 5.33139, 5.90611, 4.99861, 5.50611,
    4.57139, 3.63694, 4.77417, 5.54139, 3.61583, 5.86972, 6.285,
    3.9925, 5.37361, 6.23806, 5.79417, 4.15861, 5.15361, 3.40667,
    6.16639, 4.96746, 4.29083, 5.7625, 6.34833, 6.13639, 6.14028,
    4.33761, 4.91417, 5.02111, 5.80694, 3.63333, 5.10194, 4.05667,
    5.04528, 4.83833, 5.77389, 6.33639, 6.36611, 4.84704, 6.28861,
    5.42056, 5.66556, 5.58417, 6.25, 3.48611, 4.46028, 4.767,
    5.46972, 4.48444, 4.50417, 5.22389, 4.38722, 4.45278, 3.83098,
    2.65283, 4.64583, 4.39194, 3.86389, 4.39056, 5.22083, 3.20444,
    5.30722, 5.44278, 4.48444, 3.14722, 4.76889, 2.86222, 3.82028,
    5.40417, 5.59056, 5.91028, 5.20167, 5.44, 4.95778, 5.855,
    3.49444, 3.47556 , 4.95917, 5.375, 4.75333, 5.52639
]
 
 
# init dictionnaire de référence (latitude: longitude)
 
gps_locations = dict(zip(latitude_degres_init, longitude_degres_init))
 
# fusion des latitudes
 
latitudes = merge(gps_locations.keys(), radius=0.5)
 
print("\nsorted and merged latitudes:", latitudes)
 
clean_up = dict()
 
for latitude in latitudes:
 
    clean_up[latitude] = gps_locations[latitude]
 
# end for
 
# update GPS locations
 
gps_locations = clean_up
 
print("\nnew GPS locations (latitude: longitude):\n\n", gps_locations)
 
# fusion des longitudes
 
longitudes = merge(gps_locations.values(), radius=0.5)
 
print("\nsorted and merged longitudes:", longitudes)
 
clean_up = dict()
 
for latitude, longitude in gps_locations.items():
 
    if longitude in longitudes:
 
        clean_up[latitude] = longitude
 
        longitudes.remove(longitude)
 
    # end if
 
# end for
 
# update GPS locations
 
gps_locations = clean_up
 
del clean_up
 
# résultats
 
latitudes = gps_locations.keys()
 
longitudes = gps_locations.values()
 
print("\nnew GPS locations (latitude: longitude):\n\n", gps_locations)

Je ne sais pas si c'est bien ce que vous cherchez, en tout cas, je me suis bien amusé. :mrgreen: ;)

@+.

Salut,

Une question se pose, les données ne sont pas classées par ordre de grandeur, ce qui signifie que les éliminations de données seront aussi tributaires de leur ordre.

Exemple:
[lat1, lat2, lat3, lat4, lat5, ...]
[lon1, lon2, lon3, lon4, lon5, ...]

Si la paire (lat2, lon2) élimine la paire (lat3, lon3) et qu'ensuite la paire (lat1, lon1) élimine la paire (lat2, lon2), alors peut-être que (lat3, lon3) n'aurait pas du être éliminée puisque suffisament éloignée de la première.

Autrement expliqué, l'élimination est importante - voir ma proposition de code - mais il y a certainement des coordonnées qui pourraient y être replacées parce que celles qui les ont écartées ont elle-même été écartées.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
# -*- coding: utf-8 -*-
 
import time
 
latitude_degres_init=[50.90778, 51.19047, 50.75686, 51.17059, 50.2414, 50.90233, 51.11861, 50.57397, 51.34806, 50.87667, 50.45392, 50.74944, 51.09472, 50.65397, 50.58583, 51.165, 50.51472, 51.18767, 50.897, 50.90828, 50.91139, 50.89, 50.46269, 50.82058, 50.63175, 50.64431, 51.19683, 50.96472, 50.92028, 50.82403, 50.48953, 51.22031, 51.16742, 50.478, 50.74722, 50.29917, 50.60222, 51.00306, 50.64917, 50.70944, 50.77933, 50.87997, 51.1825, 50.59278, 50.72306, 51.37083, 51.29131, 50.13, 50.63667, 50.87944, 51.23611, 49.52333, 49.83194, 50.63917, 51.195, 50.83806, 51.16667, 50.9125, 50.75194, 50.25389, 50.94528, 49.74167, 50.3725, 50.92694, 50.14389, 50.59306, 50.44278, 50.83306, 50.66278, 51.26944, 49.97861, 50.71957, 50.69389, 50.49694, 50.3775, 50.69583, 50.68917, 51.36585, 50.66222, 49.77583, 50.07778, 50.47333, 50.41778, 50.61806, 50.80639, 51.19056, 50.25278, 50.46944, 50.36722, 50.66958, 50.28278, 49.60111, 50.6825, 49.60833, 50.26667, 50.73944, 51.18944, 50.75783, 51.16833, 50.90139, 51.34083, 49.89167, 50.15278, 50.46, 50.57591, 51.09033, 50.24333, 50.94861, 50.75556, 51.30528, 51.18083, 50.81722, 51.12, 50.63639, 50.90139, 50.85278, 50.48806, 51.19889, 50.4575, 50.03583, 50.9475, 50.4825, 50.79194, 50.03417, 50.78167, 50.5525, 50.52972, 51.14417, 51.39417, 50.97, 51.26472, 51.01528]
 
longitude_degres_init=[4.13889, 4.47258, 4.76874, 5.46609, 4.65326, 4.53808, 4.84222, 3.83287, 3.35528, 5.13444, 4.44139, 4.64167, 2.65167, 5.47042, 5.71028, 4.18389, 5.62361, 4.46828, 4.51964, 4.50189, 4.49472, 4.49442, 4.46653, 3.21822, 5.43281, 5.44844, 2.86161, 3.49611, 4.61617, 3.22486, 4.55539, 3.01161, 4.56622, 5.91303, 3.71861, 6.13222, 6.25194, 4.17167, 5.84889, 3.21444, 4.28136, 4.36214, 5.44889, 5.25139, 4.60111, 3.36694, 4.27945, 4.37278, 6.20722, 4.02778, 3.6575, 6.35861, 5.33139, 5.90611, 4.99861, 5.50611, 4.57139, 3.63694, 4.77417, 5.54139, 3.61583, 5.86972, 6.285, 3.9925, 5.37361, 6.23806, 5.79417, 4.15861, 5.15361, 3.40667, 6.16639, 4.96746, 4.29083, 5.7625, 6.34833, 6.13639, 6.14028, 4.33761, 4.91417, 5.02111, 5.80694, 3.63333, 5.10194, 4.05667, 5.04528, 4.83833, 5.77389, 6.33639, 6.36611, 4.84704, 6.28861, 5.42056, 5.66556, 5.58417, 6.25, 3.48611, 4.46028, 4.767, 5.46972, 4.48444, 4.50417, 5.22389, 4.38722, 4.45278, 3.83098, 2.65283, 4.64583, 4.39194, 3.86389, 4.39056, 5.22083, 3.20444, 5.30722, 5.44278, 4.48444, 3.14722, 4.76889, 2.86222, 3.82028, 5.40417, 5.59056, 5.91028, 5.20167, 5.44, 4.95778, 5.855, 3.49444, 3.47556, 4.95917, 5.375, 4.75333, 5.52639]
 
begin = time.clock()
 
lats = latitude_degres_init
longs = longitude_degres_init
 
def find_nearest(start):
    discarded = []
    for idx, lat in enumerate(lats[start+1:]):
        if abs(lats[start] - lat) < 0.5 and abs(longs[start] - longs[idx+start+1]) < 0.5:
            discarded.append(idx+start+1)
    return discarded
 
pos = 0
while 1:
    nearest = find_nearest(pos)
    for i in reversed(nearest):
        lats.pop(i)
        longs.pop(i)
    pos += 1
    if pos >= len(lats) - 1:
        break
 
print lats
print longs
print 'Done at:', time.clock() - begin

Code:

1
2
3
4
 
[50.90778, 50.75686, 51.17059, 50.2414, 51.34806, 51.09472, 50.65397, 50.82058, 50.29917, 49.52333, 49.83194, 51.39417]
[4.13889, 4.76874, 5.46609, 4.65326, 3.35528, 2.65167, 5.47042, 3.21822, 6.13222, 6.35861, 5.33139, 4.95917]
Done at: 0.0

02/06/2014, 22h18
Invité

Merci beaucoup à tous.

Vos propositions sont très intéressantes et j'apprends sans cesse de nouvelles choses sur Python grâce aux diverses propositions.

J'ai reporté sur un graph les valeurs de latitude/longitude. Les points les mieux répartis par rapport à la distribution initale (tous les points) ont été pour la deuxième proposition. Merci beaucoup.

En tout cas, ravie que tarball69 vous vous soyez amusé.

Bonne soirée!
03/06/2014, 08h07
Invité

Perso, je n'avais pas compris votre 3ème indication :

Citation:

point A (50.0, 3.4)
point B (50.4)
--> les latitudes et longitudes ont l'écart souhaité, on prend A et B

Le point B sonne bizarre, j'ai donc écarté cette hypothèse. ;)

@VinsS : super bien vu l'algo, chapeau ! :ccool:

Merci de cliquer :resolu: si le problème a trouvé solution ou si cette discussion est close.

@+.
03/06/2014, 13h20
plxpy

Bonjour,

Je voudrais te proposer une approche plus "géographique" mais j'ai deux questions préalables :

Citation:

Envoyé par mp0777236

Je ne souhaite pas calculer la distance entre les points.

Pourquoi ? C'est interdit ? Ou c'est la difficulté (apparente) qui t'a fait y renoncer ?

Deuxième question : 0.5 degré c'est énorme. A la (grosse) louche, c'est de l'ordre de 50 km. C'est réellement ton besoin ou c'est une valeur "comme ça" ? (Je n'ai pas fait l'exercice en entier mais rien qu'en visualisant tes points, avec 0.5 degré, il ne va plus te rester grand chose !)
03/06/2014, 14h38
VinsS

Citation:

Envoyé par plxpy

Bonjour,
0.5 degré c'est énorme. ... il ne va plus te rester grand chose !)

Il ne reste plus grand chose effectivement, sur 132 points au départ il en subsiste 12, principalement parce qu'ils s'éliminent de proche en proche comme je l'explique dans mon post.

En fait cet exercice peut se voir comme le jeu de la vie, maintenir une population minimale dans une zone données. Et c'est pas inintéressant.
04/06/2014, 16h48
plxpy

@VinsS

J'ai regardé attentivement ton code, d'autant plus que, avec les données initiales du PO, je ne trouve pas 12 mais 1 seul et même gros paquet au final. Avec 132 points au départ, c'est fastidieux de tout se palucher à la mano pour être certain de ce qu'on avance, mais j'ai trouvé un contre exemple.

Avec 3 points : longs = [ 0., 0.2, 0.6 ] et les 3 latitudes égales à 0.

Ton algo retient 2 groupes alors qu'avec cette fameuse "transitivité" (A confondu avec B, B confondu avec C alors A confondu avec C même si A et C, directement, ne sont pas proches) il ne devrait y en avoir qu'un seul.

Je posterai mon code prochainement.
04/06/2014, 16h59
Invité

Salut,

0,5° c'est correct comme ordre de grandeur donc c'est bon.

Effectivement il reste peu de points mais c'est suffisant (temps de calcul des traitements suivant augmente très vite avec le nombre de points).

Effectivement, erreur sur mon troisième couple, désolée. point B (50.5, 4.9) par exemple

Pour plxpy: Ce n'est pas interdit de calculer la distance et d'ailleurs je le fais par la suite. Mais ma base de donnée totale contient 5000 points donc calculer les distances entre deux points pour tous les points, ça fait factoriel 5000 calculs. C'est pour ça que je souhaite réduire mon nombre de points avant de calculer les distance. Ca aurait été trop simple ;)
04/06/2014, 17h15
plxpy

Citation:

Envoyé par mp0777236

0,5° c'est correct comme ordre de grandeur donc c'est bon.

Je n'ai strictement rien compris ! C'est bon donc c'est bon ?????
Peux-tu t'étendre un peu plus sur le contexte ?
04/06/2014, 18h04
wiztricks

Citation:

Envoyé par mp0777236

Pour plxpy: Ce n'est pas interdit de calculer la distance et d'ailleurs je le fais par la suite. Mais ma base de donnée totale contient 5000 points donc calculer les distances entre deux points pour tous les points, ça fait factoriel 5000 calculs. C'est pour ça que je souhaite réduire mon nombre de points avant de calculer les distance. Ca aurait été trop simple ;)

A votre avis, pourquoi a-t-on créé des bases de données orientées système d'information géographique ?

- W
04/06/2014, 18h07
Invité

Citation:

Envoyé par wiztricks

A votre avis, pourquoi a-t-on créé des bases de données orientées système d'information géographique ?

- W

Je suis désolée mais je n'ai pas compris.
De toute façon, j'ai utilisé l'une des solutions proposées plus haut. Merci beaucoup.

Bonne soirée
04/06/2014, 22h27
dividee

Citation:

Envoyé par mp0777236

Pour plxpy: Ce n'est pas interdit de calculer la distance et d'ailleurs je le fais par la suite. Mais ma base de donnée totale contient 5000 points donc calculer les distances entre deux points pour tous les points, ça fait factoriel 5000 calculs. C'est pour ça que je souhaite réduire mon nombre de points avant de calculer les distance. Ca aurait été trop simple ;)

Euh non, avec 5000 points ça fait (5000*4999)/2 calculs, c'est beaucoup beaucoup moins que la factorielle de 5000.
04/06/2014, 22h31
Invité

Citation:

Envoyé par dividee

Euh non, avec 5000 points ça fait (5000*4999)/2 calculs, c'est beaucoup beaucoup moins que la factorielle de 5000.

C'est vrai, honteuse erreur de ma part, merci de m'avoir corrigée ;)
Mais c'est quand même trop de calculs

Je sais que la discussion est résolue, mais pour m'amuser j'ai codé une solution qui utilise l'algorithme de clustering k-means.
k est le nombre de points que l'on souhaite obtenir. Ce ne sont pas des points qui sont dans les données initiales, mais les barycentres des partitions.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
latitudes = [50.90778, 51.19047, 50.75686, 51.17059, 50.2414, 50.90233, 51.11861, 50.57397, 51.34806, 50.87667, 50.45392, 50.74944, 51.09472, 50.65397, 50.58583, 51.165, 50.51472, 51.18767, 50.897, 50.90828, 50.91139, 50.89, 50.46269, 50.82058, 50.63175, 50.64431, 51.19683, 50.96472, 50.92028, 50.82403, 50.48953, 51.22031, 51.16742, 50.478, 50.74722, 50.29917, 50.60222, 51.00306, 50.64917, 50.70944, 50.77933, 50.87997, 51.1825, 50.59278, 50.72306, 51.37083, 51.29131, 50.13, 50.63667, 50.87944, 51.23611, 49.52333, 49.83194, 50.63917, 51.195, 50.83806, 51.16667, 50.9125, 50.75194, 50.25389, 50.94528, 49.74167, 50.3725, 50.92694, 50.14389, 50.59306, 50.44278, 50.83306, 50.66278, 51.26944, 49.97861, 50.71957, 50.69389, 50.49694, 50.3775, 50.69583, 50.68917, 51.36585, 50.66222, 49.77583, 50.07778, 50.47333, 50.41778, 50.61806, 50.80639, 51.19056, 50.25278, 50.46944, 50.36722, 50.66958, 50.28278, 49.60111, 50.6825, 49.60833, 50.26667, 50.73944, 51.18944, 50.75783, 51.16833, 50.90139, 51.34083, 49.89167, 50.15278, 50.46, 50.57591, 51.09033, 50.24333, 50.94861, 50.75556, 51.30528, 51.18083, 50.81722, 51.12, 50.63639, 50.90139, 50.85278, 50.48806, 51.19889, 50.4575, 50.03583, 50.9475, 50.4825, 50.79194, 50.03417, 50.78167, 50.5525, 50.52972, 51.14417, 51.39417, 50.97, 51.26472, 51.01528]
longitudes = [4.13889, 4.47258, 4.76874, 5.46609, 4.65326, 4.53808, 4.84222, 3.83287, 3.35528, 5.13444, 4.44139, 4.64167, 2.65167, 5.47042, 5.71028, 4.18389, 5.62361, 4.46828, 4.51964, 4.50189, 4.49472, 4.49442, 4.46653, 3.21822, 5.43281, 5.44844, 2.86161, 3.49611, 4.61617, 3.22486, 4.55539, 3.01161, 4.56622, 5.91303, 3.71861, 6.13222, 6.25194, 4.17167, 5.84889, 3.21444, 4.28136, 4.36214, 5.44889, 5.25139, 4.60111, 3.36694, 4.27945, 4.37278, 6.20722, 4.02778, 3.6575, 6.35861, 5.33139, 5.90611, 4.99861, 5.50611, 4.57139, 3.63694, 4.77417, 5.54139, 3.61583, 5.86972, 6.285, 3.9925, 5.37361, 6.23806, 5.79417, 4.15861, 5.15361, 3.40667, 6.16639, 4.96746, 4.29083, 5.7625, 6.34833, 6.13639, 6.14028, 4.33761, 4.91417, 5.02111, 5.80694, 3.63333, 5.10194, 4.05667, 5.04528, 4.83833, 5.77389, 6.33639, 6.36611, 4.84704, 6.28861, 5.42056, 5.66556, 5.58417, 6.25, 3.48611, 4.46028, 4.767, 5.46972, 4.48444, 4.50417, 5.22389, 4.38722, 4.45278, 3.83098, 2.65283, 4.64583, 4.39194, 3.86389, 4.39056, 5.22083, 3.20444, 5.30722, 5.44278, 4.48444, 3.14722, 4.76889, 2.86222, 3.82028, 5.40417, 5.59056, 5.91028, 5.20167, 5.44, 4.95778, 5.855, 3.49444, 3.47556, 4.95917, 5.375, 4.75333, 5.52639]
 
points = list(zip(latitudes, longitudes))
 
def sqdist(p1, p2):
    dx = p1[0] - p2[0]
    dy = p1[1] - p2[1]
    return dx * dx + dy * dy
 
def assign(pts, centers):
    assn = [[] for c in centers]
    for p in pts:
        m = min(range(len(centers)), key=lambda n: sqdist(p,centers[n]))
        assn[m].append(p)
    return assn
 
def update(assn):
    centers = []
    for cluster in assn:
        if len(cluster) > 0:
            lat = sum(p[0] for p in cluster)
            lon = sum(p[1] for p in cluster)
            centers.append((lat / len(cluster), lon / len(cluster)))
    return centers
 
k = 15
import random
centers = random.sample(points, k)
old_centers = False
steps = 0
while centers != old_centers and steps < 20:
    steps += 1
    assn = assign(points, centers)
    old_centers = centers
    centers = update(assn)
 
print(centers)

Evidemment, ce n'est pas correct de calculer la distance entre les points comme s'il s'agissait de coordonnées cartésiennes, mais bon, c'est un détail :p

Comme promis, voici comment je traite habituellement ce "problème" de points équivalents, à la façon de déterminer l'équivalence de deux points près.
(les explications sont les commentaires dans le code)

Et je ne trouve qu'un seul et même gros paquet : tous les points sont équivalents, de proche en proche.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# -*- coding: utf-8 -*-
 
import time
 
latitude_degres_init  = [50.90778, 51.19047, 50.75686, 51.17059, 50.2414, 50.90233, 51.11861, 50.57397, 51.34806, 50.87667, 50.45392, 50.74944, 51.09472, 50.65397, 50.58583, 51.165, 50.51472, 51.18767, 50.897, 50.90828, 50.91139, 50.89, 50.46269, 50.82058, 50.63175, 50.64431, 51.19683, 50.96472, 50.92028, 50.82403, 50.48953, 51.22031, 51.16742, 50.478, 50.74722, 50.29917, 50.60222, 51.00306, 50.64917, 50.70944, 50.77933, 50.87997, 51.1825, 50.59278, 50.72306, 51.37083, 51.29131, 50.13, 50.63667, 50.87944, 51.23611, 49.52333, 49.83194, 50.63917, 51.195, 50.83806, 51.16667, 50.9125, 50.75194, 50.25389, 50.94528, 49.74167, 50.3725, 50.92694, 50.14389, 50.59306, 50.44278, 50.83306, 50.66278, 51.26944, 49.97861, 50.71957, 50.69389, 50.49694, 50.3775, 50.69583, 50.68917, 51.36585, 50.66222, 49.77583, 50.07778, 50.47333, 50.41778, 50.61806, 50.80639, 51.19056, 50.25278, 50.46944, 50.36722, 50.66958, 50.28278, 49.60111, 50.6825, 49.60833, 50.26667, 50.73944, 51.18944, 50.75783, 51.16833, 50.90139, 51.34083, 49.89167, 50.15278, 50.46, 50.57591, 51.09033, 50.24333, 50.94861, 50.75556, 51.30528, 51.18083, 50.81722, 51.12, 50.63639, 50.90139, 50.85278, 50.48806, 51.19889, 50.4575, 50.03583, 50.9475, 50.4825, 50.79194, 50.03417, 50.78167, 50.5525, 50.52972, 51.14417, 51.39417, 50.97, 51.26472, 51.01528]
longitude_degres_init = [4.13889, 4.47258, 4.76874, 5.46609, 4.65326, 4.53808, 4.84222, 3.83287, 3.35528, 5.13444, 4.44139, 4.64167, 2.65167, 5.47042, 5.71028, 4.18389, 5.62361, 4.46828, 4.51964, 4.50189, 4.49472, 4.49442, 4.46653, 3.21822, 5.43281, 5.44844, 2.86161, 3.49611, 4.61617, 3.22486, 4.55539, 3.01161, 4.56622, 5.91303, 3.71861, 6.13222, 6.25194, 4.17167, 5.84889, 3.21444, 4.28136, 4.36214, 5.44889, 5.25139, 4.60111, 3.36694, 4.27945, 4.37278, 6.20722, 4.02778, 3.6575, 6.35861, 5.33139, 5.90611, 4.99861, 5.50611, 4.57139, 3.63694, 4.77417, 5.54139, 3.61583, 5.86972, 6.285, 3.9925, 5.37361, 6.23806, 5.79417, 4.15861, 5.15361, 3.40667, 6.16639, 4.96746, 4.29083, 5.7625, 6.34833, 6.13639, 6.14028, 4.33761, 4.91417, 5.02111, 5.80694, 3.63333, 5.10194, 4.05667, 5.04528, 4.83833, 5.77389, 6.33639, 6.36611, 4.84704, 6.28861, 5.42056, 5.66556, 5.58417, 6.25, 3.48611, 4.46028, 4.767, 5.46972, 4.48444, 4.50417, 5.22389, 4.38722, 4.45278, 3.83098, 2.65283, 4.64583, 4.39194, 3.86389, 4.39056, 5.22083, 3.20444, 5.30722, 5.44278, 4.48444, 3.14722, 4.76889, 2.86222, 3.82028, 5.40417, 5.59056, 5.91028, 5.20167, 5.44, 4.95778, 5.855, 3.49444, 3.47556, 4.95917, 5.375, 4.75333, 5.52639]
 
# equiv : True si deux points sont proches (au SEUIL donné) et considérés comme équivalents
SEUIL = 0.5
equiv = lambda xya, xyb: max(abs(xya[0]-xyb[0]), abs(xya[1]-xyb[1])) < SEUIL
 
begin = time.clock()
 
points = zip(longitude_degres_init, latitude_degres_init)
 
# constitution de paquets de points équivalents (je travaille avec les indices)
# pour un point (indice) donné, le paquet contient son indice et les indices
# SUPERIEURS (pour ne pas faire les choses en double) des points qui lui sont
# équivalents. Ces paquets NE sont PAS les paquets définitifs.
 
equivalences = [ [p] for p in range(len(points)) ]
for a, ptA in enumerate(points[:-1]):
    for b, ptB in enumerate(points[a+1:], start=a+1):
        if equiv(ptA, ptB):
            equivalences[a].append(b)
 
# passage ("cast") aux ensembles, non pas pour supprimer d'éventuels doublons
# (il n'y en a pas) mais utiliser les méthodes intersection et union de set
 
equivalences = [ set(elt) for elt in equivalences ]
 
# A RECULONS (indispensable), je tente de fusionner un paquet de points
# équivalents avec un autre paquet (indice inférieur) qui possède un (au
# moins) point en commun. Quand il y a fusion, on détruit le paquet courant
 
for a in range(len(equivalences)-1, 0, -1):
    for b in range(a-1, -1, -1):
        if equivalences[a].intersection(equivalences[b]):
            equivalences[b] = equivalences[b].union(equivalences[a])
            del equivalences[a]
            break
 
print len(equivalences)
 
# petite vérif : a-t-on toujours tous les points/indices ?
indices = reduce(lambda a, b: a.union(b), equivalences)
assert indices == set(range(len(points)))
 
print 'Done at:', time.clock() - begin