geometry.lib.php 15 KB

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