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));
  }

  public function getPassedVectors($algo="BRESENHAM")
  {
    if ($algo=="BRESENHAM")
      return $this->getPassedVectorsGbham();
      
    if ($algo=="QUABLA")
      return $this->getPassedVectorsQuabla();
      
    if ($algo=="QUABLA2")
      return $this->getPassedVectorsQuablaEnhanced();
      
    if ($algo=="DIDI")
      return $this->getPassedVectorsDidi();
      
    die ('UNKNOWN ALGORITHM "'.$algo.'"');
  }
    
  /**
   * returns all Vectors that are passed
   * 
   */
  private function getPassedVectorsDidi()
  {
    $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());
    }
  }
  
  private 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
   */
  private 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();
    }
  }
 
  private 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)');

$algos=array("DIDI","QUABLA","QUABLA2","BRESENHAM");

$randRangeMin=-100;
$randRangeMax=100;

//basic test
foreach ($algos as $a=>$algo)
{
  echo "Test $a: $algo\n";
  $result=array_keys($v->getPassedVectors($algo));
	
	if ($target==$result)
	{
	  echo "$algo results are OK\n";
	} else {
	  echo "PASST NICHT\n";
	  echo "Got:\n";
	  var_dump($result);
	  echo "Expected:\n";
	  var_dump($target);
	  exit;
	}
}
	
for ($i=0;$i<1000;$i++)
{
  $x=rand($randRangeMin,$randRangeMax);
  $y=rand($randRangeMin,$randRangeMax);
  $t=new Vector($x,$y);
  foreach ($algos as $a=>$algo)
  {
    $res[$a]=$t->getPassedVectors($algo) ;
  }
  
  if (($res[0]==$res[1]) &&($res[1]==$res[2]) && ($res[2]==$res[3]))
  {
    echo "$i: All equal on $t\n";
  } else {
    if ($res[0]!=$res[1]) {
      echo "error 1-2\n";
    } 
    if ($res[0]!=$res3){
      echo "error 1-3\n";
    } 
    if ($res[0]!=$res4){
      echo "error 1-4\n";
    } 
    if ($res[1]!=$res3){
      echo "error 2-3\n";
    } 
    if ($res[1]!=$res4){
      echo "error 2-4\n";
    } 
    if ($res3!=$res4){
      echo "error 3-4\n";
    } 
    
    echo "ERROR ON $t\n";
    foreach ($algos as $a=>$algo) {
      echo "$a: $algo\n";
      var_dump($res[$a]);
    }
    exit;
  }
}


$repeats=5000;
echo "\n\nTiming on $repeats loops, vector range ($randRangeMin,$randRangeMax):\n\n";

foreach ($algos as $algo)
{
	echo $algo.": ";
	$time_start = microtime(true);
	
	for ($i=1;$i<=$repeats;$i++)
	{
	  $x=rand($randRangeMin,$randRangeMax);
	  $y=rand($randRangeMin,$randRangeMax);
	  $t=new Vector($x,$y);
	  $res[0]=$t->getPassedVectors($algo);
	}
	
	$time_end = microtime(true);
	$time = $time_end - $time_start;
	echo "$time\n";
}