diff -r 216f02b50b0a -r 9727e545b0bc src/layers/edittools.cpp
--- a/src/layers/edittools.cpp	Sun Jul 03 13:21:49 2022 +0300
+++ b/src/layers/edittools.cpp	Sun Jul 03 13:44:11 2022 +0300
@@ -18,24 +18,13 @@
 
 #include <QMouseEvent>
 #include <QPainter>
-#include "thirdparty/earcut.h"
 #include "src/model.h"
 #include "src/ui/objecteditor.h"
 #include "src/gl/partrenderer.h"
 #include "src/circularprimitive.h"
 #include "src/layers/edittools.h"
 #include "src/invert.h"
-
-// Make mapbox::earcut work with glm::vec3
-template<> struct mapbox::util::nth<0, glm::vec3>
-{
-	static constexpr float get(const glm::vec3& t) { return t.x; }
-};
-
-template<> struct mapbox::util::nth<1, glm::vec3>
-{
-	static constexpr float get(const glm::vec3& t) { return t.y; }
-};
+#include "src/triangulate.h"
 
 EditTools::EditTools(QObject* parent) :
 	QObject{parent},
@@ -416,68 +405,6 @@
 	}
 }
 
-struct MergedTriangles
-{
-	std::vector<Quadrilateral> quadrilaterals;
-	std::set<std::size_t> cutTriangles;
-};
-
-static MergedTriangles mergeTriangles(
-	const std::vector<std::uint16_t>& indices,
-	const std::vector<glm::vec3>& polygon)
-{
-	MergedTriangles result;
-	using indextype = std::uint16_t;
-	using indexpair = std::pair<indextype, indextype>;
-	struct boundaryinfo { indextype third; std::size_t triangleid; };
-	std::map<indexpair, boundaryinfo> boundaries;
-	for (std::size_t i = 0; i < indices.size(); i += 3) {
-		const auto add = [&](const std::size_t o1, const std::size_t o2, const std::size_t o3){
-			const auto key = std::make_pair(indices[i + o1], indices[i + o2]);
-			boundaries[key] = {indices[i + o3], i};
-		};
-		add(0, 1, 2);
-		add(1, 2, 0);
-		add(2, 0, 1);
-	}
-	std::vector<std::array<indextype, 4>> quadindices;
-	std::vector<Quadrilateral> quads;
-	bool repeat = true;
-	const auto iscut = [&result](const std::size_t i){
-		return result.cutTriangles.find(i) != result.cutTriangles.end();
-	};
-	while (repeat) {
-		repeat = false;
-		// Go through triangle boundaries
-		for (const auto& it1 : boundaries) {
-			const indexpair& pair1 = it1.first;
-			const boundaryinfo& boundary1 = it1.second;
-			// .. the ones we haven't already merged anyway
-			if (not iscut(boundary1.triangleid)) {
-				// Look for its inverse boundary to find the touching triangle
-				const auto pair2 = std::make_pair(pair1.second, pair1.first);
-				const auto it2 = boundaries.find(pair2);
-				// Also if that hasn't been cut
-				if (it2 != boundaries.end() and not iscut(it2->second.triangleid)) {
-					const Quadrilateral quad{
-						polygon[pair1.first],
-						polygon[it2->second.third],
-						polygon[pair1.second],
-						polygon[boundary1.third],
-					};
-					if (isConvex(quad)) {
-						result.quadrilaterals.push_back(quad);
-						result.cutTriangles.insert(boundary1.triangleid);
-						result.cutTriangles.insert(it2->second.triangleid);
-						repeat = true;
-					}
-				}
-			}
-		}
-	}
-	return result;
-}
-
 
 const std::vector<ModelAction> EditTools::circleModeActions() const
 {
@@ -511,41 +438,15 @@
 		result.push_back(AppendToModel{edge(this->polygon[0], this->polygon[1])});
 	}
 	else if (this->numpoints > 2) {
-		const glm::mat4 inverseGrid = glm::inverse(this->gridMatrix);
-		std::vector<std::vector<glm::vec3>> polygons{1};
-		std::vector<glm::vec3>& polygon2d = polygons.back();
-		polygon2d.reserve(this->numpoints);
-		for (std::size_t i = 0; i < this->numpoints; ++i) {
-			polygon2d.push_back(inverseGrid * glm::vec4{this->polygon[i], 1});
-		}
-		// mapbox::earcut will always produce a CCW polygon, so if we're drawing
-		// a CW polygon, we should invert the result afterwards
-		const float shouldInvert = glm::dot(
-			glm::vec3{inverseGrid[2]},
-			glm::cross(this->polygon[0] - this->polygon[1], this->polygon[2] - this->polygon[1]));
-		using indextype = std::uint16_t;
-		const std::vector<indextype> indices = mapbox::earcut<std::uint16_t>(polygons);
-		MergedTriangles mergedTriangles = mergeTriangles(indices, this->polygon);
-		for (Quadrilateral& quad : mergedTriangles.quadrilaterals) {
-			if (shouldInvert < 0) {
-				invert(quad);
-			}
+		for (const PlainPolygonElement& poly : polygonize(
+			this->polygon.begin(),
+			this->polygon.begin() + static_cast<long>(this->numpoints),
+			this->gridMatrix)
+		) {
 			result.push_back(AppendToModel{
-				.newElement = Colored<Quadrilateral>{quad, MAIN_COLOR},
+				.newElement = elementFromPolygonAndColor(poly, MAIN_COLOR),
 			});
 		}
-		for (std::size_t i = 0; i < indices.size(); i += 3) {
-			if (mergedTriangles.cutTriangles.find(i) == mergedTriangles.cutTriangles.end()) {
-				Colored<Triangle> tri = triangle(
-					this->polygon[indices[i]],
-					this->polygon[indices[i + 1]],
-					this->polygon[indices[i + 2]]);
-				if (shouldInvert < 0) {
-					invert(tri);
-				}
-				result.push_back(AppendToModel{tri});
-			}
-		}
 	}
 	return result;
 }