Overview

Hi. Today, while coding my game, I decided to future-proof all the ways I can store collision shapes. It could be useful for me if I could make any path, whether convex or concave into some shape, and have Box2D still handle it. Some searching later I found this paper, which had an algorithm called “ear clipping”, which converts a polygon into triangles. The way I implemented it is as follows:

Algorithm

1. Loop though each point on a path.
2. Using the selected point and the 2 adjacent points, check if the angle is convex or concave.
3. If convex, loop through every other point on the path.
4. If no points are within the triangle formed by the 3 points, it is considered an “ear”.
5. Remove the selected point from the path, and save the 3 points as a triangle.
6. Repeat until there is less than 3 points on the path (no more triangles can be made).

Code

/// Functions

// Gets 'sign' of triangle (>0 = convex, <0 = concave)
// Similar to an area calculation but we don't need all of it
function triangle_sign(_x1, _y1, _x2, _y2, _x3, _y3) {
	var _s = 0;
	_s += _x1 * (_y3 - _y2);
	_s += _x2 * (_y1 - _y3);
	_s += _x3 * (_y2 - _y1);
	return _s;
}

// Returns an array of points.
// A triangle is grouped in 6 coordinates
// (x1, y1, x2, y2, x3, y3)
function path_triangulate(_p) {
	var _path = path_add();
	path_assign(_path, _p);

	var _i = 1, _len = path_get_number(_path), _pts = [];

	// Determine whether path is clockwise or not
	// Helps with further calculations
	var _isClockwise = 0;
	repeat(_len) {
		var _i2 = (_i + 1) % _len;
		
		var _x1 = path_get_point_x(_path, _i);
		var _y1 = path_get_point_y(_path, _i);
		var _x2 = path_get_point_x(_path, _i2);
		var _y2 = path_get_point_y(_path, _i2);
		_isClockwise += (_x2 - _x1) * (_y2 + _y1);
		
		_i++;
	}
	_isClockwise = _isClockwise < 0;

	_i = 1;
	while(_len > 2) {
		// Get point and 2 adjacent points
		var _i0 = (_i-1) % _len, _i1 = _i % _len, _i2 = (_i+1) % _len;
		var _x0 = path_get_point_x(_path, _i0);
		var _y0 = path_get_point_y(_path, _i0);
		var _x1 = path_get_point_x(_path, _i1);
		var _y1 = path_get_point_y(_path, _i1);
		var _x2 = path_get_point_x(_path, _i2);
		var _y2 = path_get_point_y(_path, _i2);
	
		// Find convexity
		var _sign = triangle_sign(_x0, _y0, _x1, _y1, _x2, _y2);
		var _isConvex = _isClockwise ? (_sign < 0) : (_sign > 0);
		if (_isConvex) {
			var _j = 0, _isEar = true;
			
			repeat(_len) {
				// Ear detection
				var _x = path_get_point_x(_path, _j);
				var _y = path_get_point_y(_path, _j);
		
				if (_j != _i0 && _j != _i1 && _j != _i2) {
					if (point_in_triangle(_x, _y, _x0, _y0, _x1, _y1, _x2, _y2)) {
						_isEar = false;
						break;
					}
				}
				
				_j++;
			}
	
			// Add to triangulation array
			if (_isEar) {
				if (_isClockwise) array_push(_pts, _x0, _y0, _x1, _y1, _x2, _y2);
				else array_push(_pts, _x1, _y1, _x0, _y0, _x2, _y2);
				
				path_delete_point(_path, (_i % _len));
				_i--;
				_len--;
			}
		}

		_i++;
	}
    
	path_delete(_path)

	return _pts;
}

Example

Here’s the input path I made and its resulting triangulation. This algorithm should work with any path that doesn’t intersect itself.

Final Thoughts

In the paper mentioned above it, there are some obvious optimizations I could’ve made, but I felt like the code would’ve gotten a bit too clunky, and it takes about 700 microseconds to process a very weird path, so I’m not going to.

Thanks for reading! -AH