Subversion Repositories eFlore/Applications.cel

Rev

Rev 977 | Rev 979 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 977 Rev 978
1 
<?php
 1 
<?php
2 
class CartoGroupage {
 2 
class CartoGroupage {
- 
 
 3 
 
3 
	const OFFSET = 268435456;// Moitié de la circonférence de la terre au zoom 21
 4 
	private static $seuilClusterisation = 100;
- 
 
 5 
	private static $zoomDefaut = 3;
4 
	const RADIUS = 85445659.4471; /* $offset / pi() */
 6 
	private static $zoomMaxClustering = 12;
5 
	private static $profondeurMax = 3;
 7 
	private static $pasZoomDefaut = 1;
6 
	private static $pasCorrectionCentre = 1;
 8 
	private static $pasZoomMaxClustering = 0.05;
7 
	private static $zoom = 1;
 9 
	private static $profondeurMin = 0;
8 
	private static $seuilClusterisation = 180;
 10 
	private static $profondeurMax = 8;
9
11
10 
	private static $debug = false;
 12 
	private static $pasCorrectionCentre = null;
- 
 
 13 
	private static $coefficientReductionPas = null;
- 
 
 14 
	private static $coefficientProfondeurMax = null;
11
15 
 
12 
	private static $listeNoeudsSelectionnes = array();
 16 
	private static $listeNoeudsSelectionnes = array();
13
17 
 
14 
	private static $hilbert_map_1 = array ('a' => array (
 - 
 
15 
									"0, 0" => array (0, 'd'),
 - 
 
16 
									"0, 1" => array (1, 'a'),
- 
 
17 
											"1, 0" => array (3, 'b'),
 - 
 
18 
											"1, 1" => array (2, 'a')
 - 
 
19 
									),
18 
	/*
20 
									 'b' => array (
19 
	  +---------+---------+
21 
											 "0, 0" => array (2, 'b'),
- 
 
22 
											 "0, 1" => array (1, 'b'),
20 
	  |         |         |
23 
											 "1, 0" => array (3, 'a'),
 21 
	  |    A    |    B    |
24 
											 "1, 1" => array (0, 'c')
 22 
	  |         |         |
25 
									),
- 
 
26 
									'c' => array (
23 
	  +---------*---------+
27 
											"0, 0" => array (2, 'c'),
 - 
 
28 
											"0, 1" => array (3, 'd'),
 24 
	  |         |         |
29 
											"1, 0" => array (1, 'c'),
 25 
	  |    D    |    C    |
30 
											"1, 1" => array (0, 'b')
 26 
	  |         |         |
31 
										),
- 
 
32 
									'd' => array (
 27 
	  +---------+---------+
33 
											"0, 0" => array (0, 'a'),
- 
 
34 
											"0, 1" => array (3, 'c'),
- 
 
35 
											"1, 0" => array (1, 'd'),
- 
 
36 
											"1, 1" => array (2, 'd')
 - 
 
37 
									),
 - 
 
38 
								);
 - 
 
39
28
40 
	public static $cache = array('lat->y' => array(), 'lat->y' => array());
 29 
	  Quatres cadrans sont considérés par le quad tree
- 
 
 30 
	  * = centre de la fenetre
41
31 
	 */
42 
	public static function creerGroupesManhattan($markers, $zoom) {
 32 
	public static function creerGroupesQuadtree($markers, $neLat, $neLng, $swLat, $swLng, $zoom = 3) {
43 
		$clustered = array();
 - 
 
44 
		// Distance minimum entre deux marqueurs pour l'inclure dans un cluster à un niveau de zoom donné
 - 
 
45 
		$groupeRayon = (10000000 >> $zoom) / 100000;
 - 
 
46
- 
 
47 
		/* Boucle permettant de définir les marqueurs de références. */
 - 
 
48 
		while (count($markers)) {
 33
49 
			$marker  = array_shift($markers);
 - 
 
50 
			$cluster = array();
 34 
		if(count($markers) > self::$seuilClusterisation) {
51
- 
 
52 
			/* Comparaison de la distance des autres marqueurs avec le marqueur de référence. */
 35
53 
			foreach ($markers as $key => $target) {
 36 
			self::calculerProfondeurMax($zoom);
- 
 
 37 
			self::calculerPasCorrectionCentre($zoom);
54 
				$cibleDistance = abs($marker['lat'] - $target['lat']) + abs($marker['lng'] - $target['lng']);
 38 
 
- 
 
 39 
			$noeudRacine = array('nbrePoints' => count($markers), 'points' => $markers);
- 
 
 40 
			self::attribuerAuCadran($noeudRacine, $neLat, $neLng, $swLat, $swLng);
55 
 
 41
56 
				if ($groupeRayon > $cibleDistance) {
 42 
		} else {
57 
					unset($markers[$key]);
 - 
 
- 
 
 43 
			foreach($markers as $marker) {
- 
 
 44 
				$points = array($marker);
58 
					$cluster['cibles'][] = $target;
 45 
				$noeudSimple = array('points' => $points, 'nbrePoints' => 1);
- 
 
 46 
				self::$listeNoeudsSelectionnes[] = self::ajouterGroupeOuPoint($noeudSimple);
- 
 
 47 
			}
- 
 
 48 
		}
- 
 
 49
59 
				}
 50 
		return self::$listeNoeudsSelectionnes;
- 
 
 51 
	}
- 
 
 52
60 
			}
 53 
	private function calculerCoefficientReductionPas() {
61
54 
		if(self::$coefficientReductionPas == null) {
62 
			$clustered[] = self::ajouterGroupe($cluster, $marker);
 55 
			self::$coefficientReductionPas = (self::$pasZoomMaxClustering - self::$pasZoomDefaut)/(self::$zoomMaxClustering - self::$zoomDefaut);
63 
		}
 - 
 
64
- 
 
65 
		return $clustered;
 56 
		}
66 
	}
 - 
 
67
- 
 
68 
	public static function creerGroupesPixel($markers, $zoom, $clusterDistance = 20) {
 - 
 
69 
		$clustered = array();
 - 
 
70 
		/* Loop until all markers have been compared. */
 - 
 
71 
		while (count($markers)) {
 - 
 
72 
			$marker  = array_shift($markers);
 57
73 
			$cluster = array();
 - 
 
74
- 
 
75 
			/* Compare against all markers which are left. */
 - 
 
76 
			foreach ($markers as $key => $target) {
 - 
 
77 
				$cibleDistance = self::pixelDistance($marker['lat'], $marker['lng'], $target['lat'], $target['lng'], $zoom);
 - 
 
78 
 
 - 
 
79 
				if ($clusterDistance > $cibleDistance) {
 - 
 
80 
					//$m = "Distance entre %s,%s et %s,%s vaut %d pixels.\n";
 - 
 
81 
					//printf($m, $marker['lat'], $marker['lng'], $target['lat'], $target['lng'], $pixels);
 - 
 
82 
					unset($markers[$key]);
 - 
 
83 
					$cluster['cibles'][] = $target;
 - 
 
84 
					$cluster['latMax'] = ($cluster['latMax'] < $target['lat']) ? $target['lat'] : $cluster['latMax'];
 - 
 
85 
					$cluster['lngMax'] = ($cluster['lngMax'] < $target['lng']) ? $target['lng'] : $cluster['lngMax'];
- 
 
86 
				}
 58 
		return self::$coefficientReductionPas;
87 
			}
 59 
	}
88 
			$clustered[] = self::ajouterGroupe($cluster, $marker);
 - 
 
89 
		}
 60
90 
		return $clustered;
 - 
 
91 
	}
 - 
 
92
- 
 
93 
	public static function ajouterGroupe($cluster, $marker) {
 - 
 
94 
		$groupe = array();
 - 
 
95 
		$nbreMarqueurs = count($cluster['cibles']);
 - 
 
96 
		if ($nbreMarqueurs > 0) {
 61 
	private function calculerPasCorrectionCentre($zoom) {
97 
			$groupe['id'] = 'GROUPE:'.$marker['lat'].';'.$marker['lng'];
 - 
 
98 
			$groupe['lat'] = $marker['lat'];
 - 
 
99 
			$groupe['lng'] = $marker['lng'];
 - 
 
100 
			$groupe['latMax'] = $cluster['latMax'];
 62 
		self::$pasCorrectionCentre = ($zoom - self::$zoomDefaut) * self::calculerCoefficientReductionPas() + self::$pasZoomDefaut;
- 
 
 63 
	}
101 
			$groupe['lngMax'] = $cluster['lngMax'];
 64
102 
			// +1 car le marqueur servant de point de départ n'est pas ajouté au cluster
 65 
	private function calculerCoefficientProfondeurMax() {
103 
			$groupe['nbreMarqueur'] = $nbreMarqueurs + 1;
 - 
 
104 
		} else {
 - 
 
105 
			$groupe = $marker;
 66 
		if(self::$coefficientProfondeurMax == null) {
106 
		}
 - 
 
107 
		return $groupe;
 - 
 
108 
	}
 - 
 
109
67 
			self::$coefficientProfondeurMax = (self::$profondeurMax - self::$profondeurMin)/(self::$zoomMaxClustering - self::$zoomDefaut);
110 
	public static function creerGroupesQuadtree2($markers, $neLat, $neLng, $swLat, $swLng, $zoom = 3) {
 - 
 
111
- 
 
112 
		if(count($markers) > self::$seuilClusterisation) {
 - 
 
113
- 
 
114 
			//$_GET['debug'] = true;
 - 
 
115
- 
 
116 
			self::$zoom = $zoom;
 68 
		}
117 
			self::$pasCorrectionCentre = 10/self::$zoom;
 - 
 
118
- 
 
119 
			self::$profondeurMax = round(pow($zoom,1.05),0) - 1;
 - 
 
120
- 
 
121 
			echo ($_GET['debug'] == true) ? '<pre>' : '';
 - 
 
122
69
123 
			echo ($_GET['debug'] == true) ? 'zoom :'.$zoom.' profondeur max '.self::$profondeurMax : '';
 - 
 
124
70 
		return self::$coefficientProfondeurMax;
125 
			//echo "$neLat, $neLng, $swLat, $swLng";
 - 
 
126 
			$noeud = array('coordCentre' => null,'nbrePoints' => count($markers), 'points' => $markers);
 - 
 
127 
			self::attribuerAuCarre($noeud, $neLat, $neLng, $swLat, $swLng);
- 
 
128 
			echo ($_GET['debug'] == true) ? '</pre>' : '';
 71 
	}
129 
		} else {
 - 
 
130 
			foreach($markers as $marker) {
 - 
 
131 
				$points = array($marker);
 72
132 
				$noeud_fictif = array('points' => $points, 'nbrePoints' => 1);
 - 
 
133 
				self::$listeNoeudsSelectionnes[] = self::ajouterGroupe2($noeud_fictif);
 73 
	private function calculerProfondeurMax($zoom) {
134 
			}
 74 
		if($zoom > self::$zoomDefaut) {
135 
		}
 75 
			self::$profondeurMax = round(($zoom - self::$zoomDefaut) * self::calculerCoefficientProfondeurMax() + self::$profondeurMin,0);
136
76 
		} else {
137 
		return self::$listeNoeudsSelectionnes;
 77 
			self::$profondeurMax = 1;
- 
 
 78 
		}
- 
 
 79 
	}
- 
 
 80
138 
	}
 81 
	/**
139
82 
	 *
140 
	private static function attribuerAuCarre(&$noeud, $neLat, $neLng, $swLat, $swLng, $profondeur = 0) {
 - 
 
141
83 
	 * @param mixed $noeud Le noeud à traiter par le quadtree
142
84 
	 * @param float $neLat Latitude du coin nord est de la fenetre
143 
		echo ($_GET['debug'] == true) ? "coordonnees parametres : $neLat, $neLng, $swLat, $swLng" : "";
 85 
	 * @param float $neLng Longitude du coin nord est de la fenetre
144 
		//$latCentre = $noeud['coordCentre']['lat'] = ($neLat+$swLat)/2;
 86 
	 * @param float $swLat Latitude du coin sud ouest de la fenetre
145 
		//$lngCentre = $noeud['coordCentre']['lng'] = ($neLng+$swLng)/2;
 87 
	 * @param float $swLng Longitude du coin sud ouest de la fenetre
146
- 
 
147 
		$latCentre = $noeud['coordCentre']['lat'] = round((($neLat+$swLat)/2)/self::$pasCorrectionCentre,0)*self::$pasCorrectionCentre;
 88 
	 * @param int $profondeur profondeur courante de l'arbre
148 
		$lngCentre = $noeud['coordCentre']['lng'] = round((($neLng+$swLng)/2)/self::$pasCorrectionCentre,0)*self::$pasCorrectionCentre;
 - 
 
149
- 
 
150 
		echo ($_GET['debug'] == true) ? "\n\n profondeur : $profondeur\n" : "";
 - 
 
151 
		echo ($_GET['debug'] == true) ? "\t centre : $lngCentre  $latCentre \n" : "";
 - 
 
152
- 
 
153 
		foreach ($noeud['points'] as &$point) {
 - 
 
154 
			if ($point['lng'] < $lngCentre) {
 - 
 
155 
				if ($point['lat'] > $latCentre) {
 - 
 
156 
					//Carré A
 - 
 
157 
					$noeud['A']['points'][] = $point;
 - 
 
158 
					$noeud['A']['nbrePoints']++;
 - 
 
159 
					$noeud['A']['latMoyenne'] += $point['lat'];
 - 
 
160 
					$noeud['A']['lngMoyenne'] += $point['lng'];
 - 
 
161 
				} else {
 - 
 
162 
					//Carré D
 - 
 
163 
					$noeud['D']['points'][] = $point;
- 
 
164 
					$noeud['D']['nbrePoints']++;
 - 
 
165 
					$noeud['D']['latMoyenne'] += $point['lat'];
 - 
 
166 
					$noeud['D']['lngMoyenne'] += $point['lng'];
 - 
 
167 
				}
 - 
 
168 
			} else {
 - 
 
169 
				if ($point['lat'] > $latCentre) {
 89 
	 */
170 
					//Carré B
 - 
 
171 
					$noeud['B']['points'][] = $point;
 - 
 
172 
					$noeud['B']['nbrePoints']++;
 - 
 
173 
					$noeud['B']['latMoyenne'] += $point['lat'];
 - 
 
174 
					$noeud['B']['lngMoyenne'] += $point['lng'];
 - 
 
175 
				} else {
 90 
	private static function attribuerAuCadran(&$noeud, $neLat, $neLng, $swLat, $swLng, $profondeur = 0) {
176 
					//Carré C
 91
177 
					$noeud['C']['points'][] = $point;
 92 
		$latCentre = round((($neLat+$swLat)/2)/self::$pasCorrectionCentre,0)*self::$pasCorrectionCentre;
178 
					$noeud['C']['nbrePoints']++;
 93 
		$lngCentre = round((($neLng+$swLng)/2)/self::$pasCorrectionCentre,0)*self::$pasCorrectionCentre;
179 
					$noeud['C']['latMoyenne'] += $point['lat'];
 94
180 
					$noeud['C']['lngMoyenne'] += $point['lng'];
 95 
		foreach ($noeud['points'] as &$point) {
181 
				}
 96 
			$cadran = self::obtenirCadranPourPoint($latCentre, $lngCentre, $point);
182 
			}
 97 
			self::ajouterFils($noeud,$cadran,$point);
183 
		}
 98 
		}
184
99
185 
		$profondeur++;
 100 
		$profondeur++;
186
- 
 
187 
		$centreNoeud = array('id' => $latCentre.' '.$lngCentre, 'lat' => $latCentre, 'lng' => $lngCentre, 'nbreMarqueur' => 0);
- 
 
188 
		//self::$listeNoeudsSelectionnes[] = $centreNoeud;
 101
189 
		if($profondeur <= self::$profondeurMax) {
- 
 
190 
			//echo "noeud A\n";
102 
		if($profondeur <= self::$profondeurMax) {
191 
			($noeud['A'] != null) ? self::attribuerAuCarre($noeud['A'], $neLat, $lngCentre , $latCentre, $lngSw, $profondeur) : '';
 - 
 
192 
			//echo "noeud B\n";
 103 
			($noeud['A'] != null) ? self::attribuerAuCadran($noeud['A'], $neLat, $lngCentre , $latCentre, $lngSw, $profondeur) : '';
193 
			($noeud['B'] != null) ? self::attribuerAuCarre($noeud['B'], $neLat, $neLng, $latCentre, $lngCentre, $profondeur) : '';
 - 
 
194 
			//echo "noeud C\n";
 104 
			($noeud['B'] != null) ? self::attribuerAuCadran($noeud['B'], $neLat, $neLng, $latCentre, $lngCentre, $profondeur) : '';
195 
			($noeud['C'] != null) ? self::attribuerAuCarre($noeud['C'], $latCentre, $neLng, $swLat, $lngCentre, $profondeur) : '';
 - 
 
196 
			//echo "noeud D\n";
 105 
			($noeud['C'] != null) ? self::attribuerAuCadran($noeud['C'], $latCentre, $neLng, $swLat, $lngCentre, $profondeur) : '';
197 
			($noeud['D'] != null) ? self::attribuerAuCarre($noeud['D'], $latCentre, $lngCentre, $swLat, $swLng, $profondeur) : '';
 106 
			($noeud['D'] != null) ? self::attribuerAuCadran($noeud['D'], $latCentre, $lngCentre, $swLat, $swLng, $profondeur) : '';
198 
		}
 107 
		}
199
- 
 
200 
		//self::$listeNoeudsSelectionnes[] = self::ajouterGroupe2($noeud);
 108
201 
		if(self::estUneFeuille($noeud['A']) && self::estUneFeuille($noeud['B']) && self::estUneFeuille($noeud['C']) && self::estUneFeuille($noeud['D'])) {
 - 
 
202 
			self::$listeNoeudsSelectionnes[] = self::ajouterGroupe2($noeud);
 - 
 
203 
		} else {
 109 
		if(self::estUnParentFeuilles($noeud)) {
204 
			//self::$listeNoeudsSelectionnes[] = self::ajouterGroupe2($noeud);
 110 
			self::$listeNoeudsSelectionnes[] = self::ajouterGroupeOuPoint($noeud);
205 
		}
 111 
		}
206 
	}
 112 
	}
- 
 
 113
- 
 
 114 
	private function obtenirCadranPourPoint($latCentre,$lngCentre, &$point) {
- 
 
 115 
		if ($point['lng'] < $lngCentre) {
- 
 
 116 
			if ($point['lat'] > $latCentre) {
- 
 
 117 
					$cadran = 'A';
- 
 
 118 
				} else {
- 
 
 119 
					$cadran = 'D';
- 
 
 120 
				}
- 
 
 121 
		} else {
- 
 
 122 
			if ($point['lat'] > $latCentre) {
- 
 
 123 
				$cadran = 'B';
- 
 
 124 
			} else {
- 
 
 125 
				$cadran = 'C';
- 
 
 126 
			}
- 
 
 127 
		}
- 
 
 128 
		return $cadran;
- 
 
 129 
	}
- 
 
 130
- 
 
 131 
	private static function ajouterFils(&$noeud, $cadran, &$point) {
- 
 
 132 
		$noeud[$cadran]['points'][] = $point;
- 
 
 133 
		$noeud[$cadran]['nbrePoints']++;
- 
 
 134 
		$noeud[$cadran]['latMoyenne'] += $point['lat'];
- 
 
 135 
		$noeud[$cadran]['lngMoyenne'] += $point['lng'];
- 
 
 136 
	}
207
137
208 
	public static function ajouterGroupe2($noeud) {
 138 
	private static function ajouterGroupeOuPoint($noeud) {
209 
		$groupe = array();
 139 
		$groupe = array();
210 
		if ($noeud['nbrePoints'] > 1) {
 - 
 
211 
			$groupe['id'] = 'GROUPE:'.$noeud['coordCentre']['lat'].';'.$noeud['coordCentre']['lng'];
 - 
 
212 
			// TODO changer la génération de l'id
 140 
		if ($noeud['nbrePoints'] > 1) {
213 
			$groupe['lat'] = $noeud['latMoyenne']/$noeud['nbrePoints'];
 141 
			$groupe['lat'] = $noeud['latMoyenne']/$noeud['nbrePoints'];
214 
			$groupe['lng'] = $noeud['lngMoyenne']/$noeud['nbrePoints'];
 142 
			$groupe['lng'] = $noeud['lngMoyenne']/$noeud['nbrePoints'];
215 
			echo ($_GET['debug'] == true) ? "\ncentre moyenne ".$groupe['lat']."  ".$groupe['lng'] : "";
 143 
			$groupe['id'] = 'GROUPE:'.$groupe['lat'].';'.$groupe['lng'];
216 
			$groupe['nbreMarqueur'] = $noeud['nbrePoints'];
 - 
 
217 
			//$groupe['latMax'] = $cluster['latMax'];
 - 
 
218 
			//$groupe['lngMax'] = $cluster['lngMax'];
 144 
			$groupe['nbreMarqueur'] = $noeud['nbrePoints'];
219 
		} else {
 - 
 
220 
			//echo '<pre>'.print_r($noeud['points'][0],true).'</pre>';
 145 
		} else {
221 
			$groupe = $noeud['points'][0];
 146 
			$groupe = $noeud['points'][0];
222 
		}
 147 
		}
223 
		return $groupe;
 148 
		return $groupe;
224 
	}
 149 
	}
225
150
226 
	private static function estUneFeuille($noeud) {
- 
 
227 
		return $noeud == null || ($noeud['A'] == null && $noeud['B'] == null && $noeud['C'] == null && $noeud['D'] == null);
 - 
 
228 
	}
 - 
 
229
- 
 
230 
	public static function creerGroupesQuadtree($markers, $zoom) {
 - 
 
231 
		$ordre = $zoom - 3;
 - 
 
232 
		$clustered = array();
 - 
 
233 
		foreach ($markers as $key => $marker) {
 151 
	private static function estUnParentFeuilles($noeud) {
234 
			$x = self::lonToX($marker['lng']);
 152 
		return  self::estUneFeuille($noeud['A']) &&
235 
			$y = self::latToY($marker['lat']);
 - 
 
236 
			$payload = self::pointToQuadtree($x, $y, $ordre);
 - 
 
237
- 
 
238 
			if (isset($clustered[$payload])) {
 - 
 
239 
				$clustered[$payload]['nbreMarqueur']++;
 - 
 
240 
			} else {
 - 
 
241 
				$cluster = array();
 - 
 
242 
				$cluster['id'] = 'GROUPE';
 153 
				self::estUneFeuille($noeud['B']) &&
243 
				$cluster['lat'] = $marker['lat'];
 154 
				self::estUneFeuille($noeud['C']) &&
244 
				$cluster['lng'] = $marker['lng'];
 - 
 
245 
				$cluster['nbreMarqueur'] = 1;
 - 
 
246 
				$clustered[$payload] = $cluster;
 - 
 
247 
			}
- 
 
248 
		}
 - 
 
249 
		return array_values($clustered);
 - 
 
250 
	}
 - 
 
251
- 
 
252 
	private static function pixelDistance($lat1, $lon1, $lat2, $lon2, $zoom) {
 - 
 
253 
		$x1 = self::lonToX($lon1);
 - 
 
254 
		$y1 = self::latToY($lat1);
 - 
 
255 
 
 - 
 
256 
		$x2 = self::lonToX($lon2);
 - 
 
257 
		$y2 = self::latToY($lat2);
 - 
 
258
- 
 
259 
		return sqrt(pow(($x1 - $x2), 2) + pow(($y1 - $y2), 2)) >> (21 - $zoom);
 - 
 
260 
	}
 - 
 
261
- 
 
262 
	private static function lonToX($lon) {
 - 
 
263 
		if (! isset(self::$cache['lng->x'][$lon])) {
 - 
 
264 
			self::$cache['lng->x'][$lon] = round(self::OFFSET + self::RADIUS * $lon * pi() / 180);
 - 
 
265 
		}
 - 
 
266 
		return self::$cache['lng->x'][$lon];
- 
 
267 
	}
 - 
 
268
- 
 
269 
	private static function latToY($lat) {
 - 
 
270 
		if (! isset(self::$cache['lat->y'][$lat])) {
 - 
 
271 
			$logLat = log((1 + sin($lat * pi() / 180)) / (1 - sin($lat * pi() / 180)));
 - 
 
272 
			self::$cache['lat->y'][$lat] = round(self::OFFSET - self::RADIUS * $logLat / 2);
 - 
 
273 
		}
 - 
 
274 
		return self::$cache['lat->y'][$lat];
 155 
				self::estUneFeuille($noeud['D']);
275 
	}
 - 
 
276
- 
 
277 
	public static function haversineDistance($lat1, $lon1, $lat2, $lon2) {
 - 
 
278 
		$latd = deg2rad($lat2 - $lat1);
 - 
 
279 
		$lond = deg2rad($lon2 - $lon1);
 - 
 
280 
		$a = sin($latd / 2) * sin($latd / 2) +
 - 
 
281 
			cos(deg2rad($lat1)) * cos(deg2rad($lat2)) *
 - 
 
282 
			sin($lond / 2) * sin($lond / 2);
 - 
 
283 
			$c = 2 * atan2(sqrt($a), sqrt(1 - $a));
 - 
 
284 
		return 6371.0 * $c;
 - 
 
285 
	}
 156 
	}
286
- 
 
287 
	private static function pointToQuadtree($x, $y, $order=16) {
- 
 
288 
		$current_square = 'a' ;
 - 
 
289 
		$payload = 0;
- 
 
290 
		foreach (range($order-1, 0, -1) as $i) {
- 
 
291 
			$quad_x = $x & (1 << $i) ? 1 : 0;
 157
292 
			$quad_y = $y & (1 << $i) ? 1 : 0;
 - 
 
293 
			list($quad_position, $current_square) = self::$hilbert_map_1[$current_square]["$quad_x, $quad_y"];
 - 
 
294 
			$payload .= $quad_position;
 - 
 
295 
		}
 158 
	private static function estUneFeuille($noeud) {
296 
		return $payload;
 - 
 
297 
	}
 - 
 
298
159 
		return $noeud == null || ($noeud['A'] == null && $noeud['B'] == null && $noeud['C'] == null && $noeud['D'] == null);
299
160 
	}
300 
}
 161 
}
301 
?>
 162 
?>