Polygon Class v1.6 Documentation

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

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:

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.

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