Polygon Class v1.6 Documentation
Copyright © 2005-2010 Brenor Brophy
The source code included in this package is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation.

This 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.

Contents

About the Polygon Class

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 anti-clockwise. 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 uni-erlangen dot de) and Kai Hormann (hormann at informatik dot tu-clausthal dot de), ACM Transactions on Graphics 1998;17(2):71-83. The paper may be accessed at:

http://www2.in.tu-clausthal.de/~hormann/papers/Greiner.1998.ECO.pdf

Using the algorithm described I have extended the capability to support arc segments between vertices.

 

Arc Segments

The original application for the polygon class needed arc segments and so the algorithm was extended to deal with them. Of course, strictly speaking there is no such thing as polygon with arc segments, so they are something of a kluge, though a very useful one for many CAD & mapping operations. Arc segments must be constant radius and are defined by their center coordinate, their direction (CW or CCW) and of course their starting and ending vertices.

An arc segment is created by adding a vertex that in addition to the vertex coordinates also specifies the arc segment center coordinate, and the arc direction. The direction is either clockwise(d=-1) or counter-clockwise(d=+1) from the starting vertex point. The end of the arc is the next vertex. This means of course that the next vertex added to the polygon must fall on the arc. The polygon class does not enforce this, so its quite possible to add a vertex that does not meet this requirement, in this case the polygon is not closed and you will encounter problems when you try to perform boolean operations upon it. Figure 2 below illustrates how a polygon with arc segments is created.

 

Degenerate Vertex Issue

A significant issue with the Greiner/Hormann algorithm is how it treats degenerate vertices. A degenerate vertex is a vertex of one polygon that falls exactly on the edge of another polygon. This situation can easily arise if two polygons have a vertex at the same coordinate or have an edge or part of in edge in common. The algorithm solves the problem by perturbing the vertex very slightly, that is, it changes one coordinate by a very small amount so that it no longer falls exactly on the edge of the other polygon. Unfortunately this perturb method while working much of the time can still lead to unsatisfactory and unpredictable results in some cases. The issue is explained in detail in the paper "An Extension of Polygon Clipping To Resolve Degenerate Cases" by Dae Hyun Kim (cregeo at gmail dot com) and Myoung-Jun Kim. The published paper is available from:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.9804&rep=rep1&type=pdf

A slightly more verbose pre-publication version is available with DH Kim's permission at:

http://getwx.com/Poly/Kim-Kim-Extended-Clipping.pdf

The modified algorithm as described in this paper is not yet incorporated into the polygon class.

Degenerate vertices caused by arc segments, such as a line from one polygon tangentially touching an arc in the other polygon, or two arc segments in two polygons touching at a single point, will not work correctly for boolean operations.

Polygon Class Methods
 

$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 (non-planer) 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 anti-clockwise 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
"A|B"
 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 anti-clockwise. 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).
 

 

Vertex Class Methods
(In general you should not need any of these)
 

$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 non-zero 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.
 

 

Code Examples
 

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, anti-clockwise
$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,"A|B") // 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 Anti-Clockwise, d == 1 the arc is clockwise
**
** imagearc only draws clockwise arcs, so if we have an Anti-Clockwise arc we
** must reverse the order of start-angle and end-angle.
**
** 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 anti-clockwise). Thus the points in
** the polygon are assumed to exist in real world coordinates. Thus they
** are 'inverted' in the y-axis 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 = 360-rad2deg($p->angle($v->Xc(), $v->Yc(), $v->X(), $v->Y())); // Start angle
          $e = 360-rad2deg($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               // Anti-Clockwise
            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
}

 
Revision History
 
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.