Hallo, Gast! (Registrieren)

Letzte Ankündigung: MyBB 1.8.8 veröffentlicht (17.10.16)


Benutzer, die gerade dieses Thema anschauen: 1 Gast/Gäste
[PHP]Prüfung auf Überlagerung zweier Vielecke
#1
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.

Zitieren
#2
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'] =  1;
$v1['y'] =  5;
#$v1['z'] =  0 - 0;
//v2 = p2 - p0 // This is the vector from p0 to p2
$v2['x'] =  1;
$v2['y'] =  5;
#$v2['z'] =  0 - 0;
//vX = x - p0 // This is the vector from p0 to your point
$vX['x'] =  1;
$vX['y'] =  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((<= $d1) AND ($d1 <= 1))
{
    print(
'Die Objekte überlagern sich (-)'."\n");
}
//0 <= d2 <= 1
if((<= $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).
?>

Zitieren
#3
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);
}
?>

Zitieren
#4
Ok, letztes Update Wink
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 

Zitieren