[Jan]

Hallo zusammen,

wie kann ich mit PHP überprüfen, ob zwei Vielecke sich irgendwie überlagern? Ich habe die Eckkoordinaten der Vielecke in der Form x:y vorliegen.

Bin für jede Hilfe dankbar.

[Jan]

Kann jemand hier einen Fehler finden? Die Prüfung schlägt nämlich auch bei x = 12|12 fehl, was sie eigentlich nicht tun sollte.

PHP-Code:

<?php
/*
First you'll need to be familiar with vector math, including dot products:
http://mathworld.wolfram.com/DotProduct.html

So, pick an arbitrary point on the rectangle and get the vectors for
the 2 sides. So, for a rectangle at:

p0----------p1
|             |
|     x         |
|             |
p2----------p3

     x|y|z
p0 = 1|5|0
p1 = 5|5|0
p2 = 1|1|0
p3 = 5|1|0
x  = 3|3|0
*/

//calculate:
//v1 = p1 - p0 // This is the vector from p0 to p1
$v1['x'] =  5 - 1;
$v1['y'] =  5 - 5;
#$v1['z'] =  0 - 0;
//v2 = p2 - p0 // This is the vector from p0 to p2
$v2['x'] =  1 - 1;
$v2['y'] =  1 - 5;
#$v2['z'] =  0 - 0;
//vX = x - p0 // This is the vector from p0 to your point
$vX['x'] =  3 - 1;
$vX['y'] =  3 - 5;
#$vX['z'] =  0 - 0;


//Now, do:
//d1 = dot(vX, v1)
$d1 = $vX['x'] * $v1['x']  +  $vX['y'] * $v1['y'];
//d2 = dot(vX, v2)
$d2 = $vX['x'] * $v2['x']  +  $vX['y'] * $v2['y'];

//Now, if the point is in the rectangle then:
//0 <= d1 <= 1
if((0 <= $d1) AND ($d1 <= 1))
{
    print('Die Objekte überlagern sich (-)'."\n");
}
//0 <= d2 <= 1
if((0 <= $d2) AND ($d2 <= 1))
{
    print('Die Objekte überlagern sich (-)'."\n");
}

//That is, assuming I got my math right (doing this all in my head w/o any paper).
?>

[Jan]

Hier nochmal was zum Thema:
http://wiki.gamedev.net/index.php/Polygon_Collision
Ich habe das versucht so umzusetzten, allerdings stimmt es noch nicht ganz, da ich nciht weiß was ich der Funktion übergeben muss:

PHP-Code:

<?php
/*

p0----------p1
|             |
|     x         |
|             |
p2----------p3

     x|y|z
p0 = 0|0|0
p1 = 5|0|0
p2 = 0|5|0
p3 = 5|5|0
x  = 3|3|0
*/

$a = array('x' => 0, 'y' => 0);
$b = array('x' => 5, 'y' => 0);
$c = array('x' => 0, 'y' => 5);
$d = array('x' => 5, 'y' => 5);

function determinant($vec1,$vec2){
    return $vec1['x']*$vec2['y'] - $vec1['y']*$vec2['x'];
}

//one edge is a-b, the other is c-d
function edgeIntersection($a, $b, $c, $d){
    $det = (double) determinant(
                                array(
                                        'x' => $b['x'] - $a['x'],
                                        'y' => $b['x'] - $a['x']
                                    ),
                                array(
                                        'x' => $c['x'] - $d['x'],
                                        'y' => $c['y'] - $d['y']
                                    )
                                );
    
    $t = (double) determinant(
                                array(
                                        'x' => $c['x'] - $a['x'],
                                        'y' => $c['x'] - $a['x']
                                    ),
                                array(
                                        'x' => $c['x'] - $d['x'],
                                        'y' => $c['y'] - $d['y']
                                    )
                            )/$det;
    
    $u =(double)  determinant(
                                array(
                                        'x' => $b['x'] - $a['x'],
                                        'y' => $b['x'] - $a['x']
                                    ),
                                array(
                                        'x' => $c['x'] - $a['x'],
                                        'y' => $c['y'] - $a['y']
                                    )
                            )/$det;
    
    if (($t<0)||($u<0)||($t>1)||($u>1))return true;
    return false;
    return $a * (1-$t)+$t*$b;
}

if(edgeIntersection($a, $b, $c, $d) != true)
{
    print('Die Objekte überlagern sich (-)'."\n");
    $return = edgeIntersection($a, $b, $c, $d);
    print_r($return);
}
?>

[Jan]

Ok, letztes Update
http://www.phpclasses.org/browse/package/2544.html
habe die Klasse nur um die Methode hinzugefügt:

PHP-Code:

    /*
    ** Test if a polygon lies entirly outside this polygon
    */
    function isOutsidePoly (&$p)
    {
        $outside = TRUE;
        $c =& $p->getFirst();    // Get the first vertex in polygon $p
        do
        {
            if ($this->isInside($c))    // If vertex is NOT inside this polygon
                $outside = FALSE;        // then set flag to false
            $c =& $c->Next();            // Get the next vertex in polygon $p
        }
        while ($c->id() != $p->first->id());
        return $outside;
    } // end of isOutsidePoly