geometry.lib.php 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336
  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. }