* @package chamilo.include.geometry */ DEFINE('DEBUG', false); /** * poly_init - build the array which will store the image of the polygone * @param max[x] X resolution * @param max[y] Y resolution * @returns an array such as: for all i in [0..max[x][ : for all j in [0..max[y][ : array[i][j] = FALSE */ function poly_init($max) { return array_fill(0, $max["x"]-1, array_fill(0, $max["y"]-1, FALSE)); } /** * poly_compile - return an array which holds the image of the polygone * FALSE = blank pixel * TRUE = black pixel * * @param poly points from the polygone * example: * poly[0]['x'] = ... * poly[0]['y'] = ... * poly[1]['x'] = ... * poly[1]['y'] = ... * ... * poly[n]['x'] = * poly[n]['y'] = * poly[n+1]['x'] = * poly[n+1]['y'] = * ... * @param max see poly_init * @param boolean print or not a debug * * @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) * in_poly(poly,i,j) = true iff (i,j) is inside the polygon defined by poly */ function poly_compile($poly, $max, $test = false) { $res = poly_init($max); // looking for EDGES // may be optimized by a dynamic choice // between Y and X based on max[y] $bord_lenght) { $bord_lenght = $max['y']; } //$bords = array_fill(0, $bord_lenght-1, array()); // building this array $bords = array_fill(0, $bord_lenght, array()); // building this array /* adding the first point of the polygone */ if (is_array($bords[$poly[0]['y']])) //avoid warning array_push($bords[$poly[0]['y']], $poly[0]['x']); $i = 1; // we re-use $i and $old_pente bellow the loop $old_pente=0; for ( ; // for each points of the polygon but the first $i1) if (($old_pente<0 && $pente>0) || ($old_pente>0 && $pente<0)) { if (is_array($bords[$poly[$i]['y']])) //avoid warning array_push($bords[$poly[$i]['y']],$poly[$i]['x']); if (DEBUG) echo '*('.$poly[$i]['x']. ';'.$poly[$i]['y'].') '; } /* detect the direction of the elevation in Y */ $dy_inc = ($poly[$i]['y']-$poly[$i-1]['y']) > 0 ? 1 : -1; $x = $poly[$i-1]['x']; // if (DEBUG) echo "init: ".$poly[$i-1]['y']." dy_inc: ".$dy_inc. // " end: ".$poly[$i]['y']." pente:".$pente; /* computing points between $poly[$i-1]['y'] and $poly[$i-1]['y'] */ // we iterate w/ $dy in ]$poly[$i-1]['y'],$poly[$i-1]['y'][ // w/ $dy_inc as increment for ($dy = $poly[$i-1]['y']+$dy_inc; $dy != $poly[$i]['y']; $dy += $dy_inc) { $x += $pente*$dy_inc; array_push($bords[$dy], $x); // if (DEBUG) echo '/('.$x.';'.$dy.') '; } $old_pente = $pente; } // closing the polygone (the edge between $poly[$i-1] and $poly[0]) if ($poly[$i-1]['y']!=$poly[0]['y']) {// droite--> rien à faire // elevation between $poly[0]['x'] and $poly[1]['x']) $rest = $poly[0]['y']-$poly[1]['y']; if ($rest!=0) $pente1 = ($poly[0]['x']-$poly[1]['x'])/($rest); else $pente1 = 0; // elevation between $poly[$i-1]['x'] and $poly[0]['x']) $pente = ($poly[$i-1]['x']-$poly[0]['x'])/ ($poly[$i-1]['y']-$poly[0]['y']); // if (DEBUG) echo 'start('.$poly[$i-1]['x'].','.$poly[$i-1]['y']. // ')-end('.$poly[0]['x'].','.$poly[0]['y']. // ')-pente'.$pente; // doubling the first point if needed (see above) if (($pente1<0 && $pente>0) || ($pente1>0 && $pente<0)) { if (is_array($bords[$poly[$i]['y']])) array_push($bords[$poly[$i]['y']], round($poly[$i]['x'])); //if (DEBUG) echo '('.$poly[$i-1]['x'].';'.$poly[$i-1]['y'].') '; } // doubling the last point if neededd if (($old_pente<0 && $pente>0) || ($old_pente>0 && $pente<0)) { if (is_array($bords[$poly[$i-1]['y']])) //avoid warning array_push($bords[$poly[$i-1]['y']], round($poly[$i-1]['x'])); //if (DEBUG) echo '*('.$poly[$i-1]['x'].';'.$poly[$i-1]['y'].') '; } $dy_inc = ($poly[0]['y']-$poly[$i-1]['y']) > 0 ? 1 : -1; $x = $poly[$i-1]['x']; // if (DEBUG) echo "init: ".$poly[$i-1]['y']." dy_inc: ".$dy_inc. // " end: ".$poly[0]['y']; for ($dy = $poly[$i-1]['y']+$dy_inc; $dy != $poly[0]['y']; $dy += $dy_inc) { $x += $pente*$dy_inc; array_push($bords[$dy], round($x)); // if (DEBUG) echo '/('.$x.';'.$dy.') '; } } /* filling the polygon */ /* basic idea: we sort a column of edges. For each pair of point, we color the points in between */ $n = count($bords); for ($i = 0; $i<$n; $i++) { // Y //error_log(__FILE__.' - Border Num '.$i,0); if (is_array($bords[$i])) { sort($bords[$i]); } for ($j = 0; $j'; } } } return $res; } /** * poly_dump - dump an image on the screen * * @param array the polygone as output by poly_compile() * @param array see above (poly_init) * @param string Format ('raw' text or 'html') * * @return string html code of the representation of the polygone image */ function poly_dump(&$poly, $max, $format='raw') { if ($format == 'html') { $s = "

\n";
    }
    for ($i=0; $i<$max['y']; $i++) {
        for($j=0; $j<$max['x']; $j++)
            if($poly[$j][$i] == TRUE)
                $s .= ($format=='html'?"1":'1');
            else
                $s .= "0";
        $s .= ($format=='html'?"
\n":"\n");
    }
    $s .= ($format=='html'?"

\n":"\n"); return $s; } /** * poly_result - compute statis for two polygones * * @param poly1 first polygone as returned by poly_compile * @param poly2 second .... * @param max resolution as specified for poly_init * * @returns (see below, UTSL) */ function poly_result(&$poly1, &$poly2, $max) { $onlyIn1 = 0; $surfaceOf1 = 0; $surfaceOf2 = 0; for ($i=0; $i<$max['x']; $i++) for($j=0; $j<$max['y']; $j++) { if (isset($poly1[$i][$j]) && ($poly1[$i][$j] == TRUE)) { $surfaceOf1++; if (isset($poly2[$i][$j]) && ($poly2[$i][$j] == FALSE)) $onlyIn1++; } if (isset($poly2[$i][$j]) && ($poly2[$i][$j] == TRUE)) $surfaceOf2++; } return array ( "s1" => $surfaceOf1, "s2" => $surfaceOf2, "both" => $surfaceOf1 - $onlyIn1, "s1Only" => $onlyIn1, "s2Only" => $surfaceOf2 - ($surfaceOf1 - $onlyIn1)); } /** * poly_touch - compute statis for two polygones * * @param poly1 first polygone as returned by poly_compile * @param poly2 second .... * @param max resolution as specified for poly_init * * @returns (see below, UTSL) */ function poly_touch(&$poly1, &$poly2, $max) { for ($i=0; $i<$max['x']; $i++) { for($j=0; $j<$max['y']; $j++) { if (isset($poly1[$i][$j]) && ($poly1[$i][$j] == true) && isset($poly2[$i][$j]) && ($poly2[$i][$j] == true)) { return true; } } } return FALSE; } /** * Convert a list of points in x1;y1|x2;y2|x3;y3 or x1;y1/x2;y2 format to * the format in which the functions in this library are expecting their data * @param string List of points in x1;y1|... format (or /) * @param string The points separator for the list (| or /) * @return array An array of points in the right format to use with the * local functions */ function convert_coordinates($coords,$sep='|') { $points = array(); $pairs = explode($sep,$coords); foreach ($pairs as $idx => $pcoord) { list($x,$y) = explode(';',$pcoord); $points[] = array('x'=>$x,'y'=>$y); } return $points; } /** * Returns the maximum coordinates in x,y (from 0,0) that the geometrical form * can reach * @param array Coordinates of one polygon * @return array ('x'=>val,'y'=>val) */ function poly_get_max(&$coords1, &$coords2) { $mx = 0; $my = 0; foreach ($coords1 as $coord) { if ($coord['x'] > $mx) { $mx = $coord['x']; } if ($coord['y'] > $my) { $my = $coord['y']; } } foreach ($coords2 as $coord) { if ($coord['x'] > $mx) { $mx = $coord['x']; } if ($coord['y'] > $my) { $my = $coord['y']; } } return array('x'=>$mx,'y'=>$my); }