Skip to content

Instantly share code, notes, and snippets.

@quabla
Forked from xosofox/Vectors.class.php
Created November 26, 2010 20:59
Show Gist options
  • Save quabla/717207 to your computer and use it in GitHub Desktop.
Save quabla/717207 to your computer and use it in GitHub Desktop.
<?php
//erst die Klasse
class Vector
{
private $x;
private $y;
public function getX() {
return $this->x;
}
public function getY() {
return $this->y;
}
public function setX($newx) {
$this->x=$newx;
}
public function setY($newy) {
$this->y=$newy;
}
public function __construct($x,$y) {
$this->x=$x;
$this->y=$y;
}
public function __toString() {
return '('.$this->x.'|'.$this->y.')';
}
public function getLength() {
return sqrt(pow($this->getX(),2)+pow($this->getY(),2));
}
/**
* returns all Vectors that are passed
*
*/
public function getPassedVectors()
{
$rowvector=$this->getY();
$colvector=$this->getX();
$points=array();
if ($rowvector!=0)
{
//0,5er Schritt in row-richtung
$iy=$rowvector/abs($rowvector)/2;
//von 0 bis rowvector, $i l�uft in 0,5er schritten hoch
for ($i=0;abs($i)<=abs($rowvector);$i=$i+$iy)
{
$x=round($colvector/$rowvector*$i,0);
if ($x==-0)
$x=0;
$y=round($i,0);
if ($y==-0)
$y=0;
$v=new Vector($x,$y);
$points[$v->__toString()]=$v;
}
}
if ($colvector!=0)
{
$ix=$colvector/abs($colvector)/2;
for ($i=0;abs($i)<=abs($colvector);$i=$i+$ix)
{
$y=round($rowvector/$colvector*$i,0);
if ($y==-0)
$y=0;
$x=round($i,0);
if ($x==-0)
$x=0;
$v=new Vector($x,$y);
$points[$v->__toString()]=$v;
}
}
uasort($points,function(Vector $a, Vector $b)
{
$la=$a->getLength();
$lb=$b->getLength();
if ($la==$lb) return 0;
return ($la > $lb) ? 1 : -1;
});
if (count($points)==0)
$points["(0|0)"]=new Vector(0, 0);
return $points;
}
private function getSlope()
{
if ($this->getX()==0)
{
return 9999999;
} else {
return ($this->getY()/$this->getX());
}
}
public function getPassedVectorsQuabla()
{
//get algebraic signs
$x=$this->getX();
$y=$this->getY();
$xSign=0;
$ySign=0;
if ($x!=0) $xSign=abs($x)/$x;
if ($y!=0) $ySign=abs($y)/$y;
//get slope of target vector
$testV=new Vector(abs($x),abs($y));
$slope=$testV->getSlope();
$walkX=0;
$walkY=0;
//start on 0|0
$v=new Vector($walkX,$walkY);
//we always start at (0|0);
$vecs=array($v->__toString()=>$v);
//while destination not reached, go there 1 by 1
$i=0;
while ((!($v==$this)))
{
$testV=new Vector($walkX+.5,$walkY+.5);
$vSlope=$testV->getSlope();
// echo "Slopes: current: $vSlope vs. $slope\n";
if ($vSlope<=$slope)
{
// go down
$walkY++;
}
if ($vSlope>=$slope)
{
//go right
$walkX++;
}
$v=new Vector($walkX*$xSign, $walkY*$ySign);
$vecs[$v->__toString()]=$v;
$i++;
}
return $vecs;
}
/**
* checking special cases first
*/
public function getPassedVectorsQuablaEnhanced()
{
$x=$this->getX();
$y=$this->getY();
if (($x==0) || ($y==0) || (abs($x)==abs($y)))
{
//for next
$xi=0;
$yi=0;
if ($x!=0) $xi=abs($x)/$x;
if ($y!=0) $yi=abs($y)/$y;
$end=max(abs($x),abs($y));
$v=new Vector(0, 0);
$vecs=array($v->__toString()=>$v);
for ($i=0;$i<=$end;$i++)
{
$v=new Vector($i*$xi, $i*$yi);
$vecs[$v->__toString()]=$v;
}
return $vecs;
} else {
return $this->getPassedVectorsQuabla();
}
}
public function getPassedVectorsGbham()
/*--------------------------------------------------------------
* von quabla modifizierter Bresenham-Algorithmus
* nach der auf wikipedia gefundenen C-Implementierung
*---------------------------------------------------------------
*/
{
$dx=$this->getX();
$dy=$this->getY();
/* Vorzeichen des Inkrements bestimmen */
$incx = ($dx > 0) ? 1 :( ($dx < 0) ? -1 : 0);
$incy = ($dy > 0) ? 1 : (($dy < 0) ? -1 : 0);
// negative positiv machen
if($dx<0) {$dx = -$dx;}
if($dy<0) {$dy = -$dy;}
/* feststellen, welche Entfernung größer ist */
if ($dx>$dy) {
/* x ist schnelle Richtung */
$pdx=$incx; $pdy=0; /* pd. ist Parallelschritt */
$qdx=0; $qdy=$incy; /* qd. ist Querschritt */
$ddx=$incx; $ddy=$incy; /* dd. ist Diagonalschritt */
$es =$dy; $el =$dx; /* Fehlerschritte schnell, langsam */
} else {
/* y ist schnelle Richtung */
$pdx=0; $pdy=$incy; /* pd. ist Parallelschritt */
$qdx=$incx; $qdy=0; /* qd. ist Querschritt */
$ddx=$incx; $ddy=$incy; /* dd. ist Diagonalschritt */
$es =$dx; $el =$dy; /* Fehlerschritte schnell, langsam */
}
/* Initialisierungen vor Schleifenbeginn */
$x = 0;
$y = 0;
$v=new Vector($x, $y);
$vecs[$v->__toString()]=$v;
/* Pixel berechnen */
$err = ($el-$es)/2;
/* das Vorzeichen von err gibt an, auf welcher Seite des Vektors sich
* der Mittelpunkt des zuletzt betrachteten Kaestchens befindet.
* Bei Abweichung in "langsamer" Richtung ist err positiv,
* und wir machen einen Schritt in "schneller" Richtung.
* bei Abweichung in "schneller" Richtung ist err negativ,
* und wir machen einen Schritt in "langsamer" Richtung.
*/
// echo "putting $x, $y at $err\n";
do {
if($err<0) {
/* Fehlerterm wieder positiv (>=0) machen */
/* Schritt in langsame Richtung, Querschritt */
$err += $el;
$x += $qdx;
$y += $qdy;
} elseif ($err > 0) {
/* Schritt in schnelle Richtung, Parallelschritt */
$err -= $es;
$x += $pdx;
$y += $pdy;
} else {
/* Schrit Diagonal */
$err += $el;
$err -= $es;
$x += $ddx;
$y += $ddy;
}
// echo "putting $x, $y at $err\n";
$v=new Vector($x, $y);
$vecs[$v->__toString()]=$v;
} while ((abs($x) != $dx) || (abs($y) != $dy));
return $vecs;
}
}
//Und hier der Test
$v=new Vector(-6,-7);
$target=array('(0|0)','(0|-1)','(-1|-1)','(-1|-2)','(-2|-2)','(-2|-3)','(-3|-3)','(-3|-4)','(-4|-4)','(-4|-5)','(-5|-5)','(-5|-6)','(-6|-6)','(-6|-7)');
$result=array_keys($v->getPassedVectors());
if ($target==$result)
{
echo "original SUPI!!!!\n";
} else {
echo "PASST NICHT\n";
echo "Got:\n";
var_dump($result);
echo "Expected:\n";
var_dump($target);
exit;
}
$result=array_keys($v->getPassedVectorsQuabla());
if ($target==$result)
{
echo "quabla SUPI!!!!\n";
} else {
echo "PASST NICHT\n";
echo "Got:\n";
var_dump($result);
echo "Expected:\n";
var_dump($target);
exit;
}
$result=array_keys($v->getPassedVectorsGbham());
if ($target==$result)
{
echo "Gbhm SUPI!!!!\n";
} else {
echo "PASST NICHT\n";
echo "Got:\n";
var_dump($result);
echo "Expected:\n";
var_dump($target);
exit;
}
$randRangeMin=-5;
$randRangeMax=5;
for ($i=0;$i<1000;$i++)
{
$x=rand($randRangeMin,$randRangeMax);
$y=rand($randRangeMin,$randRangeMax);
// $x=2;
//$y=2;
$t=new Vector($x,$y);
$res1=array_keys($t->getPassedVectors());
$res2=array_keys($t->getPassedVectorsQuabla());
$res3=array_keys($t->getPassedVectorsQuablaEnhanced());
$res4=array_keys($t->getPassedVectorsGbham());
if (($res1==$res2) &&($res2==$res3) && ($res3==$res4))
{
echo "All equal on $t\n";
} else {
if ($res1!=$res2) {
echo "error 1-2\n";
}
if ($res1!=$res3){
echo "error 1-3\n";
}
if ($res1!=$res4){
echo "error 1-4\n";
}
if ($res2!=$res3){
echo "error 2-3\n";
}
if ($res2!=$res4){
echo "error 2-4\n";
}
if ($res3!=$res4){
echo "error 3-4\n";
}
echo "ERROR ON $t\n";
echo "Mine: \n";
var_dump($res1);
echo "Quabla: \n";
var_dump($res2);
echo "Quabla++: \n";
var_dump($res3);
echo "Gbham: \n";
var_dump($res4);
exit;
}
}
$repeats=100000;
echo "\n\nTiming on $repeats loops:\n\n";
//**********************************
echo "Didi: ";
$time_start = microtime(true);
for ($i=1;$i<=$repeats;$i++)
{
$x=rand($randRangeMin,$randRangeMax);
$y=rand($randRangeMin,$randRangeMax);
$t=new Vector($x,$y);
$res1=$t->getPassedVectors();
}
$time_end = microtime(true);
$time = $time_end - $time_start;
echo "$time\n";
//**********************************
$time_start = microtime(true);
echo "Quabla: ";
for ($i=1;$i<=$repeats;$i++)
{
$x=rand($randRangeMin,$randRangeMax);
$y=rand($randRangeMin,$randRangeMax);
$t=new Vector($x,$y);
$res1=$t->getPassedVectorsQuabla();
}
$time_end = microtime(true);
$time = $time_end - $time_start;
echo "$time\n";
//**********************************
echo "Quabla Enhanced: ";
$time_start = microtime(true);
for ($i=1;$i<=$repeats;$i++)
{
$x=rand($randRangeMin,$randRangeMax);
$y=rand($randRangeMin,$randRangeMax);
$t=new Vector($x,$y);
$res1=$t->getPassedVectorsQuablaEnhanced();
}
$time_end = microtime(true);
$time = $time_end - $time_start;
echo "$time\n";
//**********************************
echo "Gbham: ";
$time_start = microtime(true);
for ($i=1;$i<=$repeats;$i++)
{
$x=rand($randRangeMin,$randRangeMax);
$y=rand($randRangeMin,$randRangeMax);
$t=new Vector($x,$y);
$res1=$t->getPassedVectorsGbham();
}
$time_end = microtime(true);
$time = $time_end - $time_start;
echo "$time\n";
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment