geometry.lib.php 16 KB

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