Vectors.class.php

<?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";