tec20

  web systems
  business-to-business applications
  mobile apps

Polygon Triangulation in PHP

I have been working on a project that requires rendering various shapes in 3D. A common problem is having to represent a polygon in a way that makes it possible to render the shape in 3D. The standard approach is to break the polygon down into triangles.

I’m having to work in PHP. It wouldn’t be my first choice to run a mathematically intense calculation, but needs must. Having searched for a while looking for possible libraries or classes, there appear to be none. Time to get coding….

I’m going to be using the basic ear-clipping algorithm to carve up the polygon. The algorithm is fast and simple to implement, however I would still recommend reading the link above in order to understand how the algorithm works.

To start with, I’m going to have to create some classes to represent the geometric shapes we’re working with. First up is a class to store co-ordinates, or points.

class Point2D {
	public $x;
	public $y;

	public function __construct($x, $y) {
		$this->x = (float) $x;
		$this->y = (float) $y;
	}

	public function __toString() {
		return '{x:' . $this->x . ',y:' . $this->y . '}';
	}
}

This class is very basic, but it keeps the implementation tidy.

Next up is a class to represent the polygon:

class Polygon2D {
	protected $points;

	public function __construct(array $points = null) {
		if (!is_null($points)) {
			$this->points = $points;
		} else {
			$this->points = array();
		}
	}

	public function addPoint(Point2D $point) {
		$this->points[] = $point;
	}

	public function getPoints() {
		return $this->points;
	}

	public function removePoint($index, $length = 1) {
		array_splice($this->points, $index, $length);
	}

	public function __toString() {
		$output = '';
		foreach($this->getPoints() as $index => $point) {
			$output .= $point . "\n";
		}
		return $output;
	}
}

Now we have some classes to represent the polygon that we are going to triangulate. Next we need to implement the ear-clipping algorithm.

I have created a separate class containing some static methods for the triangulation. I have chosen to do it this way as I may want to triangulate more than just a Polygon2D object. The core loop of the ear-clipping algorithm iterates over the polygon, looks for suitable corners (the ‘ears’) and cuts them off. This is repeated until you are left with a triangle, which is the final triangle in the triangulation. An ear is determined by the angle of the corner being internal (being negative if we loop over the polygon clockwise) and doesn’t contain any other points of the polygon inside the triangle formed by the lines connecting the corner.

class TrigUtil {
	/**
	 * Convert a polygon into an array of triangles.
	 * 
	 * @param Polygon2D $polygon
	 * @return array:Polygon2D
	 */
	public static function triangulate(Polygon2D $polygon) {
		// Instantiate the empty array to place the triangles in
		$triangles = array();

		// Make a copy of the polygon's shape, which will be iteratively deconstructed
		$polygonPoints = $polygon->getPoints();

		// determine whether the polygon is clockwise or anti-clockwise
		$totalAngle = 0;
		$lastPoint = null;
		for ($p = 0; $p < sizeof($polygonPoints); $p++) {
			if (!is_null($lastPoint) && $polygonPoints[$p] == $lastPoint) {
				// This point is the same as the last, so remove it
				$this->removePoint($p);
				continue;
			}
			$angle = TrigUtil::angleBetweenLines(
					$polygonPoints[($p - 1) == -1 ? sizeof($polygonPoints) - 1
									: $p - 1], $polygonPoints[$p],
					$polygonPoints[($p + 1) % sizeof($polygonPoints)]);
			$totalAngle += $angle;
			$lastPoint = $polygonPoints[$p];
		}
		if ((int) $totalAngle == -360) {
			/* Points are anti-clockwise, so reverse the array to make them
			 * clockwise.
			 */
			$polygonPoints = array_reverse($polygonPoints);
		}

		// If our polygon only has 3 sides, it's a triangle and we're done
		while (sizeof($polygonPoints) > 3) {
			for ($p = 0; $p < sizeof($polygonPoints); $p++) {
				$pointA = $polygonPoints[($p - 1) == -1 ? sizeof($polygonPoints)
								- 1 : $p - 1];
				$pointB = $polygonPoints[$p];
				$pointC = $polygonPoints[($p + 1) % sizeof($polygonPoints)];

				$angle = TrigUtil::angleBetweenLines($pointA, $pointB, $pointC);

				// If the angle is positive (bends to the left), it is internal
				// (as the polygon is anti-clockwise)
				if ($angle == 180 || $angle == -180) {
					// triangle has no area, so ignore it but pretend we've just added it
					array_splice($polygonPoints, $p, 1);
					continue 2;
				} elseif ($angle >= 0) {
					/* 
					 * This corner may be suitable, check that it doesn't
					 * overlap with any other point and is therefore an ear
					 */
					foreach ($polygonPoints as $index => $point) {
						if ($point == $pointA || $point == $pointB
								|| $point == $pointC) {
							/* one of the triangle points,
							 * so move on to the next point
							 */
							continue;
						}

						if (TrigUtil::isPointInsideTriangle($point, $pointA,
								$pointB, $pointC)) {
							/* Can't use this corner,
							 * so move on to the next corner
							 */
							continue 2;
						}
					}

					// Found a suitable ear, remove it from the polygon
					array_splice($polygonPoints, $p, 1);

					// add the triangle to the array
					$triangles[] = new Polygon2D(
							array($pointC, $pointB, $pointA));

					// start from the top with our new polygon
					continue 2;
				}
			}
		}

		// Add the remaining 3-sided polygon (the final triangle)
		$triangles[] = new Polygon2D($polygonPoints);

		return $triangles;
	}

	/**
	 * Determine if a point sits inside a triangle
	 *
	 * @param Point $point The point to test
	 * @param Point $triangleA First corner of the triangle
	 * @param Point $triangleB Second corner of the triangle
	 * @param Point $triangleC Third corner of the triangle
	 * @return boolean
	 */
	public static function isPointInsideTriangle(Point2D $point,
			Point2D $triangleA, Point2D $triangleB, Point2D $triangleC) {

		// Find the dot product of each line of the traingle with respect to the point
		$lineAB = ($triangleA->x - $point->x) * ($triangleB->y - $point->y)
				- ($triangleB->x - $point->x) * ($triangleA->y - $point->y);
		$lineBC = ($triangleB->x - $point->x) * ($triangleC->y - $point->y)
				- ($triangleC->x - $point->x) * ($triangleB->y - $point->y);
		$lineCA = ($triangleC->x - $point->x) * ($triangleA->y - $point->y)
				- ($triangleA->x - $point->x) * ($triangleC->y - $point->y);

		// A 'sign' of zero would indicate that the point is on the plane
		$signAB = ($lineAB > 0) ? 1 : (($lineAB < 0) ? -1 : 0);
		$signBC = ($lineBC > 0) ? 1 : (($lineBC < 0) ? -1 : 0);
		$signCA = ($lineCA > 0) ? 1 : (($lineCA < 0) ? -1 : 0);

		// In order to determine if the triangle is inside or not, we have to check
		// that all signs match (or they are not opposing)
		$isInside = true;
		if (($signAB == -1 && $signBC == 1) || ($signAB == 1 && $signBC == -1))
			$isInside = false;
		if (($signBC == -1 && $signCA == 1) || ($signBC == 1 && $signCA == -1))
			$isInside = false;
		if (($signAB == -1 && $signCA == 1) || ($signAB == 1 && $signCA == -1))
			$isInside = false;

		return $isInside;
	}

	/**
	 * Calculate the angle between vector 1 to 2 and 2 to 3.
	 * Angle is positive for clockwise, negative for anti-clockwise
	 * 
	 * @param Point2D $point1
	 * @param Point2D $point2
	 * @param Point2D $point3
	 * @return float
	 */
	public static function angleBetweenLines(Point2D $point1, Point2D $point2,
			Point2D $point3) {
		$d1x = $point2->x - $point1->x;
		$d1y = $point2->y - $point1->y;

		$d2x = $point3->x - $point2->x;
		$d2y = $point3->y - $point2->y;

		$angle = atan2($d1x * $d2y - $d1y * $d2x, $d1x * $d2x + $d1y * $d2y);
		$angle = rad2deg($angle);

		return $angle;
	}
}

One important part to understand is that all polygons must be handled in an anti-clockwise direction. When we work with this assumption, all the corners that qualify as an ear will have a positive angle. Conversely, all unsuitable corners will have a negative angle. This is crucial to detect this angle. In order to guarantee that the polygon is wound anti-clockwise, a loop at the start of the triangulate() method performs this check. If it finds the polygon to be wound in the wrong direction, it reverses the order of the points. (When working in 3D, it is normal to process shapes in an anti-clockwise direction).

The two additional methods in the class, isPointInsideTriangle() and angleBetweenLines(), are standard techniques and key to the main triangulation loop.

My actual solution is part of a larger library, which has more functionality in the Point2D and Polygon2D classes. I have condensed the cut-down code into a single file so you can play with the triangulation implementation. To test the code, unremark the example at the bottom of the file.

As for the limitations in my implementation, this solution does not cater for holes in the polygon. It would be straightforward enough to add this functionality, as detailed in the pdf, however I don’t require this so have left it out.

Posted in , | | 0 responses

Leave a comment