Andrew Que Sites list Photos
Projects Contact
Main

December 15, 2007

Line clipping in PHP

    One problem with my drive price script was that the linear regression plot could extend beyond the margins of the graph area. It was necessary to first clip the lines before drawing them. Should be simple--or so I thought. Line clipping has been around likely as long as drawing lines on a screen. But I had a hard time finding a decent implementation of a clipping algorithm. I would have thought someone would have implemented a line clipping algorithm in PHP, but I couldn't find one. And when no one else has what you need, you have to do it yourself.
    After looking around, the best algorithm I found was implemented in C#. It took some time to get a translation to work, mainly because I couldn't find a good way to get around nested functions. I ended up with a part-class implementation. I would have preferred an other way, but this works and is fairly clean. Here's the code.
 
<?php
/***************************************************************************/
/* Name: ClipLine.php                                                      */
/* Uses: Used for clipping a line in a define square                       */
/* Date: 12/7/2007                                                         */
/* Authors:                                                                */
/*   Andrew Que (http://www.DrQue.net/)                                    */
/* References:                                                             */
/*   This unit was constructed mostly from an example in Wikipedia, which  */
/*   had the following credit:                                             */
/*     "Mark S. Sobkow, Paul Pospisil and Yee-Hong Yang. A Fast Two-       */
/*   Dimensional Line Clipping Algorithm via Line Encoding//Computer &     */
/*   Graphics, Vol. 11, No. 4, pp. 459-467, 1987."                         */
/*   The port to PHP was done by Andrew Que                                */
/* Revisions:                                                              */
/*   1.0 - 12/7/2007 - QUE - Creation                                      */
/*                                                                         */
/*                           (C) Copyright 2007                            */
/*                               Andrew Que                                */
/*                                   ≡|>                                   */
/***************************************************************************/

//---------------------------------------------------------------------------
// Implementation of the Fast-Clipping algorithm
// This is a class, but acts more like a function.  The reason 
// implementation is done this way is because of the sub-functions that
// need access to the local variables.  
//---------------------------------------------------------------------------
class ClipLine
{
   public 
$x;
   public 
$y;
   public 
$xx;
   public 
$yy;

   public 
$X_Min;
   public 
$Y_Min;
   public 
$X_Max;
   public 
$Y_Max;

   
//------------------------------------------------------
   // Constructor
   //------------------------------------------------------
   
public function __construct
     
(
      &
$x , &$y , &$xx , &$yy 
      
$X_Min $Y_Min $X_Max $Y_Max
     
)
   {
      
// Set local variables
      
$this->x     = &$x;
      
$this->y     = &$y;
      
$this->xx    = &$xx;
      
$this->yy    = &$yy;
      
$this->X_Min = &$X_Min;
      
$this->Y_Min = &$Y_Min;
      
$this->X_Max = &$X_Max;
      
$this->Y_Max = &$Y_Max;

      
// Clip the line
      
$this->Clip();
   }

   
//------------------------------------------------------
   // Clipping function
   // (There is one clipping function for each of the 8 areas)
   //------------------------------------------------------

   // Start top
   
private function clipStartTop()
   {
     
$DeltaX $this->xx $this->x;
     
$DeltaY $this->yy $this->y;
     
$this->+= $DeltaX * ( $this->Y_Min $this->) / $DeltaY;
     
$this->$this->Y_Min;
   }
 
   
// Start bottom
   
private function clipStartBottom()
   {
     
$DeltaX $this->xx $this->x;
     
$DeltaY $this->yy $this->y;
     
$this->+= $DeltaX * ( $this->Y_Max $this->) / $DeltaY;
     
$this->$this->Y_Max;
   }
 
   
// Start right
   
private function clipStartRight()
   {
     
$DeltaX $this->xx $this->x;
     
$DeltaY $this->yy $this->y;
     
$this->+= $DeltaY * ( $this->X_Max $this->) / $DeltaX;
     
$this->$this->X_Max;
   }
 
   
// Start left
   
private function clipStartLeft()
   {
     
$DeltaX $this->xx $this->x;
     
$DeltaY $this->yy $this->y;
     
$this->+= $DeltaY * ( $this->X_Min $this->) / $DeltaX;
     
$this->$this->X_Min;
   }
 
   
// End top
   
private function clipEndTop()
   {                                  
     
$DeltaX $this->xx $this->x;
     
$DeltaY $this->yy $this->y;
     
$this->xx += $DeltaX * ( $this->Y_Min $this->yy ) / $DeltaY;
     
$this->yy $this->Y_Min;
   }
 
   
// End bottom
   
private function clipEndBottom()
   {
     
$DeltaX $this->xx $this->x;
     
$DeltaY $this->yy $this->y;
     
$this->xx += $DeltaX * ( $this->Y_Max $this->yy ) / $DeltaY;
     
$this->yy $this->Y_Max;
   }
 
   
// End right
   
private function clipEndRight()
   {
     
$DeltaX $this->xx $this->x;
     
$DeltaY $this->yy $this->y;
     
$this->yy += $DeltaY * ( $this->X_Max $this->xx ) / $DeltaX;
     
$this->xx $this->X_Max;
   }
 
   
// End Left
   
private function clipEndLeft()
   {
     
$DeltaX $this->xx $this->x;
     
$DeltaY $this->yy $this->y;
     
$this->yy += $DeltaY * ( $this->X_Min $this->xx ) / $DeltaX;
     
$this->xx $this->X_Min;
   }

   
//------------------------------------------------------
   // Main body of clipping function
   //------------------------------------------------------
   
private function Clip()
   {
     
$LineCode 0;
 
     
// Figure out which sides clip
     
if ( $this->$this->Y_Min )  
       
$LineCode |= 0x80// BIT8
     
else 
     if ( 
$this->$this->Y_Max )  
       
$LineCode |= 0x40// BIT7
 
     
if ( $this->$this->X_Max )  
       
$LineCode |= 0x20// BIT6
     
else 
     if ( 
$this->$this->X_Min )  
       
$LineCode |= 0x10// BIT5

     
if ( $this->yy $this->Y_Min 
       
$LineCode |= 0x08// BIT4
     
else 
     if ( 
$this->yy $this->Y_Max 
       
$LineCode |= 0x04// BIT3
 
     
if ( $this->xx $this->X_Max 
       
$LineCode |= 0x02// BIT2
     
else 
     if ( 
$this->xx $this->X_Min 
       
$LineCode |= 0x01// BIT1
 
     // 9 - 8 - A
     // |   |   |
     // 1 - 0 - 2
     // |   |   |
     // 5 - 4 - 6
     
switch ( $LineCode 
     {
       
//------------------------------
       // Center
       //------------------------------

       
case 0x00:
       {
         
// Line is perfect, no clipping needed
         
break;
       }
 
       case 
0x01:
       {
         
$this->clipEndLeft();
         break;
       }
 
       case 
0x02:
       {
         
$this->clipEndRight();
         break;
       }
 
       case 
0x04:
       {
         
$this->clipEndBottom();
         break;
       }
 
       case 
0x05:
       {
         
$this->clipEndLeft();

         if ( 
$this->yy $this->Y_Max 
           
$this->clipEndBottom();

         break;
       }
 
       case 
0x06:
       {
         
$this->clipEndRight();

         if ( 
$this->yy $this->Y_Max 
           
$this->clipEndBottom();

         break;
       }
 
       case 
0x08:
       {
         
$this->clipEndTop();
         break;
       }
 
       case 
0x09:
       {
         
$this->clipEndLeft();

         if ( 
$this->yy $this->Y_Min 
           
$this->clipEndTop();

         break;
       }
 
       case 
0x0A:
       {
         
$this->clipEndRight();

         if ( 
$this->yy $this->Y_Min 
           
$this->clipEndTop();

         break;
       }
 
       
//------------------------------
       // Left
       //------------------------------

       
case 0x10:
       {
         
$this->clipStartLeft();
         break;
       }
 
       case 
0x12:
       {
         
$this->clipStartLeft();
         
$this->clipEndRight();
         break;
       }
 
       case 
0x14:
       {
         
$this->clipStartLeft();

         if ( 
$this->$this->Y_Max 
           break;

         
$this->clipEndBottom();

         break;
       }
 
       case 
0x16:
       {
         
$this->clipStartLeft();

         if ( 
$this->$this->Y_Max 
           break;

         
$this->clipEndBottom();

         if ( 
$this->xx $this->X_Max 
           
$this->clipEndRight();

         break;
       }
 
       case 
0x18:
       {
         
$this->clipStartLeft();

         if ( 
$this->$this->Y_Min 
           break;

         
$this->clipEndTop();

         break;
       }
 
       case 
0x1A:
       {
         
$this->clipStartLeft();

         if ( 
$this->$this->Y_Min 
           break;

         
$this->clipEndTop();

         if ( 
$this->xx $this->X_Max 
           
$this->clipEndRight();

         break;
       }
 
       
//------------------------------
       // Right
       //------------------------------

       
case 0x20:
       {
         
$this->clipStartRight();
         break;
       }
 
       case 
0x21:
       {
         
$this->clipStartRight();
         
$this->clipEndLeft();
         break;
       }
 
       case 
0x24:
       {
         
$this->clipStartRight();

         if ( 
$this->$this->Y_Max 
           break;

         
$this->clipEndBottom();

         break;
       }
 
       case 
0x25:
       {
         
$this->clipStartRight();
         if ( 
$this->$this->Y_Max 
           break;

         
$this->clipEndBottom();

         if ( 
$this->xx $this->X_Min 
           
$this->clipEndLeft();

         break;
       }
 
       case 
0x28:
       {
         
$this->clipStartRight();

         if ( 
$this->$this->Y_Min 
           break;

         
$this->clipEndTop();

         break;
       }
 
       case 
0x29:
       {
         
$this->clipStartRight();

         if ( 
$this->$this->Y_Min 
           break;

         
$this->clipEndTop();

         if ( 
$this->xx $this->X_Min 
           
$this->clipEndLeft();

         break;
       }
 
       
//------------------------------
       // Bottom
       //------------------------------

       
case 0x40:
       {
         
$this->clipStartBottom();
         break;
       }
 
       case 
0x41:
       {
         
$this->clipStartBottom();

         if ( 
$this->$this->X_Min 
           break;

         
$this->clipEndLeft();

         if ( 
$this->yy $this->Y_Max 
           
$this->clipEndBottom();

         break;
       }
 
       case 
0x42:
       {
         
$this->clipStartBottom();

         if ( 
$this->$this->X_Max 
           break;

         
$this->clipEndRight();

         break;
       }
 
       case 
0x48:
       {
         
$this->clipStartBottom();
         
$this->clipEndTop();

         break;
       }
 
       case 
0x49:
       {
         
$this->clipStartBottom();

         if ( 
$this->$this->X_Min 
           break;

         
$this->clipEndLeft();

         if ( 
$this->yy $this->Y_Min 
           
$this->clipEndTop();

         break;
       }
 
       case 
0x4A:
       {
         
$this->clipStartBottom();

         if ( 
$this->$this->X_Max 
           break;

         
$this->clipEndRight();

         if ( 
$this->yy $this->Y_Min 
           
$this->clipEndTop();

         break;
       }
 
       
//------------------------------
       // Bottom-left
       //------------------------------

       
case 0x50:
       {
         
$this->clipStartLeft();

         if ( 
$this->$this->Y_Max 
           
$this->clipStartBottom();

         break;
       }
 
       case 
0x52:
       {
         
$this->clipEndRight();
         if ( 
$this->yy $this->Y_Max 
           break;

         
$this->clipStartBottom();

         if ( 
$this->$this->X_Min 
           
$this->clipStartLeft();

         break;
       }
 
       case 
0x58:
       {
         
$this->clipEndTop();

         if ( 
$this->xx $this->X_Min 
           break;

         
$this->clipStartBottom();

         if ( 
$this->$this->X_Min 
           
$this->clipStartLeft();

         break;
       }
 
       case 
0x5A:
       {
         
$this->clipStartLeft();

         if ( 
$this->$this->Y_Min 
           break;

         
$this->clipEndRight();

         if ( 
$this->yy $this->Y_Max 
           break;

         if ( 
$this->$this->Y_Max 
           
$this->clipStartBottom();

         if ( 
$this->yy $this->Y_Min 
           
$this->clipEndTop();

         break;
       }
 
       
//------------------------------
       // Bottom-right
       //------------------------------

       
case 0x60:
       {
         
$this->clipStartRight();

         if ( 
$this->$this->Y_Max 
           
$this->clipStartBottom();

         break;
       }
 
       case 
0x61:
       {
         
$this->clipEndLeft();

         if ( 
$this->yy $this->Y_Max 
           break;

         
$this->clipStartBottom();

         if ( 
$this->$this->X_Max 
           
$this->clipStartRight();

         break;
       }
 
       case 
0x68:
       {
         
$this->clipEndTop();

         if ( 
$this->xx $this->X_Max 
           break;

         
$this->clipStartRight();

         if ( 
$this->$this->Y_Max 
           
$this->clipStartBottom();

         break;
       }
 
       case 
0x69:
       {
         
$this->clipEndLeft();

         if ( 
$this->yy $this->Y_Max 
           break;

         
$this->clipStartRight();

         if ( 
$this->$this->Y_Min 
           break;

         if ( 
$this->yy $this->Y_Min 
           
$this->clipEndTop();

         if ( 
$this->$this->Y_Max 
           
$this->clipStartBottom();

         break;
       }
 
       
//------------------------------
       // Top
       //------------------------------

       
case 0x80:
       {
         
$this->clipStartTop();
         break;
       }
 
       case 
0x81:
       {
         
$this->clipStartTop();

         if ( 
$this->$this->X_Min 
           break;

         
$this->clipEndLeft();

         break;
       }
 
       case 
0x82:
       {
         
$this->clipStartTop();

         if ( 
$this->$this->X_Max 
           break;

         
$this->clipEndRight();

         break;
       }
 
       case 
0x84:
       {
         
$this->clipStartTop();
         
$this->clipEndBottom();
         break;
       }
 
       case 
0x85:
       {
         
$this->clipStartTop();

         if ( 
$this->$this->X_Min 
           break;

         
$this->clipEndLeft();

         if ( 
$this->yy $this->Y_Max 
           
$this->clipEndBottom();

         break;
       }
 
       case 
0x86:
       {
         
$this->clipStartTop();

         if ( 
$this->$this->X_Max 
           break;

         
$this->clipEndRight();

         if ( 
$this->yy $this->Y_Max 
           
$this->clipEndBottom();

         break;
       }
 
       
//------------------------------
       // Top-left
       //------------------------------

       
case 0x90:
       {
         
$this->clipStartLeft();

         if ( 
$this->$this->Y_Min 
           
$this->clipStartTop();

         break;
       }
 
       case 
0x92:
       {
         
$this->clipEndRight();

         if ( 
$this->yy $this->Y_Min 
           break;

         
$this->clipStartTop();

         if ( 
$this->$this->X_Min 
           
$this->clipStartLeft();

         break;
       }
 
       case 
0x94:
       {
         
$this->clipEndBottom();

         if ( 
$this->xx $this->X_Min 
           break;

         
$this->clipStartLeft();

         if ( 
$this->$this->Y_Min 
           
$this->clipStartTop();

         break;
       }
 
       case 
0x96:
       {
         
$this->clipStartLeft();

         if ( 
$this->$this->Y_Max 
           break;

         
$this->clipEndRight();

         if ( 
$this->yy $this->Y_Min 
           break;

         if ( 
$this->$this->Y_Min 
           
$this->clipStartTop();

         if ( 
$this->yy $this->Y_Max 
           
$this->clipEndBottom();

         break;
       }
 
       
//------------------------------
       // Top-right
       //------------------------------

       
case 0xA0:
       {
         
$this->clipStartRight();

         if ( 
$this->$this->Y_Min 
           
$this->clipStartTop();

         break;
       }
 
       case 
0xA1:
       {
         
$this->clipEndLeft();

         if ( 
$this->yy $this->Y_Min 
           break;

         
$this->clipStartTop();

         if ( 
$this->$this->X_Max 
           
$this->clipStartRight();

         break;
       }
 
       case 
0xA4:
       {
         
$this->clipEndBottom();

         if ( 
$this->xx $this->X_Max 
           break;

         
$this->clipStartRight();

         if ( 
$this->$this->Y_Min 
           
$this->clipStartTop();

         break;
       }
 
       case 
0xA5:
       {
         
$this->clipEndLeft();

         if ( 
$this->yy $this->Y_Min 
           break;

         
$this->clipStartRight();

         if ( 
$this->$this->Y_Max 
           break;

         if ( 
$this->yy $this->Y_Max 
           
$this->clipEndBottom();

         if ( 
$this->$this->Y_Min 
           
$this->clipStartTop();

         break;
       }
     }
 
     
// Round result
     
$this->x  round$this->);
     
$this->y  round$this->);
     
$this->xx round$this->xx );
     
$this->yy round$this->yy );
   }
}

//---------------------------------------------------------------------------
// Clip line
//---------------------------------------------------------------------------
function ClipLine
  &
$x , &$y , &$xx , &$yy 
  
$X_Min $Y_Min $X_Max $Y_Max )
{
   
// All of the work is done simply by creating a clip class
   
$Clip = new 
     
ClipLine
     

       
$x $y $xx $yy 
       
$X_Min $Y_Min $X_Max $Y_Max 
     
);
}

//---------------------------------------------------------------------------
// Draw clipped line
//---------------------------------------------------------------------------
function DrawClippedLine
  
$Image 
  
$x $y $xx $yy 
  
$X_Min $Y_Min $X_Max $Y_Max ,
  
$Color )
{
   
// Clip this line
   
ClipLine
      
$x $y $xx $yy 
      
$X_Min $Y_Min $X_Max $Y_Max );

   
// Draw the results
   
imageline$Image ,  $x  $y  $xx $yy $Color );
}

// "Those who dream by day are cognizant of many things which escape those 
// who dream only by night." - Edgar Allan Poe

?>

December 14, 2007

Indigo Dragon cleanup

Rachel

Rachel

    The White Dragon has been hosting DrQue.net for the last day while the Indigo Dragon receives updates.  Along with software updates, I gave the computer a cleaning.  One of the case fans was ceased and beyond repair.  The case was rather filthy, which is to be expected after around a year of dust build up.  I gave the case a blow down using my shopvac, pulled off the CPU can and heatsink and gave both a thorough cleaning.  After the cleaning, I did a RAM test with memtest86 to see if maybe a RAM failure had caused our problem.  The test ran without issue, so I have to believe something was responsible. 
    After the Indigo Dragon was reassembled and booted, I checked to see if all the services were running as expected and found Dovecot, the POP3 e-mail server, wasn't working.  It turns out that during the updates, something changed in the new version of Dovecot that made the old config file incompatible with the new version.  It was a bit of a pain to fix, since I never did any config myself--I did everything through Webmin.  My version of Webmin was also out-of-date, thus couldn't properly configure Dovecot.  But once I updated Webmin, I got Dovecot working and the Indigo Dragon was again running.  What's funny is, the only reason I run Dovecot is because that happened to be the first POP3 server I got to run.  A quick log sync with the White Dragon, and the Indigo Dragon was back to being it's server self.
    Since I was at it, I did all the same updates on the White Dragon as well, then put it back to sleep.  A fine server the White Dragon :)

December 13, 2007

Indigo Dragon reboot

Danielle

Danielle

    This morning I noticed the drive script wasn't retrieving new data.  After some investigation, I found the Indigo Dragon was in some strange defunct state.  I couldn't even log in with the console.  Oddly, the website was running and so were all the SSH connections already established.  Since I always have 'top' running over SSH, I tried looking at the process list.  It was huge, full of pop3 and rsync instances.  I tried shutting a bunch of them down manually, but to no avail--the system was in bad shape.  So, for the first time in 230 days (almost 3/4 of a year), I reset the Indigo Dragon. 
   That isn't a horrible thing.  Gives me a chance to do some updates and physical cleaning of the system.  I installed all the updates for Debian and compiled/installed the latest version of Apache, PHP and OpenSSL.

December 11, 2007

Welcome Pluvi

    The other day, our good friend Pluvius sold me his laptop.  In his honer, I've named the laptop 'Compaq Pluvius', or Pluvi.  I've needed a new laptop since the Iron Dragon's departure.  Here are the specs:
AMD Turion 64 2.0 GHz, 1MB L2 cache
2,048 MB 333 MHz DDR-SRAM
ATI x200 chipset
WD Scorpio 120 GB 5400 RPM hard drive
Hitachi DVD Burner with Lightscribe
ATI Mobility Radeon XPress 200M video card
14.0" widescreen
12 cell Lithium Ion battery
    Now begins the long process of moving into the new machine.  I started by updating his install of Ubuntu to 7.10 and getting some of the settings the way I like them.  Next I'm going to have to start moving data onto the system.
    This is a remix of an old picture I took back in 2005.  I found the facial expression interesting and decided to zoom and retouch this area.
    I don't actually know this person's name.  However, she asked if I would answerer some questions for a survey she was doing as part of a class project.  And since she was there, I snapped a couple frames.
    Originally I had planned on skating this evening.  At noon, I went into the theater to help setup lights for a dance recital being preformed that evening.  It turned out to be quite a bit more lighting then anyone had expected and I was asked if I could stay to administer the lightboard.  So I did and snapped a few shots while I was in the booth.  They aren't very good, since I didn't have my zoom lens.