diff -r 72b456f2f3c2 -r ce81db996275 src/document.cpp
--- a/src/document.cpp	Tue Jun 14 23:04:49 2022 +0300
+++ b/src/document.cpp	Wed Jun 15 12:17:29 2022 +0300
@@ -18,11 +18,26 @@
 
 #include <QMouseEvent>
 #include <QPainter>
+#include "algorithm/earcut.h"
 #include "document.h"
 #include "model.h"
 #include "ui/objecteditor.h"
 #include "gl/partrenderer.h"
 
+// Make mapbox::earcut work with glm::vec3
+namespace mapbox {
+namespace util {
+template<> struct nth<0, glm::vec3>
+{
+	static constexpr float get(const glm::vec3& t) { return t.x; };
+};
+template<> struct nth<1, glm::vec3>
+{
+	static constexpr float get(const glm::vec3& t) { return t.y; };
+};
+}
+}
+
 EditTools::EditTools(QObject* parent) :
 	QObject{parent},
 	RenderLayer{}
@@ -72,6 +87,10 @@
 		this->worldPosition = this->gridMatrix * glm::vec4{*this->worldPosition, 1};
 		this->polygon.back() = *this->worldPosition;
 	}
+	this->numpoints = this->polygon.size();
+	if (this->isCloseToExistingPoints()) {
+		this->numpoints -= 1;
+	}
 }
 
 static QVector<QPointF> convertWorldPointsToScreenPoints(
@@ -152,7 +171,6 @@
 		.pointBrush = {Qt::white},
 		.pointPen = {QBrush{Qt::black}, 2.0},
 		.polygonPen = {QBrush{Qt::black}, 2.0, Qt::DashLine},
-		.badPolygonPen = {QBrush{Qt::red}, 2.0, Qt::DashLine},
 		.greenPolygonBrush = {QColor{64, 255, 128, 192}},
 		.redPolygonBrush = {QColor{255, 96, 96, 192}},
 	};
@@ -160,7 +178,6 @@
 		.pointBrush = {Qt::black},
 		.pointPen = {QBrush{Qt::white}, 2.0},
 		.polygonPen = {QBrush{Qt::white}, 2.0, Qt::DashLine},
-		.badPolygonPen = {QBrush{Qt::red}, 2.0, Qt::DashLine},
 		.greenPolygonBrush = {QColor{64, 255, 128, 192}},
 		.redPolygonBrush = {QColor{255, 96, 96, 192}},
 	};
@@ -169,7 +186,7 @@
 	case SelectMode:
 		break;
 	case DrawMode:
-		painter->setPen(this->isconcave ? pens.badPolygonPen : pens.polygonPen);
+		painter->setPen(pens.polygonPen);
 		for (const ModelAction& action : this->actions()) {
 			const opt<std::vector<glm::vec3>> points = modelActionPoints(action);
 			if (points.has_value()) {
@@ -201,13 +218,6 @@
 	}
 }
 
-void EditTools::updatePreviewPolygon()
-{
-	if (this->polygon.size() > 2) {
-		this->isconcave = not isConvex(this->polygon);
-	}
-}
-
 void EditTools::removeLastPoint()
 {
 	if (this->polygon.size() > 1) {
@@ -215,12 +225,17 @@
 	}
 }
 
-template<typename T>
-bool isCloseToExistingPoints(T begin, T end, const glm::vec3 &pos)
+bool EditTools::isCloseToExistingPoints() const
 {
-	return std::any_of(begin, end, [&pos](const glm::vec3& p){
-		return isclose(pos, p);
-	});
+	if (this->worldPosition.has_value()) {
+		const glm::vec3& pos = *this->worldPosition;
+		return std::any_of(this->polygon.begin(), this->polygon.end() - 1, [&pos](const glm::vec3& p){
+			return isclose(pos, p);
+		});
+	}
+	else {
+		return false;
+	}
 }
 
 EditingMode EditTools::currentEditingMode() const
@@ -239,12 +254,11 @@
 		break;
 	case DrawMode:
 		if (event->button() == Qt::LeftButton and this->worldPosition.has_value()) {
-			if (isCloseToExistingPoints(this->polygon.begin(), this->polygon.end() - 1, *this->worldPosition)) {
+			if (isCloseToExistingPoints()) {
 				this->closeShape();
 			}
 			else {
 				this->polygon.push_back(*this->worldPosition);
-				this->updatePreviewPolygon();
 			}
 		}
 		else if (true
@@ -252,53 +266,142 @@
 			and this->polygon.size() > 1
 		) {
 			this->removeLastPoint();
-			updatePreviewPolygon();
 		}
 		break;
 	}
 }
 
+constexpr float distancesquared(const glm::vec3& p1, const glm::vec3& p2)
+{
+	const float dx = p2.x - p1.x;
+	const float dy = p2.y - p1.y;
+	const float dz = p2.z - p1.z;
+	return (dx * dx) + (dy * dy) + (dz * dz);
+}
+
+inline float area(const Quadrilateral& q)
+{
+	return 0.5 * (
+		glm::length(glm::cross(q.p2 - q.p1, q.p3 - q.p1)) +
+		glm::length(glm::cross(q.p3 - q.p2, q.p4 - q.p2))
+	);
+}
+
+inline float energy(const Quadrilateral& q)
+{
+	const float L2 = distancesquared(q.p1, q.p2)
+		+ distancesquared(q.p2, q.p3)
+		+ distancesquared(q.p3, q.p4)
+		+ distancesquared(q.p4, q.p1);
+	return 1 - 6.928203230275509 * area(q) / L2;
+}
+
+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 = [&](int o1, int o2, int 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;
+		// TODO: make this a function that returns quadrilateral indices
+		// 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::actions() const
 {
 	std::vector<ModelAction> result;
-	if (this->polygon.size() >= 2 and this->polygon.size() <= 4) {
-		switch (this->polygon.size()) {
-		case 2:
-			result.push_back(AppendToModel{
-				.newElement = Colored<LineSegment>{
-					LineSegment{
-						.p1 = this->polygon[0],
-						.p2 = this->polygon[1],
-					},
-					EDGE_COLOR,
-				}
-			});
-			break;
-		case 3:
+	if (this->numpoints == 2) {
+		result.push_back(AppendToModel{
+			.newElement = Colored<LineSegment>{
+				LineSegment{
+					.p1 = this->polygon[0],
+					.p2 = this->polygon[1],
+				},
+				EDGE_COLOR,
+			}
+		});
+	}
+	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});
+		}		
+		using indextype = std::uint16_t;
+		const std::vector<indextype> indices = mapbox::earcut<std::uint16_t>(polygons);
+		MergedTriangles mergedTriangles = mergeTriangles(indices, this->polygon);
+		for (const Quadrilateral& quad : mergedTriangles.quadrilaterals) {
 			result.push_back(AppendToModel{
-				.newElement = Colored<Triangle>{
-					Triangle{
-						.p1 = this->polygon[0],
-						.p2 = this->polygon[1],
-						.p3 = this->polygon[2],
-					},
-					MAIN_COLOR,
-				}
+				.newElement = Colored<Quadrilateral>{quad, MAIN_COLOR},
 			});
-			break;
-		case 4:
-			result.push_back(AppendToModel{
-				.newElement = Colored<Quadrilateral>{
-					Quadrilateral{
-						.p1 = this->polygon[0],
-						.p2 = this->polygon[1],
-						.p3 = this->polygon[2],
-						.p4 = this->polygon[3],
-					},
-					MAIN_COLOR,
-				}
-			});
-			break;
+		}
+		for (std::size_t i = 0; i < indices.size(); i += 3) {
+			if (mergedTriangles.cutTriangles.find(i) == mergedTriangles.cutTriangles.end()) {
+				result.push_back(AppendToModel{
+					.newElement = Colored<Triangle>{
+						Triangle{
+							.p1 = this->polygon[indices[i]],
+							.p2 = this->polygon[indices[i + 1]],
+							.p3 = this->polygon[indices[i + 2]],
+						},
+						MAIN_COLOR,
+					}
+				});
+			}
 		}
 	}
 	return result;
@@ -310,5 +413,4 @@
 		Q_EMIT this->modelAction(action);
 	}
 	this->polygon.clear();
-	this->updatePreviewPolygon();
 }