Drawing random dots and triangle, calculating number of dots covered by this triangle.

triangle_coverage.php

<?php

$x = 1600;
$y = 800;

$n = 100;


$dots = random_dots($x, $y, $n);


$triangle = array(
    array( rand(0,$x), rand(0,$y)),
    array( rand(0,$x), rand(0,$y)),
    array( rand(0,$x), rand(0,$y)),
);

function random_dots($x, $y, $n)
{
    $d = array();
    for ($i=0;$i<$n; $i++) {
        $d[] = array( rand(0,$x), rand(0,$y));
    }
    return $d;
}

// http://www.blackpawn.com/texts/pointinpoly/

function sameSide($p1,$p2, $a,$b)
{
    $cp1 = crossProduct( vectorSubtraction($b,$a), vectorSubtraction($p1,$a) );
    $cp2 = crossProduct( vectorSubtraction($b,$a), vectorSubtraction($p2,$a) );

    return dotProduct($cp1, $cp2) >= 0;
}

function inTriangle($p, $a,$b,$c)
{
    return sameSide($p,$a, $b,$c) and sameSide($p,$b, $a,$c) and sameSide($p,$c, $a,$b);
}

function crossProduct($v1, $v2) {
    $v[0] =   ( ($v1[1] * $v2[2]) - ($v1[2] * $v2[1]) );
    $v[1] = - ( ($v1[0] * $v2[2]) - ($v1[2] * $v2[0]) );
    $v[2] =   ( ($v1[0] * $v2[1]) - ($v1[1] * $v2[0]) );

    return $v;
}

function dotProduct($v1, $v2) {
    return array_sum(array_map(function($a,$b) { return $a*$b; }, $v1, $v2));
}

function vectorSubtraction($v1, $v2)
{
    $v[0] = $v1[0] - $v2[0];
    $v[1] = $v1[1] - $v2[1];
    $v[2] = $v1[2] - $v2[2];

    return $v;
}

function draw_triangle($a, $b, $c, $color = 'red')
{
    return '<polygon points="'. $a[0].','.$a[1]. ', '.$b[0].','.$b[1]. ', '.$c[0].','.$c[1].'" style="fill:none;stroke:'.$color.';stroke-width:1" />';
}

$svg = '<?xml version="1.0" standalone="no"?>';
$svg.= '<svg width="'.$x.'" height="'.$y.'" version="1.1" xmlns="http://www.w3.org/2000/svg">';

$t = 0;

foreach ($dots as $p) {
    list($a, $b, $c) = $triangle;

    if ($in = inTriangle($p, $a, $b, $c)) {
        $t ++;
    }

    $svg.=  '<circle cx="'.$p[0].'" cy="'.$p[1].'" r="3" stroke="black" stroke-width="1" fill="'.($in?'red':'none').'" />';
}

$svg.= draw_triangle($triangle[0], $triangle[1], $triangle[2]);

$svg.=  '<text x="10" y="15" fill="red">Dots= '.$n.', Covered= '.$t.' </text>';

$svg.=  '</svg>';

header('Content-Type: image/svg+xml');
echo $svg;