sélectionner des points GPS aléatoires

Version imprimable

22/03/2012, 17h14
fadex

sélectionner des points GPS aléatoires

Bonjour

Je veux écrire un programme php pour sélectionner 16 points aléatoires à partir de 400 points dans ma base de données

(tableau de points: id - Titre - latitude - longitude).

exemple de point :
id : 1
titre : un titre
latitude : 37.9824
longitude: -87.5781547

exigences, 16 points aléatoires, dont chaque point est au moins à 1km de l'autre point.

par exemple:

si le programme sélectionne 3 points A, B et C.

la distance entre les point doivent être:

A et B >= 1 KM

A et C >= 1 KM

B et C >= 1 km

ps : j'ai crée une table distance sur la quelle il y a la distance entre chaque deux points :

exemple :

point_1 : 1
point_2 : 2
distance : 1200

point_1 : 3
point_2 : 6
distance : 800

ma question est comment sélectionner les 16 points aléatoires, dont chaque point est au moins à 1km de l'autre point.

Merci d'avance
22/03/2012, 17h34
Benjamin Delespierre

Quelle est ta question ?
23/03/2012, 00h27
fadex

ma question est comment sélectionner les 16 points aléatoires, dont chaque point est au moins à 1km de l'autre point.
23/03/2012, 12h08
Benjamin Delespierre

Une solution simple serait de récupérer toutes les cordonnées éloignées d'1km, de les mettre en cache, de les mélanger et d'en sortir 16 :)
24/03/2012, 17h58
fadex

tu peux développer plus votre solution ( simple ) ??
- vu que je ne pence pas que c aussi simple :)

Je pensais à quelque chose dans ce genre (en utilisant PDO):

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<?php
define("CACHE_FILE", "coords.cache");
 
if (!is_file(CACHE_FILE) || !@include(CACHE_FILE)) {
	$query = "SELECT x,y,z FROM table WHERE blah";
	if (!$results = $pdo->query($query))
		throw new RuntimeException("Query execution fails");
	$data = $results->fetchAll(PDO::FETCH_ASSOC);
	// écriture du cache
	if (!file_put_contents(CACHE_FILE, '<?php $data='.var_export($data,true).';')) {
		throw new RuntimeException("Could not write cache file " . CACHE_FILE);
	}
}
 
// sait on jamais
!empty($data) or $data = array();
 
shuffle($data);
$firsts = array_slice($data, 0, 16);
 
var_dump($firsts);

A toi de jouer ;)

27/03/2012, 09h46
Marc3001

Je pense que tu dois y aller point par point.

1/ Tu récupères un point aléatoire en base (via point)
2/ Tu récupères tous les points à au moins 1 km de celui récupéré en 1/ (via distance )
3/ Tu sélectionnes un point (ou plusieurs) au hasard dans la liste en 2/
4/ Tu recommences depuis le 1/ avec le (ou les) points récupéré(s) en 3/
27/03/2012, 10h10
Benjamin Delespierre

Tu peux aussi utiliser l'algorithme de Dijkstra, ce serait marrant en plus à implémenter :)
27/03/2012, 11h19
Marc3001

Citation:

Envoyé par Benjamin Delespierre

Tu peux aussi utiliser l'algorithme de Dijkstra, ce serait marrant en plus à implémenter :)

J'suis pas sûr que ça colle avec le besoin....
27/03/2012, 11h33
Benjamin Delespierre

Non bien entendu, ce serait utile s'il voulait trouver un parcours de points éloignés de 1km (en modifiant un peu l'algo) plutôt qu'un parcours aléatoire.

lol benjamin scéance :sm:

dijkstra ou A* sont des algorithmes de parcours de GRAPH... :mouarf:

tu te fais une procédure stockée qui:

crée une table temporaire temp(idpoint int)
tant que count(idpoint)<16 faire:
- utiliser la requête de génération de point
- si un point a été généré l'insérer
faire un select sur la table temporaire

la requête serait un truc du genre:

Code:

1
2
3
4
5
6
7
8
9
10
 
select count(t.idpoint)
from temp t
inner join distance d on d.point_1=t.idpoint
and d.point_2=
    (select point_2
    from distance
    where distance>1000 and point_1>=(select max(id)*rand() from points)
    limit 1)
and d.distance>1000

mais vu que l'optimiseur mysql bug parfois avec les sous requête on va diviser pour mieux régner...

la procédure serait:

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
delimiter $$
drop procedure points$$
create procedure points()
begin
    declare nb,i int default 0;
    declare b bool;
    create temporary table temp(idpoint int);
    while nb<16 do
        -- on récupère un point au hasard qu'on stocke dans i
        select point_2 into i
        from distance
        where distance>1000
            and point_1>=(select max(id)*rand() from points)
        limit 1;
        if nb=0 then
            insert into temp(idpoint)values(i);
        else
            -- on teste si le point est à 1000m mini de ceux déjà sélectionné
            select count(t.idpoint) into b
            from temp t
            inner join distance d on d.point_1=t.idpoint
                and d.point_2=i
            and d.distance>1000;
            if b then
                insert into temp(idpoint)values(i);
            end if;
        end if;
    end while;
    select idpoints from temp;
end$$
delimiter ;
-- appel
call points;

ça devrait marcher... j'ai pas testé...

28/03/2012, 00h13
stealth35

ta table distance est complète ?

si t'as 3 points A B C

y'a :

A B distance
A C distance
B A distance
B C distance
C A distance
C B distance

?

sinon 16 requêtes c'est pas la mort, vaut mieux lui passer plein de petites requête qu'une grosse
28/03/2012, 00h34
ericd69

logiquement il a environ 400²=160000 combinaisons donc lignes (en fait, la formule exacte est n(n-1) donc 400*399=159600 lignes exactement vu qu'il a 400 points) :zoubi:

mais le pb c'est que tous les points sélectionnés doivent être à 1000m mini les uns des autres... d'où la boucle pour retirer des points tant qu'on en a pas 16 qui répondent à la contrainte...

en plus là y a 1 seul échange mysql/php donc moins de bande passante et de latence à cause de ça
:ccool:
28/03/2012, 09h35
stealth35

Citation:

Envoyé par ericd69

en plus là y a 1 seul échange mysql/php donc moins de bande passante et de latence à cause de ça:ccool:

non ça mettra plus de temps
28/03/2012, 10h00
Marc3001

Citation:

Envoyé par stealth35

non ça mettra plus de temps

Je pense que c'est tellement dépendant des requêtes (jointures, tris,...) que seul un bench ou une analyse des plans d'exec peux répondre à cette question.
28/03/2012, 15h54
NoSmoking

Bonjour,

comme l'a dit Marc3001

Citation:

1/ Tu récupères un point aléatoire en base (via point)

puis tu fais ta requête comme vu sur ce post http://www.developpez.net/forums/d11...s/#post6266103, en adaptant la distance et le nombre de retour.
28/03/2012, 19h10
ericd69
Citation:

Envoyé par stealth35

non ça mettra plus de temps

Tu te bases sur quoi pour dire ça? :?

Petite réflexion:

Quoiqu'il arrive et quelque soit l'algorithme, étape 1:
- échange(s) TCP/IP: requête DNS (ou résolution local si sur même host)... rappel: échange limité par la connexion réseau, en général entre 100Mo et 1Go de bande passante maxi en interne ou avec fibre et si tu es en ADSL 20Mo/s max mais en réalité plus souvent 2 à 5 car toute la bande passante n'est jamais utilisée...
- connexion tcp/ip (même en local)
- échange tcp/ip: identification
étape 2 (à chaque requête SQL):
- échange tcp/ip: envoi requête
- analyse requête (interprétation, optimisation, exécution)
- mise en cache résultat coté mysql
- échange tcp/ip: envoi résultat
- mise en cache coté php
Le problème vois tu, c'est que le goulot d'étranglement c'est le réseau... car tu as des temps d'accès niveau disque dur entre plusieurs centaines de Mo/s (SATA DD mécaniques) à plusieurs Go/s (en SATA SSD)... et selon la taille de ta requête, du coup, l'échange et la double mise en cache peuvent devenir plus long que l'exécution de la requête...

Dans la conception classique php/mysql, tu as:
- l'étape 1
- autan d'étape 2 que tu as besoin de fois d'interroger la BD, l'algorithme se partage entre php et mysql
Dans une conception plus avancée (attention, tout ne pouvant pas être fais coté mysql comme les remplacements à base de regex par exemple...), tu as:
- l'étape 1
- l'étape 2 (l'algorithme est entièrement coté mysql donc plus d'échanges tcp/ip et de double bufferisation des résultats intermédiaires coté php et mysql). le langage procédural SQL est au moins aussi rapide (voir bien plus que php, car plus simple)
Donc quand tu as des traitements qui peuvent être lourds et/ou répétitifs sans réellement avoir besoin de faire un truc coté php pourquoi ne pas faire ça finalement coté mysql et s'éviter des échanges TCP/IP et mises en cache inutiles?

Et là je rappelle le problème tirer 16 points aléatoire parmi 400 tous distants au moins de 1000m les uns des autres...

un algorithme s'analyse en terme de nombre d'opérations (complexité):
- au mieux
- en moyenne
- au pire
:aie::mouarf:
28/03/2012, 19h25
stealth35

parce que la procédure présenté est compliquer et demande beaucoup de ressource, une connexion demande pas grand chose un retour avec un petit résultat non plus.

faudrait que je retrouve le brench, mais sur certain fonction de PHP (genre de Date) c'est pourquoi plus rapide de se connecté au serveur mysql lui dire de faire la même chose, renvoyé le résultat et l'afficher

c'est beaucoup moins couteux de récupérer plein de petit résultat que 1 gros, c'est que fait Doctrine par exemple, au lieu de faire un JOIN pour récupéré les donnée, tu fais un requêtes préparée sur chaque ligne
28/03/2012, 19h41
ericd69

compliqué?

beaucoup de ressources?

:mouarf:

tu dois pas souvent aller voir sur le forum mysql notamment la partie procédurale...

parce que ton script php interprété à la volée il en consomme pas? :mouarf:

elle consomme moins de ressources que les 16 allers-retours (étape 2) de ta solution (au mieux car en moyenne tu risques de devoir en faire plutôt beaucoup plus que 16)... du fait, que plus tu va tirer de points plus tu vas avoir des points qui ne seront pas bon avec la conditions de distance, t'obligeant à recommencer le tirage...
29/03/2012, 10h34
stealth35

~~Non 16 requête (et peu être même moins), il suffit de de prendre un point au hasard et tourner en spirale autour du point~~

EDIT : non c'est nul