* * @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 bool 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, []); // 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 each points of the polygon but the first for (; $i < sizeof($poly) && (!empty($poly[$i]['x']) && !empty($poly[$i]['y'])); $i++) { /* special cases */ if ($poly[$i - 1]['y'] == $poly[$i]['y']) { if ($poly[$i - 1]['x'] == $poly[$i]['x']) { continue; } // twice the same point else { // infinite elevation of the edge if (is_array($bords[$poly[$i]['y']])) { array_push($bords[$poly[$i]['y']], $poly[$i]['x']); } $old_pente = 0; continue; } } //echo 'point:'.$poly[$i]['y']; bug here // adding the point as a part of an edge 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'].') '; } /* computing the elevation of the edge going */ // from $poly[$i-1] to $poly[$i] $pente = ($poly[$i - 1]['x'] - $poly[$i]['x']) / ($poly[$i - 1]['y'] - $poly[$i]['y']); // if the sign of the elevation change from the one of the // previous edge, the point must be added a second time inside // $bords if ($i > 1) { 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 - 1]['y']])) { array_push($bords[$poly[$i - 1]['y']], round($poly[$i - 1]['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)); } } /* 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 < sizeof($bords[$i]); $j += 2) { // bords if (!isset($bords[$i][$j + 1])) { continue; } for ($k = round($bords[$i][$j]); $k <= $bords[$i][$j + 1]; $k++) { $res[$k][$i] = true; //filling the array with trues if ($test == 1) { /*how to draw the polygon in a human way: In ubuntu : sudo apt-get install gnuplot Create an empty file with all points with the result of this echos (No commas, no point, no headers) In gnuplot: For 1 polygon: plot "/home/jmontoya/test" For 2 polygons: plot "/home/jmontoya/test", "/home/jmontoya/test2" A new window will appear with the plot */ echo $k.' '.$i; echo '
'; } } } } 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 [ "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 = []; $pairs = explode($sep, $coords); foreach ($pairs as $idx => $pcoord) { list($x, $y) = explode(';', $pcoord); $points[] = ['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 ['x' => $mx, 'y' => $my]; } /** * Class Geometry * Utils for decode hotspots and check if the user choices are correct. */ class Geometry { /** * Decode a user choice as a point. * * @param string $coordinates * * @return array The x and y properties for a point */ public static function decodePoint($coordinates) { $coordinates = explode(';', $coordinates); return [ 'x' => intval($coordinates[0]), 'y' => intval($coordinates[1]), ]; } /** * Decode a square info as properties. * * @param string $coordinates * * @return array The x, y, width, and height properties for a square */ public static function decodeSquare($coordinates) { $coordinates = explode('|', $coordinates); $originString = explode(';', $coordinates[0]); return [ 'x' => intval($originString[0]), 'y' => intval($originString[1]), 'width' => intval($coordinates[1]), 'height' => intval($coordinates[2]), ]; } /** * Decode an ellipse info as properties. * * @param string $coordinates * * @return array The center_x, center_y, radius_x, radius_x properties for an ellipse */ public static function decodeEllipse($coordinates) { $coordinates = explode('|', $coordinates); $originString = explode(';', $coordinates[0]); return [ 'center_x' => intval($originString[0]), 'center_y' => intval($originString[1]), 'radius_x' => intval($coordinates[1]), 'radius_y' => intval($coordinates[2]), ]; } /** * Decode a polygon info as properties. * * @param string $coordinates * * @return array The array of points for a polygon */ public static function decodePolygon($coordinates) { $coordinates = explode('|', $coordinates); $points = []; foreach ($coordinates as $coordinate) { $point = explode(';', $coordinate); $points[] = [ intval($point[0]), intval($point[1]), ]; } return $points; } /** * Check if the point is inside of a square. * * @param array $properties The hotspot properties * @param array $point The point properties * * @return bool */ public static function pointIsInSquare($properties, $point) { $left = $properties['x']; $right = $properties['x'] + $properties['width']; $top = $properties['y']; $bottom = $properties['y'] + $properties['height']; $xIsValid = $point['x'] >= $left && $point['x'] <= $right; $yIsValid = $point['y'] >= $top && $point['y'] <= $bottom; return $xIsValid && $yIsValid; } /** * Check if the point is inside of an ellipse. * * @param array $properties The hotspot properties * @param array $point The point properties * * @return bool */ public static function pointIsInEllipse($properties, $point) { $dX = $point['x'] - $properties['center_x']; $dY = $point['y'] - $properties['center_y']; $dividend = pow($dX, 2) / pow($properties['radius_x'], 2); $divider = pow($dY, 2) / pow($properties['radius_y'], 2); return $dividend + $divider <= 1; } /** * Check if the point is inside of a polygon. * * @param array $properties The hotspot properties * @param array $point The point properties * * @return bool */ public static function pointIsInPolygon($properties, $point) { $points = $properties; $isInside = false; for ($i = 0, $j = count($points) - 1; $i < count($points); $j = $i++) { $xi = $points[$i][0]; $yi = $points[$i][1]; $xj = $points[$j][0]; $yj = $points[$j][1]; $intersect = (($yi > $point['y']) !== ($yj > $point['y'])) && ($point['x'] < ($xj - $xi) * ($point['y'] - $yi) / ($yj - $yi) + $xi); if ($intersect) { $isInside = !$isInside; } } return $isInside; } }