 [PHP]Prüfung auf Überlagerung zweier Vielecke
|
|
17.07.2008, 15:38
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.
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).
?>
17.07.2008, 20:07
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);
}
?>
18.07.2008, 12:15
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
|
|
|
