/* * ---------------------------------------------------------------------------- * "THE BEER-WARE LICENSE" (Revision 42): * wrote this file. As long as you retain this notice you * can do whatever you want with this stuff. If we meet some day, and you think * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp * ---------------------------------------------------------------------------- * $Id: plt2g.c,v 1.29 2009/06/03 19:04:42 phk Exp $ * */ /* * Ideas: * * Treat closed curves specially: we enter and exit the same place, so * for the global optimization we can treat them as points with a choice * of coordinates from the possible set. * * Treat segments as such, with a start and an end point. Need to detect * intersections and resolve in multiple segments. */ #include #include #include #include #include #include #include #include #include #include #include "plt2g.h" /**********************************************************************/ static double pen_width[] = { [1] = 0.80 * 1000, [2] = 0.80 * 1000, [3] = 0.20 * 1000, [4] = 0.80 * 1000, [5] = 0.80 * 1000, [6] = 2.00 * 1000, }; static FILE *gs; static int npages; static int opt_p = -1; int bit_width = 250; static int lift_cost = 2500; /********************************************************************** * The easy part: Read and parse the HPGL */ static struct run * find_run(struct job *j) { struct run *r; if (j->last_run != NULL && j->last_run->pen == j->pen) return (j->last_run); TAILQ_FOREACH(r, &j->runs, list) { if (r->pen == j->pen) { j->last_run = r; return (r); } } r = calloc(sizeof *r, 1); assert(r != NULL); TAILQ_INIT(&r->vectors); r->job = j; // fprintf(stderr, "New Run, pen %d\n", j->pen); r->pen = j->pen; TAILQ_INSERT_HEAD(&j->runs, r, list); j->last_run = r; return (r); } static void vector(struct job *j, int x, int y) { struct run *r; struct vector *v; r = find_run(j); if (j->down == 1 && j->vx == x && j->vy == y) { // fprintf(stderr, "NULL move (%d %d %d)\n", j->pen, x, y); return; } if (j->down) { v = calloc(sizeof *v, 1); assert(v != NULL); v->x0 = j->vx; v->y0 = j->vy; v->x1 = x; v->y1 = y; TAILQ_INSERT_TAIL(&r->vectors, v, list); r->nvect++; j->down = 1; if (v->x0 < j->x0) j->x0 = v->x0; if (v->x1 < j->x0) j->x0 = v->x1; if (v->x0 > j->x1) j->x1 = v->x0; if (v->x1 > j->x1) j->x1 = v->x1; if (v->y0 < j->y0) j->y0 = v->y0; if (v->y1 < j->y0) j->y0 = v->y1; if (v->y0 > j->y1) j->y1 = v->y0; if (v->y1 > j->y1) j->y1 = v->y1; } j->vx = x; j->vy = y; } static int i32(char **p) { int i; // printf("i32>>%s", *p); i = strtol(*p, p, 0); if (**p == ',') (*p)++; // printf("i32==%d %s", i, *p); return (i); } static void parse_plt(struct job *j, char *p) { int cmd, x, y; while (*p != '\0') { if (isspace(*p)) { p++; continue; } // printf("%s", p); assert(isalpha(p[0])); assert(isalpha(p[1])); cmd = (tolower(p[0]) << 8) | tolower(p[1]); p+=2; switch (cmd) { case ('i' << 8 | 'n'): break; case ('i' << 8 | 'p'): i32(&p); i32(&p); i32(&p); i32(&p); break; case ('p' << 8 | 'a'): x = i32(&p); y = i32(&p); vector(j, x * 25, y * 25); break; case ('p' << 8 | 'd'): j->down = 2; break; case ('p' << 8 | 'u'): j->down = 0; break; case ('s' << 8 | 'c'): i32(&p); i32(&p); i32(&p); i32(&p); break; case ('s' << 8 | 'p'): j->pen = i32(&p); break; default: exit (1); } while (isspace(*p)) p++; if (*p == ';') p++; } } /**********************************************************************/ static void parse_nc(struct job *j, char *p) { (void)p; static double x, y; int i, g; pen_width[0] = bit_width; if (*p != 'G' || p[1] != '0') return; if (!memcmp(p, "G00 Z", 5)) { j->down = 0; return; } if (!memcmp(p, "G01 Z", 5)) { j->down = 1; return; } if (p[4] != 'X') { fprintf(stderr, ">>> %s", p); } else { i = sscanf(p, "G%d X%lf Y%lf", &g, &x, &y); if (i == 3 && (g == 0 || g == 1)) vector(j, x * 1000, y * 1000); else fprintf(stderr, "i%d g%d x%g y%g\n", i, g, x, y); } } /**********************************************************************/ static void open_gs(void) { gs = popen("tee _ | gs > /dev/null 2>&1", "w"); assert(gs != NULL); setbuf(gs, NULL); fprintf(gs, "%%!PS-Adobe-3.0\n"); fprintf(gs, "%%%%Pages: (atend)\n"); fprintf(gs, "%%%%BoundingBox: 0 0 600 500\n"); fprintf(gs, "%%%%EndComments\n"); fprintf(gs, "%%%%BeginProlog\n"); fprintf(gs, "/init {\n"); fprintf(gs, "gsave\n"); fprintf(gs, "100 100 translate\n"); fprintf(gs, "1 25.4 1e3 mul 72 div div dup scale\n"); fprintf(gs, "6 6 scale\n"); fprintf(gs, "} def\n"); fprintf(gs, "/finis {\n"); fprintf(gs, "grestore\n"); fprintf(gs, "} def\n"); fprintf(gs, "%%%%EndProlog\n"); sleep (3); } static void close_gs(void) { fprintf(gs, "%%%%Trailer\n"); fprintf(gs, "%%%%Pages: %d\n", npages); fprintf(gs, "%%%%EOF\n"); fclose(gs); } /**********************************************************************/ static void flip(struct vector *v) { int i; i = v->x0; v->x0 = v->x1; v->x1 = i; i = v->y0; v->y0 = v->y1; v->y1 = i; } static void flip_seg(struct segment *s) { struct vhead vh; struct vector *v; int i; i = s->x0; s->x0 = s->x1; s->x1 = i; i = s->y0; s->y0 = s->y1; s->y1 = i; TAILQ_INIT(&vh); while (!TAILQ_EMPTY(&s->vectors)) { v = TAILQ_FIRST(&s->vectors); TAILQ_REMOVE(&s->vectors, v, list); flip(v); TAILQ_INSERT_TAIL(&vh, v, list); } while (!TAILQ_EMPTY(&vh)) { v = TAILQ_FIRST(&vh); TAILQ_REMOVE(&vh, v, list); TAILQ_INSERT_HEAD(&s->vectors, v, list); } } static struct segment * new_seg(void) { struct segment *s; s = calloc(sizeof *s, 1); assert(s != NULL); TAILQ_INIT(&s->vectors); return (s); } static void rotate_loop(struct segment *s, struct vector *vb) { struct vector *v; while (1) { v = TAILQ_FIRST(&s->vectors); if (v == vb) break; TAILQ_REMOVE(&s->vectors, v, list); TAILQ_INSERT_TAIL(&s->vectors, v, list); } s->x0 = s->x1 = v->x0; s->y0 = s->y1 = v->y0; } /********************************************************************** * Sort segments in nearest successor order */ static void sort_seg(struct run *r) { struct segment *s; struct vector *v, *vb; double d, dmin; int lx, ly, rev; int n, m, nb; lx = HOME_X; ly = HOME_Y; memcpy(r->worklist, r->seglist, r->listlen); /* Skip first and last segments, they are homing segments */ for (m = 1; m < r->nseg - 1; m++) { dmin = 9e99; nb = m; vb = NULL; rev = 0; for (n = m; n < r->nseg - 1; n++) { s = r->worklist[n]; if (s->loop) { TAILQ_FOREACH(v, &s->vectors, list) { d = hypot(lx - v->x0, ly - v->y0); if (d < dmin) { vb = v; nb = n; dmin = d; } } } else { d = hypot(lx - s->x0, ly - s->y0); if (d < dmin) { nb = n; rev = 0; dmin = d; } d = hypot(lx - s->x1, ly - s->y1); if (d < dmin) { nb = n; rev = 1; dmin = d; } } } if (nb != m) { s = r->worklist[nb]; r->worklist[nb] = r->worklist[m]; r->worklist[m] = s; } s = r->worklist[m]; if (rev) flip_seg(s); if (s->loop && vb != NULL) rotate_loop(s, vb); lx = s->x1; ly = s->y1; } memcpy(r->seglist, r->worklist, r->listlen); } /********************************************************************** * Split list of lines into segments and loops. */ static struct vector * find_next_vect(struct vhead *vh, struct vector *v) { struct vector *v0, *vb; int n = 0; TAILQ_FOREACH(v0, vh, list) { if (v0->x0 == v->x1 && v0->y0 == v->y1) { vb = v0; n++; } else if (v0->x1 == v->x1 && v0->y1 == v->y1) { flip(v0); vb = v0; n++; } } if (n == 1) return (vb); if (n) fprintf(stderr, "N%d (%d,%d)\n", n, vb->x0, vb->y0); return (NULL); } static struct vector * find_prev_vect(struct vhead *vh, struct vector *v) { struct vector *v0, *vb; int n = 0; TAILQ_FOREACH(v0, vh, list) { if (v0->x1 == v->x0 && v0->y1 == v->y0) { vb = v0; n++; } else if (v0->x0 == v->x0 && v0->y0 == v->y0) { flip(v0); vb = v0; n++; } } if (n == 1) return (vb); if (n) fprintf(stderr, "P%d (%d,%d)\n", n, vb->x1, vb->y1); return (NULL); } static struct segment * home_vect(void) { struct segment *s; struct vector *v; s = new_seg(); s->x0 = s->x1 = HOME_X; s->y0 = s->y1 = HOME_Y; v = calloc(sizeof *v, 1); assert(v != NULL); v->x0 = HOME_X; v->y0 = HOME_Y; v->x1 = HOME_X; v->y1 = HOME_Y; TAILQ_INSERT_TAIL(&s->vectors, v, list); return (s); } static void segment(struct run *r) { struct segment *s; struct vector *v, *vn; int nloop = 0; int n; TAILQ_HEAD(,segment) segments; TAILQ_INIT(&segments); assert(r->nseg == 0); s = home_vect(); TAILQ_INSERT_TAIL(&segments, s, list); r->nseg++; while(!TAILQ_EMPTY(&r->vectors)) { // fprintf(stderr, "\n"); s = new_seg(); TAILQ_INSERT_TAIL(&segments, s, list); r->nseg++; v = TAILQ_FIRST(&r->vectors); TAILQ_REMOVE(&r->vectors, v, list); TAILQ_INSERT_TAIL(&s->vectors, v, list); while (1) { vn = find_prev_vect(&r->vectors, v); if (vn == NULL) break; // fprintf(stderr, "P (%d,%d) - (%d,%d) -> (%d,%d) - (%d,%d)\n", // vn->x0, vn->y0, vn->x1, vn->y1, // v->x0, v->y0, v->x1, v->y1); v = vn; TAILQ_REMOVE(&r->vectors, v, list); TAILQ_INSERT_HEAD(&s->vectors, v, list); } v = TAILQ_LAST(&s->vectors, vhead); while (1) { vn = find_next_vect(&r->vectors, v); if (vn == NULL) break; // fprintf(stderr, "N (%d,%d) - (%d,%d) -> (%d,%d) - (%d,%d)\n", // v->x0, v->y0, v->x1, v->y1, // vn->x0, vn->y0, vn->x1, vn->y1); v = vn; TAILQ_REMOVE(&r->vectors, v, list); TAILQ_INSERT_TAIL(&s->vectors, v, list); } v = TAILQ_FIRST(&s->vectors); s->x0 = v->x0; s->y0 = v->y0; vn = TAILQ_LAST(&s->vectors, vhead); s->x1 = vn->x1; s->y1 = vn->y1; if (v != vn && s->x0 == s->x1 && s->y0 == s->y1) { s->loop = 1; nloop++; } } s = home_vect(); TAILQ_INSERT_TAIL(&segments, s, list); r->nseg++; r->listlen = sizeof s * r->nseg; r->seglist = calloc(r->listlen, 1); r->worklist = calloc(r->listlen, 1); assert(r->seglist != NULL); n = 0; TAILQ_FOREACH(s, &segments, list) r->seglist[n++] = s; assert(n == r->nseg); fprintf(stderr, "\tFound %d segments, %d loops\n", r->nseg, nloop); } /**********************************************************************/ static void draw_vectors(struct vhead *vh, int *lx, int *ly, double *du, double *dd, int loop, int down) { double d; struct vector *v; int x = 0; TAILQ_FOREACH(v, vh, list) { // fprintf(stderr, "(%d,%d) -> (%d,%d)\n", v->x0, v->y0, v->x1, v->y1); if (v->x0 != *lx || v->y0 != *ly) { d = hypot(*lx - v->x0, *ly - v->y0); if (d > bit_width) d += lift_cost; if (down) { if (x) fprintf(gs, "stroke\n"); x = 0; if (d > bit_width) fprintf(gs, "1 0 0 setrgbcolor\n"); else fprintf(gs, "0 0 1 setrgbcolor\n"); fprintf(gs, "%d %d moveto\n", *lx, *ly); fprintf(gs, "%d %d lineto stroke\n", v->x0, v->y0); } *du += d; *lx = v->x0; *ly = v->y0; } if (down) { if (x == 0) { if (loop) fprintf(gs, "0 1 0 setrgbcolor\n"); else fprintf(gs, "0 0 0 setrgbcolor\n"); fprintf(gs, "%d %d moveto\n", *lx, *ly); x++; } fprintf(gs, "%d %d lineto\n", v->x1, v->y1); } *dd += hypot(*lx - v->x1, *ly - v->y1); *lx = v->x1; *ly = v->y1; } if (down) { if (x) fprintf(gs, "stroke\n"); } } /**********************************************************************/ static void draw_seg(struct segment *s, int *lx, int *ly, double *du, double *dd, int down) { struct vector *v; v = TAILQ_FIRST(&s->vectors); if (v != NULL) { assert(s->x0 == v->x0); assert(s->y0 == v->y0); } v = TAILQ_LAST(&s->vectors, vhead); if (v != NULL) { assert(s->x1 == v->x1); assert(s->y1 == v->y1); } draw_vectors(&s->vectors, lx, ly, du, dd, s->loop, down); } /**********************************************************************/ static void stat_run(struct run *r, int down) { int lx, ly; int i; double d; double du; double dd; lx = HOME_X; ly = HOME_Y; du = 0; dd = 0; if (down) { fprintf(gs, "%%%%Page: %d\n", ++npages); fprintf(gs, "init\n"); } if (r->seglist) { for (i = 0; i < r->nseg; i++) draw_seg(r->seglist[i], &lx, &ly, &du, &dd, down); } else { draw_vectors(&r->vectors, &lx, &ly, &du, &dd, 0, down); if (HOME_X != lx || HOME_Y != ly) { if (down) { fprintf(gs, "1 0 0 setrgbcolor\n"); fprintf(gs, "%d %d moveto\n", lx, ly); fprintf(gs, "%d %d lineto stroke\n", HOME_X, HOME_Y); } d = hypot(lx - HOME_X, ly - HOME_Y); if (d > bit_width) d += lift_cost; du += d; lx = HOME_X; ly = HOME_Y; usleep(1000); } r->dist_0 = du; } assert(lx == HOME_X); assert(ly == HOME_Y); fprintf(stderr, "File: %s Pen %2d Up: %9.2f Down: %7.0f Ratio %7.4f\n", r->job->fn, r->pen, du, dd, du / (du + dd)); if (down) { fprintf(gs, "finis\n"); fprintf(gs, "/Courier findfont 12 scalefont setfont\n"); fprintf(gs, "25 25 moveto\n"); fprintf(gs, "(File: %s Pen: %d Up: %7.0f Down: %7.0f Ratio %7.4f) show\n", r->job->fn, r->pen, du, dd, du / (du + dd)); fprintf(gs, "showpage\n"); usleep(100000); } r->dist_up = du; } /**********************************************************************/ static void best_loop(struct run *r, int n) { struct vector *v; struct segment *sp, *s, *sn; double d, db; if (n <= 0 || n >= r->nseg - 1) return; if (!r->worklist[n]->loop) return; sp = r->worklist[n - 1]; s = r->worklist[n]; sn = r->worklist[n + 1]; db = 9e99; TAILQ_FOREACH(v, &s->vectors, list) { if (sp->loop && sp->vb != NULL) d = hypot(sp->vb->x0 - v->x0, sp->vb->y0 - v->y0); else d = hypot(sp->x1 - v->x0, sp->y1 - v->y0); if (sn->loop && sn->vb != NULL) d += hypot(sn->vb->x0 - v->x0, sn->vb->y0 - v->y0); else d += hypot(sn->x0 - v->x0, sn->y0 - v->y0); if (d < db) { s->vb = v; db = d; } } } static double cost(struct run *r, int t, int *lx, int *ly) { struct segment *s; double d1, d2; s = r->worklist[t]; if (s->loop && s->vb != NULL) { d1 = hypot(*lx - s->vb->x0, *ly - s->vb->y0); if (d1 > bit_width) d1 += lift_cost; *lx = s->vb->x0; *ly = s->vb->y0; return (d1); } if (s->loop) { d1 = hypot(*lx - s->x0, *ly - s->y0); if (d1 > bit_width) d1 += lift_cost; *lx = s->x0; *ly = s->y0; return (d1); } d1 = hypot(*lx - s->x0, *ly - s->y0); d2 = hypot(*lx - s->x1, *ly - s->y1); if (d1 < d2) { if (d1 > bit_width) d1 += lift_cost; *lx = s->x1; *ly = s->y1; s->flip = 0; return (d1); } if (d2 > bit_width) d2 += lift_cost; *lx = s->x0; *ly = s->y0; s->flip = 1; return (d2); } static double cost_fwd(struct run *r) { int lx, ly; double du; int n; lx = HOME_X; ly = HOME_Y; du = 0; for (n = 0; n < r->nseg; n++) { du += cost(r, n, &lx, &ly); if (du > r->dist_up) return (du); } assert(lx = HOME_X); assert(ly = HOME_Y); return (du); } static void prep(struct run *r) { int n; memcpy(r->worklist, r->seglist, r->listlen); for (n = 0; n < r->nseg; n++) { r->worklist[n]->vb = NULL; r->worklist[n]->flip = 0; } } static void commit(struct run *r) { int n; struct segment *s; static time_t l, last; for (n = 0; n < r->nseg; n++) { s = (r->seglist[n]); if (s->flip) { flip_seg(s); s->flip = 0; } if (s->loop && s->vb != NULL) { rotate_loop(s, s->vb); s->vb = NULL; } } memcpy(r->seglist, r->worklist, r->listlen); time(&l); if (l > last + 3) { stat_run(r, 1); last = l; } else { stat_run(r, 0); } } static int inversions(struct run *r) { double du; struct segment *s; int n, m, n1, n2; int retval = 0; assert(r->nseg > 0); for (n1 = 1; n1 < r->nseg - 3; n1++) { for (n2 = r->nseg - (n1 + 1); n2 > 1; n2--) { assert (n2 >= 2); assert(n1 + n2 < r->nseg); prep(r); /* reverse run from n1 to n1 + n2 */ n = n1; for (m = n1 + n2 - 1; m > n; m--, n++) { s = r->worklist[n]; r->worklist[n] = r->worklist[m]; r->worklist[m] = s; } /* optimize loops near the transitions */ for (n = 3; n >= -3; n--) { best_loop(r, n + n1); best_loop(r, n + n1 + n2); } for (n = -3; n < 3; n++) { best_loop(r, n + n1); best_loop(r, n + n1 + n2); } du = cost_fwd(r); if (du + .01 >= r->dist_up) continue; // fprintf(stderr, "INV %d %d %g %g\n", n1, n2, du, r->dist_up); commit(r); assert(r->dist_up == du); retval++; } } return (retval); } /**********************************************************************/ static int cross(struct run *r) { double x43, y43, x13, y13, x21, y21; double ua, ub, d; struct segment *s; int n1, n2, n, m; int retval = 0; for (n1 = 1; n1 < r->nseg - 3; n1++) { for (n2 = n1 + 2; n2 < r->nseg - 2; n2++) { x13 = r->seglist[n1]->x1 - r->seglist[n2]->x1; y13 = r->seglist[n1]->y1 - r->seglist[n2]->y1; x21 = r->seglist[n1 + 1]->x0 - r->seglist[n1]->x1; y21 = r->seglist[n1 + 1]->y0 - r->seglist[n1]->y1; x43 = r->seglist[n2 + 1]->x0 - r->seglist[n2]->x1; y43 = r->seglist[n2 + 1]->y0 - r->seglist[n2]->y1; d = (double)y43*x21 - (double)x43*y21; if (d == 0) continue; ua = ((double)x43*y13-(double)y43*x13) / d; ub = ((double)x21*y13-(double)y21*x13) / d; if (ua <= 0 || ub <= 0 || ua >= 1 || ub >= 1) continue; fprintf(stderr, "[%d, %d] %g %g %g\n", n1, n2, d, ua, ub); fprintf(stderr, "(%d,%d)-(%d,%d)", r->seglist[n1]->x1, r->seglist[n1]->y1, r->seglist[n1+1]->x0, r->seglist[n1+1]->y0); fprintf(stderr, " <-> (%d,%d)-(%d,%d)\n", r->seglist[n2]->x1, r->seglist[n2]->y1, r->seglist[n2+1]->x0, r->seglist[n2+1]->y0); prep(r); /* reverse run from n1 to n1 + n2 */ n = n1 + 1; for (m = n2; m > n; m--, n++) { flip_seg(r->worklist[n]); flip_seg(r->worklist[m]); s = r->worklist[n]; r->worklist[n] = r->worklist[m]; r->worklist[m] = s; } commit(r); retval++; } } return (retval); } /**********************************************************************/ static int slide_fwd(struct run *r, int x) { double du; struct segment *s; int i, n, n1, n2; int retval = 0; fprintf(stderr, "fwd%d\n", x); assert(r->nseg > 0); for (n1 = 1; n1 < r->nseg - (2 + x); n1++) { prep(r); for (n2 = n1; n2 < r->nseg - (1 + x); n2++) { s = r->worklist[n2 + x]; for (i = x; i > 0; i--) r->worklist[n2 + i] = r->worklist[n2 + i - 1]; r->worklist[n2] = s; /* optimize loops near the transitions */ for (n = 3; n >= -3; n--) { best_loop(r, n + n2); best_loop(r, n + n2 + x); } for (n = -3; n < 3; n++) { best_loop(r, n + n2); best_loop(r, n + n2 + x); } du = cost_fwd(r); if (du + .01 >= r->dist_up) continue; fprintf(stderr, "FWD%d %d %d %g %g\n", x, n1, n2, du, r->dist_up); commit(r); assert(r->dist_up == du); retval++; } } return (retval); } static int slide_rev(struct run *r, int x) { double du; struct segment *s; int i, n, n1, n2; int retval = 0; assert(r->nseg > 0); fprintf(stderr, "rev%d\n", x); for (n1 = r->nseg - (1 + x); n1 > 1; n1--) { prep(r); for (n2 = n1 - 1; n2 > 0; n2--) { s = r->worklist[n2]; for (i = 0; i < x; i++) r->worklist[n2 + i] = r->worklist[n2 + 1 + i]; r->worklist[n2 + i] = s; /* optimize loops near the transitions */ for (n = 3; n >= -3; n--) { best_loop(r, n + n2); best_loop(r, n + n2 + x); } for (n = -3; n < 3; n++) { best_loop(r, n + n2); best_loop(r, n + n2 + x); } du = cost_fwd(r); if (du + .01 >= r->dist_up) continue; fprintf(stderr, "REV%d %d %d %g %g\n", x, n1, n2, du, r->dist_up); commit(r); assert(r->dist_up == du); retval++; } } return (retval); } /**********************************************************************/ static void rotate(struct run *r) { int i; prep(r); for (i = 0; i < r->nseg; i++) best_loop(r, i); for (i = r->nseg - 1; i >= 0; i--) best_loop(r, i); commit(r); } /**********************************************************************/ static int stitch(struct run *r) { int n; double d; struct segment *s, *sn; struct vector *v, *v2; for (n = 0; n < r->nseg - 1; n++) { s = r->seglist[n]; sn = r->seglist[n + 1]; if (s->loop || sn->loop) continue; d = hypot(s->x1 - sn->x0, s->y1 - sn->y0); if (d > pen_width[r->pen]) continue; /* The new vector */ v = calloc(sizeof *v, 1); assert(v != NULL); v->x0 = s->x1; v->y0 = s->y1; v->x1 = sn->x0; v->y1 = sn->y0; TAILQ_INSERT_TAIL(&s->vectors, v, list); TAILQ_FOREACH_SAFE(v, &sn->vectors, list, v2) { TAILQ_REMOVE(&sn->vectors, v, list); TAILQ_INSERT_TAIL(&s->vectors, v, list); } s->x1 = sn->x1; s->y1 = sn->y1; for (n++; n < r->nseg - 1; n++) r->seglist[n] = r->seglist[n + 1]; r->nseg--; stat_run(r, 0); return (1); } return (0); } /**********************************************************************/ static void bridge_2(struct run *r) { int n, m, n1, n2, n3, n4; n1 = 1 + (random() % (r->nseg - 16)); n2 = n1 + (random() % (r->nseg - (11 + n1))); n3 = n2 + (random() % (r->nseg - (6 + n2))); n4 = n3 + (random() % (r->nseg - (1 + n3))); fprintf(stderr, "Bridge2 %d-%d <--> %d-%d\n", n1, n2, n3, n4); prep(r); m = 0; for (n = 0; n < n1; n++) r->worklist[m++] = r->seglist[n]; for (n = n3; n < n4; n++) r->worklist[m++] = r->seglist[n]; for (n = n2; n < n3; n++) r->worklist[m++] = r->seglist[n]; for (n = n1; n < n2; n++) r->worklist[m++] = r->seglist[n]; for (n = n4; n < r->nseg; n++) r->worklist[m++] = r->seglist[n]; commit(r); } /**********************************************************************/ static void stats(struct job *j) { struct run *r; int did, n; TAILQ_FOREACH(r, &j->runs, list) { if (opt_p >= 0 && opt_p != r->pen) continue; fprintf(stderr, "\n"); if (r->nvect == 0) continue; stat_run(r, 1); segment(r); stat_run(r, 1); if (1) { sort_seg(r); stat_run(r, 0); } if (0) { rotate(r); } stat_run(r, 0); if (0) { stat_run(r, 1); break; } do { did = cross(r); did += inversions(r); if (did) continue; for (n = 1; !did && n < 4; n++) { did += slide_fwd(r, n); if (!did) did += slide_rev(r, n); } if (!did) while (stitch(r)) did++; if (0 && !did) { stat_run(r, 1); bridge_2(r); // bridge_2(r); // bridge_2(r); did++; } } while (did); fprintf(stderr, " stable\n"); stat_run(r, 1); } } /**********************************************************************/ static void do_file(const char *fn) { char buf[BUFSIZ]; struct job *j; FILE *fi; const char *p; enum {F_NC, F_PLT} fmt; struct run *r; struct vector *v; p = strchr(fn, '\0'); assert(p != NULL); assert(p > buf + 4); if (p[-1] == 'c' && p[-2] == 'n' && p[-3] == '.') { fmt = F_NC; } else if (p[-1] == 't' && p[-2] == 'l' && p[-3] == 'p' && p[-4] == '.') { fmt = F_PLT; } else { errx(1, "Unknown format: %s", fn); } j = calloc(sizeof *j, 1); assert(j != NULL); j->x0 = 2000000000; j->y0 = 2000000000; j->x1 = -2000000000; j->y1 = -2000000000; j->fn = strdup(fn); assert(j->fn != NULL); TAILQ_INIT(&j->runs); fprintf(stderr, "\nFILE: %s\n", fn); fi = fopen(fn, "r"); if (fi == NULL) err(1, "Cannot open %s", fn); while (fgets(buf, sizeof buf, fi)) { if (fmt == F_PLT) parse_plt(j, buf); else parse_nc(j, buf); } fclose(fi); fprintf(stderr, "X = [%d,%d] Y = [%d, %d]\n", j->x0, j->x1, j->y0, j->y1); TAILQ_FOREACH(r, &j->runs, list) { TAILQ_FOREACH(v, &r->vectors, list) { v->x0 -= j->x0; v->x1 -= j->x0; v->y0 -= j->y0; v->y1 -= j->y0; } } j->x1 -= j->x0; j->y1 -= j->y0; j->x0 -= j->x0; j->y0 -= j->y0; stats(j); fprintf(stderr, "X = [%d,%d] Y = [%d, %d]\n", j->x0, j->x1, j->y0, j->y1); emit_gcode(j); } int main(int argc, char **argv) { int i; while ((i = getopt(argc, argv, "p:")) != -1) { switch (i) { case 'p': opt_p = strtoul(optarg, NULL, 0); break; default: fprintf(stderr, "Usage (%d)\n", i); exit (1); } } srandomdev(); open_gs(); argc -= optind; argv += optind; for (i = 0; i < argc; i++) do_file(argv[i]); close_gs(); return (0); }