Copyright © 20052010 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 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.


Polygon is a PHP class, that allows the creation of polygons with both
line and arc segments between vertices. Polygons may be convex or concave
and may self intersect. Methods are available to perform clipping and
boolean operations between arbitrary polygons; to perform tests for vertex
inside a polygon and polygon inside a polygon; and to move or rotate a
polygon.
A vertex is a point at a location x,y. A segment lies between two vertices,
by default it is a line, but it may also be an arc with a center at Xc,Yc
and a direction either clockwise or anticlockwise. The radius of an arc
is the distance from its starting vertex to its center. The center of
the arc Xc,Yc must be equidistant from both starting and ending vertices.
A polygon is composed of a double linked list of vertices. The linked
list of vertices is closed, that is, the last vertex in the list links
back to the first one (and the first links to the last). Thus the polygons
must always be a closed shape, though they may self intersect. The diagram
below shows an example of the data structure. Each vertex (V1,V2,V3,V4)
links backwards and forwards to its neighbors. Segments (S1,S2,S3,S4)
exist as separate objects. A vertex object holds a reference to its previous
and next segment object. The polygon object only holds a reference to
the first vertex in the polygon.


Polygon implements the basic data structure and a method for performing
boolean operations between polygons from the excellent paper entitled
"Efficient Clipping of Arbitrary Polygons" by Gunther Greiner
(greiner at informatik dot unierlangen dot de) and Kai Hormann (hormann
at informatik dot tuclausthal dot de), ACM Transactions on Graphics 1998;17(2):7183.
The paper may be accessed at:
http://www2.in.tuclausthal.de/~hormann/papers/Greiner.1998.ECO.pdf
Using the algorithm described I have extended the capability to support
arc segments between vertices.

$poly =& new polygon(); 
Creates a new polygon. It has no vertices so there
is nothing you can do with it yet. 
$poly>addv($x, $y, [$xc, $yc,
$direction]); 
Add a vertex at point $x, $y. Polygon doesn't care
what units you use for coordinates, but it will assume that they are
coordinates on a 2 dimensional plane when it performs any geometric
operations. So for example $x,$y could be pixels on an image or Easting
or Northing values in meters from a map. It is fine to store other
types of (nonplaner) coordinates in $x,$y, like for example a Longitude/Latitude.
But you must convert them to planer coordinates before you do any
geometry. By default the method adds a line segment. However an arc
segment may be added using the optional arguments $xc, $yc and $direction.
As you would expect $xc, $yc is the center of the arc. $direction
should be +1 for anticlockwise or 1 for clockwise. This method creates
a new vertex object for $x,$y and a new segment object with $xc,$yc,$direction.
It then links them into the polygon object vertex list.

$v =& $poly>getFirst(); 
Returns a reference to the first vertex object in
a polygon. Used if you wish to start iterating over the list of vertices
in a polygon. 
$p =& $poly>NextPoly(); 
A polygon object may store a reference to another
polygon object. This method returns that reference if it exists, else
it returns NULL. It is possible for a clipping or boolean operation
between two polygons to result in several new polygons. When this
happens the method returns a reference to the first polygon in a linked
list of polygons. Subsequent polygons in the list are accessed with
the NextPoly() method. 
$poly>print_poly(); 
This function is useful for debug. It will output
each vertex in the format (X,Y)(Xc,Yc,d). If it is called to print
a polygon during the boolean method then it may display additional
information about vertices which are intersection points between the
polygons being processed by the boolean method. 
$v =& $poly>del($old); 
This method deletes a vertex from a polygon ($old
should be a reference to the vertex to be deleted). It also deletes
the vertex and associated segment objects from memory. It returns
a reference to the next vertex in the polygon (the one right after
the one just deleted). 
$p =& $poly>copy_poly(); 
This method generates a copy of the polygon and returns
a reference to the copy. A polygon object just contains a reference
to the first vertex in a linked list. So simply copying the polygon
object (by using the assignment operator = for example) will not work.
This method creates a completely new list of vertices with identical
coordinates. 
$found = $poly>ints($p1, $p2, $q1, $q2, $num_ints,
$ints_x, $ints_y, $alpha_P, $alpha_Q); 
Find all intersections between the segment defined
by vertices $p1, $p2 and vertices $q1, $q2. The number of intersections
found is returned by reference in $num_ints, this will be a number
between 0 & 2. A 0 means no intersections were found. Arc to line
and arc to arc intersections may return 0, 1 or 2. A line line intersection
can only return 0 or 1. $ints_x and $ints_y are arrays that return
all intersection coordinates by reference. $alpha_P and $alpha_Q are
also arrays that return associated alpha values by reference for each
intersection found. An alpha value is a number between 0 and 1 that
represents where along a segment an intersection occurred. $alpha_P
is for segment $p1,$p2. $alpha_Q is for segment $q1,$q2. An alpha
value of 0.5 would mean that the intersection occurred exactly in
the middle of the segment (halfway between p1 and p2 for example).
An alpha value of 0.25 would mean that the intersection occurred 25%
along the segment starting from the beginning (that is 25% along the
segment from p1 for example). The alpha values work in exactly the
same way for both line and arc segments. The method returns TRUE if
any intersections were found and FALSE if none were found.

$inside = $poly>isInside($v); 
This method returns TRUE if vertex $v is inside the
polygon. A known "feature" of this method (as of version
1.1) is that it may return FALSE even when a vertex is inside a polygon
if the y coordinate of the vertex is exactly the same as the y coordinate
of a vertex in the polygon whose x coordinate is less than the vertex
begin tested (that is, the polygon vertex is exactly left of the vertex
being tested). 
$inside = $poly>isPolyInside($poly1); 
This method works in a similar way to the one above.
In this case all of $poly1 is checked to determine if it lies within
the polygon. The method treats arc segments correctly. TRUE is returned
if $poly1 is completely enclosed by $poly, else FALSE is returned.
A polygon is considered to be inside another polygon if all vertices
of the the first polygon lie within the second polygon and no points
of intersection exist between both polygons. 
$outside = $poly>isPolyOutside($poly1); 
This method works in a similar way to the one above.
In this case all of $poly1 is checked to determine if it lies outside
the polygon. The method treats arc segments correctly. TRUE is returned
if $poly1 is completely outside of $poly, else FALSE is returned.
A polygon is considered to be outside another polygon if all vertices
of the the first polygon lie outside the second polygon and no points
of intersection exist between both polygons. 
$intersect = $poly>isPolyIntersect($poly1); 
This method returns TRUE if there exists any intersection
between the two polygons. 
$intersect = $poly>isPolySelfIntersect(); 
This method returns TRUE if there exists any self
intersection in the polygon. 
$polyR =& $polyA>boolean($polyB,
$oper); 
This method allows 4 different operations between
$polyA and $polyB selected by the argument $oper as follows:
$oper 
Operation 
Value of $polyR of if no intersection exists 
"A&B" 
AND, Intersection 
Copy of $polyA 
"AB" 
OR, Union 
Polygon list consisting of $polyA and $polyB 
"A\B" 
A  B 
Copy of $polyA 
"B\A" 
B  A 
Copy of $polyB 
This is a very powerful method and was in fact initial reason for
creating this class. The method returns a polygon representing the
result of the operation between the two initial polygons. It may
return a polygon list if multiple polygons were generated in the
operation. In the case where no points of intersection exist between
the two polygons then the table above shows what the method will
return. The algorithm used in this method is from the research paper
mentioned at the start of this document. It is a well written and
easy to understand paper that is well worth reading.

$distance = $poly>dist($x1, $y1, $x2, $y2); 
Calculates and returns the straight line distance
between point x1,y1 and point x2,y2. 
$a = $poly>angle($xc, $yc, $x, $y); 
Returns the angle in radians between the line $xc,
$xc to $x, $y and a horizontal line extending from $xc, $yc to the
right (that is to the 3 O'Clock position on a circle whose center
is $xc, $yc). This function is used to calculate the start and end
angles for the imagearc function (when we are drawing arcs) and to
calculate the alpha value for arc segments in the ints() method.

$poly>move($delta_x, $delta_y); 
Move a polygon (that is all vertices that comprise
a polygon) by $delta_x, $delta_y. 
$poly>rotate($center_x, $center_y, $angle); 
Rotate a polygon $angle radians about a point $center_x,
$center_y. Positive values for $angle rotate anticlockwise. negative
values rotate clockwise. 
$bounding_rectangle =& $poly>bRect(); 
This method returns a new polygon that represents
a bounding rectangle for $poly. The polygon returned will have 4 vertices
as follows (xMin,yMin)(xMin,yMax)(xMax,yMax)(xMax,yMin). Arc segments
within $poly will be treated correctly. 
$poly>scale($sx, $sy); 
Multiplies all x coordinates of $poly by $sx and all
y coordinates by $sy. Effectively resizing the polygon by the x and
Y scales given in $sx and $sy. 
$poly>translate($xmin, $ymin, $xmax, $ymax); 
Combines the scale & move methods to translate
$poly to a boundary rectangle defined by the corners ($xmin,$ymin)
and ($xmax,$ymax). 

$v =& new vertex($x,
$y, [$xc, $yc, $direction]); 
This method creates a new vertex. Its arguments work
exactly the same as the polygon method addv().

$v>setX($x); $v>setY($y); $v>setXc($xc);
$v>setYc($yc); 
Setter methods for vertex x,y and arc segment center
Xc,Yc. 
$x = $v>X(); $y = $v>Y(); $xc = $v>Xc([$gate]);
$yc = $v>Yc([$gate]); $d = $v>d([$gate]); 
Getter methods for vertex x,y and arc segment center
Xc,Yc and direction d. A useful test to determine if a segment is
an arc or not is to test the value of d. A nonzero value (1 or +1)
indicates an arc, 0 indicates a line. The optional $gate variable
for the segment getter methods is only used if the vertex $v is an
intersection between two polygons and we which to control whether
we get the previous or next segment in the intersecting polygon. This
capability is only used by the polygon boolean
method. 
$v>setNext($nv); $v>setPrev($pv); $n =&
$v>Next(); $p =& $v>Prev(); 
Setter & Getter methods for the Next/Previous
pointers in the polygon double linked list. The $v>Next() method
may be used when iterating over a polygon. 
$v>setNextPoly($p); $np =& $v>NextPoly(); 
In a polygon list the reference to NextPoly is stored
in the first vertex of the polygon. These are the setter and getter
methods for the NextPoly reference. 
$v>print_vertex(); 
Method called by print_poly()
to print out a polygons vertices. 
$ident = $v>id(); 
Returns the unique identity number of a vertex. This
number is a random number between 0 and 1,000,000 that is assigned
to the vertex when it is created. It is used to easily compare vertices
for equality, typically to determine that we have reached the end
of a polygon because the current vertex id is the same as the id of
the first vertex in the polygon. 

Create a new polygon and add some vertices to it.
This creates a 100x100 square. 
$polyA =& new polygon();
$polyA>addv(0,0);
$polyA>addv(100,0);
$polyA>addv(100,100);
$polyA>addv(0,100);

The polygon class does not handle a polygon with a single vertex,
at least two are needed. In this case a circle is represented by a
polygon with two vertices, each with 180 degree arc between them.
A circle with radius 50, centered at 100,100 would be created with
the following code. Remember, the polygon is always closed, so the
second vertex describes an arc from 100,50 centered on 100,100, clockwise
back to the start point which is the first vertex at 100,150. 
$polyB =& new polygon();
$polyB>addv(100,150,100,100,1);
// Arc from top, anticlockwise
$polyB>addv(100,50,100,100,1);
// to bottom of circle, and back 
Given the square ($polyA) and the circle ($polyB) created above we
can now use the boolean method to get the Intersection, Union and
difference with the following code: 
$poly1 =& $polyA>boolean($polyB,"A&B")
// AND, Intersect operation
$poly2 =& $polyA>boolean($polyB,"AB")
// OR, Union operation
$poly3 =& $polyA>boolean($polyB,"A\B")
// A  B
$poly4 =& $polyA>boolean($polyB,"B\A")
// B  A 
Remember that the boolean method may return a polygon list. So any
functions that handle polygons should also handle the polygon list
case. A simple way to do this is as follows: 
do
{ // //
do something with the polygon here //
$poly =& $poly>NextPoly();
} while($poly); 
The following code draws a polygon in an image $i. It illustrates
how you iterate over all vertices in a polygon and all polygons in
a polygon list. 
/*
** A simple function that draws the polygons onto an image
**
** $x,$y .. are an offset that will be added to all coordinates
of the polygon
** $i .. an image created with the imagecreate
function
** $p .. A polygon Object to be drawn (could be
a list of polygons)
** $col .. An array of allocated colors for the image
** $c .. Index to the colors array  i.e. the
draw color
**
** Real Angle 0 45 90
135 180 225 270 315 360
** imagearc Angle 360 315 270 225 180 135 90 45
0 (To draw real angle)
** Thus imagearc Angle = 360  Real Angle
**
** If d == 1 the arc is AntiClockwise, d == 1 the arc is clockwise
**
** imagearc only draws clockwise arcs, so if we have an AntiClockwise
arc we
** must reverse the order of startangle and endangle.
**
** images have their origin point (0,0) at the top left corner.
However in
** real world math the origin is at the bottom left. This really
only matters
** for arcs (determining clockwise or anticlockwise). Thus the
points in
** the polygon are assumed to exist in real world coordinates. Thus
they
** are 'inverted' in the yaxis to plot them on the image.
*/
function drawPolyAt($x, $y, &$i,
&$p, &$col, $c)
{
if ($i) $sy = imagesy($i);
// Determine the height of the image in pixels
//
All $y coords will be subtracted from this
if ($p) //
If a polygon exists
do //
For all polygons in the list
{
$v =& $p>getFirst();
// get the first vertex of the polygon
do
//
For all vertices in this polygon
{
$n =& $v>Next();
// Get the next vertex
if
($v>d() == 0) // Check
is this an Arc segment
{ //
It is a line
//
So draw a line vertex to vertex
imageLine($i,$x+$v>X(),$sy($y+$v>Y()),$x+$n>X(),$sy($y+$n>Y()),$col[$c]);
}
else
{ //
It is an Arc
$s =
360rad2deg($p>angle($v>Xc(),
$v>Yc(), $v>X(), $v>Y())); //
Start angle
$e =
360rad2deg($p>angle($v>Xc(),
$v>Yc(), $n>X(), $n>Y())); //
End angle
$dia
= 2*$p>dist($v>X(), $v>Y(), $v>Xc(), $v>Yc());
if
($v>d() == 1) // Clockwise
imagearc($i,
$x+$v>Xc(), $sy($y+$v>Yc()),$dia,$dia,$s,$e,$col[$c]);
else
//
AntiClockwise
imagearc($i,
$x+$v>Xc(), $sy($y+$v>Yc()),$dia,$dia,$e,$s,$col[$c]);
}
$v =& $n; //
Move to next vertex
}
while
($v>id() != $p>first>id()); //
Keep drawing until the last vertex
$p =& $p>NextPoly();
// Get the next polygon in the list
}
while ($p);
// Keep drawing polygons as long as they exist
} 

Rev 
Date 
Details 
1.0 
25 Aug 2005 
Initial Release. 
1.1 
4 Sep 2005 
Added the following methods to the polygon Class in
response to a user request: Move($dx,$dy) //
Move a polygon Rotate($xc,$yc,$angle) //
Rotate a polygon isPolyInside($p) //
Test if a polygon is inside another polygon
Created new class documentation (readme.htm)
Removed old html documentation from polyExample.php
Added screen shots of the example images to the class homepage
Added software license language to all source files. 
1.2 
7 Sep 2005 
Fixed a divide by zero error when an attempt is made
to find an intersection between two arcs with the same center point. 
1.3 
16 Apr 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 
19 Mar 2009 
Added isPolyOutside($p) and isPolyIntersect($p) methods.
Added an example to show how they work in polyExample.php. Fixed a
significant bug in the perturb() function in polygon.php. The old
function was simply wrong and could cause unexpected results. 
1.5 
16 Jul 2009 
Added isPolySelfIntersect() method. Added a new example
to show how its used in polyExample.php. 
1.6 
15 May 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. Added some more examples of
degenerate vertices in the polyExample.php file, and added a section
in the this readme file about arc segments and the degenerate vertex
issue. 
