Skip to content

Instantly share code, notes, and snippets.

@commy2 commy2/triangulate.sqf
Last active Apr 18, 2019

What would you like to do?
private _polygon = +_this; // deep copy
private _triangles = [];
private _fnc_triangleHeight = { // height from v to uw
params ["_u", "_v", "_w"];
private _a = _v vectorDistance _u;
private _b = _v vectorDistance _w;
private _c = _u vectorDistance _w;
private _s = (_a+_b+_c)/2;
2/_c * sqrt (_s * (_s-_a) * (_s-_b) * (s-_c)) // return
private _fnc_splitTriangle = {
private _polygon = _this;
// already triangular
if (count _polygon <= 3) exitWith {
_triangles append _polygon;
// shift, so left most (and lowest) vertex is second
private _sort = +_polygon;
_sort sort true; // ascending
private _leftBottomMostIndex = _polygon find (_sort select 0);
_polygon = (_polygon select [_leftBottomMostIndex, 1e7]) + (_polygon select [0, _leftBottomMostIndex]);
reverse _polygon;
_polygon pushBack (_polygon deleteAt 0);
reverse _polygon;
// find rogue vertices in triangle uvw
_polygon params ["_u", "_v", "_w"];
private _triangle = [_u, _v, _w];
private _rogues = (_polygon select [3, 1e7]) select {_x inPolygon _triangle};
if (count _rogues isEqualTo 0) then {
// lucky, split polygon with N vertices into a triangle plus a polygon with N-1 vertices
_triangles append [_u, _v, _w];
_polygon deleteAt 1; // remove middle vertex
_polygon call _fnc_splitTriangle; // recursion with smaller polygon
} else {
// unlucky, find furthest vertex from uw
private _sort = _rogues apply {[
[_u, _x, _w] call _fnc_triangleHeight,
_sort sort false; // descending
private _furthest = _sort select 0 select 1;
// split polygon into two smaller polygons at vf axis and continue with both
private _furthestIndex = _polygon find _furthest;
private _polygon1 = [_u, _v] + (_polygon select [_furthestIndex, 1e7]);
private _polygon2 = _polygon select [1, _furthestIndex];
_polygon1 call _fnc_splitTriangle;
_polygon2 call _fnc_splitTriangle;
_polygon call _fnc_splitTriangle;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.