Created
November 25, 2010 10:00
-
-
Save xosofox/715148 to your computer and use it in GitHub Desktop.
Please improve this one!
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?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($poins)==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)) && ($i<100)) | |
{ | |
$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 | |
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(); | |
} | |
} | |
} | |
//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 "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 "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); | |
$t=new Vector($x,$y); | |
$res1=$t->getPassedVectors(); | |
$res2=$t->getPassedVectorsQuabla(); | |
$res3=$t->getPassedVectorsQuablaEnhanced(); | |
if (($res1==$res2) &&($res2==$res3)) | |
{ | |
echo "All equal on $t\n"; | |
} else { | |
echo "ERROR ON $t\n"; | |
echo "Mine: \n"; | |
//var_dump($res1); | |
echo "Quabla: \n"; | |
//var_dump($res2); | |
echo "Quabla++: \n"; | |
var_dump($res3); | |
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"; | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment