geometry.lib.php 37 KB

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