Login   Register  
PHP Classes
elePHPant
Icontem

File: polygon.php

Recommend this page to a friend!
Stumble It! Stumble It! Bookmark in del.icio.us Bookmark in del.icio.us
  Classes of Brenor Brophy  >  Polygon  >  polygon.php  >  Download  
File: polygon.php
Role: Class source
Content type: text/plain
Description: Polygon class
Class: Polygon
Perform geometric operations on polygons
Author: By
Last change: Added scale() & translate() methods. Modified move(), rotate(), bRect() methods to correctly handle Polygon lists. Fixed a bug in how the perturb function is called. It was being incorrectly called for intersections between lines when the intersection occurred outside the line segments.
Date: 4 years ago
Size: 41,809 bytes
 

Contents

Class file image Download
<?php
/*------------------------------------------------------------------------------
** File:		polygon.php
** Description:	PHP class for a polygon. 
** Version:		1.6
** Author:		Brenor Brophy
** Email:		brenor dot brophy at gmail dot com
** Homepage:	www.brenorbrophy.com 
**------------------------------------------------------------------------------
** COPYRIGHT (c) 2005-2010 BRENOR BROPHY
**
** The source code included in this package is free software; you can
** redistribute it and/or modify it under the terms of the GNU General Public
** License as published by the Free Software Foundation. This license can be
** read at:
**
** http://www.opensource.org/licenses/gpl-license.php
**
** This program is distributed in the hope that it will be useful, but WITHOUT 
** ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 
** FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. 
**------------------------------------------------------------------------------
**
** Based on the paper "Efficient Clipping of Arbitary Polygons" by Gunther
** Greiner (greiner at informatik dot uni-erlangen dot de) and Kai Hormann
** (hormann at informatik dot tu-clausthal dot de), ACM Transactions on Graphics
** 1998;17(2):71-83.
**
** Available at:
**
**      http://www2.in.tu-clausthal.de/~hormann/papers/Greiner.1998.ECO.pdf
**
** Another useful site describing the algorithm and with some example
** C code by Ionel Daniel Stroe is at:
**
**		http://davis.wpi.edu/~matt/courses/clipping/
**
** The algorithm is extended by Brenor Brophy to allow polygons with
** arcs between vertices.
**
** Rev History
** -----------------------------------------------------------------------------
** 1.0	08/25/2005	Initial Release
** 1.1	09/04/2005	Added Move(), Rotate(), isPolyInside() and bRect() methods.
**                	Added software license language to header comments
** 1.2	09/07/2005	Fixed a divide by zero error when an attempt is made to
**					find an intersection between two arcs with the same center
**					point. Fixed an undefined variable warning for $last in
**					boolean() method. Added protection against divide by zero
**					warning in angle() method.
** 1.3  04/16/2006  Fixed a bug in the ints() function. The perturb() function
**					was being called with uninitialized parameters. This caused
**					incorrect clipping in cases where a vertex on one polygon
**					exactly fell on a line segment of the other polygon. Thanks
**					to Allan Wright who found the bug.
** 1.4  03/19/2009  Added isPolyOutside() and isPolyIntersect() methods.
**                  Created a new perturb function, the old one was simply
**                  wrong.
** 1.5  07/16/2009  Added isPolySelfIntersect() method.
** 1.6  15/05/2010  Added scale() & translate() methods. Modified move(), rotate(),
**                  bRect() methods to correctly handle Polygon lists.
**                  Fixed a bug in how the perturb function is called. It was being
**                  incorrectly called for intersections between lines when the
**                  intersection occurred outside the line segments.
*/
define ("infinity", 100000000);	// for places that are far far away

require('vertex.php');		// A polygon consists of vertices. So the polygon
							// class is just a reference to a linked list of vertices
class polygon
{
/*------------------------------------------------------------------------------
** This class manages a doubly linked list of vertex objects that represents
** a polygon. The class consists of basic methods to manage the list
** and methods to implement boolean operations between polygon objects.
*/
	var $first;		// Reference to first vertex in the linked list
					// Polygons are always closed so the last vertex will point back
					// to the first, hence there is no need to store a reference to the
					// last vertex (it is just the one before the first)
	var $cnt;		// Tracks number of vertices in the polygon
	/*
	** Construct a new shiny polygon
	*/
	function polygon ($first = NULL){
		$this->first = $first;
		$this->cnt = 0;}
	/*
	** Get the first vertex
	*/
	function &getFirst (){
		return $this->first;}
	/*
	** Return the next polygon
	*/
	function &NextPoly() {
		return $this->first->NextPoly(); }
	/*
	** Print out main variables of the polygon for debugging
	*/
	function print_poly()
	{
		print("Polygon:<br>");
		$c =& $this->first;
		do
		{
			$c->print_vertex();
			$c =& $c->Next();
		}
		while ($c->id() != $this->first->id());
		if ($this->first->nextPoly)
		{
			print("Next Polygon:<br>");
			$this->first->nextPoly->print_poly();
		}
	}
	/*
	** Add a vertex object to the polygon (vertex is added at the "end" of the list)
	** Which because polygons are closed lists means it is added just before the first
	** vertex.
	*/
	function add (&$nv)
	{
		if ($this->cnt == 0)				// If this is the first vertex in the polygon
		{
			$this->first =& $nv;			// Save a reference to it in the polygon
			$this->first->setNext($nv);		// Set its pointer to point to itself
			$this->first->setPrev($nv);		// because it is the only vertex in the list
			$ps =& $this->first->Nseg();	// Get ref to the Next segment object
			$this->first->setPseg($ps);		// and save it as Prev segment as well
		}
		else								// At least one other vertex already exists
		{
			// $p <-> $nv <-> $n
			//    $ps     $ns
			$n =& $this->first;				// Get a ref to the first vertex in the list
			$p =& $n->Prev();				// Get ref to previous vertex
			$n->setPrev($nv);				// Add at end of list (just before first)
			$nv->setNext($n);				// link the new vertex to it
			$nv->setPrev($p);				// link to the pervious EOL vertex
			$p->setNext($nv);				// And finally link the previous EOL vertex
			// Segments
			$ns =& $nv->Nseg();				// Get ref to the new next segment
			$ps =& $p->Nseg();				// Get ref to the previous segment
			$n->setPseg($ns);				// Set new previous seg for $this->first
			$nv->setPseg($ps);				// Set previous seg of the new vertex
		}
		$this->cnt++;						// Increment the count of vertices
	}
	/*
	** Create a vertex and then add it to the polygon
	*/
	function addv ($x, $y, $xc=0, $yc=0, $d=0)
	{
		$nv =& new vertex($x, $y, $xc, $yc, $d);
		$this->add($nv);
	}
	/*
	** Delete a vertex object from the polygon. This is not used by the main algorithm
	** but instead is used to clean-up a polygon so that a second boolean operation can
	** be performed.
	*/
	function &del (&$v)
	{
		// $p <-> $v <-> $n				   Will delete $v and $ns
		//    $ps    $ns
		$p =& $v->Prev();				// Get ref to previous vertex
		$n =& $v->Next();				// Get ref to next vertex
		$p->setNext($n);				// Link previous forward to next 
		$n->setPrev($p);				// Link next back to previous
		// Segments
		$ps =& $p->Nseg();				// Get ref to previous segment
		$ns =& $v->Nseg();				// Get ref to next segment
		$n->setPseg($ps);				// Link next back to previous segment
		$ns = NULL; $v = NULL;			// Free the memory
		$this->cnt--;					// One less vertex
		return $n;						// Return a ref to the next valid vertex
	}
	/*
	** Reset Polygon - Deletes all intersection vertices. This is used to
	** restore a polygon that has been processed by the boolean method
	** so that it can be processed again.
	*/
	function res ()
	{
		$v =& $this->getFirst();		// Get the first vertex
		do
		{
			$v =& $v->Next();		// Get the next vertex in the polygon
			while ($v->isIntersect())	// Delete all intersection vertices
				$v =& $this->del($v);
		}
		while ($v->id() != $this->first->id());
	}
	/*
	** Copy Polygon - Returns a reference to a new copy of the poly object
	** including all its vertices & their segments
	*/
	function &copy_poly ()
	{
		$this_class = get_class($this);			// Findout the class I'm in
		$n =& new $this_class;;		// Create a new instance of this class
		$v =& $this->getFirst();
		do
		{
			$n->addv($v->X(),$v->Y(),$v->Xc(),$v->Yc(),$v->d());
			$v =& $v->Next();
		}
		while ($v->id() != $this->first->id());
		return $n;
	}

	/*
	** Insert and Sort a vertex between a specified pair of vertices (start and end)
	**
	** This function inserts a vertex (most likely an intersection point) between two
	** other vertices. These other vertices cannot be intersections (that is they must
	** be actual vertices of the original polygon). If there are multiple intersection
	** points between the two vertices then the new vertex is inserted based on its
	** alpha value.
	*/
	function insertSort (&$nv, &$s, &$e)
	{
		$c =& $s;						// Set current to the sarting vertex
		while ($c->id() != $e->id()  && $c->Alpha() < $nv->Alpha())
			$c =& $c->Next();		// Move current past any intersections
										// whose alpha is lower but don't go past
										// the end vertex
		// $p <-> $nv <-> $c
		$nv->setNext($c);				// Link new vertex forward to curent one
		$p =& $c->Prev();				// Get a link to the previous vertex
		$nv->setPrev($p);				// Link the new vertex back to the previous one
		$p->setNext($nv);				// Link previous vertex forward to new vertex
		$c->setPrev($nv);				// Link current vertex back to the new vertex
		// Segments
		$ps =& $p->Nseg();
		$nv->setPseg($ps);
		$ns =& $nv->Nseg();
		$c->setPseg($ns);
		$this->cnt++;					// Just added a new vertex
	}
	/*
	** return the next non intersecting vertex after the one specified
	*/
	function &nxt (&$v)
	{
		$c =& $v;						// Initialize current vertex
		while ($c && $c->isIntersect())	// Move until a non-intersection
			$c =& $c->Next();		// vertex if found		
		return $c;						// return that vertex
	}
	/*
	** Check if any unchecked intersections remain in the polygon. The boolean
	** method is complete when all intersections have been checked.
	*/
	function unckd_remain ()
	{
		$remain = FALSE;
		$v =& $this->first;
		do
		{
			if ($v->isIntersect() && !$v->isChecked())
				$remain = TRUE;		// Set if an unchecked intersection is found
			$v =& $v->Next();
		}
		while ($v->id() != $this->first->id());
		return $remain;
	}
	/*
	** Return a ref to the first unchecked intersection point in the polygon.
	** If none are found then just the first vertex is returned.
	*/
	function &first_unckd_intersect ()
	{
		$v =& $this->first;
		do									// Do-While
		{									// Not yet reached end of the polygon
			$v =& $v->Next();			// AND the vertex if NOT an intersection
		}									// OR it IS an intersection, but has been checked already
		while($v->id() != $this->first->id() && ( !$v->isIntersect() || ( $v->isIntersect() && $v->isChecked() ) ) );
		return $v;
	}
	/*
	** Return the distance between two points
	*/
	function dist ($x1, $y1, $x2, $y2){
		return sqrt(($x1-$x2)*($x1-$x2) + ($y1-$y2)*($y1-$y2));}
	/*
	** Calculate the angle between 2 points, where Xc,Yc is the center of a circle
	** and x,y is a point on its circumference. All angles are relative to
	** the 3 O'Clock position. Result returned in radians
	*/
	function angle ($xc, $yc, $x1, $y1)
	{
		$d = $this->dist($xc, $yc, $x1, $y1); // calc distance between two points
		if ($d != 0)
			if ( asin( ($y1-$yc)/$d ) >= 0 )
				$a1 = acos( ($x1-$xc)/$d );
			else
				$a1 = 2*pi() - acos( ($x1-$xc)/$d );
		else
			$a1 = 0;
		return $a1;
	}
	/*
	** Return Alpha value for an Arc
	**
	** X1/Y1 & X2/Y2 are the end points of the arc, Xc/Yc is the center & Xi/Yi
	** the intersection point on the arc. $d is the direction of the arc
	*/
	function aAlpha ($x1, $y1, $x2, $y2, $xc, $yc, $xi, $yi, $d)
	{
		$sa = $this->angle($xc, $yc, $x1, $y1); // Start Angle
		$ea = $this->angle($xc, $yc, $x2, $y2); // End Angle
		$ia = $this->angle($xc, $yc, $xi, $yi); // Intersection Angle
		if ($d == 1)	// Anti-Clockwise
		{
			$arc = $ea - $sa;
			$int = $ia - $sa;
		}
		else			// Clockwise
		{
			$arc = $sa - $ea;
			$int = $sa - $ia;
		}
		if ($arc < 0) $arc += 2*pi();
		if ($int < 0) $int += 2*pi();
		$a = $int/$arc;
		return  $a;
	}
	/*
	** This function handles the degenerate case where a vertex of one
	** polygon lies directly on an edge of the other. This case can
	** also occur during the isInside() function, where the search
	** line exactly intersects with a vertex. The function works
	** by shortening the line by a tiny amount.
    **
	** Revision 1.4 Completely new perturb function. The old version was
	** simply wrong, I'm amazed it took so long to show up as a problem.
	*/
	function perturb (&$p1, &$p2, &$q1, &$q2, $aP, $aQ)
	{
		$PT = 0.00001;      // Perturbation factor
		if ($aP == 0)       // q1,q2 intersects p1 exactly, move vertex p1 closer to p2
		{
            $h = $this->dist($p1->X(),$p1->Y(),$p2->X(),$p2->Y());
            $a = ($PT * $this->dist($p1->X(),$p1->Y(),$p2->X(),$p1->Y()))/$h;
            $b = ($PT * $this->dist($p2->X(),$p2->Y(),$p2->X(),$p1->Y()))/$h;
			$p1->setX($p1->X() + $a);
			$p1->setY($p1->Y() + $b);
		}
		elseif ($aP == 1)	// q1,q2 intersects p2 exactly, move vertex p2 closer to p1
		{
            $h = $this->dist($p1->X(),$p1->Y(),$p2->X(),$p2->Y());
            $a = ($PT * $this->dist($p1->X(),$p1->Y(),$p2->X(),$p1->Y()))/$h;
            $b = ($PT * $this->dist($p2->X(),$p2->Y(),$p2->X(),$p1->Y()))/$h;
			$p2->setX($p2->X() - $a);
			$p2->setY($p2->Y() - $b);
		}
		elseif ($aQ == 0)	// p1,p2 intersects q1 exactly, move vertex q1 closer to q2
		{
            $h = $this->dist($q1->X(),$q1->Y(),$q2->X(),$q2->Y());
            $a = ($PT * $this->dist($q1->X(),$q1->Y(),$q2->X(),$q1->Y()))/$h;
            $b = ($PT * $this->dist($q2->X(),$q2->Y(),$q2->X(),$q1->Y()))/$h;
			$q1->setX($q1->X() + $a);
			$q1->setY($q1->Y() + $b);
		}
		elseif ($aQ == 1)	// p1,p2 intersects q2 exactly, move vertex q2 closer to q1
		{
            $h = $this->dist($q1->X(),$q1->Y(),$q2->X(),$q2->Y());
            $a = ($PT * $this->dist($q1->X(),$q1->Y(),$q2->X(),$q1->Y()))/$h;
            $b = ($PT * $this->dist($q2->X(),$q2->Y(),$q2->X(),$q1->Y()))/$h;
			$q2->setX($q2->X() - $a);
			$q2->setY($q2->Y() - $b);
		}
    }
	/*
	** Determine the intersection between two pairs of vertices p1/p2, q1/q2
	**
	** Either or both of the segments passed to this function could be arcs.
	** Thus we must first determine if the intersection is line/line, arc/line
	** or arc/arc. Then apply the correct math to calculate the intersection(s).
	**
	** Line/Line can have 0 (no intersection) or 1 intersection
	** Line/Arc and Arc/Arc can have 0, 1 or 2 intersections
	**
	** The function returns TRUE is any intersections are found
	** The number found is returned in $n
	** The arrays $ix[], $iy[], $alphaP[] & $alphaQ[] return the intersection points
	** and their associated alpha values.
	*/
	function ints (&$p1, &$p2, &$q1, &$q2, &$n, &$ix, &$iy, &$alphaP, &$alphaQ)
	{

		$found = FALSE; $n = 0;							// No intersections found yet
		$pt = $p1->d();	$qt = $q1->d();	// Do we have Arcs or Lines?

		if ($pt == 0 && $qt == 0) // Is it line/Line ?
		{
		/* LINE/LINE
		** Algorithm from: http://astronomy.swin.edu.au/~pbourke/geometry/lineline2d/
		*/
			$x1 = $p1->X(); $y1 = $p1->Y(); 
			$x2 = $p2->X(); $y2 = $p2->Y(); 
			$x3 = $q1->X(); $y3 = $q1->Y(); 
			$x4 = $q2->X(); $y4 = $q2->Y(); 
			$d = (($y4-$y3)*($x2-$x1)-($x4-$x3)*($y2-$y1));
			if ($d != 0)
			{ // The lines intersect at a point somewhere
				$ua = (($x4-$x3)*($y1-$y3)-($y4-$y3)*($x1-$x3))/$d;
				$ub = (($x2-$x1)*($y1-$y3)-($y2-$y1)*($x1-$x3))/$d;
		// The values of $ua and $ub tell us where the intersection occurred.
		// A value between 0 and 1 means the intersection occurred within the
		// line segment.
		// A value less tha 0 or greater than 1 means the intersection occurred
		// outside the line segment
		// A value of exactly 0 or 1 means the intersection occurred right at the
		// start or end of the line segment. For our purposes we will consider this
		// NOT to be an intersection and we will move the vertex a tiny distance
		// away from the intersecting line. 
				if ( (($ua==0 || $ua==1 )&&($ub>=0 && $ub<=1)) || (($ub==0 || $ub==1)&&($ua>=0 && $ua<=1)))
				{ // Degenerate case - vertex exactly touches a line
//					print("Perturb: P(".$p1->X().",".$p1->Y().")(".$p2->X().",".$p2->Y().") Q(".$q1->X().",".$q1->Y().")(".$q2->X().",".$q2->Y().") UA(".$ua.") UB(".$ub.")<br>");
					$this->perturb($p1, $p2, $q1, $q2, $ua, $ub);
					$found = FALSE;
				}
				elseif (($ua > 0 && $ua < 1) && ($ub > 0 && $ub < 1))
				{ // Intersection occurs on both line segments
					$x = $x1 + $ua*($x2-$x1);
					$y = $y1 + $ua*($y2-$y1);
					$iy[0] = $y; $ix[0] = $x;
					$alphaP[0] = $ua; $alphaQ[0] = $ub;
					$n = 1; $found = TRUE;
				}
				else
				{ // The lines do not intersect within the line segments
					$found = FALSE;
				}
			}
			else
			{ // The lines do not intersect
				$found = FALSE;
			}
		}	// End of find Line/Line intersection
		elseif ($pt != 0 && $qt != 0)	// Is  it Arc/Arc?
		{
		/* ARC/ARC
		** Algorithm from: http://astronomy.swin.edu.au/~pbourke/geometry/2circle/
		*/
			$x0 = $p1->Xc(); $y0 = $p1->Yc(); // Center of first Arc
			$r0 = $this->dist($x0,$y0,$p1->X(),$p1->Y());	// Calc the radius
			$x1 = $q1->Xc(); $y1 = $q1->Yc(); // Center of second Arc
			$r1 = $this->dist($x1,$y1,$q1->X(),$q1->Y());	// Calc the radius

			$dx = $x1 - $x0;	// dx and dy are the vertical and horizontal 
			$dy = $y1 - $y0;	// distances between the circle centers.
			$d = sqrt(($dy*$dy) + ($dx*$dx)); // Distance between the centers.

			if ($d == 0)		// Don't try an find intersection if centers are the same.
			{					// Added in Rev 1.2
				$found = FALSE;
			}
			elseif ($d > ($r0 + $r1))		// Check for solvability.
			{								// no solution. circles do not intersect.
				$found = FALSE;
			}
			elseif ($d < abs($r0 - $r1))
			{							// no solution. one circle inside the other
				$found = FALSE;
			}
			else
			{
				/*
				** 'xy2' is the point where the line through the circle intersection
				** points crosses the line between the circle centers.  
				*/
				$a = (($r0*$r0)-($r1*$r1)+($d*$d))/(2.0*$d); // Calc the distance from xy0 to xy2.
				$x2 = $x0 + ($dx * $a/$d);		// Determine the coordinates of xy2.
				$y2 = $y0 + ($dy * $a/$d);
				if ($d == ($r0 + $r1)) // Arcs touch at xy2 exactly (unlikely)
				{
					$alphaP[0] = $this->aAlpha($p1->X(), $p1->Y(), $p2->X(), $p2->Y(), $x0, $y0, $x2, $y2, $pt);
					$alphaQ[0] = $this->aAlpha($q1->X(), $q1->Y(), $q2->X(), $q2->Y(), $x1, $y1, $x2, $y2, $qt);
					if (($alphaP[0] >0 && $alphaP[0] < 1) && ($alphaQ[0] >0 && $alphaQ[0] < 1))
					{
						$ix[0] = $x2;
						$iy[0] = $y2;
						$n = 1; $found = TRUE;
					}
				}
				else					// Arcs intersect at two points
				{
					$h = sqrt(($r0*$r0) - ($a*$a)); // Calc the distance from xy2 to either
													// of the intersection points.
					$rx = -$dy * ($h/$d);	// Now determine the offsets of the 
					$ry =  $dx * ($h/$d);	// intersection points from xy2
					$x[0] = $x2 + $rx; $x[1] = $x2 - $rx;		// Calc the absolute intersection points.
					$y[0] = $y2 + $ry; $y[1] = $y2 - $ry;
					$alP[0] = $this->aAlpha($p1->X(), $p1->Y(), $p2->X(), $p2->Y(), $x0, $y0, $x[0], $y[0], $pt);
					$alQ[0] = $this->aAlpha($q1->X(), $q1->Y(), $q2->X(), $q2->Y(), $x1, $y1, $x[0], $y[0], $qt);
					$alP[1] = $this->aAlpha($p1->X(), $p1->Y(), $p2->X(), $p2->Y(), $x0, $y0, $x[1], $y[1], $pt);
					$alQ[1] = $this->aAlpha($q1->X(), $q1->Y(), $q2->X(), $q2->Y(), $x1, $y1, $x[1], $y[1], $qt);
					for ($i=0; $i<=1; $i++)
						if (($alP[$i] >0 && $alP[$i] < 1) && ($alQ[$i] >0 && $alQ[$i] < 1))
						{
							$ix[$n] = $x[$i]; $iy[$n] = $y[$i];
							$alphaP[$n] = $alP[$i]; $alphaQ[$n] = $alQ[$i];
							$n++; $found = TRUE;
						}
				}
			}
		}	// End of find Arc/Arc intersection
		else	// It must be Arc/Line
		{
		/* ARC/LINE
		** Algorithm from: http://astronomy.swin.edu.au/~pbourke/geometry/sphereline/
		*/
			if ($pt == 0)	// Segment p1,p2 is the line
			{				// Segment q1,q2 is the arc
				$x1 = $p1->X(); $y1 = $p1->Y();
				$x2 = $p2->X(); $y2 = $p2->Y();
				$xc = $q1->Xc(); $yc = $q1->Yc();
				$xs = $q1->X(); $ys = $q1->Y();
				$xe = $q2->X(); $ye = $q2->Y();
				$d = $qt;
			}
			else			// Segment q1,q2 is the line
			{				// Segment p1,p2 is the arc
				$x1 = $q1->X(); $y1 = $q1->Y();
				$x2 = $q2->X(); $y2 = $q2->Y();
				$xc = $p1->Xc(); $yc = $p1->Yc();
				$xs = $p1->X(); $ys = $p1->Y();
				$xe = $p2->X(); $ye = $p2->Y();
				$d = $pt;
			}
			$r = $this->dist($xc,$yc,$xs,$ys);
			$a = pow(($x2 - $x1),2)+pow(($y2 - $y1),2);	
			$b = 2* ( ($x2 - $x1)*($x1 - $xc)
      				+ ($y2 - $y1)*($y1 - $yc) );
			$c = pow($xc,2) + pow($yc,2) +
				 pow($x1,2) + pow($y1,2) -
			 	2* ( $xc*$x1 + $yc*$y1) - pow($r,2);
			$i =   $b * $b - 4 * $a * $c;
			if ( $i < 0.0 ) // no intersection
 			{
				$found = FALSE;
	 		}
			elseif ( $i == 0.0 )	// one intersection
			{
				if ($a != 0)
				   $mu = -$b/(2*$a);
				$x = $x1 + $mu*($x2-$x1);
				$y = $y1 + $mu*($y2-$y1);
				$al = $mu; // Line Alpha
				$aa = $this->aAlpha($xs, $ys, $xe, $ye, $xc, $yc, $x, $y, $d); // Arc Alpha
				if (($al >0 && $al <1)&&($aa >0 && $aa <1))
				{
					$ix[0] = $x; $iy[0] = $y;
					$n = 1; $found = TRUE;
					if ($pt == 0)
					{
						$alphaP[0] = $al; $alphaQ[0] = $aa;
					}
					else
					{
						$alphaP[0] = $aa; $alphaQ[0] = $al;
					}
				}
			}
			elseif ( $i > 0.0 ) 	// two intersections
			{
				if ($a != 0)
				   $mu[0] = (-$b + sqrt( pow($b,2) - 4*$a*$c )) / (2*$a);	// first intersection
				$x[0] = $x1 + $mu[0]*($x2-$x1);
				$y[0] = $y1 + $mu[0]*($y2-$y1);
				if ($a != 0)
				   $mu[1] = (-$b - sqrt(pow($b,2) - 4*$a*$c )) / (2*$a); // second intersection
				$x[1] = $x1 + $mu[1]*($x2-$x1);
				$y[1] = $y1 + $mu[1]*($y2-$y1);
				$al[0] = $mu[0];
				$aa[0] = $this->aAlpha($xs, $ys, $xe, $ye, $xc, $yc, $x[0], $y[0], $d);
				$al[1] = $mu[1];
				$aa[1] = $this->aAlpha($xs, $ys, $xe, $ye, $xc, $yc, $x[1], $y[1], $d);
				for ($i=0; $i<=1; $i++)
					if (($al[$i] >0 && $al[$i] < 1) && ($aa[$i] >0 && $aa[$i] < 1))
					{
						$ix[$n] = $x[$i]; $iy[$n] = $y[$i];
						if ($pt == 0)
						{
							$alphaP[$n] = $al[$i]; $alphaQ[$n] = $aa[$i];
						}
						else
						{
							$alphaP[$n] = $aa[$i]; $alphaQ[$n] = $al[$i];
						}
						$n++; $found = TRUE;
					}
			}
		}	// End of find Arc/Line intersection
		return $found;
	} // end of intersect function
	/*
	** Test if a vertex lies inside the polygon
	**
	** This function calculates the "winding" number for the point. This number
	** represents the number of times a ray emitted from the point to infinity
	** intersects any edge of the polygon. An even winding number means the point
	** lies OUTSIDE the polygon, an odd number means it lies INSIDE it.
	**
	** Right now infinity is set to -10000000, some people might argue that infinity
	** actually is a bit bigger. Those people have no lives.
	*/
	function isInside (&$v)
	{
		$winding_number = 0;
		$point_at_infinity =& new vertex(-10000000,$v->Y());	// Create point at infinity
		$q =& $this->first;		// End vertex of a line segment in polygon
		do
		{
			if (!$q->isIntersect())
			{
				if ($this->ints($point_at_infinity, $v, $q, $this->nxt($q->Next()), $n, $x, $y, $aP, $aQ))
					$winding_number += $n;		// Add number of intersections found
			}
			$q =& $q->Next();
		}
		while ($q->id() != $this->first->id());
		$point_at_infinity = NULL;		// Free the memory for neatness
		if ($winding_number % 2 == 0)	// Check even or odd
			return FALSE;				// even == outside
		else
			return TRUE;				// odd == inside
	}
	/*
	**	Execute a Boolean operation on a polygon
	**
	** This is the key method. It allows you to AND/OR this polygon with another one
	** (equvalent to a UNION or INTERSECT operation. You may also subtract one from
	** the other (same as DIFFERENCE). Given two polygons A, B the following operations
	** may be performed:
	**
	** A|B ... A OR  B (Union of A and B)
	** A&B ... A AND B (Intersection of A and B)
	** A\B ... A - B
	** B\A ... B - A
	**
	** A is the object and B is the polygon passed to the method.
	*/
	function &boolean (&$polyB, $oper)
	{
		$last = NULL;
		$s =& $this->first;			// First vertex of the subject polygon
		$c =& $polyB->getFirst();	// First vertex of the "clip" polygon
		/*
		** Phase 1 of the algoritm is to find all intersection points between the two
		** polygons. A new vertex is created for each intersection and it is added to
		** the linked lists for both polygons. The "neighbor" reference in each vertex
		** stores the link between the same intersection point in each polygon. 
		*/
		do
		{
			if (!$s->isIntersect())
			{
				do
				{
					if (!$c->isIntersect())
					{
						if ($this->ints($s, $this->nxt($s->Next()),$c, $polyB->nxt($c->Next()), $n, $ix, $iy, $alphaS, $alphaC))
						{
							for ($i=0; $i<$n; $i++)
							{
								$is =& new vertex($ix[$i], $iy[$i], $s->Xc(), $s->Yc(), $s->d(), NULL, NULL, NULL, TRUE, NULL, $alphaS[$i], FALSE, FALSE);
								$ic =& new vertex($ix[$i], $iy[$i], $c->Xc(), $c->Yc(), $c->d(), NULL, NULL, NULL, TRUE, NULL, $alphaC[$i], FALSE, FALSE);
								$is->setNeighbor($ic);
								$ic->setNeighbor($is);
								$this->insertSort($is, $s, $this->nxt($s->Next()));
								$polyB->insertSort($ic, $c, $polyB->nxt($c->Next()));
							}
						}
					} // end if $c is not an intersect point
					$c =& $c->Next();
				}
				while ($c->id() != $polyB->first->id());
			} // end if $s not an intersect point
			$s =& $s->Next();
		}
		while ($s->id() != $this->first->id());
		/*
		** Phase 2 of the algorithm is to identify every intersection point as an
		** entry or exit point to the other polygon. This will set the entry bits
		** in each vertex object.
		**
		** What is really stored in the entry record for each intersection is the
		** direction the algorithm should take when it arrives at that entry point.
		** Depending in the operation requested (A&B, A|B, A/B, B/A) the direction is
		** set as follows for entry points (f=foreward, b=Back), exit poits are always set
		** to the opposite:
		**       Enter       Exit
		**       A    B     A    B
		** A|B   b    b     f    f
		** A&B   f    f     b    b
		** A\B   b    f     f    b
		** B\A   f    b     b    f
		**
		** f = TRUE, b = FALSE when stored in the entry record
		*/
		switch ($oper)
		{
			case "A|B":	$A = FALSE;	$B = FALSE;	break;
			case "A&B":	$A = TRUE;	$B = TRUE;	break;
			case "A\B":	$A = FALSE;	$B = TRUE;	break;
			case "B\A":	$A = TRUE;	$B = FALSE;	break;
			default:	$A = TRUE;	$B = TRUE;	break;
		}
		$s =& $this->first;
		if ($polyB->isInside($s)) // if we are already inside
			$entry = !$A;		// next intersection must be an exit
		else					// otherwise
			$entry = $A;		// next intersection must be an entry
		do
		{
			if ($s->isIntersect())
			{
				$s->setEntry($entry);
				$entry = !$entry;
			}
			$s =& $s->Next();
		}
		while ($s->id() != $this->first->id());
		/*
		** Repeat for other polygon
		*/
		$c =& $polyB->first;
		if ($this->isInside($c)) // if we are already inside
			$entry = !$B;	// next intersection must be an exit
		else				// otherwise
			$entry = $B;	// next intersection must be an entry
		do
		{
			if ($c->isIntersect())
			{
				$c->setEntry($entry);
				$entry = !$entry;
			}
			$c =& $c->Next();
		}
		while ($c->id() != $polyB->first->id());
		/*
		** Phase 3 of the algorithm is to scan the linked lists of the
		** two input polygons an construct a linked list of result
		** polygons. We start at the first intersection then depending
		** on whether it is an entry or exit point we continue building
		** our result polygon by following the source or clip polygon
		** either forwards or backwards.
		*/
		while ($this->unckd_remain())				// Loop while unchecked intersections remain
		{
			$v =& $this->first_unckd_intersect();	// Get the first unchecked intersect point
			$this_class = get_class($this);			// Findout the class I'm in
			$r =& new $this_class;					// Create a new instance of that class
			do
			{
				$v->setChecked();					// Set checked flag true for this intersection
				if ($v->isEntry())
				{
					do
					{
						$v =& $v->Next(); 
						$nv =& new vertex($v->X(),$v->Y(),$v->Xc(),$v->Yc(),$v->d());
						$r->add($nv);
					}
					while (!$v->isIntersect());
				}
				else
				{
					do
					{
						$v =& $v->Prev();
						$nv =& new vertex($v->X(),$v->Y(),$v->Xc(FALSE),$v->Yc(FALSE),$v->d(FALSE));
						$r->add($nv);
					}
					while (!$v->isIntersect());
				}
				$v =& $v->Neighbor();
			}
			while (!$v->isChecked()); // until polygon closed
			if ($last)							// Check in case first time thru the loop
				$r->first->setNextPoly($last);	// Save ref to the last poly in the first vertex
												// of this poly
			$last =& $r;						// Save this polygon
		} // end of while there is another intersection to check
	/*
	** Clean up the input polygons by deleting the intersection points
	*/
		$this->res();
		$polyB->res();
	/*
	** It is possible that no intersection between the polygons was found and
	** there is no result to return. In this case we make function fail
	** gracefully as follows (depending on the requested operation):
	**
	** A|B : Return $this with $polyB in $this->first->nextPoly
	** A&B : Return $this
	** A\B : Return $this
	** B\A : return $polyB
	*/
		if (!$last)
		{
			switch ($oper)
			{
				case "A|B":	$last =& $this->copy_poly();
							$p    =& $polyB->copy_poly();
							$last->first->setNextPoly($p);
							break;
				case "A&B":	$last =&  $this->copy_poly();	break;
				case "A\B":	$last =&  $this->copy_poly();	break;
				case "B\A":	$last =&  $polyB->copy_poly();	break;
				default:	$last =&  $this->copy_poly();	break;
			}
		}
		elseif ($this->first->nextPoly)
		{
			$last->first->nextPoly =& $this->first->NextPoly();
		}
		return $last;
	} // end of boolean function
	/*
	** Test if a polygon lies entirly inside this polygon
	**
	** First every point in the polygon is tested to determine if it is
	** inside this polygon. If all points are inside, then the second
	** test is performed that looks for any intersections between the
	** two polygons. If no intersections are found then the polygon
	** must be completely enclosed by this polygon.
	*/
	function isPolyInside (&$p)
	{
		$inside = TRUE;
		$c =& $p->getFirst();	// Get the first vertex in polygon $p
		do
		{
			if (!$this->isInside($c))	// If vertex is NOT inside this polygon
				$inside = FALSE;		// then set flag to false
			$c =& $c->Next();			// Get the next vertex in polygon $p
		}
		while ($c->id() != $p->first->id());
		if ($inside)
		{
			$c =& $p->getFirst();		// Get the first vertex in polygon $p
			$s =& $this->getFirst();	// Get the first vertex in this polygon
			do
			{
				do
				{
					if ($this->ints($s, $s->Next(),$c, $c->Next(), $n, $x, $y, $aS, $aC))
						$inside = FALSE;
					$c =& $c->Next();
				}
				while ($c->id() != $p->first->id());
				$s =& $s->Next();
			}
			while ($s->id() != $this->first->id());
		}
		return $inside;
	} // end of isPolyInside
	/*
	** Test if a polygon lies completely outside this polygon
	**
	** First every point in the polygon is tested to determine if it is
	** outside this polygon. If all points are outside, then the second
	** test is performed that looks for any intersections between the
	** two polygons. If no intersections are found then the polygon
	** must be completely outside this polygon.
	*/
	function isPolyOutside (&$p)
	{
		$outside = TRUE;
		$c =& $p->getFirst();	// Get the first vertex in polygon $p
		do
		{
			if ($this->isInside($c))	// If vertex is inside this polygon
				$outside = FALSE;		// then set flag to false
			$c =& $c->Next();			// Get the next vertex in polygon $p
		}
		while ($c->id() != $p->first->id());
		if ($outside)
		{
			$c =& $p->getFirst();		// Get the first vertex in polygon $p
			$s =& $this->getFirst();	// Get the first vertex in this polygon
			do
			{
				do
				{
					if ($this->ints($s, $s->Next(),$c, $c->Next(), $n, $x, $y, $aS, $aC))
						$outside = FALSE;
					$c =& $c->Next();
				}
				while ($c->id() != $p->first->id());
				$s =& $s->Next();
			}
			while ($s->id() != $this->first->id());
		}
		return $outside;
	} // end of isPolyOutside
	/*
	** Test if a polygon intersects anywhere with this polygon
	** looks for any intersections between the two polygons.
	** If no intersections between any segments are found then
	** the polygons do not intersect. However, one could be
	** completely inside the other.
	*/
    function isPolyIntersect (&$p)
    {
        $intersect = FALSE;
            $c =& $p->getFirst();        // Get the first vertex in polygon $p
            $s =& $this->getFirst();    // Get the first vertex in this polygon
            do
            {
                do
                {
                    if ($this->ints($s, $s->Next(),$c, $c->Next(), $n, $x, $y, $aS, $aC))
                        $intersect = TRUE;
                    $c =& $c->Next();
                }
                while ($c->id() != $p->first->id());
                $s =& $s->Next();
            }
            while ($s->id() != $this->first->id());
        return $intersect;
    } // end of isPolyIntersect
    /*
	** Test if this polygon intersects anywhere with itself
	** looks for any self intersections within the polygon.
	** If no intersections between any segments are found then
	** the polygon does not self intersect.
	*/
    function isPolySelfIntersect ()
    {
        $intersect = FALSE;
            $s =& $this->getFirst();    // Get the first vertex in this polygon
            $c =& $s->Next();            // Get the next vertex
            do
            {
                do
                {
                    if ($this->ints($s, $s->Next(),$c, $c->Next(), $n, $x, $y, $aS, $aC)) // If the segments intersect
                        for ($i=0; $i<=$n; $i++) // then for each intersection point
                            if (($aS[$i] <> 0) || ($aC[$i] <> 0)) // check that it NOT at the end of the segment
                                $intersect = TRUE; // Because sequential segments always intersect at their ends
                    $c =& $c->Next();
                }
                while ($c->id() != $this->first->id());
                $s =& $s->Next();
            }
            while ($s->id() != $this->first->id());
        return $intersect;
    } // end of isPolySelfIntersect
	/*
	** Move Polygon
	**
	** Translates polygon by delta X and delta Y
	*/
	function move ($dx, $dy)
	{
        $p =& $this;
        if ($p) // For a valid polygon
        do
		{
			$v =& $p->getFirst();
			do
			{
				$v->setX($v->X() + $dx);
				$v->setY($v->Y() + $dy);
				if ($v->d() != 0)
				{
					$v->setXc($v->Xc() + $dx);
					$v->setYc($v->Yc() + $dy);
				}
				$v =& $v->Next();
			}
			while($v->id() != $p->first->id());
            $p =& $p->NextPoly();   // Get the next polygon in the list
        }
        while ($p);     // Keep checking polygons as long as they exist
	} // end of move polygon	
	/*
	** Rotate Polygon
	**
	** Rotates a polgon about point $xr/$yr by $a radians
	*/
	function rotate ($xr, $yr, $a)
	{
		$this->move(-$xr,-$yr);		// Move the polygon so that the point of
									// rotation is at the origin (0,0)
		if ($a < 0)					// We might be passed a negitive angle
			$a += 2*pi();			// make it positive

        $p =& $this;
        if ($p) // For a valid polygon
        do
		{
			$v =& $p->first;
			do
			{
				$x=$v->X(); $y=$v->Y();
				$v->setX($x*cos($a) - $y*sin($a));	// x' = xCos(a)-ySin(a)
				$v->setY($x*sin($a) + $y*cos($a));	// y' = xSin(a)+yCos(a)
				if ($v->d() != 0)
				{
					$x=$v->Xc(); $y=$v->Yc();
					$v->setXc($x*cos($a) - $y*sin($a));
					$v->setYc($x*sin($a) + $y*cos($a));
				}
				$v =& $v->Next();
			}
			while($v->id() != $p->first->id());
            $p =& $p->NextPoly();   // Get the next polygon in the list
        }
        while ($p);     // Keep checking polygons as long as they exist	
		$this->move($xr,$yr);		// Move the rotated polygon back 
	} // end of rotate polygon
	/*
	** Return Bounding Rectangle for a Polygon
	**
	** returns a polygon object that represents the bounding rectangle
	** for this polygon. Arc segments are correctly handled.
	**
	** Remember the polygon object allows for a linked list of polygons.
	** If more than one polygon is linked through the NextPoly list
	** then the bounding rectangle will be for ALL polygons in the
	** list.
	*/
	function &bRect ()
	{
		$minX = INF; $minY = INF; $maxX = -INF; $maxY = -INF;
        $p =& $this;
        if ($p) // For a valid polygon
        do
		{
		    $v =& $p->first;	// Get the first vertex
		    do
		    {
			    if ($v->d() != 0)	// Is it an arc segment
			    {
				    $vn =& $v->Next();					// end vertex of the arc segment
				    $v1 =& new vertex($v->Xc(), -infinity);	// bottom point of vertical line thru arc center
				    $v2 =& new vertex($v->Xc(), +infinity);	// top point of vertical line thru arc center
				    if ($p->ints($v, $vn, $v1, $v2, $n, $x, $y, $aS, $aC))	// Does line intersect the arc ?
				    {
					    for ($i=0; $i<$n; $i++)			// check y portion of all intersections
					    {
						    $minY = min($minY, $y[$i], $v->Y());
						    $maxY = max($maxY, $y[$i], $v->Y());
					    }
				    }
				    else	// There was no intersection so bounding rect is determined
				    {		// by the start point only, not the edge of the arc
					    $minY = min($minY, $v->Y());
					    $maxY = max($maxY, $v->Y());
				    }
				    $v1 = NULL; $v2 = NULL;	// Free the memory used
				    $h1 =& new vertex(-infinity, $v->Yc());	// left point of horozontal line thru arc center
				    $h2 =& new vertex(+infinity, $v->Yc());	// right point of horozontal line thru arc center
				    if ($p->ints($v, $vn, $h1, $h2, $n, $x, $y, $aS, $aC))	// Does line intersect the arc ?
				    {
					    for ($i=0; $i<$n; $i++)			// check x portion of all intersections
					    {
						    $minX = min($minX, $x[$i], $v->X());
						    $maxX = max($maxX, $x[$i], $v->X());
					    }
				    }
				    else
				    {
					    $minX = min($minX, $v->X());
					    $maxX = max($maxX, $v->X());
				    }
				    $h1 = NULL; $h2 = NULL;
			    }
			    else	// Straight segment so just check the vertex
			    {
				    $minX = min($minX, $v->X());
				    $minY = min($minY, $v->Y());
				    $maxX = max($maxX, $v->X());
				    $maxY = max($maxY, $v->Y());
			    }
			    $v =& $v->Next();
		    }
		    while($v->id() != $p->first->id());	
            $p =& $p->NextPoly();                   // Get the next polygon in the list
        }
        while ($p);     // Keep checking polygons as long as they exist
		//
		// Now create an return a polygon with the bounding rectangle
		//
		$this_class = get_class($this);			// Findout the class I'm in (might be an extension of polygon)
		$p =& new $this_class;					// Create a new instance of that class
		$p->addv($minX,$minY);
		$p->addv($minX,$maxY);
		$p->addv($maxX,$maxY);
		$p->addv($maxX,$minY);
		return $p;
	} // end of bounding rectangle
	/*
	** Scale a Polygon
	**
	** Resize a polygon by scale X & scale Y
	*/
	function scale ($sx, $sy)
	{
        $p =& $this;
        if ($p) // For a valid polygon
        do
		{
			$v =& $p->getFirst();
			do
			{
				$v->setX($v->X() * $sx);
				$v->setY($v->Y() * $sy);
				if ($v->d() != 0)
				{
					$v->setXc($v->Xc() * $sx);
					$v->setYc($v->Yc() * $sy);
				}
				$v =& $v->Next();
			}
			while($v->id() != $p->first->id());
            $p =& $p->NextPoly();                   // Get the next polygon in the list
        }
        while ($p);     // Keep checking polygons as long as they exist
	} // end of scale polygon	
	/*
	** translate a Polygon
	**
	** Resize & move a polygon so that its bounding rectangle becomes
	** the rectangle defined by the two points (xmin,ymin) and
	** (xmax,ymax).
	*/
	function translate ($xmin, $ymin, $xmax, $ymax)
	{
        $nXsize = $xmax - $xmin;
		$nYsize = $ymax - $ymin;

        $o_br =& $this->bRect(); // Get the min/max corners of the original polygon bounding rect
		$v =& $o_br->getFirst(); // First vertex of bRect is xmin & ymin of the polygon
		$o_xmin = $v->X(); $o_ymin = $v->Y();
		$v =& $v->Next(); // Next vertex has ymax
        $o_ymax = $v->Y();
		$v =& $v->Next(); // Next vertex has xmax
        $o_xmax = $v->X();

		$oXsize = $o_xmax - $o_xmin;
		$oYsize = $o_ymax - $o_ymin;

		$xScale = $nXsize / $oXsize; // Calculate the X axis scale factor
		$yScale = $nYsize / $oYsize; // Calculate the X axis scale factor

		$xMove = $xmin - ($o_xmin * $xScale);
		$yMove = $ymin - ($o_ymin * $yScale);

		$this->scale($xScale, $yScale);
		$this->move($xMove, $yMove);
	} // end of translate polygon
} //end of class polygon
?>