Split the solver into it's own file

1 files changed, 519 insertions, 0 deletions

diff --git a/src/solve.c b/src/solve.c
new file mode 100644
index 0000000..fd0c7cd
--- /dev/null
+++ b/src/solve.c
@@ -0,0 +1,519 @@
+#include "cad/solve.h"
+
+#define SWAP(x, y) do { \
+		typeof(x) tmp = x; \
+		x = y; \
+		y = tmp; \
+	}while(0)
+
+char *constraint_type_name[] = {
+	[CT_POINT_POINT_DISTANCE] = "Point Point Distance",
+	[CT_POINT_LINE_DISTANCE] = "Point Line Distance",
+	[CT_LINE_LINE_ANGLE] = "Line Line Angle",
+};
+
+// @IMPROVE: We should do something better than this. I don't really know what.
+struct frontier {
+	struct component *elems[64];
+	size_t n;
+};
+
+static bool frontier_scan(struct frontier *frontier, struct component *component) {
+	for(size_t i = 0; i < sizeof(frontier->elems)/sizeof(frontier->elems[0]); i++) {
+		if(frontier->elems[i] == component) return true;
+	}
+
+	return false;
+}
+
+static void add_frontier(struct frontier *frontier, struct component *component) {
+	assert(!frontier_scan(frontier, component));
+	frontier->elems[frontier->n++] = component;
+}
+
+static void build_angle_point_line(struct drawing *drawing, struct component *local_i, struct component *local_j, struct component *oppo_i, bool swap) {
+	assert(local_i->e != NULL);
+	assert(local_j->e != NULL);
+	assert(local_i->type == COM_LINE);
+	assert(local_j->type == COM_POINT);
+	struct element *theta = insert_cmd(drawing, (struct command){
+		.op = CMD_VALUE_INPUT,
+		.result.type = ETYPE_VALUE,
+	});
+
+	struct element *d = insert_cmd(drawing, (struct command){
+		.op = CMD_VALUE_INPUT,
+		.result.type = ETYPE_VALUE,
+	});
+
+	if(swap) SWAP(theta, d);
+
+	struct element* l = insert_cmd(drawing, (struct command){
+		.op = CMD_LINE_POINT_LINE_ANGLE,
+		.hidden = !oppo_i->show_when_placed,
+		.result.type = ETYPE_LINE,
+		.arg1 = local_j->e,
+		.arg2 = local_i->e,
+		.arg3 = theta,
+	});
+	assert(l != NULL);
+
+	oppo_i->e = insert_cmd(drawing, (struct command){
+		.op = CMD_LINE_LINE_DISTANCE_PARALLEL,
+		.hidden = !oppo_i->show_when_placed,
+		.result.type = ETYPE_LINE,
+		.arg1 = l,
+		.arg2 = d,
+	});
+}
+
+struct angle_search_frame {
+	size_t constraint_i;
+	struct component *head;
+	bool dir;
+};
+static bool find_angle(struct constraint *constraints, size_t constraints_num, struct component *first_component, struct component *needle, struct path_step *path) {
+	struct angle_search_frame frames[SEARCH_DEPTH];
+	struct angle_search_frame *frame = frames;
+
+	frame->constraint_i = 0;
+	frame->head = first_component;
+
+	bool *checked = calloc(sizeof(bool), constraints_num);
+
+	while(frame >= frames) {
+		assert(frame < frames + SEARCH_DEPTH);
+		assert(frame >= frames);
+
+		assert(frame->constraint_i <= constraints_num);
+		if(frame->constraint_i == constraints_num) {
+#if 0
+			printf("Dead end at: ");
+			for(struct angle_search_frame *i = frames; i <= frame; i++) {
+				printf("%ld -> ", i->constraint_i);
+			}
+			printf("\n");
+#endif
+			frame--;
+			frame->constraint_i++;
+			continue;
+		}
+
+		if(checked[frame->constraint_i]) {
+			frame->constraint_i++;
+			continue;
+		}
+
+		struct constraint *constraint = &constraints[frame->constraint_i];
+		if(constraint->type != CT_LINE_LINE_ANGLE) {
+			frame->constraint_i++;
+			continue;
+		}
+
+		struct component *other;
+
+		if(constraint->c1 == frame->head) {
+			other = constraint->c2;
+			frame->dir = true;
+		} else if(constraint->c2 == frame->head) {
+			other = constraint->c1;
+			frame->dir = false;
+		} else {
+			frame->constraint_i++;
+			continue;
+		}
+
+		if(other == needle) {
+			for(struct angle_search_frame *i = frames; i <= frame; i++) {
+				path[i - frames].i = i->constraint_i;
+				path[i - frames].direction = i->dir;
+			}
+			if(frame < frames + SEARCH_DEPTH-1) {
+				path[frame - frames + 1].i = -1;
+			}
+			return true;
+		}
+
+		checked[frame->constraint_i] = true;
+
+		frame++;
+		frame->constraint_i = 0;
+		frame->head = other;
+	}
+
+	return false;
+}
+
+struct solve_step {
+	size_t i;
+	size_t j;
+	bool i_forward;
+	bool j_forward;
+};
+
+static bool fix_first(struct constraint *constraints, size_t constraints_num, size_t *c) {
+
+	for(size_t i = 0; i < constraints_num; i++) {
+		if(constraints[i].used) continue;
+		if(constraints[i].type != CT_POINT_POINT_DISTANCE) continue;
+
+		*c = i;
+		return true;
+	}
+
+	return false;
+}
+
+static size_t build_triangles(struct constraint *constraints, size_t constraints_num, size_t origin, struct solve_step *steps) {
+	struct frontier frontier = {};
+	uint64_t order = 1;
+
+	for(size_t i = 0; i < constraints_num; i++) {
+		if(constraints[i].used) continue;
+
+		constraints[i].path[0].i = -1;
+		constraints[i].forward = true;
+	}
+
+	constraints[origin].used = true;
+	constraints[origin].order = order++;
+	add_frontier(&frontier, constraints[origin].c1);
+	add_frontier(&frontier, constraints[origin].c2);
+
+	size_t steps_i = 0;
+
+	while(true) {
+		for(size_t i = 0; i < constraints_num; i++) {
+			if(constraints[i].used) continue;
+
+			struct component *oppo_i;
+			bool i_forward;
+
+			if(frontier_scan(&frontier, constraints[i].c1)) {
+				oppo_i = constraints[i].c2;
+				i_forward = true;
+			} else if(frontier_scan(&frontier, constraints[i].c2)) {
+				oppo_i = constraints[i].c1;
+				i_forward = false;
+			} else continue;
+
+			for(size_t j = i+1; j < constraints_num; j++) {
+				if(constraints[j].used) continue;
+
+				struct component *oppo_j;
+				bool j_forward;
+
+				if(frontier_scan(&frontier, constraints[j].c1)) {
+					oppo_j = constraints[j].c2;
+					j_forward = true;
+				} else if(frontier_scan(&frontier, constraints[j].c2)) {
+					oppo_j = constraints[j].c1;
+					j_forward = false;
+				} else continue;
+
+				// One of the constraints can't be an angle one
+				if(constraints[i].type == CT_LINE_LINE_ANGLE && constraints[j].type == CT_LINE_LINE_ANGLE) continue;
+
+				if(oppo_i != oppo_j) {
+					if(constraints[i].type == CT_LINE_LINE_ANGLE) {
+						if(!find_angle(constraints, constraints_num, oppo_i, oppo_j, constraints[i].path)) continue;
+
+						oppo_i = oppo_j;
+					} else if(constraints[j].type == CT_LINE_LINE_ANGLE) {
+						if(!find_angle(constraints, constraints_num, oppo_j, oppo_i, constraints[j].path)) continue;
+
+						oppo_j = oppo_i;
+					} else continue;
+				}
+
+				// constraints[i].forward = i_forward;
+				// constraints[j].forward = j_forward;
+
+				add_frontier(&frontier, oppo_i);
+				constraints[i].used = true;
+				constraints[i].order = order++;
+				constraints[j].used = true;
+				constraints[j].order = order++;
+				steps[steps_i].i = i;
+				steps[steps_i].j = j;
+				steps[steps_i].i_forward = i_forward;
+				steps[steps_i].j_forward = j_forward;
+				steps_i++;
+				goto candidate_found;
+			}
+		}
+		// No candidate found
+		break;
+
+candidate_found:
+		;
+	}
+
+	return steps_i;
+}
+
+bool solve_constraints(struct constraint *constraints, size_t constraints_num, struct drawing *drawing) {
+	// Step 1 Pick some point point distance constraint as the base
+	size_t fix;
+	if(!fix_first(constraints, constraints_num, &fix)) {
+		return false;
+	}
+
+	// Build the root of the drawing
+	constraints[fix].c1->e = insert_cmd(drawing, (struct command){
+		.op = CMD_ORIGIN,
+		.hidden = true,
+		.result.type = ETYPE_POINT,
+	});
+
+	struct element *xaxis = insert_cmd(drawing, (struct command){
+		.op = CMD_LINE_X,
+		.hidden = true,
+		.result.type = ETYPE_LINE,
+	});
+
+	struct element *distance = insert_cmd(drawing, (struct command){
+		.op = CMD_VALUE_INPUT,
+		.result.type = ETYPE_VALUE,
+	});
+
+	struct element *c = insert_cmd(drawing, (struct command){
+		.op = CMD_CIRCLE_CENTER_RADIUS,
+		.hidden = true,
+		.result.type = ETYPE_CIRCLE,
+		.arg1 = constraints[fix].c1->e,
+		.arg2 = distance,
+	});
+
+	constraints[fix].c2->e = insert_cmd(drawing, (struct command){
+		.op = CMD_POINT_CIRCLE_LINE,
+		.hidden = true,
+		.result.type = ETYPE_POINT,
+		.arg1 = c,
+		.arg2 = xaxis,
+	});
+
+	struct solve_step *steps = malloc(sizeof(struct solve_step) * constraints_num);
+	size_t steps_num = build_triangles(constraints, constraints_num, fix, steps);
+
+	// printf("Solved in %ld steps\n", steps_num);
+
+	for(struct solve_step *step = steps; step < (steps + steps_num); step++) {
+		struct component *local_i;
+		struct component *oppo_i;
+		if(step->i_forward) {
+			local_i = constraints[step->i].c1;
+			oppo_i = constraints[step->i].c2;
+		} else {
+			local_i = constraints[step->i].c2;
+			oppo_i = constraints[step->i].c1;
+		}
+
+		struct component *local_j;
+		struct component *oppo_j;
+		if(step->j_forward) {
+			local_j = constraints[step->j].c1;
+			oppo_j = constraints[step->j].c2;
+		} else {
+			local_j = constraints[step->j].c2;
+			oppo_j = constraints[step->j].c1;
+		}
+
+		if(oppo_i != oppo_j) {
+			if(constraints[step->i].type == CT_LINE_LINE_ANGLE) {
+				oppo_i = oppo_j;
+			} else if(constraints[step->j].type == CT_LINE_LINE_ANGLE) {
+				// Do nothing, oppo_j isn't used below
+			} else {
+				assert(false);
+			}
+		}
+
+		assert(local_i->e != NULL);
+		assert(local_j->e != NULL);
+
+		bool shown = oppo_i->show_when_placed;
+
+		if(constraints[step->i].type == CT_POINT_POINT_DISTANCE
+			&& local_i->type == COM_POINT
+			&& constraints[step->j].type == CT_POINT_POINT_DISTANCE
+			&& local_j->type == COM_POINT) {
+			assert(oppo_i->type == COM_POINT);
+
+			struct element *d1 = insert_cmd(drawing, (struct command){
+				.op = CMD_VALUE_INPUT,
+				.result.type = ETYPE_VALUE,
+			});
+
+			struct element *d2 = insert_cmd(drawing, (struct command){
+				.op = CMD_VALUE_INPUT,
+				.result.type = ETYPE_VALUE,
+			});
+
+			struct element *c1 = insert_cmd(drawing, (struct command){
+				.op = CMD_CIRCLE_CENTER_RADIUS,
+				.hidden = !shown,
+				.result.type = ETYPE_CIRCLE,
+				.arg1 = local_i->e,
+				.arg2 = d1,
+			});
+
+			struct element *c2 = insert_cmd(drawing, (struct command){
+				.op = CMD_CIRCLE_CENTER_RADIUS,
+				.hidden = !shown,
+				.result.type = ETYPE_CIRCLE,
+				.arg1 = local_j->e,
+				.arg2 = d2,
+			});
+
+			oppo_i->e = insert_cmd(drawing, (struct command){
+				.op = CMD_POINT_CIRCLE_CIRCLE,
+				.hidden = !shown,
+				.result.type = ETYPE_POINT,
+				.arg1 = c1,
+				.arg2 = c2,
+			});
+		} else if(constraints[step->i].type == CT_POINT_LINE_DISTANCE
+			&& local_i->type == COM_POINT
+			&& constraints[step->j].type == CT_POINT_LINE_DISTANCE
+			&& local_j->type == COM_POINT) {
+			assert(oppo_i->type == COM_LINE);
+
+			struct element *d1 = insert_cmd(drawing, (struct command){
+				.op = CMD_VALUE_INPUT,
+				.result.type = ETYPE_VALUE,
+			});
+			struct element *d2 = insert_cmd(drawing, (struct command){
+				.op = CMD_VALUE_INPUT,
+				.result.type = ETYPE_VALUE,
+			});
+
+			struct element *c1 = insert_cmd(drawing, (struct command){
+				.op = CMD_CIRCLE_CENTER_RADIUS,
+				.hidden = !shown,
+				.result.type = ETYPE_CIRCLE,
+				.arg1 = local_i->e,
+				.arg2 = d1,
+			});
+
+			struct element *c2 = insert_cmd(drawing, (struct command){
+				.op = CMD_CIRCLE_CENTER_RADIUS,
+				.hidden = !shown,
+				.result.type = ETYPE_CIRCLE,
+				.arg1 = local_j->e,
+				.arg2 = d2,
+			});
+
+			oppo_i->e = insert_cmd(drawing, (struct command){
+				.op = CMD_LINE_CIRCLE_CIRCLE_TANGENT,
+				.hidden = !shown,
+				.result.type = ETYPE_LINE,
+				.arg1 = c1,
+				.arg2 = c2,
+			});
+		} else if(constraints[step->i].type == CT_POINT_LINE_DISTANCE
+			&& local_i->type == COM_LINE
+			&& constraints[step->j].type == CT_POINT_LINE_DISTANCE
+			&& local_j->type == COM_LINE) {
+			assert(oppo_i->type == COM_POINT);
+
+			struct element *d1 = insert_cmd(drawing, (struct command){
+				.op = CMD_VALUE_INPUT,
+				.result.type = ETYPE_VALUE,
+			});
+			struct element *d2 = insert_cmd(drawing, (struct command){
+				.op = CMD_VALUE_INPUT,
+				.result.type = ETYPE_VALUE,
+			});
+
+			struct element *l1 = insert_cmd(drawing, (struct command){
+				.op = CMD_LINE_LINE_DISTANCE_PARALLEL,
+				.hidden = !shown,
+				.result.type = ETYPE_LINE,
+				.arg1 = local_i->e,
+				.arg2 = d1,
+			});
+
+			struct element *l2 = insert_cmd(drawing, (struct command){
+				.op = CMD_LINE_LINE_DISTANCE_PARALLEL,
+				.hidden = !shown,
+				.result.type = ETYPE_LINE,
+				.arg1 = local_j->e,
+				.arg2 = d2,
+			});
+
+			oppo_i->e = insert_cmd(drawing, (struct command){
+				.op = CMD_POINT_LINE_LINE,
+				.hidden = !shown,
+				.result.type = ETYPE_POINT,
+				.arg1 = l1,
+				.arg2 = l2,
+			});
+		} else if(constraints[step->i].type == CT_LINE_LINE_ANGLE
+			&& local_i->type == COM_LINE
+			&& constraints[step->j].type == CT_POINT_LINE_DISTANCE
+			&& local_j->type == COM_POINT) {
+			assert(oppo_i->type == COM_LINE);
+
+			constraints[step->i].forward = step->i_forward;
+			constraints[step->j].forward = step->j_forward;
+
+			build_angle_point_line(drawing, local_i, local_j, oppo_i, false);
+		} else if(constraints[step->i].type == CT_POINT_LINE_DISTANCE
+			&& local_i->type == COM_POINT
+			&& constraints[step->j].type == CT_LINE_LINE_ANGLE
+			&& local_j->type == COM_LINE) {
+			assert(oppo_i->type == COM_LINE);
+
+			constraints[step->i].forward = step->i_forward;
+			constraints[step->j].forward = step->j_forward;
+
+			build_angle_point_line(drawing, local_j, local_i, oppo_i, true);
+		} else if(constraints[step->i].type == CT_POINT_LINE_DISTANCE
+			&& local_i->type == COM_LINE
+			&& constraints[step->j].type == CT_POINT_POINT_DISTANCE
+			&& local_j->type == COM_POINT) {
+			assert(oppo_i->type == COM_POINT);
+
+			struct element *d1 = insert_cmd(drawing, (struct command){
+				.op = CMD_VALUE_INPUT,
+				.result.type = ETYPE_VALUE,
+			});
+			struct element *d2 = insert_cmd(drawing, (struct command){
+				.op = CMD_VALUE_INPUT,
+				.result.type = ETYPE_VALUE,
+			});
+
+			struct element *l = insert_cmd(drawing, (struct command){
+				.op = CMD_LINE_LINE_DISTANCE_PARALLEL,
+				.hidden = !shown,
+				.result.type = ETYPE_LINE,
+				.arg1 = local_i->e,
+				.arg2 = d1,
+			});
+
+			struct element *c = insert_cmd(drawing, (struct command){
+				.op = CMD_CIRCLE_CENTER_RADIUS,
+				.hidden = !shown,
+				.result.type = ETYPE_CIRCLE,
+				.arg1 = local_j->e,
+				.arg2 = d2,
+			});
+
+			oppo_i->e = insert_cmd(drawing, (struct command){
+				.op = CMD_POINT_CIRCLE_LINE,
+				.hidden = !shown,
+				.root = constraints[step->j].c2 == local_j,
+				.result.type = ETYPE_POINT,
+				.arg1 = c,
+				.arg2 = l,
+			});
+		} else {
+			printf("Unknown constraint combination %s and %s\n", constraint_type_name[constraints[step->i].type], constraint_type_name[constraints[step->j].type]);
+			abort();
+		}
+
+	}
+
+	return true;
+}