1 | <?php |
||
2 | /* For licensing terms, see /license.txt */ |
||
3 | /** |
||
4 | * @author Arnaud Ligot (CBlue SPRL) <[email protected]> |
||
5 | * |
||
6 | * @package chamilo.include.geometry |
||
7 | */ |
||
8 | define('DEBUG', false); |
||
9 | |||
10 | /** |
||
11 | * poly_init - build the array which will store the image of the polygone. |
||
12 | * |
||
13 | * @param max[x] X resolution |
||
14 | * @param max[y] Y resolution |
||
15 | * @returns an array such as: for all i in [0..max[x][ : for all j in [0..max[y][ : array[i][j] = FALSE |
||
16 | */ |
||
17 | function poly_init($max) |
||
18 | { |
||
19 | return array_fill( |
||
20 | 0, |
||
21 | $max["x"] - 1, |
||
22 | array_fill(0, $max["y"] - 1, false) |
||
23 | ); |
||
24 | } |
||
25 | |||
26 | /** |
||
27 | * poly_compile - return an array which holds the image of the polygone |
||
28 | * FALSE = blank pixel |
||
29 | * TRUE = black pixel. |
||
30 | * |
||
31 | * @param poly points from the polygone |
||
32 | * example: |
||
33 | * poly[0]['x'] = ... |
||
34 | * poly[0]['y'] = ... |
||
35 | * poly[1]['x'] = ... |
||
36 | * poly[1]['y'] = ... |
||
37 | * ... |
||
38 | * poly[n]['x'] = <empty> |
||
39 | * poly[n]['y'] = <empty> |
||
40 | * poly[n+1]['x'] = <empty> |
||
41 | * poly[n+1]['y'] = <empty> |
||
42 | * ... |
||
43 | * @param max see poly_init |
||
44 | * @param bool print or not a debug |
||
45 | * |
||
46 | * @returns an array such as: for all i in [0..max[x][ : for all j in [0..max[y][ : array[i][j] = in_poly(poly, i,j) |
||
47 | * in_poly(poly,i,j) = true iff (i,j) is inside the polygon defined by poly |
||
48 | */ |
||
49 | function poly_compile($poly, $max, $test = false) |
||
50 | { |
||
51 | $res = poly_init($max); |
||
52 | |||
53 | // looking for EDGES |
||
54 | // may be optimized by a dynamic choice |
||
55 | // between Y and X based on max[y]<max[x] |
||
56 | /* |
||
57 | * bords cointains the edges of the polygone |
||
58 | * it is an array of array, |
||
59 | * there are an array for each collon of the image |
||
60 | * |
||
61 | * for all j in [O..max[y][ : for all i in bords[$j] : |
||
62 | * (i,j) is a point inside an edge of the polygone |
||
63 | */ |
||
64 | $bord_lenght = $max['x']; |
||
65 | if ($max['y'] > $bord_lenght) { |
||
66 | $bord_lenght = $max['y']; |
||
67 | } |
||
68 | |||
69 | $bords = array_fill(0, $bord_lenght, []); // building this array |
||
70 | |||
71 | /* adding the first point of the polygone */ |
||
72 | if (isset($bords[$poly[0]['y']]) && is_array($bords[$poly[0]['y']])) { |
||
73 | // avoid warning |
||
74 | array_push($bords[$poly[0]['y']], $poly[0]['x']); |
||
75 | } |
||
76 | |||
77 | $i = 1; // we re-use $i and $old_pente bellow the loop |
||
78 | $old_pente = 0; |
||
79 | // for each points of the polygon but the first |
||
80 | for (; $i < count($poly) && (!empty($poly[$i]['x']) && !empty($poly[$i]['y'])); $i++) { |
||
81 | /* special cases */ |
||
82 | if ($poly[$i - 1]['y'] == $poly[$i]['y']) { |
||
83 | if ($poly[$i - 1]['x'] == $poly[$i]['x']) { |
||
84 | continue; |
||
85 | } // twice the same point |
||
86 | else { // infinite elevation of the edge |
||
87 | if (is_array($bords[$poly[$i]['y']])) { |
||
88 | array_push($bords[$poly[$i]['y']], $poly[$i]['x']); |
||
89 | } |
||
90 | $old_pente = 0; |
||
91 | continue; |
||
92 | } |
||
93 | } |
||
94 | |||
95 | //echo 'point:'.$poly[$i]['y']; bug here |
||
96 | // adding the point as a part of an edge |
||
97 | if (isset($poly[$i]) && |
||
98 | isset($poly[$i]['y']) && |
||
99 | isset($bords[$poly[$i]['y']]) && |
||
100 | is_array($bords[$poly[$i]['y']]) |
||
101 | ) { |
||
102 | // Avoid warning |
||
103 | array_push($bords[$poly[$i]['y']], $poly[$i]['x']); |
||
104 | } |
||
105 | |||
106 | if (DEBUG) { |
||
107 | echo '('.$poly[$i]['x'].';'.$poly[$i]['y'].') '; |
||
108 | } |
||
109 | |||
110 | /* computing the elevation of the edge going */ |
||
111 | // from $poly[$i-1] to $poly[$i] |
||
112 | $pente = ($poly[$i - 1]['x'] - $poly[$i]['x']) / |
||
113 | ($poly[$i - 1]['y'] - $poly[$i]['y']); |
||
114 | |||
115 | // if the sign of the elevation change from the one of the |
||
116 | // previous edge, the point must be added a second time inside |
||
117 | // $bords |
||
118 | if ($i > 1) { |
||
119 | if (($old_pente < 0 && $pente > 0) |
||
120 | || ($old_pente > 0 && $pente < 0)) { |
||
121 | if (isset($poly[$i]) && isset($poly[$i]['y']) && |
||
122 | isset($bords[$poly[$i]['y']]) && |
||
123 | is_array($bords[$poly[$i]['y']]) |
||
124 | ) { |
||
125 | array_push($bords[$poly[$i]['y']], $poly[$i]['x']); |
||
126 | } |
||
127 | |||
128 | if (DEBUG) { |
||
129 | echo '*('.$poly[$i]['x']. |
||
130 | ';'.$poly[$i]['y'].') '; |
||
131 | } |
||
132 | } |
||
133 | } |
||
134 | |||
135 | /* detect the direction of the elevation in Y */ |
||
136 | $dy_inc = ($poly[$i]['y'] - $poly[$i - 1]['y']) > 0 ? 1 : -1; |
||
137 | $x = $poly[$i - 1]['x']; |
||
138 | /* computing points between $poly[$i-1]['y'] and $poly[$i-1]['y'] */ |
||
139 | |||
140 | // we iterate w/ $dy in ]$poly[$i-1]['y'],$poly[$i-1]['y'][ |
||
141 | // w/ $dy_inc as increment |
||
142 | for ($dy = $poly[$i - 1]['y'] + $dy_inc; |
||
143 | $dy != $poly[$i]['y']; |
||
144 | $dy += $dy_inc) { |
||
145 | $x += $pente * $dy_inc; |
||
146 | array_push($bords[$dy], $x); |
||
147 | } |
||
148 | $old_pente = $pente; |
||
149 | } |
||
150 | |||
151 | // closing the polygone (the edge between $poly[$i-1] and $poly[0]) |
||
152 | if ($poly[$i - 1]['y'] != $poly[0]['y']) { |
||
153 | // droite--> rien à faire |
||
154 | // elevation between $poly[0]['x'] and $poly[1]['x']) |
||
155 | $rest = $poly[0]['y'] - $poly[1]['y']; |
||
156 | if ($rest != 0) { |
||
157 | $pente1 = ($poly[0]['x'] - $poly[1]['x']) / ($rest); |
||
158 | } else { |
||
159 | $pente1 = 0; |
||
160 | } |
||
161 | |||
162 | // elevation between $poly[$i-1]['x'] and $poly[0]['x']) |
||
163 | $pente = ($poly[$i - 1]['x'] - $poly[0]['x']) / |
||
164 | ($poly[$i - 1]['y'] - $poly[0]['y']); |
||
165 | |||
166 | // if (DEBUG) echo 'start('.$poly[$i-1]['x'].','.$poly[$i-1]['y']. |
||
167 | // ')-end('.$poly[0]['x'].','.$poly[0]['y']. |
||
168 | // ')-pente'.$pente; |
||
169 | |||
170 | // doubling the first point if needed (see above) |
||
171 | if (($pente1 < 0 && $pente > 0) || ($pente1 > 0 && $pente < 0)) { |
||
172 | if (is_array($bords[$poly[$i - 1]['y']])) { |
||
173 | array_push($bords[$poly[$i - 1]['y']], round($poly[$i - 1]['x'])); |
||
174 | } |
||
175 | //if (DEBUG) echo '('.$poly[$i-1]['x'].';'.$poly[$i-1]['y'].') '; |
||
176 | } |
||
177 | // doubling the last point if neededd |
||
178 | if (($old_pente < 0 && $pente > 0) || ($old_pente > 0 && $pente < 0)) { |
||
179 | if (is_array($bords[$poly[$i - 1]['y']])) { //avoid warning |
||
180 | array_push($bords[$poly[$i - 1]['y']], round($poly[$i - 1]['x'])); |
||
181 | } |
||
182 | //if (DEBUG) echo '*('.$poly[$i-1]['x'].';'.$poly[$i-1]['y'].') '; |
||
183 | } |
||
184 | |||
185 | $dy_inc = ($poly[0]['y'] - $poly[$i - 1]['y']) > 0 ? 1 : -1; |
||
186 | $x = $poly[$i - 1]['x']; |
||
187 | // if (DEBUG) echo "init: ".$poly[$i-1]['y']." dy_inc: ".$dy_inc. |
||
188 | // " end: ".$poly[0]['y']; |
||
189 | |||
190 | for ($dy = $poly[$i - 1]['y'] + $dy_inc; $dy != $poly[0]['y']; $dy += $dy_inc) { |
||
191 | $x += $pente * $dy_inc; |
||
192 | array_push($bords[$dy], round($x)); |
||
193 | } |
||
194 | } |
||
195 | |||
196 | /* filling the polygon */ |
||
197 | /* basic idea: we sort a column of edges. |
||
198 | For each pair of point, we color the points in between */ |
||
199 | $n = count($bords); |
||
200 | for ($i = 0; $i < $n; $i++) { // Y |
||
201 | if (is_array($bords[$i])) { |
||
202 | sort($bords[$i]); |
||
203 | } |
||
204 | |||
205 | for ($j = 0; $j < count($bords[$i]); $j += 2) { // bords |
||
206 | if (!isset($bords[$i][$j + 1])) { |
||
207 | continue; |
||
208 | } |
||
209 | |||
210 | for ($k = round($bords[$i][$j]); $k <= $bords[$i][$j + 1]; $k++) { |
||
211 | $res[$k][$i] = true; //filling the array with trues |
||
212 | if ($test == 1) { |
||
213 | /*how to draw the polygon in a human way: |
||
214 | In ubuntu : sudo apt-get install gnuplot |
||
215 | Create an empty file with all points with the result of this echos (No commas, no point, no headers) |
||
216 | In gnuplot: |
||
217 | For 1 polygon: plot "/home/jmontoya/test" |
||
218 | For 2 polygons: plot "/home/jmontoya/test", "/home/jmontoya/test2" |
||
219 | A new window will appear with the plot |
||
220 | */ |
||
221 | echo $k.' '.$i; |
||
222 | echo '<br />'; |
||
223 | } |
||
224 | } |
||
225 | } |
||
226 | } |
||
227 | |||
228 | return $res; |
||
229 | } |
||
230 | |||
231 | /** |
||
232 | * poly_dump - dump an image on the screen. |
||
233 | * |
||
234 | * @param array the polygone as output by poly_compile() |
||
235 | * @param array see above (poly_init) |
||
236 | * @param string Format ('raw' text or 'html') |
||
237 | * |
||
238 | * @return string html code of the representation of the polygone image |
||
239 | */ |
||
240 | function poly_dump(&$poly, $max, $format = 'raw') |
||
241 | { |
||
242 | if ($format == 'html') { |
||
243 | $s = "<div style='font-size: 8px; line-height:3px'><pre>\n"; |
||
244 | } |
||
245 | for ($i = 0; $i < $max['y']; $i++) { |
||
246 | for ($j = 0; $j < $max['x']; $j++) { |
||
247 | if ($poly[$j][$i] == true) { |
||
248 | $s .= ($format == 'html' ? "<b>1</b>" : '1'); |
||
0 ignored issues
–
show
Comprehensibility
Best Practice
introduced
by
Loading history...
|
|||
249 | } else { |
||
250 | $s .= "0"; |
||
251 | } |
||
252 | } |
||
253 | $s .= ($format == 'html' ? "<br />\n" : "\n"); |
||
254 | } |
||
255 | $s .= ($format == 'html' ? "</pre></div>\n" : "\n"); |
||
256 | |||
257 | return $s; |
||
258 | } |
||
259 | |||
260 | /** |
||
261 | * poly_result - compute statis for two polygones. |
||
262 | * |
||
263 | * @param poly1 first polygone as returned by poly_compile |
||
264 | * @param poly2 second .... |
||
265 | * @param max resolution as specified for poly_init |
||
266 | * |
||
267 | * @returns (see below, UTSL) |
||
268 | */ |
||
269 | function poly_result(&$poly1, &$poly2, $max) |
||
270 | { |
||
271 | $onlyIn1 = 0; |
||
272 | $surfaceOf1 = 0; |
||
273 | $surfaceOf2 = 0; |
||
274 | |||
275 | for ($i = 0; $i < $max['x']; $i++) { |
||
276 | for ($j = 0; $j < $max['y']; $j++) { |
||
277 | if (isset($poly1[$i][$j]) && ($poly1[$i][$j] == true)) { |
||
278 | $surfaceOf1++; |
||
279 | if (isset($poly2[$i][$j]) && ($poly2[$i][$j] == false)) { |
||
280 | $onlyIn1++; |
||
281 | } |
||
282 | } |
||
283 | if (isset($poly2[$i][$j]) && ($poly2[$i][$j] == true)) { |
||
284 | $surfaceOf2++; |
||
285 | } |
||
286 | } |
||
287 | } |
||
288 | |||
289 | return [ |
||
290 | "s1" => $surfaceOf1, |
||
291 | "s2" => $surfaceOf2, |
||
292 | "both" => $surfaceOf1 - $onlyIn1, |
||
293 | "s1Only" => $onlyIn1, |
||
294 | "s2Only" => $surfaceOf2 - ($surfaceOf1 - $onlyIn1), ]; |
||
295 | } |
||
296 | |||
297 | /** |
||
298 | * poly_touch - compute statis for two polygones. |
||
299 | * |
||
300 | * @param poly1 first polygone as returned by poly_compile |
||
301 | * @param poly2 second .... |
||
302 | * @param max resolution as specified for poly_init |
||
303 | * |
||
304 | * @returns (see below, UTSL) |
||
305 | */ |
||
306 | function poly_touch(&$poly1, &$poly2, $max) |
||
307 | { |
||
308 | for ($i = 0; $i < $max['x']; $i++) { |
||
309 | for ($j = 0; $j < $max['y']; $j++) { |
||
310 | if (isset($poly1[$i][$j]) && ($poly1[$i][$j] == true) |
||
311 | && isset($poly2[$i][$j]) && ($poly2[$i][$j] == true)) { |
||
312 | return true; |
||
313 | } |
||
314 | } |
||
315 | } |
||
316 | |||
317 | return false; |
||
318 | } |
||
319 | |||
320 | /** |
||
321 | * Convert a list of points in x1;y1|x2;y2|x3;y3 or x1;y1/x2;y2 format to |
||
322 | * the format in which the functions in this library are expecting their data. |
||
323 | * |
||
324 | * @param string List of points in x1;y1|... format (or /) |
||
325 | * @param string The points separator for the list (| or /) |
||
326 | * |
||
327 | * @return array An array of points in the right format to use with the |
||
328 | * local functions |
||
329 | */ |
||
330 | function convert_coordinates($coords, $sep = '|') |
||
331 | { |
||
332 | $points = []; |
||
333 | $pairs = explode($sep, $coords); |
||
334 | if (!empty($pairs)) { |
||
335 | foreach ($pairs as $idx => $pcoord) { |
||
336 | if (empty($pcoord)) { |
||
337 | continue; |
||
338 | } |
||
339 | $parts = explode(';', $pcoord); |
||
340 | if (!empty($parts)) { |
||
341 | $points[] = ['x' => $parts[0], 'y' => $parts[1]]; |
||
342 | } |
||
343 | } |
||
344 | } |
||
345 | |||
346 | return $points; |
||
347 | } |
||
348 | |||
349 | /** |
||
350 | * Returns the maximum coordinates in x,y (from 0,0) that the geometrical form |
||
351 | * can reach. |
||
352 | * |
||
353 | * @param array Coordinates of one polygon |
||
354 | * |
||
355 | * @return array ('x'=>val,'y'=>val) |
||
356 | */ |
||
357 | function poly_get_max(&$coords1, &$coords2) |
||
358 | { |
||
359 | $mx = 0; |
||
360 | $my = 0; |
||
361 | foreach ($coords1 as $coord) { |
||
362 | if ($coord['x'] > $mx) { |
||
363 | $mx = $coord['x']; |
||
364 | } |
||
365 | if ($coord['y'] > $my) { |
||
366 | $my = $coord['y']; |
||
367 | } |
||
368 | } |
||
369 | foreach ($coords2 as $coord) { |
||
370 | if ($coord['x'] > $mx) { |
||
371 | $mx = $coord['x']; |
||
372 | } |
||
373 | if ($coord['y'] > $my) { |
||
374 | $my = $coord['y']; |
||
375 | } |
||
376 | } |
||
377 | |||
378 | return ['x' => $mx, 'y' => $my]; |
||
379 | } |
||
380 | |||
381 | /** |
||
382 | * Class Geometry |
||
383 | * Utils for decode hotspots and check if the user choices are correct. |
||
384 | */ |
||
385 | class Geometry |
||
386 | { |
||
387 | /** |
||
388 | * Decode a user choice as a point. |
||
389 | * |
||
390 | * @param string $coordinates |
||
391 | * |
||
392 | * @return array The x and y properties for a point |
||
393 | */ |
||
394 | public static function decodePoint($coordinates) |
||
395 | { |
||
396 | $coordinates = explode(';', $coordinates); |
||
397 | |||
398 | return [ |
||
399 | 'x' => intval($coordinates[0]), |
||
400 | 'y' => intval($coordinates[1]), |
||
401 | ]; |
||
402 | } |
||
403 | |||
404 | /** |
||
405 | * Decode a square info as properties. |
||
406 | * |
||
407 | * @param string $coordinates |
||
408 | * |
||
409 | * @return array The x, y, width, and height properties for a square |
||
410 | */ |
||
411 | public static function decodeSquare($coordinates) |
||
412 | { |
||
413 | $coordinates = explode('|', $coordinates); |
||
414 | $originString = explode(';', $coordinates[0]); |
||
415 | |||
416 | return [ |
||
417 | 'x' => intval($originString[0]), |
||
418 | 'y' => intval($originString[1]), |
||
419 | 'width' => intval($coordinates[1]), |
||
420 | 'height' => intval($coordinates[2]), |
||
421 | ]; |
||
422 | } |
||
423 | |||
424 | /** |
||
425 | * Decode an ellipse info as properties. |
||
426 | * |
||
427 | * @param string $coordinates |
||
428 | * |
||
429 | * @return array The center_x, center_y, radius_x, radius_x properties for an ellipse |
||
430 | */ |
||
431 | public static function decodeEllipse($coordinates) |
||
432 | { |
||
433 | $coordinates = explode('|', $coordinates); |
||
434 | $originString = explode(';', $coordinates[0]); |
||
435 | |||
436 | return [ |
||
437 | 'center_x' => intval($originString[0]), |
||
438 | 'center_y' => intval($originString[1]), |
||
439 | 'radius_x' => intval($coordinates[1]), |
||
440 | 'radius_y' => intval($coordinates[2]), |
||
441 | ]; |
||
442 | } |
||
443 | |||
444 | /** |
||
445 | * Decode a polygon info as properties. |
||
446 | * |
||
447 | * @param string $coordinates |
||
448 | * |
||
449 | * @return array The array of points for a polygon |
||
450 | */ |
||
451 | public static function decodePolygon($coordinates) |
||
452 | { |
||
453 | $coordinates = explode('|', $coordinates); |
||
454 | |||
455 | $points = []; |
||
456 | |||
457 | foreach ($coordinates as $coordinate) { |
||
458 | $point = explode(';', $coordinate); |
||
459 | |||
460 | $points[] = [ |
||
461 | intval($point[0]), |
||
462 | intval($point[1]), |
||
463 | ]; |
||
464 | } |
||
465 | |||
466 | return $points; |
||
467 | } |
||
468 | |||
469 | /** |
||
470 | * Check if the point is inside of a square. |
||
471 | * |
||
472 | * @param array $properties The hotspot properties |
||
473 | * @param array $point The point properties |
||
474 | * |
||
475 | * @return bool |
||
476 | */ |
||
477 | public static function pointIsInSquare($properties, $point) |
||
478 | { |
||
479 | $left = $properties['x']; |
||
480 | $right = $properties['x'] + $properties['width']; |
||
481 | $top = $properties['y']; |
||
482 | $bottom = $properties['y'] + $properties['height']; |
||
483 | |||
484 | $xIsValid = $point['x'] >= $left && $point['x'] <= $right; |
||
485 | $yIsValid = $point['y'] >= $top && $point['y'] <= $bottom; |
||
486 | |||
487 | return $xIsValid && $yIsValid; |
||
488 | } |
||
489 | |||
490 | /** |
||
491 | * Check if the point is inside of an ellipse. |
||
492 | * |
||
493 | * @param array $properties The hotspot properties |
||
494 | * @param array $point The point properties |
||
495 | * |
||
496 | * @return bool |
||
497 | */ |
||
498 | public static function pointIsInEllipse($properties, $point) |
||
499 | { |
||
500 | $dX = $point['x'] - $properties['center_x']; |
||
501 | $dY = $point['y'] - $properties['center_y']; |
||
502 | |||
503 | $dividend = pow($dX, 2) / pow($properties['radius_x'], 2); |
||
504 | $divider = pow($dY, 2) / pow($properties['radius_y'], 2); |
||
505 | |||
506 | return $dividend + $divider <= 1; |
||
507 | } |
||
508 | |||
509 | /** |
||
510 | * Check if the point is inside of a polygon. |
||
511 | * |
||
512 | * @param array $properties The hotspot properties |
||
513 | * @param array $point The point properties |
||
514 | * |
||
515 | * @return bool |
||
516 | */ |
||
517 | public static function pointIsInPolygon($properties, $point) |
||
518 | { |
||
519 | $points = $properties; |
||
520 | $isInside = false; |
||
521 | |||
522 | for ($i = 0, $j = count($points) - 1; $i < count($points); $j = $i++) { |
||
523 | $xi = $points[$i][0]; |
||
524 | $yi = $points[$i][1]; |
||
525 | $xj = $points[$j][0]; |
||
526 | $yj = $points[$j][1]; |
||
527 | |||
528 | $intersect = (($yi > $point['y']) !== ($yj > $point['y'])) && |
||
529 | ($point['x'] < ($xj - $xi) * ($point['y'] - $yi) / ($yj - $yi) + $xi); |
||
530 | |||
531 | if ($intersect) { |
||
532 | $isInside = !$isInside; |
||
533 | } |
||
534 | } |
||
535 | |||
536 | return $isInside; |
||
537 | } |
||
538 | } |
||
539 |