#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
#include <vector>
#include <map>
#define RASTER 100 // mil
#define MAX_ROUND (100/10) // allow 10% raster offset when aligning
#define MIN_OVERLAP (100/10) // require 10% overlap for merging
#define MIN(a, b) (((a)<(b))?(a):(b))
#define MAX(a, b) (((a)>(b))?(a):(b))
#define POW2(a) ((a)*(a))
#define LOG(fmt, ...) fprintf(stderr, fmt "\n", ##__VA_ARGS__);
typedef struct point_s {
unsigned x, y;
unsigned radius;
bool consumed;
bool operator==(const point_s& p) const {
return p.x == x && p.y == y;
}
bool operator!=(const point_s& p) const {
return p.x != x || p.y != y;
}
bool intersects(const point_s& p) const {
return (p.x >= x-radius-p.radius+MIN_OVERLAP && p.x <= x+radius+p.radius-MIN_OVERLAP && p.y >= y-radius-p.radius+MIN_OVERLAP && p.y <= y+radius+p.radius-MIN_OVERLAP);
}
unsigned sqdist(const point_s& p) const {
return POW2((x>p.x)? x-p.x: p.x-x) + POW2((y>p.y)? y-p.y: p.y-y);
}
unsigned dist(const point_s& p) const {
return (unsigned)round(sqrt(sqdist(p)));
}
} point_t;
typedef struct {
point_t a, b;
bool includes(const point_t& p) const {
if (a.x == b.x) {
if (p.x != a.x) return false;
if (a.y < b.y) return p.y >= a.y && p.y <= b.y;
return p.y >= b.y && p.y <= a.y;
} else {
assert(a.y == b.y);
if (p.y != a.y) return false;
if (a.x < b.x) return p.x >= a.x && p.x <= b.x;
return p.x >= b.x && p.x <= a.x;
}
}
} line_t;
static bool point_align(const point_t& raster, point_t& p, int& round_max) {
if (p.x < raster.x || p.y < raster.y) {
LOG("cannot align: %u/%u", p.x, p.y);
return false;
}
int off_x = ((int)p.x % RASTER) - (int)raster.x;
int off_y = ((int)p.y % RASTER) - (int)raster.y;
if (off_x || off_y) {
if (abs(off_x) > MAX_ROUND || abs(off_y) > MAX_ROUND) {
LOG("too much off to align: %u/%u", p.x, p.y);
return false;
}
p.x -= off_x;
p.y -= off_y;
if (abs(off_x) > abs(round_max)) round_max = off_x;
if (abs(off_y) > abs(round_max)) round_max = off_y;
}
return true;
}
static bool point2pad(point_t& p, std::vector<point_t>& pads) {
for (std::vector<point_t>::iterator it=pads.begin(); it!=pads.end(); ++it) {
if (p.intersects(*it)) {
p = *it;
it->consumed = true;
return true;
}
}
return false;
}
int main(int argc, char **argv) {
std::vector<point_t> pads;
std::vector<line_t> lines;
// parse input, check for unsupported features, and fill pads and lines
std::map<unsigned, unsigned> apertures;
point_t last_point = {};
bool last_point_set = false;
unsigned last_aperture = 0;
bool last_aperture_set = false;
static char line[256];
while (fgets(line, sizeof(line), stdin)) {
size_t len = strlen(line);
while (len && line[len-1] == '\n') {
line[--len] = '\0';
}
float a, b;
unsigned x, y;
unsigned cmd;
char s[sizeof(line)];
if (strncmp(line, "G04", 3) == 0 || strncmp(line, "%LN", 3) == 0 || strncmp(line, "M02*", 4) == 0 || strncmp(line, "D02*", 4) == 0 || strncmp(line, "G70*", 4) == 0 || strncmp(line, "G90*", 4) == 0) {
// comment, redundant, or unneeded
} else if (sscanf(line, "%%MO%[^*]*%%", s) == 1) {
if (strcmp(s, "IN") != 0) {
LOG("requiring inch units");
return 1;
}
} else if (sscanf(line, "%%AS%[^*]*%%", s) == 1) {
if (strcmp(s, "AXBY") != 0) {
LOG("no AX/BY axis");
return 1;
}
} else if (sscanf(line, "%%FS%[^X]X%uY%u*%%", s, &x, &y) == 3) {
if (strcmp(s, "LA") != 0) {
LOG("requiring absolute coordinates");
return 1;
}
if (x != 23 || y != 23) {
LOG("requiring 2.3 coordinate format");
return 1;
}
} else if (sscanf(line, "%%OFA%uB%u*%%", &x, &y) == 2) {
if (x != 0 || y != 0) {
LOG("coordinate offset given");
return 1;
}
} else if (sscanf(line, "%%SFA%fB%f*%%", &a, &b) == 2) {
if (a != 1.0 || b != 1.0) {
LOG("coordinate scale given");
return 1;
}
} else if (sscanf(line, "%%ADD%uC,%f*%%", &x, &a) == 2) {
if (apertures.find(x) != apertures.end()) {
LOG("aperture %u already defined", x);
return 1;
}
apertures.insert(std::pair<unsigned, unsigned>(x, a*1000));
} else if (sscanf(line, "%%ADD%uR,%fX%f*%%", &x, &a, &b) == 3) {
if (apertures.find(x) != apertures.end()) {
LOG("aperture %u already defined", x);
return 1;
}
if (a != b) {
LOG("irregular rectangular shape for aperture %u", x);
return 1;
}
apertures.insert(std::pair<unsigned, unsigned>(x, a*1000)); // sqrt(^2) instead?
} else if (sscanf(line, "G54D%u*", &x) == 1 || sscanf(line, "D%u*", &x) == 1) {
if (apertures.find(x) == apertures.end()) {
LOG("unknown aperture %u", x);
return 1;
}
last_aperture = apertures.find(x)->second;
last_aperture_set = true;
} else if (sscanf(line, "X%uY%uD%u*", &x, &y, &cmd) == 3) {
if (!last_aperture_set) {
LOG("no aperture set for: %s", line);
return 1;
} else if (cmd == 3) { // flash
pads.push_back((point_t){x, y, last_aperture/2, false});
last_point_set = false;
} else if (cmd == 2) { // goto while off
last_point.x = x;
last_point.y = y;
last_point.radius = last_aperture/2;
last_point.consumed = true;
last_point_set = true;
} else if (cmd == 1) { // goto while on
if (!last_point_set || last_aperture/2 != last_point.radius) {
LOG("unknown starting point for: %s", line);
return 1;
}
lines.push_back((line_t){(point_t){last_point.x, last_point.y, last_aperture/2, true}, (point_t){x, y, last_aperture/2, true}});
last_point.x = x;
last_point.y = y;
last_point_set = true;
} else {
LOG("unknown point suffix command: %s", line);
return 1;
}
} else {
LOG("ignoring unknown line: %s", line);
}
}
LOG("loaded input with %zu pads, %zu lines", pads.size(), lines.size());
// determine the global raster offset by majority of pads and line bends
point_t raster_start = {0, 0};
unsigned mods_num = 0;
unsigned mods_x[RASTER] = {};
unsigned mods_y[RASTER] = {};
for (std::vector<point_t>::const_iterator it=pads.begin(); it!=pads.end(); ++it) {
mods_num++;
mods_x[it->x % RASTER]++;
mods_y[it->y % RASTER]++;
}
for (std::vector<line_t>::const_iterator it1=lines.begin(); it1!=lines.end(); ++it1) {
for (std::vector<line_t>::const_iterator it2=lines.begin(); it2!=lines.end(); ++it2) {
if (it1-lines.begin() == it2-lines.begin()) continue;
if (it1->a == it2->a || it1->a == it2->b) {
mods_num++;
mods_x[it1->a.x % RASTER]++;
mods_y[it1->a.y % RASTER]++;
break;
} else if (it1->b == it2->a || it1->b == it2->b) {
mods_num++;
mods_x[it1->b.x % RASTER]++;
mods_y[it1->b.y % RASTER]++;
break;
}
}
}
for (unsigned i=0; i<RASTER; ++i) {
if (mods_x[i] > mods_x[raster_start.x]) {
raster_start.x = i;
}
if (mods_y[i] > mods_y[raster_start.y]) {
raster_start.y = i;
}
}
unsigned raster_x_ok = mods_x[((raster_start.x?:100)-1)%RASTER] + mods_x[raster_start.x] + mods_x[(raster_start.x+1)%RASTER];
unsigned raster_y_ok = mods_y[((raster_start.y?:100)-1)%RASTER] + mods_y[raster_start.y] + mods_y[(raster_start.y+1)%RASTER];
LOG("best %u mil raster offset: %ux%u mil", RASTER, raster_start.x, raster_start.y);
if (raster_x_ok < mods_num/2 || raster_y_ok < mods_num/2) {
LOG("too less matching offset samples (%u samples, %u/%u match)", mods_num, raster_x_ok, raster_y_ok);
return 1;
}
// align pads to global raster
int round_max = 0;
for (std::vector<point_t>::iterator it=pads.begin(); it!=pads.end(); ++it) { // we could go through mods, but we want to know the offending pad, if any
if (!point_align(raster_start, *it, round_max)) {
return 1;
}
}
LOG("aligned pads, max rounding error: %d mil", round_max);
// make sure pads are unique (can happen e.g. for different apertures)
unsigned dupes = 0;
for (std::vector<point_t>::iterator it1=pads.begin(); it1!=pads.end();) {
for (std::vector<point_t>::iterator it2=pads.begin(); it2!=pads.end();) {
if (it1-pads.begin() != it2-pads.begin()) {
if (*it1 == *it2) {
//LOG("pad %ux%u (%u,%u) given twice, ignoring", it1->x, it1->y, it1->radius, it2->radius);
dupes++;
if (it1->radius > it2->radius) {
it2 = pads.erase(it2);
continue;
} else {
it1 = pads.erase(it1);
goto cont2;
}
}
if (it1->intersects(*it2)) {
LOG("pad %ux%u intersects with %ux%u", it1->x, it1->y, it2->x, it2->y);
return 1;
}
}
++it2;
}
++it1;
cont2:;
}
LOG("ignored %u duplicate pads", dupes);
// align lines to global raster or snap them to the nearest pad
round_max = 0;
for (std::vector<line_t>::iterator it=lines.begin(); it!=lines.end(); ++it) {
if (!point2pad(it->a, pads) && !point_align(raster_start, it->a, round_max)) {
return 1;
}
if (!point2pad(it->b, pads) && !point_align(raster_start, it->b, round_max)) {
return 1;
}
if (it->a.x != it->b.x && it->a.y != it->b.y) {
LOG("skewed line: %ux%u -> %ux%u", it->a.x, it->a.y, it->b.x, it->b.y);
return 1;
}
if (it->a == it->b) {
LOG("zero length line: %ux%u", it->a.x, it->a.y); // maybe aperture intersected with the same pad for both points
return 1;
}
// let it start from the smaller point as convenience invariant
if (it->a.x > it->b.x || it->a.y > it->b.y) {
point_t tmp = it->a;
it->a = it->b;
it->b = tmp;
}
}
LOG("max. line rounding error: %d", round_max); // w/o pad connection
// compute result, i.e. borders for each line in raster/2
std::vector<line_t> result;
for (std::vector<line_t>::const_iterator it=lines.begin(); it!=lines.end(); ++it) {
line_t curr = *it;
// three corners for each point, acc. to general direction
static const unsigned N=1, S=2, W=4, E=8;
unsigned corner_a=N|S|W|E, corner_b=N|S|W|E;
if (curr.a.x < curr.b.x) { corner_a &= ~E; corner_b &= ~W; }
else if (curr.a.y < curr.b.y) { corner_a &= ~N; corner_b &= ~S; }
else assert(false);
// find overlappings/tees/crossings and delete corners accordingly
for (std::vector<line_t>::const_iterator ait=lines.begin(); ait!=lines.end(); ++ait) {
if (it-lines.begin() == ait-lines.begin()) continue;
line_t adj = *ait;
if (adj.a == curr.a || adj.b == curr.b) {
// ok
} else if (adj.a == curr.b || adj.b == curr.a) {
adj.a = ait->b;
adj.b = ait->a;
} else {
continue;
}
unsigned adir=0, bdir=0;
if (adj.a.x < adj.b.x) { adir = E; bdir = W; }
else if (adj.a.x > adj.b.x) { adir = W; bdir = E; }
else if (adj.a.y < adj.b.y) { adir = N; bdir = S; }
else if (adj.a.y > adj.b.y) { adir = S; bdir = N; }
else assert(false);
if (adj.a == curr.a) {
corner_a &= ~adir;
} else if (adj.b == curr.b) {
corner_b &= ~bdir;
} else assert(false);
}
// points needed for raster/2 result
point_t a_tl = {curr.a.x-(RASTER/2), curr.a.y+(RASTER/2), 1, false};
point_t a_tr = {curr.a.x+(RASTER/2), curr.a.y+(RASTER/2), 1, false};
point_t a_bl = {curr.a.x-(RASTER/2), curr.a.y-(RASTER/2), 1, false};
point_t a_br = {curr.a.x+(RASTER/2), curr.a.y-(RASTER/2), 1, false};
point_t b_tl = {curr.b.x-(RASTER/2), curr.b.y+(RASTER/2), 1, false};
point_t b_tr = {curr.b.x+(RASTER/2), curr.b.y+(RASTER/2), 1, false};
point_t b_bl = {curr.b.x-(RASTER/2), curr.b.y-(RASTER/2), 1, false};
point_t b_br = {curr.b.x+(RASTER/2), curr.b.y-(RASTER/2), 1, false};
// draw both side lines (assume there are no T junctions w/o a stop)
if (curr.a.x == curr.b.x) { // N/S
assert(curr.a.y < curr.b.y);
result.push_back((line_t){a_tl, b_bl});
result.push_back((line_t){a_tr, b_br});
} else { // W/E
assert(curr.a.x < curr.b.x);
result.push_back((line_t){a_tr, b_tl});
result.push_back((line_t){a_br, b_bl});
}
// and corners. note that everything will be coalesced afterwards
if (corner_a & N) result.push_back((line_t){a_tl, a_tr});
if (corner_a & S) result.push_back((line_t){a_bl, a_br});
if (corner_a & W) result.push_back((line_t){a_bl, a_tl});
if (corner_a & E) result.push_back((line_t){a_br, a_tr});
if (corner_b & N) result.push_back((line_t){b_tl, b_tr});
if (corner_b & S) result.push_back((line_t){b_bl, b_br});
if (corner_b & W) result.push_back((line_t){b_bl, b_tl});
if (corner_b & E) result.push_back((line_t){b_br, b_tr});
}
LOG("converted to %zu rectangular border lines", result.size());
// add unconsumed pads
for (std::vector<point_t>::iterator it=pads.begin(); it!=pads.end(); ++it) {
if (it->consumed) continue;
point_t tl = {it->x-(RASTER/2), it->y+(RASTER/2), 1, false};
point_t tr = {it->x+(RASTER/2), it->y+(RASTER/2), 1, false};
point_t bl = {it->x-(RASTER/2), it->y-(RASTER/2), 1, false};
point_t br = {it->x+(RASTER/2), it->y-(RASTER/2), 1, false};
result.push_back((line_t){tl, tr});
result.push_back((line_t){tr, br});
result.push_back((line_t){br, bl});
result.push_back((line_t){bl, tl});
}
LOG("added standalone pads, now %zu lines", result.size());
// postprocessing, sanity checks, add global borders
point_t min = {(unsigned)-1, (unsigned)-1};
point_t max = {0, 0};
for (std::vector<line_t>::iterator it=result.begin(); it!=result.end();) {
if (it->a == it->b) {
it = result.erase(it);
continue;
}
if ((it->a.x == it->b.x) == (it->a.y == it->b.y)) {
LOG("skewed line: %ux%u -> %ux%u", it->a.x, it->a.y, it->b.x, it->b.y);
return 1;
}
// let it start from the smaller point as convenience invariant, again
if (it->a.x > it->b.x || it->a.y > it->b.y) {
point_t tmp = it->a;
it->a = it->b;
it->b = tmp;
}
if (it->a.x < min.x) min.x = it->a.x;
if (it->a.y < min.y) min.y = it->a.y;
if (it->b.x > max.x) max.x = it->b.x;
if (it->b.y > max.y) max.y = it->b.y;
it++;
}
point_t tl = {min.x, max.y};
point_t br = {max.x, min.y};
result.push_back((line_t){min, tl});
result.push_back((line_t){tl, max});
result.push_back((line_t){max, br});
result.push_back((line_t){br, min});
// coalesce straight lines
again:;
for (std::vector<line_t>::iterator it1=result.begin(); it1!=result.end(); ++it1) {
for (std::vector<line_t>::iterator it2=result.begin(); it2!=result.end(); ++it2) {
if (it1-lines.begin() == it2-lines.begin()) continue;
if ((it1->a.x == it1->b.x) == (it2->a.x == it2->b.x)) { // same general direction
if (it1->includes(it2->a) || it1->includes(it2->b)) { // share a point, overlap, or inclusion
line_t tmp = *it1;
it1->a.x = MIN(MIN(tmp.a.x, tmp.b.x), MIN(it2->a.x, it2->b.x));
it1->a.y = MIN(MIN(tmp.a.y, tmp.b.y), MIN(it2->a.y, it2->b.y));
it1->b.x = MAX(MAX(tmp.a.x, tmp.b.x), MAX(it2->a.x, it2->b.x));
it1->b.y = MAX(MAX(tmp.a.y, tmp.b.y), MAX(it2->a.y, it2->b.y));
assert(it1->a != it1->b);
result.erase(it2);
goto again;
}
}
}
}
LOG("postprocessing: coalesced to %zu lines", result.size());
// print header
printf("%%ASAXBY*%%\n");
printf("%%FSLAX23Y23*%%\n");
printf("%%MOIN*%%\n");
printf("%%OFA0B0*%%\n");
printf("%%SFA1.0B1.0*%%\n");
printf("%%ADD10C,0.010000*%%\n");
printf("%%LNCOPPER0*%%\n");
// start at 0x0
printf("G54D10*\n");
printf("X0Y0D02*\n");
point_t curr = {0, 0};
// order acc. to consecutive corners or acc. to smallest noop drive
unsigned mill_len=0;
unsigned move_len=0;
unsigned moves = 0;
unsigned idle_moves = 0;
while (!result.empty()) {
std::vector<line_t>::iterator next;
unsigned next_dst = (unsigned)-1;
bool next_rev = false;
for (std::vector<line_t>::iterator nit=result.begin(); nit!=result.end(); ++nit) {
unsigned dst_a = curr.sqdist(nit->a);
unsigned dst_b = curr.sqdist(nit->b);
if (dst_a <= dst_b) {
if (dst_a < next_dst) {
next_dst = dst_a;
next = nit;
}
} else {
if (dst_b < next_dst) {
next_dst = dst_b;
next = nit;
next_rev = true;
}
}
}
moves++;
if (next_dst == 0) { // can go on to a or b while on
if (next->a == curr) {
mill_len += curr.dist(next->b);
printf("X%uY%uD01*\n", next->b.x, next->b.y);
assert(next->b != curr);
curr = next->b;
} else { // next->b == curr
mill_len += curr.dist(next->a);
printf("X%uY%uD01*\n", next->a.x, next->a.y);
assert(next->a != curr);
curr = next->a;
}
} else { // need to stop and draw new polyline
idle_moves++;
if (next_rev) {
move_len += curr.dist(next->b);
mill_len += next->b.dist(next->a);
printf("X%uY%uD02*\n", next->b.x, next->b.y);
printf("X%uY%uD01*\n", next->a.x, next->a.y);
assert(next->a != curr);
curr = next->a;
} else {
move_len += curr.dist(next->a);
mill_len += next->a.dist(next->b);
printf("X%uY%uD02*\n", next->a.x, next->a.y);
printf("X%uY%uD01*\n", next->b.x, next->b.y);
assert(next->b != curr);
curr = next->b;
}
}
result.erase(next);
}
LOG("drawing lines: %u busy movements (%u mil), %u idle movements (%u mil)", moves, mill_len, idle_moves, move_len);
// print footer & done
printf("M02*\n");
LOG("done: success");
return 0;
}
