geometry.lib.php 16 KB

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