#include #include #include #include #include #include #define TEXT_OFFSET 0.4 #define SETSIGN(b, v) ((v) * ((2 * (b)) - 1)); enum operation { CMD_VALUE_INPUT, CMD_ORIGIN, CMD_LINE_X, CMD_CIRCLE_CENTER_RADIUS, CMD_CIRCLE_CENTER_POINT, CMD_LINE_POINT_POINT, CMD_LINE_POINT_LINE_ANGLE, CMD_POINT_CIRCLE_LINE, CMD_POINT_CIRCLE_CIRCLE, CMD_POINT_LINE_LINE, // Additional operations we need to handle explicitly to avoid degenerate // cases CMD_LINE_CIRCLE_CIRCLE_TANGENT, CMD_LINE_LINE_DISTANCE_PARALLEL, }; struct point { vec2 pos; }; struct circle { vec2 center; double radius; }; struct line { vec2 norm; double C; }; enum EType { ETYPE_VALUE, ETYPE_CIRCLE, ETYPE_POINT, ETYPE_LINE, }; struct element { enum EType type; union { double value; struct circle circle; struct point point; struct line line; }; }; struct command { enum operation op; uint8_t root; bool hidden; struct element *arg1; struct element *arg2; struct element *arg3; struct element result; struct command *next; }; struct drawing { struct command *root; struct command *tail; struct command *error; }; bool circle_line_intersect(struct circle circle, struct line line, uint8_t root, struct point *point) { double a = line.norm[0]; double b = line.norm[1]; double c = line.C + glm_vec2_dot(line.norm, circle.center); double rec = pow(a, 2) + pow(b, 2); double x0 = -a*c / rec; double y0 = -b*c / rec; double r2 = pow(circle.radius, 2); double test = r2 * rec; if(pow(c, 2.0) - test > DBL_EPSILON * 1e14) { return false; } else if(fabs(pow(c, 2) - test) < DBL_EPSILON * 1e14) { point->pos[0] = x0; point->pos[1] = y0; } else { double d = r2 - pow(c, 2)/rec; double mult = sqrt(d / rec); if(root == 0) { point->pos[0] = x0 + b * mult; point->pos[1] = y0 - a * mult; } else { point->pos[0] = x0 - b * mult; point->pos[1] = y0 + a * mult; } } glm_vec2_add(point->pos, circle.center, point->pos); return true; } void line_through_points(struct point p1, struct point p2, struct line* l) { l->norm[0] = p1.pos[1] - p1.pos[1]; l->norm[1] = p2.pos[0] - p1.pos[0]; l->C = p1.pos[1] * -l->norm[1] + p1.pos[0] * -l->norm[1]; } void line_line_intersect(struct line l1, struct line l2, struct point* p) { double a1 = l1.norm[0]; double b1 = l1.norm[1]; double c1 = l1.C; double a2 = l2.norm[0]; double b2 = l2.norm[1]; double c2 = l2.C; p->pos[0] = -(c1*b2 - c2*b1) / (a1*b2 - a2*b1); p->pos[1] = -(a1*c2 - a2*c1) / (a1*b2 - a2*b1); } void plot_point(struct point p) { printf("\n", p.pos[0], -p.pos[1]); } void plot_line_between(struct point p1, struct point p2) { printf("\n", p1.pos[0], -p1.pos[1], p2.pos[0], -p2.pos[1]); } void plot_text(struct point p, double angle, char* str) { printf("%s\n", p.pos[0], -p.pos[1], angle * (180.0/M_PI), str); } enum LineStyle { LSTYLE_NORMAL, LSTYLE_CONSTRUCTION, }; void plot_line_style(struct line l, enum LineStyle style) { char *style_str; switch(style) { case LSTYLE_NORMAL: style_str = "stroke=\"black\" stroke-width=\"0.2\""; break; case LSTYLE_CONSTRUCTION: style_str = "stroke=\"blue\" stroke-width=\"0.1\" stroke-dasharray=\"0.7,0.5\" stroke-opacity=\"0.3\""; break; } if(fabs(l.norm[0]) < fabs(l.norm[1])) { double minx = -50; double maxx = 50; double miny = -(l.norm[0] * minx + l.C) / l.norm[1]; double maxy = -(l.norm[0] * maxx + l.C) / l.norm[1]; printf("\n", style_str, minx, -miny, maxx, -maxy); } else { double miny = -50; double maxy = 50; double minx = -(l.norm[1] * miny + l.C) / l.norm[0]; double maxx = -(l.norm[1] * maxy + l.C) / l.norm[0]; printf("\n", style_str, minx, -miny, maxx, -maxy); } if(style == LSTYLE_NORMAL) { double d0 = glm_vec2_norm2(l.norm); vec2 p0 = {0, 0}; glm_vec2_mulsubs(l.norm, l.C, p0); glm_vec2_divs(p0, d0, p0); vec2 p1; glm_vec2_add(p0, l.norm, p1); // printf("%f %f\n", l.norm[0], l.norm[1]); printf("\n", p0[0], -p0[1], p1[0], -p1[1]); } } void plot_line(struct line l) { plot_line_style(l, LSTYLE_NORMAL); } void plot_arc_between(struct point c, struct point p1, struct point p2) { // @COML: There's something missing here about which side of the arc we // want. I think we can figure that out from the relation of the center and // the points vec2 t; glm_vec2_sub(c.pos, p1.pos, t); double r = glm_vec2_norm(t); printf("\n", p2.pos[0], -p2.pos[1], r, r, p1.pos[0], -p1.pos[1]); } void plot_circle(struct circle c) { printf("\n", c.center[0], -c.center[1], c.radius); } void plot_generic(struct element e) { switch(e.type) { case ETYPE_VALUE: break; case ETYPE_CIRCLE: plot_circle(e.circle); break; case ETYPE_POINT: plot_point(e.point); break; case ETYPE_LINE: plot_line(e.line); break; } } void plot_distance_indicator(struct point p1, struct point p2, double distance) { vec2 dir; glm_vec2_sub(p2.pos, p1.pos, dir); glm_vec2_normalize(dir); vec2 norm = {-dir[1], dir[0]}; struct point start; struct point end; { glm_vec2_add(p1.pos, norm, start.pos); glm_vec2_add(p2.pos, norm, end.pos); plot_line_between(start, end); } // The little wings to highlight the ends vec2 tip = {.3, .3}; glm_vec2_mul(norm, tip, tip); { struct point p1; struct point p2; glm_vec2_add(start.pos, tip, p1.pos); glm_vec2_sub(start.pos, tip, p2.pos); plot_line_between(p1, p2); } { struct point p1; struct point p2; glm_vec2_add(end.pos, tip, p1.pos); glm_vec2_sub(end.pos, tip, p2.pos); plot_line_between(p1, p2); } // The text { struct point p; glm_vec2_lerp(start.pos, end.pos, 0.5, p.pos); glm_vec2_muladds(norm, TEXT_OFFSET, p.pos); double angle = atan2(dir[1], dir[0]); // Flip upside down labels if(angle > M_PI/2) { glm_vec2_muladds(norm, 0.1, p.pos); angle -= M_PI; } if(angle < -M_PI/2) { glm_vec2_muladds(norm, 0.1, p.pos); angle += M_PI; } assert(angle >= -M_PI); assert(angle <= M_PI); char buf[512]; snprintf(buf, sizeof(buf), "%.1f u", distance); plot_text(p, angle, buf); } } void plot_angle(struct line l1, struct line l2, double theta) { struct point intersect; line_line_intersect(l1, l2, &intersect); struct circle c = { .radius = 1.3 }; glm_vec2_copy(intersect.pos, c.center); struct point p1; circle_line_intersect(c, l1, 0, &p1); struct point p2; circle_line_intersect(c, l2, 0, &p2); plot_arc_between(intersect, p2, p1); vec2 l1v; vec2 l2v; glm_vec2_normalize_to(l1.norm, l1v); glm_vec2_normalize_to(l2.norm, l2v); // Label glm_vec2_negate(l2v); vec2 x; glm_vec2_add(l1v, l2v, x); glm_vec2_normalize(x); glm_vec2_muladds(x, c.radius + TEXT_OFFSET, intersect.pos); double dot = x[0]; double det = x[1]; double angle = atan2(det, dot); char buf[512]; snprintf(buf, sizeof(buf), "%.1f°", theta); plot_text(intersect, angle - M_PI/2, buf); plot_line_style(l1, LSTYLE_CONSTRUCTION); plot_line_style(l2, LSTYLE_CONSTRUCTION); } struct element* insert_cmd(struct drawing *drawing, struct command cmd) { struct command *new = calloc(sizeof(struct command), 1); memcpy(new, &cmd, sizeof(struct command)); assert(new != NULL); if(drawing->tail != NULL) drawing->tail->next = new; else drawing->root = new; drawing->tail = new; return &new->result; } struct element *create_perp(struct drawing *cmds, struct element *l, struct element *p, bool hide) { static struct element radius = { .type = ETYPE_VALUE, .value = 5, // Just an arbitrary number }; struct element *c1 = insert_cmd(cmds, (struct command){ .op = CMD_CIRCLE_CENTER_RADIUS, .result.type = ETYPE_CIRCLE, .hidden = true, .arg1 = p, .arg2 = &radius, }); struct element *p1 = insert_cmd(cmds, (struct command){ .op = CMD_POINT_CIRCLE_LINE, .result.type = ETYPE_POINT, .hidden = true, .root = 0, .arg1 = c1, .arg2 = l, }); struct element *p2 = insert_cmd(cmds, (struct command){ .op = CMD_POINT_CIRCLE_LINE, .result.type = ETYPE_POINT, .hidden = true, .root = 1, .arg1 = c1, .arg2 = l, }); struct element *c2 = insert_cmd(cmds, (struct command){ .op = CMD_CIRCLE_CENTER_POINT, .result.type = ETYPE_CIRCLE, .hidden = true, .arg1 = p2, .arg2 = p1, }); struct element *c3 = insert_cmd(cmds, (struct command){ .op = CMD_CIRCLE_CENTER_POINT, .result.type = ETYPE_CIRCLE, .hidden = true, .arg1 = p1, .arg2 = p2, }); struct element *perp1 = insert_cmd(cmds, (struct command){ .op = CMD_POINT_CIRCLE_CIRCLE, .result.type = ETYPE_POINT, .hidden = true, .arg1 = c2, .arg2 = c3, }); struct element *perp2 = insert_cmd(cmds, (struct command){ .op = CMD_POINT_CIRCLE_CIRCLE, .result.type = ETYPE_POINT, .hidden = true, .root = 1, .arg1 = c2, .arg2 = c3, }); return insert_cmd(cmds, (struct command){ .op = CMD_LINE_POINT_POINT, .result.type = ETYPE_LINE, .hidden = hide, .arg1 = perp1, .arg2 = perp2, }); } void create_rounded_3line(struct drawing *next, struct element *r, struct element *p1, struct element *p2, struct element *p3, struct element **center, struct element **start, struct element **end) { { struct element *par1; struct element *par2; { struct element *l = insert_cmd(next, (struct command){ .op = CMD_LINE_POINT_POINT, .hidden = true, .result.type = ETYPE_LINE, .arg1 = p1, .arg2 = p2, }); struct element *perp = create_perp(next, l, p2, true); struct element *c = insert_cmd(next, (struct command){ .op = CMD_CIRCLE_CENTER_RADIUS, .hidden = true, .result.type = ETYPE_CIRCLE, .arg1 = p2, .arg2 = r, }); struct element *p = insert_cmd(next, (struct command){ .op = CMD_POINT_CIRCLE_LINE, .hidden = true, .result.type = ETYPE_POINT, .arg1 = c, .arg2 = perp, }); par1 = create_perp(next, perp, p, true); } { struct element *l = insert_cmd(next, (struct command){ .op = CMD_LINE_POINT_POINT, .hidden = true, .result.type = ETYPE_LINE, .arg1 = p2, .arg2 = p3, }); struct element *perp = create_perp(next, l, p2, true); struct element *c = insert_cmd(next, (struct command){ .op = CMD_CIRCLE_CENTER_RADIUS, .hidden = true, .result.type = ETYPE_CIRCLE, .arg1 = p2, .arg2 = r, }); struct element *p = insert_cmd(next, (struct command){ .op = CMD_POINT_CIRCLE_LINE, .hidden = true, .result.type = ETYPE_POINT, .arg1 = c, .arg2 = perp, }); par2 = create_perp(next, perp, p, true); } struct element *pc = insert_cmd(next, (struct command){ .op = CMD_POINT_LINE_LINE, .hidden = true, .result.type = ETYPE_POINT, .arg1 = par1, .arg2 = par2, }); *center = pc; struct element *c = insert_cmd(next, (struct command){ .op = CMD_CIRCLE_CENTER_RADIUS, .hidden = true, .result.type = ETYPE_CIRCLE, .arg1 = pc, .arg2 = r, }); { struct element *l = insert_cmd(next, (struct command){ .op = CMD_LINE_POINT_POINT, .hidden = true, .result.type = ETYPE_LINE, .arg1 = p1, .arg2 = p2, }); struct element *p = insert_cmd(next, (struct command){ .op = CMD_POINT_CIRCLE_LINE, .hidden = true, .result.type = ETYPE_POINT, .arg1 = c, .arg2 = l, }); *start = p; } { struct element *l = insert_cmd(next, (struct command){ .op = CMD_LINE_POINT_POINT, .hidden = true, .result.type = ETYPE_LINE, .arg1 = p2, .arg2 = p3, }); struct element *p = insert_cmd(next, (struct command){ .op = CMD_POINT_CIRCLE_LINE, .hidden = true, .result.type = ETYPE_POINT, .arg1 = c, .arg2 = l, }); *end = p; } } } void execute_drawing(struct drawing *drawing, double inputs[]) { size_t input_i = 0; for(struct command *current = drawing->root; current != NULL; current = current->next) { switch(current->op) { case CMD_VALUE_INPUT: { assert(current->result.type == ETYPE_VALUE); current->result.value = inputs[input_i++]; }break; case CMD_ORIGIN: { assert(current->result.type == ETYPE_POINT); glm_vec2_zero(current->result.point.pos); }break; case CMD_LINE_X: { assert(current->result.type == ETYPE_LINE); current->result.line.norm[0] = 0; current->result.line.norm[1] = 1; current->result.line.C = 0; }break; case CMD_CIRCLE_CENTER_RADIUS: { assert(current->result.type == ETYPE_CIRCLE); glm_vec2_copy(current->arg1->point.pos, current->result.circle.center); current->result.circle.radius = current->arg2->value; }break; case CMD_LINE_POINT_POINT: { assert(current->result.type == ETYPE_LINE); line_through_points(current->arg1->point, current->arg2->point, ¤t->result.line); }break; case CMD_LINE_POINT_LINE_ANGLE: { assert(current->arg1->type == ETYPE_POINT); assert(current->arg2->type == ETYPE_LINE); assert(current->arg3->type == ETYPE_VALUE); assert(current->result.type == ETYPE_LINE); // printf("Rotate %f\n", current->arg3->value); // printf("%f %f\n", current->arg2->line.norm[0], current->arg2->line.norm[1]); glm_vec2_rotate(current->arg2->line.norm, current->arg3->value, current->result.line.norm); // printf("%f %f\n", current->result.line.norm[0], current->result.line.norm[1]); vec2 offset = {-current->arg1->point.pos[0], -current->arg1->point.pos[1]}; current->result.line.C = glm_vec2_dot(current->result.line.norm, offset); }break; case CMD_LINE_LINE_DISTANCE_PARALLEL: { assert(current->arg1->type == ETYPE_LINE); assert(current->arg2->type == ETYPE_VALUE); assert(current->result.type == ETYPE_LINE); glm_vec2_copy(current->arg1->line.norm, current->result.line.norm); double mag = glm_vec2_norm(current->result.line.norm); if(current->root == 1) mag = -mag; // printf("Magnitude is %f %f\n", mag, current->arg2->value); current->result.line.C = current->arg1->line.C - mag * current->arg2->value; }break; case CMD_LINE_CIRCLE_CIRCLE_TANGENT: { assert(current->arg1->type == ETYPE_CIRCLE); assert(current->arg2->type == ETYPE_CIRCLE); assert(current->result.type == ETYPE_LINE); if(current->arg1->circle.radius == 0 && current->arg2->circle.radius == 0) { // The tangent is just a line through the two centers // @FAST: This is wasteful. If the the procedure too the // two vectors directly, we wouldn't have to copy here. struct point p1; glm_vec2_copy(current->arg1->circle.center, p1.pos); struct point p2; glm_vec2_copy(current->arg2->circle.center, p2.pos); // printf("%f %f\n", current->arg1->circle.center[0], current->arg1->circle.center[1]); // printf("%f %f\n", current->arg2->circle.center[0], current->arg2->circle.center[1]); line_through_points(p1, p2, ¤t->result.line); } else if (fabs(current->arg1->circle.radius - current->arg2->circle.radius) < DBL_EPSILON * 1e14) { // The tangent is parallel to the line through the two // centers abort(); } else { // We should probably implement tangents for circles that // don't happen to be 0 radius abort(); } }break; case CMD_POINT_CIRCLE_LINE: { assert(current->arg1->type == ETYPE_CIRCLE); assert(current->arg2->type == ETYPE_LINE); assert(current->result.type == ETYPE_POINT); struct line translated; glm_vec2_copy(current->arg2->line.norm, translated.norm); translated.C = translated.C - glm_vec2_dot(translated.norm, current->arg1->circle.center); circle_line_intersect(current->arg1->circle, current->arg2->line, current->root, ¤t->result.point); }break; case CMD_POINT_CIRCLE_CIRCLE: { assert(current->result.type == ETYPE_POINT); vec2 between_centers; glm_vec2_sub(current->arg1->circle.center, current->arg2->circle.center, between_centers); glm_vec2_mul(between_centers, (vec2){2, 2}, between_centers); double a = between_centers[0]; double b = between_centers[1]; double c = (pow(current->arg2->circle.center[0], 2) - pow(current->arg1->circle.center[0], 2)) + \ (pow(current->arg2->circle.center[1], 2) - pow(current->arg1->circle.center[1], 2)) - \ (pow(current->arg2->circle.radius, 2) - pow(current->arg1->circle.radius, 2)); struct line radical_axis = { {a, b}, c }; if(!circle_line_intersect(current->arg1->circle, radical_axis, current->root, ¤t->result.point)) { drawing->error = current; return; } }break; case CMD_POINT_LINE_LINE: { assert(current->result.type == ETYPE_POINT); line_line_intersect(current->arg1->line, current->arg2->line, ¤t->result.point); }break; case CMD_CIRCLE_CENTER_POINT: { assert(current->result.type == ETYPE_CIRCLE); glm_vec2_copy(current->arg1->point.pos, current->result.circle.center); vec2 imm; glm_vec2_sub(current->arg1->point.pos, current->arg2->point.pos, imm); current->result.circle.radius = glm_vec2_norm(imm); }break; } // printf("%fx + %fy + %f = 0\n", cmd[2].line.norm[0], cmd[2].line.norm[1], cmd[2].line.C); } } void create_drawing(struct drawing* drawing, struct element **line_start, struct element **line_bend_start, struct element **line_ctr, struct element **line_bend_end, struct element **line_end) { *line_start = insert_cmd(drawing, (struct command){ .op = CMD_ORIGIN, .hidden = true, .result.type = ETYPE_POINT, }); struct element *element_spacing = insert_cmd(drawing, (struct command){ .op = CMD_VALUE_INPUT, .result.type = ETYPE_VALUE, }); struct element *line_corner; { struct element *xaxis = insert_cmd(drawing, (struct command){ .op = CMD_LINE_X, .hidden = true, .result.type = ETYPE_LINE, }); struct element *root_angle = insert_cmd(drawing, (struct command){ .op = CMD_VALUE_INPUT, .result.type = ETYPE_VALUE, }); struct element *l = insert_cmd(drawing, (struct command){ .op = CMD_LINE_POINT_LINE_ANGLE, .hidden = true, .result.type = ETYPE_LINE, .arg1 = *line_start, .arg2 = xaxis, .arg3 = root_angle, }); struct element *c = insert_cmd(drawing, (struct command){ .op = CMD_CIRCLE_CENTER_RADIUS, .hidden = true, .result.type = ETYPE_CIRCLE, .arg1 = *line_start, .arg2 = element_spacing, }); struct element *p = insert_cmd(drawing, (struct command){ .op = CMD_POINT_CIRCLE_LINE, .hidden = true, .result.type = ETYPE_POINT, .arg1 = c, .arg2 = l, }); line_corner = p; } { struct element *li = insert_cmd(drawing, (struct command){ .op = CMD_LINE_POINT_POINT, .hidden = true, .result.type = ETYPE_LINE, .arg1 = *line_start, .arg2 = line_corner, }); struct element *bend_angle = insert_cmd(drawing, (struct command){ .op = CMD_VALUE_INPUT, .hidden = true, .result.type = ETYPE_VALUE, }); struct element *l = insert_cmd(drawing, (struct command){ .op = CMD_LINE_POINT_LINE_ANGLE, .hidden = true, .result.type = ETYPE_LINE, .arg1 = line_corner, .arg2 = li, .arg3 = bend_angle, }); struct element *c = insert_cmd(drawing, (struct command){ .op = CMD_CIRCLE_CENTER_RADIUS, .hidden = true, .result.type = ETYPE_CIRCLE, .arg1 = line_corner, .arg2 = element_spacing, }); struct element *p = insert_cmd(drawing, (struct command){ .op = CMD_POINT_CIRCLE_LINE, .hidden = true, .result.type = ETYPE_POINT, .arg1 = c, .arg2 = l, }); *line_end = p; } struct element *round_rad = insert_cmd(drawing, (struct command){ .op = CMD_VALUE_INPUT, .hidden = true, .result.type = ETYPE_VALUE, }); create_rounded_3line(drawing, round_rad, *line_start, line_corner, *line_end, line_ctr, line_bend_start, line_bend_end); } enum component_type { COM_POINT, COM_LINE, }; struct component { enum component_type type; struct element *e; }; enum constraint_type { CT_POINT_POINT_DISTANCE, CT_POINT_LINE_DISTANCE, CT_LINE_LINE_ANGLE, }; 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", }; #define SEARCH_DEPTH 16 struct path_step { uint64_t i; bool direction; }; struct constraint { enum constraint_type type; double v; struct component *c1; struct component *c2; uint64_t order; struct path_step path[SEARCH_DEPTH]; bool forward; bool used; }; struct frontier { struct component *elems[32]; size_t n; }; 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; } void add_frontier(struct frontier *frontier, struct component *component) { assert(!frontier_scan(frontier, component)); frontier->elems[frontier->n++] = component; } void build_angle_point_line(struct drawing *drawing, struct component *local_i, struct component *local_j, struct component *oppo_i) { 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, }); struct element* l = insert_cmd(drawing, (struct command){ .op = CMD_LINE_POINT_LINE_ANGLE, .hidden = true, .result.type = ETYPE_LINE, .arg1 = local_j->e, .arg2 = local_i->e, .arg3 = theta, }); oppo_i->e = insert_cmd(drawing, (struct command){ .op = CMD_LINE_LINE_DISTANCE_PARALLEL, .hidden = true, .result.type = ETYPE_LINE, .arg1 = l, .arg2 = d, }); } struct smooth_line { struct component l1; struct component l2; struct component corner; struct component corner_center; struct component end; struct component start; struct component perp1; struct component perp2; struct component corner_start; struct component corner_end; }; struct box { struct component corner[4]; struct component side[4]; }; struct angle_search_frame { size_t constraint_i; struct component *head; bool dir; }; 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) { // printf("Found path %p %p: ", first_component, needle); for(struct angle_search_frame *i = frames; i <= frame; i++) { path[i - frames].i = i->constraint_i; path[i - frames].direction = i->dir; // printf("%ld [%d] [%p] -> ", i->constraint_i, i->dir, i->head); } // printf("\n"); 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; } int main(int argc, char *argv[]) { // struct element *line_start; // struct element *line_bend_start; // struct element *line_ctr; // struct element *line_bend_end; // struct element *line_end; // struct drawing drawing = {}; // create_drawing(&drawing, &line_start, &line_bend_start, &line_ctr, &line_bend_end, &line_end); // execute_drawing(&drawing, (double[]){8, M_PI * 0.5, M_PI * 0.4, .3}); // Figure 4 struct component components[] = { {.type = COM_POINT}, {.type = COM_POINT}, {.type = COM_POINT}, {.type = COM_LINE}, {.type = COM_LINE}, {.type = COM_POINT}, }; struct smooth_line line = { .l1 = {.type = COM_LINE}, .l2 = {.type = COM_LINE}, .corner = {.type = COM_POINT}, .corner_center = {.type = COM_POINT}, .end = {.type = COM_POINT}, .start = {.type = COM_POINT}, .perp1 = {.type = COM_LINE}, .perp2 = {.type = COM_LINE}, .corner_start = {.type = COM_POINT}, .corner_end = {.type = COM_POINT}, }; struct box box = { .corner = { {.type = COM_POINT}, {.type = COM_POINT}, {.type = COM_POINT}, {.type = COM_POINT}, }, .side = { {.type = COM_LINE}, {.type = COM_LINE}, {.type = COM_LINE}, {.type = COM_LINE}, }, }; struct constraint constraints[] = { { .type = CT_POINT_POINT_DISTANCE, .v = 13, .c1 = &components[0], .c2 = &components[1], }, { .type = CT_POINT_POINT_DISTANCE, .v = 10, .c1 = &components[1], .c2 = &components[2], }, { .type = CT_POINT_POINT_DISTANCE, .v = 10, .c1 = &components[2], .c2 = &components[0], }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &components[0], .c2 = &components[3], }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &components[1], .c2 = &components[3], }, { .type = CT_LINE_LINE_ANGLE, .v = M_PI/1.7, .c1 = &components[3], .c2 = &components[4], }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &components[4], .c2 = &components[1], }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &components[4], .c2 = &components[5], }, { .type = CT_POINT_POINT_DISTANCE, .v = 12.8, .c1 = &components[0], .c2 = &components[5], }, { .type = CT_LINE_LINE_ANGLE, .v = M_PI/2, .c1 = &components[3], .c2 = &line.l1, }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &components[5], .c2 = &line.l1, }, { .type = CT_LINE_LINE_ANGLE, .v = M_PI/2, .c1 = &line.l2, .c2 = &line.l1, }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &line.corner, .c2 = &line.l2, }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &line.corner, .c2 = &line.l1, }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &line.end, .c2 = &line.l2, }, { .type = CT_POINT_LINE_DISTANCE, .v = 10, .c1 = &line.end, .c2 = &line.l1, }, { .type = CT_POINT_LINE_DISTANCE, .v = 12, .c1 = &line.end, .c2 = &components[3], }, { .type = CT_POINT_LINE_DISTANCE, .v = 1, .c1 = &line.corner_center, .c2 = &line.l1, }, { .type = CT_POINT_LINE_DISTANCE, .v = -1, .c1 = &line.corner_center, .c2 = &line.l2, }, { .type = CT_LINE_LINE_ANGLE, .v = M_PI/2, .c1 = &line.l1, .c2 = &line.perp1, }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &line.corner_center, .c2 = &line.perp1, }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &line.corner_start, .c2 = &line.perp1, }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &line.corner_start, .c2 = &line.l1, }, { .type = CT_LINE_LINE_ANGLE, .v = M_PI/2, .c1 = &line.l2, .c2 = &line.perp2, }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &line.corner_center, .c2 = &line.perp2, }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &line.corner_end, .c2 = &line.perp2, }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &line.corner_end, .c2 = &line.l2, }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &box.corner[0], .c2 = &box.side[0], }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &box.corner[1], .c2 = &box.side[0], }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &box.corner[1], .c2 = &box.side[1], }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &box.corner[2], .c2 = &box.side[1], }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &box.corner[2], .c2 = &box.side[2], }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &box.corner[3], .c2 = &box.side[2], }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &box.corner[3], .c2 = &box.side[3], }, { .type = CT_POINT_LINE_DISTANCE, .v = 0, .c1 = &box.corner[0], .c2 = &box.side[3], }, { .type = CT_LINE_LINE_ANGLE, .v = M_PI/2, .c1 = &box.side[3], .c2 = &box.side[0], }, { .type = CT_LINE_LINE_ANGLE, .v = M_PI/2, .c1 = &box.side[1], .c2 = &box.side[2], }, { .type = CT_LINE_LINE_ANGLE, .v = M_PI/2, .c1 = &box.side[2], .c2 = &box.side[3], }, { .type = CT_LINE_LINE_ANGLE, .v = M_PI*1/2, .c1 = &components[3], .c2 = &box.side[1], }, { .type = CT_POINT_POINT_DISTANCE, .v = 10, .c1 = &line.corner_start, .c2 = &box.corner[0], }, { .type = CT_POINT_POINT_DISTANCE, .v = 10, .c1 = &line.corner_end, .c2 = &box.corner[0], }, { .type = CT_POINT_POINT_DISTANCE, .v = 20, .c1 = &box.corner[0], .c2 = &box.corner[1], }, { .type = CT_POINT_POINT_DISTANCE, .v = 10, .c1 = &box.corner[1], .c2 = &box.corner[2], }, }; struct frontier frontier = {}; struct drawing drawing = {}; uint64_t order = 1; for(size_t i = 0; i < sizeof(constraints)/sizeof(constraints[0]); i++) { constraints[i].path[0].i = -1; constraints[i].forward = true; } // Step 1 Pick some point point distance constraint as the base for(size_t i = 0; i < sizeof(constraints)/sizeof(constraints[0]); i++) { assert(!constraints[i].used); if(constraints[i].type != CT_POINT_POINT_DISTANCE) continue; constraints[i].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[i].c1->e, .arg2 = distance, }); constraints[i].c2->e = insert_cmd(&drawing, (struct command){ .op = CMD_POINT_CIRCLE_LINE, .hidden = true, .result.type = ETYPE_POINT, .arg1 = c, .arg2 = xaxis, }); constraints[i].used = true; constraints[i].order = order++; add_frontier(&frontier, constraints[i].c1); add_frontier(&frontier, constraints[i].c2); break; } // Step 2 we iteratively expand the frontier from the selected base while(true) { for(size_t i = 0; i < sizeof(constraints)/sizeof(constraints[0]); i++) { if(constraints[i].used) continue; struct component *oppo_i; struct component *local_i; if(frontier_scan(&frontier, constraints[i].c1)) { oppo_i = constraints[i].c2; local_i = constraints[i].c1; } else if(frontier_scan(&frontier, constraints[i].c2)) { oppo_i = constraints[i].c1; local_i = constraints[i].c2; } else continue; for(size_t j = i+1; j < sizeof(constraints)/sizeof(constraints[0]); j++) { if(constraints[j].used) continue; struct component *oppo_j; struct component *local_j; if(frontier_scan(&frontier, constraints[j].c1)) { oppo_j = constraints[j].c2; local_j = constraints[j].c1; } else if(frontier_scan(&frontier, constraints[j].c2)) { oppo_j = constraints[j].c1; local_j = constraints[j].c2; } 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, sizeof(constraints)/sizeof(constraints[0]), 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, sizeof(constraints)/sizeof(constraints[0]), oppo_j, oppo_i, constraints[j].path)) continue; oppo_j = oppo_i; } else continue; } // printf("Detected %ld %ld\n", i, j); if(constraints[i].type == CT_POINT_POINT_DISTANCE && local_i->type == COM_POINT && constraints[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 = true, .result.type = ETYPE_CIRCLE, .arg1 = local_i->e, .arg2 = d1, }); struct element *c2 = insert_cmd(&drawing, (struct command){ .op = CMD_CIRCLE_CENTER_RADIUS, .hidden = true, .result.type = ETYPE_CIRCLE, .arg1 = local_j->e, .arg2 = d2, }); oppo_i->e = insert_cmd(&drawing, (struct command){ .op = CMD_POINT_CIRCLE_CIRCLE, .hidden = true, .result.type = ETYPE_POINT, .arg1 = c1, .arg2 = c2, }); } else if(constraints[i].type == CT_POINT_LINE_DISTANCE && local_i->type == COM_POINT && constraints[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 = true, .result.type = ETYPE_CIRCLE, .arg1 = local_i->e, .arg2 = d1, }); struct element *c2 = insert_cmd(&drawing, (struct command){ .op = CMD_CIRCLE_CENTER_RADIUS, .hidden = true, .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 = true, .result.type = ETYPE_LINE, .arg1 = c1, .arg2 = c2, }); } else if(constraints[i].type == CT_POINT_LINE_DISTANCE && local_i->type == COM_LINE && constraints[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 = true, .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 = true, .result.type = ETYPE_LINE, .arg1 = local_j->e, .arg2 = d2, }); oppo_i->e = insert_cmd(&drawing, (struct command){ .op = CMD_POINT_LINE_LINE, .hidden = true, .result.type = ETYPE_POINT, .arg1 = l1, .arg2 = l2, }); } else if(constraints[i].type == CT_LINE_LINE_ANGLE && local_i->type == COM_LINE && constraints[j].type == CT_POINT_LINE_DISTANCE && local_j->type == COM_POINT) { assert(oppo_i->type == COM_LINE); constraints[i].forward = constraints[i].c1 == local_i; build_angle_point_line(&drawing, local_i, local_j, oppo_i); } else if(constraints[i].type == CT_POINT_LINE_DISTANCE && local_i->type == COM_POINT && constraints[j].type == CT_LINE_LINE_ANGLE && local_j->type == COM_LINE) { assert(oppo_i->type == COM_LINE); constraints[j].forward = constraints[j].c1 == local_j; // @HACK Swap the two constraints to reuse the construction // steps. This sucks, and we need to figure out some better // way of doing it. struct component* tmp = local_i; local_i = local_j; local_j = tmp; i ^= j; j = j ^ i; i ^= j; build_angle_point_line(&drawing, local_i, local_j, oppo_i); } else if(constraints[i].type == CT_POINT_LINE_DISTANCE && local_i->type == COM_LINE && constraints[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 = true, .result.type = ETYPE_LINE, .arg1 = local_i->e, .arg2 = d1, }); struct element *c = insert_cmd(&drawing, (struct command){ .op = CMD_CIRCLE_CENTER_RADIUS, .hidden = true, .result.type = ETYPE_CIRCLE, .arg1 = local_j->e, .arg2 = d2, }); oppo_i->e = insert_cmd(&drawing, (struct command){ .op = CMD_POINT_CIRCLE_LINE, .hidden = true, .result.type = ETYPE_POINT, .arg1 = c, .arg2 = l, }); } else { printf("Unknown constraint combination %s and %s\n", constraint_type_name[constraints[i].type], constraint_type_name[constraints[j].type]); abort(); } add_frontier(&frontier, oppo_i); constraints[i].used = true; constraints[i].order = order++; constraints[j].used = true; constraints[j].order = order++; goto candidate_found; } } // No candidate found break; candidate_found: ; } double *params = malloc(sizeof(double) * (sizeof(constraints)/sizeof(constraints[0]))); for(size_t i = 0; i < sizeof(constraints)/sizeof(constraints[0]); i++) { if(constraints[i].order == 0) continue; params[constraints[i].order-1] = SETSIGN(constraints[i].forward, constraints[i].v); // We need to offset angles based on the path we took to use this // constraint if(constraints[i].path[0].i != -1) { // printf("PATH %ld\n", i); for(struct path_step *p = constraints[i].path; p <= constraints[i].path+SEARCH_DEPTH && p->i != -1; p++) { params[constraints[i].order-1] += SETSIGN(p->direction, constraints[p->i].v); // printf("%ld [%d:%f] [%f] -> ", p->i, p->direction, constraints[p->i].v, params[constraints[i].order-1]); } // printf("\n"); params[constraints[i].order-1] -= (M_PI*2.0) * floor(params[constraints[i].order-1] / (M_PI*2.0)); // printf("Final Angle is %f\n", params[constraints[i].order-1]); } } execute_drawing(&drawing, params); printf("\n"); }