<?php
/*------------------------------------------------------------------------------
** File: polygon.php
** Description: PHP class for a polygon.
** Version: 1.5
** Author: Brenor Brophy
** Email: brenor dot brophy at gmail dot com
** Homepage: www.brenorbrophy.com
**------------------------------------------------------------------------------
** COPYRIGHT (c) 2005-2009 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/11/2009
*/
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 ©_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)
{ // Degenerate case - vertex exactly touches a line
$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)
{
$v =& $this->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() != $this->first->id());
} // 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
$v =& $this->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() != $this->first->id());
$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.
*/
function &bRect ()
{
$minX = INF; $minY = INF; $maxX = -INF; $maxY = -INF;
$v =& $this->first;
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 ($this->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 teh 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 ($this->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() != $this->first->id());
//
// 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
} //end of class polygon
?> |
ReTweet
Stumble It!
Bookmark in del.icio.us
Advertise on this site
Site map
Statistics
Site tips
Privacy policy
Contact