poligon.class.php

<?php
/*------------------------------------------------------------------------------
** File:        polygon.class.php
** Description:     PHP class for a polygon.
** Version:     1.6
** Author:      Blade83
** Email:       johannes_kraemer@gmx.de
**------------------------------------------------------------------------------
** COPYRIGHT (c) 2008-2013 JOHANNES KRÄMER
**
** 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
**
**------------------------------------------------------------------------------
*/
define ("infinity", 100000000);
require('vertex.class.php');

class polygon
{
    public
        $first,
        $cnt;
    /*
    ** 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
?>