geometry.lib.php 37 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969
  1. <?php
  2. /* For licensing terms, see /license.txt */
  3. //more natural array index names
  4. define(X, 0);
  5. define(Y, 1);
  6. //aproximation level to comparing reals
  7. define(APROX, 0.0001);
  8. /**
  9. * This method calculates and returns the area of an irregular
  10. * polygon. Algorithm taken from
  11. * http://forums.devx.com/showpost.php?p=423349&postcount=2
  12. *
  13. * @param array(int) xs the values of the x coordinates
  14. * @param array(int) ys the corresponding values of the y coordinates
  15. * @return double the area
  16. */
  17. function calculate_area($xs, $ys) {
  18. if (!_check_polygon($xs, $ys)) {
  19. return FALSE;
  20. }
  21. //calculate and return the answer
  22. return abs((subCalculation($xs, $ys)) - (subCalculation($ys, $xs)))/2;
  23. }
  24. /**
  25. * Area Under One Line Segment
  26. */
  27. function subCalculation($a, $b) {
  28. $answer = 0;
  29. for ($i=0; $i < (count($a)-1); $i++) {
  30. $answer += ($a[$i] * $b[$i+1]);
  31. }
  32. $answer += $a[count($a)-1] * $b[0];
  33. return $answer;
  34. }
  35. /**
  36. * Get intersection point of two lines, assumes no paralells
  37. */
  38. function lines_intersect($line1, $line2) {
  39. if (!is_array($line1) || !is_array($line2)) {
  40. $msg = '[geometry-lib] line: Invalid - each line must be array(array(x,y), array(x,y)) - line1: '. print_r($line1,1) .', line2: '. print_r($line2,1);
  41. error_log($msg);
  42. return FALSE;
  43. }
  44. if (count($line1)!=2 || count($line2)!=2) {
  45. $msg = '[geometry-lib] line: Invalid - each line must have two arrays';
  46. error_log($msg);
  47. return FALSE;
  48. }
  49. // get slopes m1 and m2
  50. // p,q,r,s points
  51. list($p,$q) = $line1;
  52. list($r,$s) = $line2;
  53. $m1 = _get_slope($p, $q);
  54. $m2 = _get_slope($r, $s);
  55. //get intersect point
  56. // solving y-y1=m(x-x1) for each pair of points
  57. if ($m1 == $m2) {
  58. return NULL;
  59. }
  60. $x = (-$m2*$r[0] + $r[1] + $m1*$p[0] - $p[1]) / ($m1-$m2);
  61. $y = (-$m1*$r[1] + $m1*$m2*($r[0]-$p[0]) + $m2*$p[1]) / ($m2-$m1);
  62. if (_is_in_segment(array($x, $y), $p, $q) && _is_in_segment(array($x, $y), $r, $s))
  63. return array($x, $y);
  64. return NULL;
  65. }
  66. /**
  67. * Verify if point p is a point of the segment ab
  68. */
  69. function _is_in_segment($p, $a, $b) {
  70. //if ($a[X]==8.7 && $b[X]==6.3) {echo ":: ?? en segmento ? <br />";
  71. // echo "px= {$p[X]}".print_r($p,1)." >= min=". min($a[X],$b[X]) ."<br />";}
  72. if ( $p[X]>=min($a[X],$b[X]) && $p[X]<=max($a[X],$b[X])
  73. && $p[Y]>=min($a[Y],$b[Y]) && $p[Y]<=max($a[Y],$b[Y]) ) {
  74. //if ($a[X]==8.7 && $b[X]==6.3) echo ":: ?? si, en linea ? <br />";
  75. return _is_in_line($p, $a, $b);
  76. }
  77. return FALSE;
  78. }
  79. /**
  80. * Verify if point p is a point of the line ab
  81. */
  82. function _is_in_line($p, $a, $b) {
  83. $m1 = _get_slope($a, $b);
  84. $b1 = $a[Y]-$m1*$a[X];
  85. if (abs($p[Y] - ($m1*$p[X] + $b1)) < APROX) {
  86. return TRUE;
  87. }
  88. }
  89. /**
  90. * Get the slope of the line that pass through points p and q
  91. */
  92. function _get_slope($p, $q) {
  93. if ($q[X]-$p[X] == 0)
  94. return 0;
  95. return ($q[Y]-$p[Y])/($q[X]-$p[X]);
  96. }
  97. /**
  98. * Check if the coordinates are correct or not
  99. */
  100. function _check_polygon($xs, $ys) {
  101. //check that xs and ys have the same length
  102. if (count($xs) != count($ys)) {
  103. $msg = '[geometry-lib] polygon: Invalid - length of x and y coordinate arrays differs';
  104. error_log($msg);
  105. return FALSE;
  106. }
  107. //check that this is a polygon (more than 2 points!!)
  108. if (count($xs) < 3) {
  109. $msg = '[geometry-lib] polygon: Invalid '. polygon2string($xs, $ys);
  110. error_log($msg);
  111. return FALSE;
  112. }
  113. return TRUE;
  114. }
  115. function polygon2string($xs, $ys) {
  116. if (count($xs) < 3) {
  117. error_log('[geometry-lib] polygon: Polygon must have more than two points');
  118. return '( not a polygon )';
  119. }
  120. $output = '( ';
  121. //do it the long way to allow print bad polygons
  122. for ($i=0; $i < count($xs); $i++) {
  123. $points[$i] = array(X => $xs[$i]);
  124. }
  125. for ($i=0; $i < count($ys); $i++) {
  126. $points[$i] = array(Y => $ys[$i]);
  127. }
  128. foreach ($points as $point) {
  129. $output .= '('. (isset($point[X]) ? $point[X]: '') .', '. (isset($point[Y])? $point[Y]: '') .'),';
  130. }
  131. $output .= ' )';
  132. return $output;
  133. }
  134. /**
  135. * Verify if the point p is inside the region delimited by the
  136. * coordinates of the polygon
  137. * note: assumes *convex* polygons
  138. */
  139. function _is_inside_polygon($p, $xs, $ys) {
  140. if (!_check_polygon($xs, $ys)) {
  141. return FALSE;
  142. }
  143. //echo ":: _is_inside_polygon :: ({$p[X]}, {$p[Y]}) ? <br />";
  144. $conditionals = _get_inside_conditionals($xs, $ys);
  145. foreach ($conditionals as $condition) {
  146. if ($condition['sign'] == 'major') {
  147. if ( !($p[Y] >= $condition['m']*$p[X]+$condition['b']) ) {
  148. return FALSE;
  149. }
  150. }
  151. else { //minor
  152. if ( !($p[Y] <= $condition['m']*$p[X]+$condition['b']) ) {
  153. return FALSE;
  154. }
  155. }
  156. }
  157. return TRUE;
  158. }
  159. /**
  160. * Get the required conditionals which together makes the is_inside
  161. * a polygon condition, assumes convex
  162. */
  163. function _get_inside_conditionals($xs, $ys) {
  164. $conditionals = array();
  165. //echo ":: get_inside_cond :: 1st element ({$xs[0]}, {$ys[0]})<br />";
  166. for ($i=0; $i < (count($xs)-1); $i++) {
  167. //describe the line between points $i and $i+1
  168. $m = _get_slope(array($xs[$i], $ys[$i]), array($xs[$i+1], $ys[$i+1]));
  169. $b = $ys[$i] - $m*$xs[$i];
  170. //echo ":: get_inside_cond :: eval {$m}x + $b<br />";
  171. //decide where is inside
  172. //echo ":: get_inside_cond :: where is inside?<br />";
  173. $sign='';
  174. for ($j=0; $j < (count($xs)); $j++) {
  175. //$tmp = $m*$xs[$j]+$b; //print
  176. if (abs($ys[$j] - ($m*$xs[$j]+$b)) < APROX) {
  177. //echo ":: get_inside_cond :: not entering on {$ys[$j]} == {$tmp}<br />";
  178. continue;
  179. }
  180. //if (abs($m+0.370370)<APROX) echo ":: get_inside_cond :: :: eval ({$ys[$j]} > {$tmp})?<br />";
  181. if ($ys[$j] > $m*$xs[$j]+$b) {
  182. $sign='major';
  183. break;
  184. }
  185. else {
  186. $sign='minor';
  187. break;
  188. }
  189. }
  190. //echo ":: get_inside_cond :: -> sign=$sign<br />";
  191. $conditionals[] = array('m' => $m, 'b' => $b, 'sign' => $sign);
  192. }
  193. //the final conditional
  194. $m = _get_slope(array($xs[count($xs)-1], $ys[count($xs)-1]), array($xs[0], $ys[0]));
  195. $b = $ys[0] - $m*$xs[0];
  196. //echo ":: get_inside_cond :: eval {$m}x + $b<br />";
  197. //decide where is inside
  198. //echo ":: get_inside_cond :: where is inside?<br />";
  199. $sign='';
  200. for ($j=0; $j < (count($xs)); $j++) {
  201. if (abs($ys[$j] - ($m*$xs[$j]+$b)) < APROX) continue;
  202. if ($ys[$j] > $m*$xs[$j]+$b) {
  203. $sign='major';
  204. break;
  205. }
  206. else {
  207. $sign='minor';
  208. break;
  209. }
  210. }
  211. $conditionals[] = array('m' => $m, 'b' => $b, 'sign' => $sign);
  212. return $conditionals;
  213. }
  214. function get_intersection_data($rxs, $rys, $uxs, $uys) {
  215. $i_pol = get_intersection_polygon($rxs, $rys, $uxs, $uys);
  216. if (!is_array($i_pol)) {
  217. return array('success' => 0);
  218. }
  219. $r_area = calculate_area($rxs, $rys);
  220. $u_area = calculate_area($uxs, $uys);
  221. $ixs=array();
  222. $iys=array();
  223. foreach ($i_pol as $point) {
  224. $ixs[] = $point['point'][X];
  225. $iys[] = $point['point'][Y];
  226. }
  227. if (!_check_polygon($ixs, $iys)) {
  228. $success=0;
  229. }
  230. else {
  231. $i_area = calculate_area($ixs, $iys);
  232. $success = $i_area/$r_area;
  233. }
  234. return array(
  235. 'success' => $success,
  236. );
  237. }
  238. /**
  239. * Get an array which describe the polygon formed by the intersection of
  240. * the two polygons given
  241. */
  242. function get_intersection_polygon($rxs, $rys, $uxs, $uys) {
  243. list($intern_points, $intersection_points) = _get_intersection_polygon_data($rxs, $rys, $uxs, $uys);
  244. //print '<br>=========<br>intersection points: '. print_r($intersection_points,1);
  245. //print '<br>=========<br>intern points: '. print_r($intern_points,1);
  246. //print '<br>=========<br>';
  247. /**
  248. * Algoritmo para encontrar el orden correcto de los puntos del
  249. * poligono resultante al intersectar los dos pasados como parametros
  250. *
  251. * pol[0] = primer x
  252. * mientras { pol[0]!=pol(tam(pol)-1) o tam(pol)==1 }
  253. * umo=pol[tam(pol)-1]
  254. * salir=false
  255. * para cada ptoInterno y !salir
  256. * si { cotiguo(ptoInterno, umo) y no es el anterior }
  257. * pol[] = ptoInterno
  258. * salir = true
  259. * fin si
  260. * fin para
  261. * para cada xfaltante y !salir
  262. * si { contiguo(x, umo) y no es el anterior }
  263. * pol[] = x
  264. * salir=true
  265. * fin si
  266. * fin para
  267. * TODO: vertices internos no contiguos a interseccion ·
  268. * fin mientras
  269. *
  270. */
  271. if (!count($intersection_points)) {
  272. if (fully_inside($uxs, $uys, $rxs, $rys)) {
  273. return _to_points_intersection($uxs, $uys);
  274. }
  275. return NULL;
  276. }
  277. // intersection polygon points ordered
  278. $pol = array();
  279. $pol[0] = array_shift($intersection_points);
  280. //$pol[0]['point'] = $intersection_point['point'];
  281. $pol[0]['type'] = 'intersection';
  282. $next_index = 1;
  283. // TODO: work out condition, now $max_v vertices is the major # supported
  284. // on intersection and there are unuseful extra work done
  285. $max_v=20;
  286. $cc=0;
  287. while (( ($pol[0]!=$pol[count($pol)-1] || count($pol)==1) ) && $cc<$max_v) {
  288. $last_point = $pol[count($pol)-1];
  289. //print 'last point = '. print_r($last_point,1);
  290. $salir = FALSE;
  291. //echo ":: bucle de internos !!<br />";
  292. for ($i=0; ($i<count($intern_points)) && !$salir; $i++) {
  293. //verify if the point is next to last_point
  294. $p=$intern_points[$i];
  295. $p['type'] = 'intern';
  296. //echo 'p='.print_r($p,1).' last_point='.print_r($last_point,1).' pol='.print_r($rr=_to_points_array($rxs,$rys),1);
  297. //TODO: consider all cases(not intern nor intersection points followed in a polygon)
  298. switch ($last_point['type']) {
  299. case 'intersection':
  300. //echo ":: entro a interseccion !!<br />";
  301. //echo ":: :: con el punto p = " . print_r($p,1) ."<br />";
  302. if ( _is_next_to($p['point'], $last_point, $rxs, $rys, TRUE)
  303. || _is_next_to($p['point'], $last_point, $uxs, $uys, TRUE) ) {
  304. //echo "-> asigno el punto !!<br />";
  305. if ( isset($pol[$next_index-2]) ) {
  306. if ($pol[$next_index-2] != $p) {
  307. $pol[] = $p;
  308. $salir=TRUE;
  309. $last_point = $pol[count($pol)-1];
  310. $next_index++;
  311. }
  312. }
  313. else {
  314. //echo $i.'shols ';
  315. //print "{$p[X]} ...... {$p[Y]}<br>";
  316. $pol[] = $p;
  317. $salir=TRUE;
  318. $last_point = $pol[count($pol)-1];
  319. $next_index++;
  320. }
  321. }
  322. break;
  323. case 'intern':
  324. //echo ":: entro a interno !!<br />";
  325. if ( _is_next_to($p, $last_point, $rxs, $rys)
  326. || _is_next_to($p, $last_point, $uxs, $uys) ) {
  327. //echo "-> asigno el punto !!<br />";
  328. if ( isset($pol[$next_index-2]) ) {
  329. if ($pol[$next_index-2] != $p) {
  330. $pol[] = $p;
  331. $salir=TRUE;
  332. $last_point = $pol[count($pol)-1];
  333. $next_index++;
  334. }
  335. }
  336. else {
  337. //echo $i.'shols ';
  338. //print "{$p[X]} ...... {$p[Y]}<br>";
  339. $pol[] = $p;
  340. $salir=TRUE;
  341. $last_point = $pol[count($pol)-1];
  342. $next_index++;
  343. }
  344. }
  345. break;
  346. }
  347. }
  348. //echo ":: FIN bucle de internos !!<br />";
  349. //print 'last point = '. print_r($last_point,1);
  350. //echo ":: bucle de intersecciones !!<br />";
  351. for ($i=0; ($i<count($intersection_points)) && !$salir; $i++) {
  352. //verify if the point is next to last_point
  353. $p=$intersection_points[$i];
  354. $p['type'] = 'intersection';
  355. //echo ":: :: con el punto p = " . print_r($p,1) ."<br />";
  356. if ( _is_next_to($p, $last_point, $rxs, $rys, TRUE)
  357. || _is_next_to($p, $last_point, $uxs, $uys, TRUE) ) {
  358. //echo "-> asigno el punto !!<br />";
  359. if ( isset($pol[$next_index-2]) ) {
  360. if ($pol[$next_index-2] != $p) {
  361. $pol[] = $p;
  362. $salir=TRUE;
  363. $last_point = $pol[count($pol)-1];
  364. $next_index++;
  365. }
  366. }
  367. else {
  368. //echo $i.'shols ';
  369. //print "{$p[X]} ...... {$p[Y]}<br>";
  370. $pol[] = $p;
  371. $salir=TRUE;
  372. $last_point = $pol[count($pol)-1];
  373. $next_index++;
  374. }
  375. }
  376. }
  377. //echo ":: FIN bucle de intersecciones !!<br />";
  378. //print 'last point = '. print_r($last_point,1);
  379. //echo ":: procesar puntos internos no limitrofes!!<br />";
  380. //echo ":: proc ptos intern :: eval ({$last_point['point'][X]}, {$last_point['point'][Y]})<br />";
  381. if ($last_point['type'] != 'intern' && $last_point['type'] != 'intern-no-limit') {
  382. continue;
  383. }
  384. else if (!$salir) { // review next_to polygon points
  385. //echo ":: proc ptos intern :: review next_to polygon points<br />";
  386. // get next_to points depending of the polygon
  387. if ( array_search($last_point['point'], $r_points=_to_points_array($rxs, $rys)) !== FALSE ) {
  388. //echo ":: proc ptos intern :: pto en el poligono resultado<br />";
  389. $right_point = _get_right_point($last_point['point'], $r_points);
  390. $left_point = _get_left_point($last_point['point'], $r_points);
  391. // is inside the other polygon?
  392. $p = array('type'=>'intern-no-limit');
  393. if (_is_inside_polygon($right_point, $uxs, $uys)) {
  394. //echo ":: proc ptos intern :: pto derecho del pto poligono dento de la region de upol<br />";
  395. //echo "-> asigno el punto !!<br />";
  396. $p['point'] = $right_point;
  397. if ( isset($pol[$next_index-2]) ) {
  398. if ($pol[$next_index-2]['point'] != $p['point']) {
  399. $pol[] = $p;
  400. $salir=TRUE;
  401. $last_point = $pol[count($pol)-1];
  402. $next_index++;
  403. }
  404. }
  405. else {
  406. $pol[] = $p;
  407. $salir=TRUE;
  408. $last_point = $pol[count($pol)-1];
  409. $next_index++;
  410. }
  411. }
  412. else if (_is_inside_polygon($left_point, $uxs, $uys)) {
  413. //echo ":: proc ptos intern :: pto izquierdo del pto poligono dento de la region de upol<br />";
  414. //echo "-> asigno el punto !!<br />";
  415. $p['point'] = $left_point;
  416. if ( isset($pol[$next_index-2]) ) {
  417. if ($pol[$next_index-2]['point'] != $p['point']) {
  418. $pol[] = $p;
  419. $salir=TRUE;
  420. $last_point = $pol[count($pol)-1];
  421. $next_index++;
  422. }
  423. }
  424. else {
  425. $pol[] = $p;
  426. $salir=TRUE;
  427. $last_point = $pol[count($pol)-1];
  428. $next_index++;
  429. }
  430. }
  431. }
  432. else if ( array_search($last_point['point'], $u_points=_to_points_array($uxs, $uys)) !== FALSE ) {
  433. //echo ":: proc ptos ern :: pto en el poligono usuario<br />";
  434. $right_point = _get_right_point($last_point['point'], $u_points);
  435. $left_point = _get_left_point($last_point['point'], $u_points);
  436. // is inside the other polygon?
  437. $p = array('type'=>'intern-no-limit');
  438. if (_is_inside_polygon($right_point, $rxs, $rys) && !$salir) {
  439. //echo ":: proc ptos intern :: pto derecho del pto poligono dentro de la region de rpol<br />";
  440. $p['point'] = $right_point;
  441. if ( isset($pol[$next_index-2]) ) {
  442. if ($pol[$next_index-2]['point'] != $p['point']) {
  443. //echo "-> asigno el punto !!<br />";
  444. $pol[] = $p;
  445. $salir=TRUE;
  446. $last_point = $pol[count($pol)-1];
  447. $next_index++;
  448. }
  449. }
  450. else {
  451. //echo "-> asigno el punto !!<br />";
  452. $pol[] = $p;
  453. $salir=TRUE;
  454. $last_point = $pol[count($pol)-1];
  455. $next_index++;
  456. }
  457. }
  458. if (_is_inside_polygon($left_point, $rxs, $rys) && !$salir) {
  459. //echo ":: proc ptos intern :: pto izquierdo del pto poligono dentro de la region de rpol<br />";
  460. //echo "-> asigno el punto !!<br />";
  461. $p['point'] = $left_point;
  462. ////echo "pol: ". print_r($pol[$next_index-2],1) ." p=".print_r($p,1)."doo !!<br />";
  463. if ( isset($pol[$next_index-2]) ) {
  464. if ($pol[$next_index-2]['point'] != $p['point']) {
  465. $pol[] = $p;
  466. $salir=TRUE;
  467. $last_point = $pol[count($pol)-1];
  468. $next_index++;
  469. }
  470. }
  471. else {
  472. $pol[] = $p;
  473. $salir=TRUE;
  474. $last_point = $pol[count($pol)-1];
  475. $next_index++;
  476. }
  477. }
  478. }
  479. }
  480. //echo ":: FIN procesar puntos internos no limitrofes!!<br />";
  481. $cc++;
  482. //print_r($pol);
  483. }
  484. //echo ":: termino con $cc iteraciones hechas<br />";
  485. return $pol;
  486. }
  487. /**
  488. * Get needed data to build the intesection polygon
  489. */
  490. function _get_intersection_polygon_data($rxs, $rys, $uxs, $uys) {
  491. $ixs = array();
  492. $iys = array();
  493. $intern_points = array();
  494. $intersection_points = array();
  495. // iterate through the result polygon sides
  496. for ($i=0; $i < (count($rxs)-1); $i++) {
  497. $rline = array( array($rxs[$i],$rys[$i]), array($rxs[$i+1],$rys[$i+1]) );
  498. // iterate through the user polygon sides
  499. for ($j=0; $j < (count($uxs)-1); $j++) {
  500. $uline = array( array($uxs[$j],$uys[$j]), array($uxs[$j+1],$uys[$j+1]) );
  501. if ( ($ipoint=lines_intersect($rline,$uline)) != NULL ) {
  502. $rpoint1 = array($rxs[$i], $rys[$i]);
  503. $rpoint2 = array($rxs[$i+1], $rys[$i+1]);
  504. $upoint1 = array($uxs[$j], $uys[$j]);
  505. $upoint2 = array($uxs[$j+1], $uys[$j+1]);
  506. //save intesection points
  507. $intersection_points[] = array(
  508. 'rsegment' => array( $rpoint1, $rpoint2 ),
  509. 'usegment' => array( $upoint1, $upoint2 ),
  510. 'point' => $ipoint,
  511. );
  512. //get intern points
  513. //echo ":: get_int_poly :: eval ({$rpoint1[X]}, {$rpoint1[Y]}) is inside upolygon?<br />";
  514. if (_is_inside_polygon($rpoint1, $uxs, $uys)) {
  515. //echo ":: get_int_poly :: ({$rpoint1[X]}, {$rpoint1[Y]}) inside: yes<br />";
  516. //echo ":: get_int_poly :: ({$rpoint1[X]}, {$rpoint1[Y]}) already on intern points?<br />";
  517. if (!in_intern_array($rpoint1, $intern_points)) {
  518. //echo ":: get_int_poly :: ({$rpoint1[X]}, {$rpoint1[Y]}) already: no, -> asigning<br />";
  519. $rp = _get_right_point($rpoint1, _to_points_array($rxs, $rys));
  520. $lp = _get_left_point($rpoint1, _to_points_array($rxs, $rys));
  521. $intern_points[] = array(
  522. 'point' => $rpoint1,
  523. 'segment1' => array($lp, $rpoint1),
  524. 'segment2' => array($rpoint1, $rp),
  525. );
  526. }
  527. }
  528. //echo ":: get_int_poly :: eval ({$rpoint2[X]}, {$rpoint2[Y]}) is inside upolygon?<br />";
  529. if (_is_inside_polygon($rpoint2, $uxs, $uys)) {
  530. //echo ":: get_int_poly :: ({$rpoint2[X]}, {$rpoint2[Y]}) inside: yes<br />";
  531. //echo ":: get_int_poly :: ({$rpoint2[X]}, {$rpoint2[Y]}) already on intern points?<br />";
  532. if (!in_intern_array($rpoint2, $intern_points)) {
  533. //echo ":: get_int_poly :: ({$rpoint2[X]}, {$rpoint2[Y]}) already: no, -> asigning<br />";
  534. $rp = _get_right_point($rpoint2, _to_points_array($rxs, $rys));
  535. $lp = _get_left_point($rpoint2, _to_points_array($rxs, $rys));
  536. $intern_points[] = array(
  537. 'point' => $rpoint2,
  538. 'segment1' => array($lp, $rpoint2),
  539. 'segment2' => array($rpoint2, $rp),
  540. );
  541. }
  542. }
  543. //echo ":: get_int_poly :: eval ({$upoint1[X]}, {$upoint1[Y]}) is inside rpolygon?<br />";
  544. if (_is_inside_polygon($upoint1, $rxs, $rys)) {
  545. //echo ":: get_int_poly :: ({$upoint1[X]}, {$upoint1[Y]}) inside: yes<br />";
  546. //echo ":: get_int_poly :: ({$upoint1[X]}, {$upoint1[Y]}) already on intern points?<br />";
  547. if (!in_intern_array($upoint1, $intern_points)) {
  548. //echo ":: get_int_poly :: ({$upoint1[X]}, {$upoint1[Y]}) already: no, -> asigning<br />";
  549. $rp = _get_right_point($upoint1, _to_points_array($uxs, $uys));
  550. $lp = _get_left_point($upoint1, _to_points_array($uxs, $uys));
  551. $intern_points[] = array(
  552. 'point' => $upoint1,
  553. 'segment1' => array($lp, $upoint1),
  554. 'segment2' => array($upoint1, $rp),
  555. );
  556. }
  557. }
  558. //echo ":: get_int_poly :: eval ({$upoint2[X]}, {$upoint2[Y]}) is inside rpolygon?<br />";
  559. if (_is_inside_polygon($upoint2, $rxs, $rys)) {
  560. //echo ":: get_int_poly :: ({$upoint2[X]}, {$upoint2[Y]}) inside: yes<br />";
  561. //echo ":: get_int_poly :: ({$upoint2[X]}, {$upoint2[Y]}) already on intern points?<br />";
  562. if (!in_intern_array($upoint2, $intern_points)) {
  563. //echo ":: get_int_poly :: ({$upoint2[X]}, {$upoint2[Y]}) already: no, -> asigning<br />";
  564. $rp = _get_right_point($upoint2, _to_points_array($uxs, $uys));
  565. $lp = _get_left_point($upoint2, _to_points_array($uxs, $uys));
  566. $intern_points[] = array(
  567. 'point' => $upoint2,
  568. 'segment1' => array($lp, $upoint2),
  569. 'segment2' => array($upoint2, $rp),
  570. );
  571. }
  572. }
  573. }
  574. }
  575. // process the final user line
  576. $uline = array( array($uxs[count($uxs)-1],$uys[count($uxs)-1]), array($uxs[0],$uys[0]) );
  577. if ( ($ipoint=lines_intersect($rline,$uline)) != NULL ) {
  578. $rpoint1 = array($rxs[$i], $rys[$i]);
  579. $rpoint2 = array($rxs[$i+1], $rys[$i+1]);
  580. $upoint1 = array($uxs[$j], $uys[$j]);
  581. $upoint2 = array($uxs[$j+1], $uys[$j+1]);
  582. //save intesection points
  583. $intersection_points[] = array(
  584. 'rsegment' => array( $rpoint1, $rpoint2 ),
  585. 'usegment' => array( $upoint1, $upoint2 ),
  586. 'point' => $ipoint,
  587. );
  588. //get intern points
  589. //echo ":: get_int_poly :: eval ({$rpoint1[X]}, {$rpoint1[Y]}) is inside upolygon?<br />";
  590. if (_is_inside_polygon($rpoint1, $uxs, $uys)) {
  591. //echo ":: get_int_poly :: ({$rpoint1[X]}, {$rpoint1[Y]}) inside: yes<br />";
  592. //echo ":: get_int_poly :: ({$rpoint1[X]}, {$rpoint1[Y]}) already on intern points?<br />";
  593. if (!in_intern_array($rpoint1, $intern_points)) {
  594. //echo ":: get_int_poly :: ({$rpoint1[X]}, {$rpoint1[Y]}) already: no, -> asigning<br />";
  595. $rp = _get_right_point($rpoint1, _to_points_array($rxs, $rys));
  596. $lp = _get_left_point($rpoint1, _to_points_array($rxs, $rys));
  597. $intern_points[] = array(
  598. 'point' => $rpoint1,
  599. 'segment1' => array($lp, $rpoint1),
  600. 'segment2' => array($rpoint1, $rp),
  601. );
  602. }
  603. }
  604. //echo ":: get_int_poly :: eval ({$rpoint2[X]}, {$rpoint2[Y]}) is inside upolygon?<br />";
  605. if (_is_inside_polygon($rpoint2, $uxs, $uys)) {
  606. //echo ":: get_int_poly :: ({$rpoint2[X]}, {$rpoint2[Y]}) inside: yes<br />";
  607. //echo ":: get_int_poly :: ({$rpoint2[X]}, {$rpoint2[Y]}) already on intern points?<br />";
  608. if (!in_intern_array($rpoint2, $intern_points)) {
  609. //echo ":: get_int_poly :: ({$rpoint2[X]}, {$rpoint2[Y]}) already: no, -> asigning<br />";
  610. $rp = _get_right_point($rpoint2, _to_points_array($rxs, $rys));
  611. $lp = _get_left_point($rpoint2, _to_points_array($rxs, $rys));
  612. $intern_points[] = array(
  613. 'point' => $rpoint2,
  614. 'segment1' => array($lp, $rpoint2),
  615. 'segment2' => array($rpoint2, $rp),
  616. );
  617. }
  618. }
  619. //echo ":: get_int_poly :: eval ({$upoint1[X]}, {$upoint1[Y]}) is inside rpolygon?<br />";
  620. if (_is_inside_polygon($upoint1, $rxs, $rys)) {
  621. //echo ":: get_int_poly :: ({$upoint1[X]}, {$upoint1[Y]}) inside: yes<br />";
  622. //echo ":: get_int_poly :: ({$upoint1[X]}, {$upoint1[Y]}) already on intern points?<br />";
  623. if (!in_intern_array($upoint1, $intern_points)) {
  624. //echo ":: get_int_poly :: ({$upoint1[X]}, {$upoint1[Y]}) already: no, -> asigning<br />";
  625. $rp = _get_right_point($upoint1, _to_points_array($uxs, $uys));
  626. $lp = _get_left_point($upoint1, _to_points_array($uxs, $uys));
  627. $intern_points[] = array(
  628. 'point' => $upoint1,
  629. 'segment1' => array($lp, $upoint1),
  630. 'segment2' => array($upoint1, $rp),
  631. );
  632. }
  633. }
  634. //echo ":: get_int_poly :: eval ({$upoint2[X]}, {$upoint2[Y]}) is inside rpolygon?<br />";
  635. if (_is_inside_polygon($upoint2, $rxs, $rys)) {
  636. //echo ":: get_int_poly :: ({$upoint2[X]}, {$upoint2[Y]}) inside: yes<br />";
  637. //echo ":: get_int_poly :: ({$upoint2[X]}, {$upoint2[Y]}) already on intern points?<br />";
  638. if (!in_intern_array($upoint2, $intern_points)) {
  639. //echo ":: get_int_poly :: ({$upoint2[X]}, {$upoint2[Y]}) already: no, -> asigning<br />";
  640. $rp = _get_right_point($upoint2, _to_points_array($uxs, $uys));
  641. $lp = _get_left_point($upoint2, _to_points_array($uxs, $uys));
  642. $intern_points[] = array(
  643. 'point' => $upoint2,
  644. 'segment1' => array($lp, $upoint2),
  645. 'segment2' => array($upoint2, $rp),
  646. );
  647. }
  648. }
  649. }
  650. // end of iterate through the user polygon sides
  651. }
  652. // process the final result line
  653. $rline = array( array($rxs[$i=count($rxs)-1],$rys[$i=count($rxs)-1]), array($rxs[0],$rys[0]) );
  654. // iterate through the user polygon sides
  655. for ($j=0; $j < (count($uxs)-1); $j++) {
  656. $uline = array( array($uxs[$j],$uys[$j]), array($uxs[$j+1],$uys[$j+1]) );
  657. if ( ($ipoint=lines_intersect($rline,$uline)) != NULL ) {
  658. $rpoint1 = array($rxs[$i], $rys[$i]);
  659. $rpoint2 = array($rxs[0], $rys[0]);
  660. $upoint1 = array($uxs[$j], $uys[$j]);
  661. $upoint2 = array($uxs[$j+1], $uys[$j+1]);
  662. //save intesection points
  663. $intersection_points[] = array(
  664. 'rsegment' => array( $rpoint1, $rpoint2 ),
  665. 'usegment' => array( $upoint1, $upoint2 ),
  666. 'point' => $ipoint,
  667. );
  668. //get intern points
  669. //echo ":: get_int_poly :: eval ({$rpoint1[X]}, {$rpoint1[Y]}) is inside upolygon?<br />";
  670. if (_is_inside_polygon($rpoint1, $uxs, $uys)) {
  671. //echo ":: get_int_poly :: ({$rpoint1[X]}, {$rpoint1[Y]}) inside: yes<br />";
  672. //echo ":: get_int_poly :: ({$rpoint1[X]}, {$rpoint1[Y]}) already on intern points?<br />";
  673. if (!in_intern_array($rpoint1, $intern_points)) {
  674. //echo ":: get_int_poly :: ({$rpoint1[X]}, {$rpoint1[Y]}) already: no, -> asigning<br />";
  675. $rp = _get_right_point($rpoint1, _to_points_array($rxs, $rys));
  676. $lp = _get_left_point($rpoint1, _to_points_array($rxs, $rys));
  677. $intern_points[] = array(
  678. 'point' => $rpoint1,
  679. 'segment1' => array($lp, $rpoint1),
  680. 'segment2' => array($rpoint1, $rp),
  681. );
  682. }
  683. }
  684. //echo ":: get_int_poly :: eval ({$rpoint2[X]}, {$rpoint2[Y]}) is inside upolygon?<br />";
  685. if (_is_inside_polygon($rpoint2, $uxs, $uys)) {
  686. //echo ":: get_int_poly :: ({$rpoint2[X]}, {$rpoint2[Y]}) inside: yes<br />";
  687. //echo ":: get_int_poly :: ({$rpoint2[X]}, {$rpoint2[Y]}) already on intern points?<br />";
  688. if (!in_intern_array($rpoint2, $intern_points)) {
  689. //echo ":: get_int_poly :: ({$rpoint2[X]}, {$rpoint2[Y]}) already: no, -> asigning<br />";
  690. $rp = _get_right_point($rpoint2, _to_points_array($rxs, $rys));
  691. $lp = _get_left_point($rpoint2, _to_points_array($rxs, $rys));
  692. $intern_points[] = array(
  693. 'point' => $rpoint2,
  694. 'segment1' => array($lp, $rpoint2),
  695. 'segment2' => array($rpoint2, $rp),
  696. );
  697. }
  698. }
  699. //echo ":: get_int_poly :: eval ({$upoint1[X]}, {$upoint1[Y]}) is inside rpolygon?<br />";
  700. if (_is_inside_polygon($upoint1, $rxs, $rys)) {
  701. //echo ":: get_int_poly :: ({$upoint1[X]}, {$upoint1[Y]}) inside: yes<br />";
  702. //echo ":: get_int_poly :: ({$upoint1[X]}, {$upoint1[Y]}) already on intern points?<br />";
  703. if (!in_intern_array($upoint1, $intern_points)) {
  704. //echo ":: get_int_poly :: ({$upoint1[X]}, {$upoint1[Y]}) already: no, -> asigning<br />";
  705. $rp = _get_right_point($upoint1, _to_points_array($uxs, $uys));
  706. $lp = _get_left_point($upoint1, _to_points_array($uxs, $uys));
  707. $intern_points[] = array(
  708. 'point' => $upoint1,
  709. 'segment1' => array($lp, $upoint1),
  710. 'segment2' => array($upoint1, $rp),
  711. );
  712. }
  713. }
  714. //echo ":: get_int_poly :: eval ({$upoint2[X]}, {$upoint2[Y]}) is inside rpolygon?<br />";
  715. if (_is_inside_polygon($upoint2, $rxs, $rys)) {
  716. //echo ":: get_int_poly :: ({$upoint2[X]}, {$upoint2[Y]}) inside: yes<br />";
  717. //echo ":: get_int_poly :: ({$upoint2[X]}, {$upoint2[Y]}) already on intern points?<br />";
  718. if (!in_intern_array($upoint2, $intern_points)) {
  719. //echo ":: get_int_poly :: ({$upoint2[X]}, {$upoint2[Y]}) already: no, -> asigning<br />";
  720. $rp = _get_right_point($upoint2, _to_points_array($uxs, $uys));
  721. $lp = _get_left_point($upoint2, _to_points_array($uxs, $uys));
  722. $intern_points[] = array(
  723. 'point' => $upoint2,
  724. 'segment1' => array($lp, $upoint2),
  725. 'segment2' => array($upoint2, $rp),
  726. );
  727. }
  728. }
  729. }
  730. }
  731. // process the final user line
  732. $uline = array( array($uxs[count($uxs)-1],$uys[count($uxs)-1]), array($uxs[0],$uys[0]) );
  733. if ( ($ipoint=lines_intersect($rline,$uline)) != NULL ) {
  734. $rpoint1 = array($rxs[$i], $rys[$i]);
  735. $rpoint2 = array($rxs[0], $rys[0]);
  736. $upoint1 = array($uxs[$j], $uys[$j]);
  737. $upoint2 = array($uxs[$j+1], $uys[$j+1]);
  738. //save intesection points
  739. $intersection_points[] = array(
  740. 'rsegment' => array( $rpoint1, $rpoint2 ),
  741. 'usegment' => array( $upoint1, $upoint2 ),
  742. 'point' => $ipoint,
  743. );
  744. //get intern points
  745. //echo ":: get_int_poly :: eval ({$rpoint1[X]}, {$rpoint1[Y]}) is inside upolygon?<br />";
  746. if (_is_inside_polygon($rpoint1, $uxs, $uys)) {
  747. //echo ":: get_int_poly :: ({$rpoint1[X]}, {$rpoint1[Y]}) inside: yes<br />";
  748. //echo ":: get_int_poly :: ({$rpoint1[X]}, {$rpoint1[Y]}) already on intern points?<br />";
  749. if (!in_intern_array($rpoint1, $intern_points)) {
  750. //echo ":: get_int_poly :: ({$rpoint1[X]}, {$rpoint1[Y]}) already: no, -> asigning<br />";
  751. $rp = _get_right_point($rpoint1, _to_points_array($rxs, $rys));
  752. $lp = _get_left_point($rpoint1, _to_points_array($rxs, $rys));
  753. $intern_points[] = array(
  754. 'point' => $rpoint1,
  755. 'segment1' => array($lp, $rpoint1),
  756. 'segment2' => array($rpoint1, $rp),
  757. );
  758. }
  759. }
  760. //echo ":: get_int_poly :: eval ({$rpoint2[X]}, {$rpoint2[Y]}) is inside upolygon?<br />";
  761. if (_is_inside_polygon($rpoint2, $uxs, $uys)) {
  762. //echo ":: get_int_poly :: ({$rpoint2[X]}, {$rpoint2[Y]}) inside: yes<br />";
  763. //echo ":: get_int_poly :: ({$rpoint2[X]}, {$rpoint2[Y]}) already on intern points?<br />";
  764. if (!in_intern_array($rpoint2, $intern_points)) {
  765. //echo ":: get_int_poly :: ({$rpoint2[X]}, {$rpoint2[Y]}) already: no, -> asigning<br />";
  766. $rp = _get_right_point($rpoint2, _to_points_array($rxs, $rys));
  767. $lp = _get_left_point($rpoint2, _to_points_array($rxs, $rys));
  768. $intern_points[] = array(
  769. 'point' => $rpoint2,
  770. 'segment1' => array($lp, $rpoint2),
  771. 'segment2' => array($rpoint2, $rp),
  772. );
  773. }
  774. }
  775. //echo ":: get_int_poly :: eval ({$upoint1[X]}, {$upoint1[Y]}) is inside rpolygon?<br />";
  776. if (_is_inside_polygon($upoint1, $rxs, $rys)) {
  777. //echo ":: get_int_poly :: ({$upoint1[X]}, {$upoint1[Y]}) inside: yes<br />";
  778. //echo ":: get_int_poly :: ({$upoint1[X]}, {$upoint1[Y]}) already on intern points?<br />";
  779. if (!in_intern_array($upoint1, $intern_points)) {
  780. //echo ":: get_int_poly :: ({$upoint1[X]}, {$upoint1[Y]}) already: no, -> asigning<br />";
  781. $rp = _get_right_point($upoint1, _to_points_array($uxs, $uys));
  782. $lp = _get_left_point($upoint1, _to_points_array($uxs, $uys));
  783. $intern_points[] = array(
  784. 'point' => $upoint1,
  785. 'segment1' => array($lp, $upoint1),
  786. 'segment2' => array($upoint1, $rp),
  787. );
  788. }
  789. }
  790. //echo ":: get_int_poly :: eval ({$upoint2[X]}, {$upoint2[Y]}) is inside rpolygon?<br />";
  791. if (_is_inside_polygon($upoint2, $rxs, $rys)) {
  792. //echo ":: get_int_poly :: ({$upoint2[X]}, {$upoint2[Y]}) inside: yes<br />";
  793. //echo ":: get_int_poly :: ({$upoint2[X]}, {$upoint2[Y]}) already on intern points?<br />";
  794. if (!in_intern_array($upoint2, $intern_points)) {
  795. //echo ":: get_int_poly :: ({$upoint2[X]}, {$upoint2[Y]}) already: no, -> asigning<br />";
  796. $rp = _get_right_point($upoint2, _to_points_array($uxs, $uys));
  797. $lp = _get_left_point($upoint2, _to_points_array($uxs, $uys));
  798. $intern_points[] = array(
  799. 'point' => $upoint2,
  800. 'segment1' => array($lp, $upoint2),
  801. 'segment2' => array($upoint2, $rp),
  802. );
  803. }
  804. }
  805. }
  806. // end of iterate through the user polygon sides
  807. // end of iterate through the result polygon sides
  808. return array($intern_points, $intersection_points);
  809. }
  810. /**
  811. * Verify if a list of points a is inside or not a polygon b
  812. */
  813. function fully_inside($axs, $ays, $bxs, $bys) {
  814. // iterate through the points
  815. for ($i=0; $i < count($axs); $i++) {
  816. if (!_is_inside_polygon(array($axs[$i],$ays[$i]), $bxs, $bys)) {
  817. return FALSE;
  818. }
  819. }
  820. return TRUE;
  821. }
  822. function _is_next_to($point, $last_point, $xs, $ys, $between_points=FALSE) {
  823. $polygon = _to_points_array($xs, $ys);
  824. if ( is_array($polygon) && ($pos=array_search($point, $polygon)) !== NULL && !empty($pos)) {
  825. //echo ":: :: is_next_to :: pos found !!<br />";
  826. if ( $rp=_get_right_point($last_point['point'], $polygon) == $point
  827. || $lp=_get_left_point($last_point['point'], $polygon) == $point ) {
  828. //echo ":: :: is_next_to :: return simple next to !!<br />";
  829. return TRUE;
  830. }
  831. }
  832. else if ($between_points) {
  833. //echo ":: :: is_next_to :: between points !!<br />";
  834. switch ($last_point['type']) {
  835. case 'intern':
  836. //echo ":: :: is_next_to :: between points :: intern !!<br />";
  837. $right_point = _get_right_point($last_point['point'], $polygon);
  838. $left_point = _get_left_point($last_point['point'], $polygon);
  839. /*echo 'left = '. print_r($left_point,1)
  840. .'right = '. print_r($right_point,1)
  841. .'point = '. print_r($point,1)
  842. .'last_point = '. print_r($last_point,1);*/
  843. //if (_is_in_segment($point, $last_point['segment'][0], $last_point['segment'][1])) {
  844. if ( _is_in_segment($point['point'], $last_point['segment1'][0], $last_point['segment1'][1])
  845. || _is_in_segment($point['point'], $last_point['segment2'][0], $last_point['segment2'][1])
  846. ) {
  847. //echo ":: :: is_next_to :: between points :: intern :: return in line !!<br />";
  848. return TRUE;
  849. }
  850. break;
  851. case 'intersection':
  852. //echo ":: :: is_next_to :: between points :: intersection !!<br />";
  853. // echo "entro a next_to_interseccion !!<br />";
  854. //echo "point=". print_r($point,1) .', last_point='. print_r($last_point) .'<br />';
  855. if ( _is_in_segment($point, $last_point['rsegment'][0], $last_point['rsegment'][1])
  856. || _is_in_segment($point, $last_point['usegment'][0], $last_point['usegment'][1])
  857. ) {
  858. //echo ":: :: is_next_to :: between points :: intersection :: return in line !!<br />";
  859. return TRUE;
  860. }
  861. break;
  862. }
  863. }
  864. return FALSE;
  865. }
  866. function _get_right_point($point, $polygon) {
  867. if ( ($pos=array_search($point, $polygon)) !== FALSE ) {
  868. if ($pos == count($polygon)-1) {
  869. return $polygon[0];
  870. }
  871. else {
  872. return $polygon[$pos+1];
  873. }
  874. }
  875. }
  876. function _get_left_point($point, $polygon) {
  877. //echo '==========?<br>'; print_r($polygon) . print_r($polygon_point) .'========<br>';
  878. if ( ($pos=array_search($point, $polygon)) !== FALSE ) {
  879. if ($pos == 0) {
  880. return $polygon[count($polygon)-1];
  881. }
  882. else {
  883. return $polygon[$pos-1];
  884. }
  885. }
  886. }
  887. function _to_points_array($xs, $ys) {
  888. if (!_check_polygon($xs, $ys)) {
  889. return FALSE;
  890. }
  891. $points = array();
  892. for ($i=0; $i < count($xs); $i++) {
  893. $points[] = array($xs[$i], $ys[$i]);
  894. }
  895. return $points;
  896. }
  897. function _to_points_intersection($xs, $ys) {
  898. if (!_check_polygon($xs, $ys)) {
  899. return FALSE;
  900. }
  901. $points = array();
  902. for ($i=0; $i < count($xs); $i++) {
  903. $points[] = array('point' => array($xs[$i], $ys[$i]));
  904. }
  905. return $points;
  906. }
  907. function in_intern_array($point, $intern_points) {
  908. foreach ($intern_points as $ipoint) {
  909. if (abs($ipoint['point'][X]-$point[X]) < APROX && abs($ipoint['point'][Y]-$point[Y]) < APROX)
  910. return TRUE;
  911. }
  912. return FALSE;
  913. }
  914. //ver si cada punto esta dentro o fuera de la figura par saber con cual comenzar