# 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

- Loop though each point on a path.
- Using the selected point and the 2 adjacent points, check if the angle is convex or concave.
- If convex, loop through every other point on the path.
- If no points are within the triangle formed by the 3 points, it is considered an “ear”.
- Remove the selected point from the path, and save the 3 points as a triangle.
- 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