From cd1df8f7cb64539842eaad425df5fa7ec9c87fb5 Mon Sep 17 00:00:00 2001 From: Jesper Jensen Date: Wed, 11 Mar 2026 21:59:34 +0100 Subject: Add an example for non-solvable figure --- examples/triangle_tip.c | 90 ++++++++++++++++++++++++++++++++++++ src/solve.c | 11 ++--- test/solve.c | 118 +++++++++++++++++++++++++++++++++++++++++++++++- 3 files changed, 211 insertions(+), 8 deletions(-) create mode 100644 examples/triangle_tip.c diff --git a/examples/triangle_tip.c b/examples/triangle_tip.c new file mode 100644 index 0000000..408c864 --- /dev/null +++ b/examples/triangle_tip.c @@ -0,0 +1,90 @@ +#include "cad.h" + +void draw_from_constraints(struct constraints *c, struct topology *t, struct canvas *cv) { + struct drawing drawing = {}; + bool rc = solve_constraints(c, &drawing); + assert(rc); + + // Copy over all the parameter values to a new array + // @PERF: Maybe we should just store them in a separate array to start with + double *params = malloc(sizeof(double) * (c->length)); + for(size_t i = 0; i < c->length; i++) { + params[i] = c->elements[i].v; + } + + place_points(&drawing, params); + free(params); + + begin_drawing(cv); + draw_topology(cv, t); + draw_constraints(cv, c); + end_drawing(cv); + + free_drawing(&drawing); +} + +int main(int argc, char *argv[]) { + struct constraints constraints = {}; + struct topology topo = {}; + + struct component p1 = {.type = COM_POINT}; + struct component p2 = {.type = COM_POINT}; + struct component p3 = {.type = COM_POINT}; + + struct component p4 = {.type = COM_POINT}; + struct component p5 = {.type = COM_POINT}; + + struct component t1base = {.type = COM_LINE}; + struct component t2base = {.type = COM_LINE}; + struct component t2side = {.type = COM_LINE}; + + add_constraint(&constraints, (struct constraint[]){ + // Make a triangle + PP_DISTANCE(&p1, &p2, 30), + PP_DISTANCE(&p1, &p3, 30), + PP_DISTANCE(&p2, &p3, 30), + + POINT_ON_LINE(&p1, &t1base), + POINT_ON_LINE(&p2, &t1base), + + // With another triangle sharing a point + PP_DISTANCE(&p4, &p5, 30), + PP_DISTANCE(&p3, &p4, 30), + + LL_ANGLE(&t2side, &t2base, DEG(120)), + + POINT_ON_LINE(&p3, &t2side), + POINT_ON_LINE(&p4, &t2side), + + POINT_ON_LINE(&p4, &t2base), + POINT_ON_LINE(&p5, &t2base), + + // The edge they don't share is constrained + LL_ANGLE(&t1base, &t2base, DEG(80)), + CEND(), + }); + + add_fragment(&topo, (struct topology_elem[]){ + TOPO_MOVETO(&p1), + TOPO_LINETO(&p2), + TOPO_LINETO(&p3), + TOPO_LINETO(&p1), + + TOPO_MOVETO(&p3), + TOPO_LINETO(&p4), + TOPO_LINETO(&p5), + TOPO_LINETO(&p3), + + TOPO_END(), + }); + + struct canvas canvas = { + .state = CANVAS_INIT, + .f = stdout, + }; + + draw_from_constraints(&constraints, &topo, &canvas); + + free_constraints(&constraints); + return 0; +} diff --git a/src/solve.c b/src/solve.c index 8ea65c1..1e329dc 100644 --- a/src/solve.c +++ b/src/solve.c @@ -310,9 +310,6 @@ static size_t build_triangles(struct constraint *constraints, size_t constraints } 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++; @@ -610,7 +607,7 @@ static void draw_solution(struct constraint *constraints, size_t fix, struct sol && local_i->type == COM_POINT && constraints[step->j].type == CT_POINT_LINE_DISTANCE && local_j->type == COM_LINE) { - // @COPYPASTA: Taken from rigth above but swapped + // @COPYPASTA: Taken from above but with params swapped assert(oppo_i->type == COM_POINT); struct element *d1 = insert_cmd(drawing, (struct command){ @@ -691,13 +688,13 @@ bool solve_constraints(struct constraints *constraints, struct drawing *drawing) } // Check for unsolved constraints + bool complete = true; for(size_t i = 0; i < constraints->length; i++) { if(!constraints->elements[i].used) { - free(steps); - return false; + complete = false; } } free(steps); - return true; + return complete; } diff --git a/test/solve.c b/test/solve.c index b52d5f9..06038c9 100644 --- a/test/solve.c +++ b/test/solve.c @@ -3,6 +3,117 @@ int main(int argc, char *argv[]) { { + printf("Triangle by 3 distances\n"); + struct constraints constraints = {}; + + struct component p1 = {.type = COM_POINT}; + struct component p2 = {.type = COM_POINT}; + struct component p3 = {.type = COM_POINT}; + + add_constraint(&constraints, (struct constraint[]){ + PP_DISTANCE(&p1, &p2, 30), + PP_DISTANCE(&p1, &p3, 30), + PP_DISTANCE(&p2, &p3, 30), + CEND(), + }); + + struct drawing drawing = {}; + bool solved = solve_constraints(&constraints, &drawing); + + assert(solved); + + free_drawing(&drawing); + free_constraints(&constraints); + } + + { + printf("Triangle by 2 angles and a distance\n"); + struct constraints constraints = {}; + + struct component l1 = {.type = COM_LINE}; + struct component l2 = {.type = COM_LINE}; + struct component l3 = {.type = COM_LINE}; + + struct component p1 = {.type = COM_POINT}; + struct component p2 = {.type = COM_POINT}; + struct component p3 = {.type = COM_POINT}; + + add_constraint(&constraints, (struct constraint[]){ + POINT_ON_LINE(&p1, &l3), + POINT_ON_LINE(&p1, &l1), + + POINT_ON_LINE(&p2, &l1), + POINT_ON_LINE(&p2, &l2), + + POINT_ON_LINE(&p3, &l2), + POINT_ON_LINE(&p3, &l3), + + PP_DISTANCE(&p1, &p2, 30), + LL_ANGLE(&l1, &l2, DEG(60)), + LL_ANGLE(&l2, &l3, DEG(60)), + CEND(), + }); + + struct drawing drawing = {}; + bool solved = solve_constraints(&constraints, &drawing); + + assert(solved); + + free_drawing(&drawing); + free_constraints(&constraints); + } + + { + printf("Two triangles sharing a point one defined by angles\n"); + struct constraints constraints = {}; + + struct component p1 = {.type = COM_POINT}; + struct component p2 = {.type = COM_POINT}; + struct component p3 = {.type = COM_POINT}; + + struct component p4 = {.type = COM_POINT}; + struct component p5 = {.type = COM_POINT}; + + struct component t1base = {.type = COM_LINE}; + struct component t2base = {.type = COM_LINE}; + struct component t2side = {.type = COM_LINE}; + + add_constraint(&constraints, (struct constraint[]){ + // Make a triangle + PP_DISTANCE(&p1, &p2, 30), + PP_DISTANCE(&p1, &p3, 30), + PP_DISTANCE(&p2, &p3, 30), + + POINT_ON_LINE(&p1, &t1base), + POINT_ON_LINE(&p2, &t1base), + + // With another triangle sharing a point + PP_DISTANCE(&p4, &p5, 30), + PP_DISTANCE(&p3, &p4, 30), + + LL_ANGLE(&t2side, &t2base, DEG(60)), + + POINT_ON_LINE(&p3, &t2side), + POINT_ON_LINE(&p4, &t2side), + + POINT_ON_LINE(&p4, &t2base), + POINT_ON_LINE(&p5, &t2base), + + // The edge they don't share is constrained + LL_ANGLE(&t1base, &t2base, DEG(40)), + CEND(), + }); + + struct drawing drawing = {}; + bool solved = solve_constraints(&constraints, &drawing); + assert(solved); + + free_drawing(&drawing); + free_constraints(&constraints); + } + + { + printf("Two triangles sharing a point with an angle constrained base\n"); struct constraints constraints = {}; struct component p1 = {.type = COM_POINT}; @@ -24,7 +135,7 @@ int main(int argc, char *argv[]) { POINT_ON_LINE(&p1, &t1base), POINT_ON_LINE(&p2, &t1base), - // With another triangle sharing the topmost point + // With another triangle sharing a point PP_DISTANCE(&p4, &p5, 30), PP_DISTANCE(&p3, &p4, 30), PP_DISTANCE(&p3, &p5, 30), @@ -40,7 +151,12 @@ int main(int argc, char *argv[]) { struct drawing drawing = {}; bool solved = solve_constraints(&constraints, &drawing); + // @COMPL: We don't currently know how to derive an angle constraint + // from the rigid triangle. We'd probably need to do some sort of + // recursive solving, and even then you can't construct it without some + // sort of math in the construction phase. assert(!solved); + // assert(solved); free_drawing(&drawing); free_constraints(&constraints); -- cgit v1.2.3