src/slotifier.c

   1 /*
   2  * Utility to convert overlapping Excellon drill hits into drill slots.
   3  * Copyright © 2018, 2021 Nick Bowler
   4  *
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, either version 3 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program.  If not, see <https://www.gnu.org/licenses/>.
  17  */
  18
  19 #include <config.h>
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23 #include <assert.h>
  24 #include <locale.h>
  25
  26 #include <getopt.h>
  27 #include <gettext.h>
  28 #include <localcharset.h>
  29 #include <mbswidth.h>
  30 #include <striconv.h>
  31
  32 #include <CNearTree.h>
  33 #include <gerbv.h>
  34
  35 #include "help.h"
  36
  37 #if !ENABLE_NLS
  38 #  undef ENABLE_NLS
  39 #  define ENABLE_NLS 0
  40 #endif
  41
  42 #define _(x) (gettext(x))
  43
  44 static const char *progname = "slotifier";
  45 static unsigned verbose;
  46
  47 #include "options.h"
  48 static const char sopts[] = SOPT_STRING;
  49 static const struct option lopts[] = {
  50         LOPTS_INITIALIZER,
  51         {0}
  52 };
  53
  54 static void print_version(void)
  55 {
  56         const char *copysign = "(C)";
  57         void *convsign = NULL;
  58
  59         puts(PACKAGE_STRING);
  60
  61         if (ENABLE_NLS) {
  62                 convsign = str_iconv("\xc2\xa9", "UTF-8", locale_charset());
  63                 if (convsign)
  64                         copysign = convsign;
  65         }
  66
  67         printf("Copyright %s 2021 Nick Bowler.\n", copysign);
  68         puts("License GPLv3+: GNU GPL version 3 or any later version.");
  69         puts("This is free software: you are free to change and redistribute it.");
  70         puts("There is NO WARRANTY, to the extent permitted by law.");
  71
  72         free(convsign);
  73 }
  74
  75 static void print_usage(FILE *f)
  76 {
  77         fprintf(f, _("Usage: %s [options] [-o filename] filename\n"), progname);
  78         if (f != stdout)
  79                 fprintf(f, _("Try %s --help for more information.\n"),
  80                            progname);
  81 }
  82
  83 static void print_help(void)
  84 {
  85         const struct option *opt;
  86
  87         print_usage(stdout);
  88
  89         puts(_("This is \"slotifier\": a tool to convert overlapping drill hits in Excellon\n"
  90                "drill files to G85 drill slots."));
  91         putchar('\n');
  92
  93         puts(_("Options:"));
  94         for (opt = lopts; opt->val; opt++) {
  95                 struct lopt_help help;
  96
  97                 if (!lopt_get_help(opt, &help))
  98                         continue;
  99
 100                 help_print_option(opt, help.arg, help.desc, 20);
 101         }
 102         putchar('\n');
 103
 104         puts(_("For more information, see the slotifier(1) man page."));
 105         putchar('\n');
 106
 107         /*
 108          * TRANSLATORS: Please add *another line* indicating where users should
 109          * report translation bugs.
 110          */
 111         printf(_("Report bugs to <%s>.\n"), PACKAGE_BUGREPORT);
 112 }
 113
 114 static void init_i18n(void)
 115 {
 116         setlocale(LC_ALL, "");
 117         bindtextdomain(PACKAGE, LOCALEDIR);
 118         textdomain(PACKAGE);
 119 }
 120
 121 static CNearTreeHandle build_search_tree(gerbv_image_t *drill)
 122 {
 123         CNearTreeHandle t;
 124         gerbv_net_t *x;
 125
 126         if (CNearTreeCreate(&t, 2, CNEARTREE_TYPE_DOUBLE|CNEARTREE_NORM_L2))
 127                 return 0;
 128
 129         /* Build a search tree from all the holes. */
 130         for (x = drill->netlist; x; x = x->next) {
 131                 double xy[2] = { x->start_x, x->start_y };
 132
 133                 assert(x->aperture >= 0 && x->aperture < APERTURE_MAX);
 134
 135                 /* Skip things that aren't drill hits */
 136                 if (!drill->aperture[x->aperture])
 137                         continue;
 138
 139                 /* Holes are marked as "flashing"; otherwise it's an existing
 140                  * slot; skip it. */
 141                 if (x->aperture_state != GERBV_APERTURE_STATE_FLASH)
 142                         continue;
 143
 144                 if (CNearTreeInsert(t, xy, x)) {
 145                         CNearTreeFree(&t);
 146                         return 0;
 147                 }
 148         }
 149
 150         if (CNearTreeCompleteDelayedInsert(t)) {
 151                 CNearTreeFree(&t);
 152                 return 0;
 153         }
 154
 155         return t;
 156 }
 157
 158 static gerbv_aperture_type_t tool_type(gerbv_image_t *drill, int aperture)
 159 {
 160         gerbv_aperture_t *tool = drill->aperture[abs(aperture)];
 161
 162         return tool->type;
 163 }
 164
 165 static double tool_radius(gerbv_image_t *drill, int aperture)
 166 {
 167         gerbv_aperture_t *tool = drill->aperture[abs(aperture)];
 168
 169         /* Half a mil slop to decisively include points on boundary. */
 170         return tool->parameter[0] / 2.0 + 0.0005;
 171 }
 172
 173 static int holes_overlap(gerbv_image_t *drill, gerbv_net_t *a, gerbv_net_t *b)
 174 {
 175         double d = hypot(a->start_x - b->start_x, a->start_y - b->start_y);
 176
 177         return tool_radius(drill, a->aperture) >= d
 178             || tool_radius(drill, b->aperture) >= d;
 179 }
 180
 181 static int combine_holes(gerbv_image_t *drill, gerbv_net_t *hole,
 182                          CNearTreeHandle t)
 183 {
 184         CVectorHandle group, tmp;
 185         int biggest_tool, ret = -1;
 186         double biggest_r;
 187         size_t i, j;
 188
 189         /*
 190          * Since we consider holes in order of decreasing size, the initial hole
 191          * considered is by definition the biggest one we will find in a group.
 192          */
 193         biggest_r = tool_radius(drill, (biggest_tool = hole->aperture));
 194
 195         if (CVectorCreate(&group, sizeof (gerbv_net_t *), 10)) {
 196                 fprintf(stderr, _("%s: failed to allocate memory\n"), progname);
 197                 return -1;
 198         }
 199
 200         if (CVectorCreate(&tmp, sizeof (void *), 10)) {
 201                 fprintf(stderr, _("%s: failed to allocate memory\n"), progname);
 202                 CVectorFree(&group);
 203                 return -1;
 204         }
 205
 206         /*
 207          * Breadth-first nearest neighbour search of holes.  We negate the
 208          * aperture to indicate which holes have been previously visited.
 209          */
 210         CVectorAddElement(group, &hole);
 211         hole->aperture = -hole->aperture;
 212
 213         for (i = 0; i < CVectorSize(group); i++) {
 214                 double xy[2];
 215
 216                 CVectorGetElement(group, &hole, i);
 217
 218                 assert(tool_type(drill, hole->aperture) == GERBV_APTYPE_CIRCLE);
 219                 assert(tool_radius(drill, hole->aperture) <= biggest_r);
 220
 221                 xy[0] = hole->start_x; xy[1] = hole->start_y;
 222                 if (CNearTreeFindInSphere(t, biggest_r, 0, tmp, xy, 1) != 0) {
 223                         /* We should always should find at least one hole! */
 224                         fprintf(stderr, _("%s: fatal error searching holes\n"),
 225                                         progname);
 226                         goto err;
 227                 }
 228
 229                 for (j = 0; j < CVectorSize(tmp); j++) {
 230                         /* I don't know why, but CNearTree returns a list
 231                          * of pointers to its internal copies of pointers
 232                          * to the objects in the tree.  So we need this
 233                          * double indirection to get the actual hole. */
 234                         gerbv_net_t *newhole;
 235                         void *p;
 236
 237                         CVectorGetElement(tmp, &p, j);
 238                         newhole = *(void **)p;
 239
 240                         if (newhole->aperture < 0)
 241                                 continue; /* already visited */
 242
 243                         if (holes_overlap(drill, hole, newhole)) {
 244                                 CVectorAddElement(group, &newhole);
 245                                 newhole->aperture = -newhole->aperture;
 246                         }
 247                 }
 248         }
 249
 250         /* Compare each pair of matched points to find the longest slot. */
 251         if (CVectorSize(group) > 1) {
 252                 int biggest_slot = 0;
 253                 double bestlen = 0;
 254
 255                 for (i = 0; i < CVectorSize(group) - 1; i++) {
 256                         CVectorGetElement(group, &hole, i);
 257                         for (j = i+1; j < CVectorSize(group); j++) {
 258                                 gerbv_net_t *h2;
 259                                 double newlen;
 260
 261                                 CVectorGetElement(group, &h2, j);
 262                                 newlen = hypot(hole->start_x - h2->start_x,
 263                                                hole->start_y - h2->start_y);
 264
 265                                 if (newlen > bestlen) {
 266                                         hole->stop_x = h2->start_x;
 267                                         hole->stop_y = h2->stop_y;
 268                                         bestlen = newlen;
 269                                         biggest_slot = i;
 270                                 }
 271                         }
 272                 }
 273
 274                 CVectorGetElement(group, &hole, biggest_slot);
 275                 hole->aperture = biggest_tool;
 276                 hole->aperture_state = GERBV_APERTURE_STATE_ON;
 277
 278                 if (verbose) {
 279                         const char *fmt = ngettext(
 280                                 "%s: merged %zu hole into slot (%.4f,%.4f)-(%.4f,%.4f)\n",
 281                                 "%s: merged %zu holes into slot (%.4f,%.4f)-(%.4f,%.4f)\n",
 282                                 CVectorSize(group));
 283
 284                         fprintf(stderr, fmt, progname, CVectorSize(group),
 285                                              hole->start_x, hole->start_y,
 286                                              hole->stop_x, hole->stop_y);
 287                 }
 288         } else {
 289                 /* The only hole we found was our original one, restore
 290                  * initial state. */
 291                 CVectorGetElement(group, &hole, 0);
 292
 293                 assert(hole->aperture < 0);
 294                 hole->aperture = -hole->aperture;
 295
 296                 if (verbose > 1) {
 297                         fprintf(stderr, _("%s: hole at (%.4f,%.4f) not merged\n"),
 298                                         progname, hole->start_x, hole->start_y);
 299                 }
 300         }
 301
 302         ret = 0;
 303 err:
 304         CVectorFree(&tmp);
 305         CVectorFree(&group);
 306         return ret;
 307 }
 308
 309 /*
 310  * Order two holes by hole diameter.
 311  */
 312 static gerbv_image_t *hsc_drill_data;
 313 static int hole_size_cmp(const void *a_, const void *b_)
 314 {
 315         gerbv_net_t * const *a = a_, * const *b = b_;
 316         gerbv_aperture_t *ta, *tb;
 317
 318         ta = hsc_drill_data->aperture[abs(a[0]->aperture)];
 319         assert(ta->type == GERBV_APTYPE_CIRCLE);
 320
 321         tb = hsc_drill_data->aperture[abs(b[0]->aperture)];
 322         assert(tb->type == GERBV_APTYPE_CIRCLE);
 323
 324         if (ta->parameter[0] > tb->parameter[0])
 325                 return -1;
 326         if (ta->parameter[0] < tb->parameter[0])
 327                 return 1;
 328         return 0;
 329 }
 330
 331 static void sort_holes_by_size(gerbv_image_t *drill, CVectorHandle work)
 332 {
 333         hsc_drill_data = drill;
 334         qsort(work->array, work->size, work->elementsize, hole_size_cmp);
 335 }
 336
 337 static int slotify(gerbv_image_t *drill)
 338 {
 339         CVectorHandle holes, work;
 340         CNearTreeHandle t;
 341         int ret = 0;
 342         size_t i;
 343
 344         t = build_search_tree(drill);
 345         if (!t) {
 346                 fprintf(stderr, _("%s: failed to build search tree\n"),
 347                                 progname);
 348                 return -1;
 349         }
 350
 351         CNearTreeObjects(t, &holes);
 352         if (!holes)
 353                 goto err_free_tree;
 354
 355         if (CVectorCreate(&work, sizeof (gerbv_net_t *), CVectorSize(holes))) {
 356                 fprintf(stderr, _("%s: failed to allocate memory\n"), progname);
 357                 goto err_free_tree;
 358         }
 359
 360         memcpy(work->array, holes->array, holes->size * holes->elementsize);
 361         work->size = holes->size;
 362         sort_holes_by_size(drill, work);
 363
 364         for (i = 0; i < CVectorSize(work); i++) {
 365                 gerbv_net_t *hole;
 366
 367                 CVectorGetElement(work, &hole, i);
 368                 /* Skip holes we've already looked at */
 369                 if (hole->aperture < 0)
 370                         continue;
 371                 if (hole->aperture_state == GERBV_APERTURE_STATE_ON)
 372                         continue;
 373
 374                 if (verbose > 1) {
 375                         fprintf(stderr, _("%s: checking hole at (%.4f,%.4f) for overlaps\n"),
 376                                         progname, hole->start_x, hole->start_y);
 377                 }
 378
 379                 if (combine_holes(drill, hole, t) < 0) {
 380                         ret = -1;
 381                         break;
 382                 }
 383         }
 384
 385         /* Clean out any holes we don't need anymore */
 386         for (i = 0; i < CVectorSize(holes); i++) {
 387                 gerbv_net_t *hole;
 388
 389                 CVectorGetElement(holes, &hole, i);
 390                 if (hole->aperture < 0)
 391                         gerbv_image_delete_net(hole);
 392         }
 393
 394         CVectorFree(&work);
 395 err_free_tree:
 396         CNearTreeFree(&t);
 397         return ret;
 398 }
 399
 400 int main(int argc, char **argv)
 401 {
 402         const char *outfile = "/dev/stdout";
 403         gerbv_project_t *gp;
 404         gerbv_image_t *drill;
 405         int opt, ret = 0;
 406
 407         if (argc > 0)
 408                 progname = argv[0];
 409
 410         init_i18n();
 411
 412         while ((opt = getopt_long(argc, argv, sopts, lopts, NULL)) != -1) {
 413                 switch (opt) {
 414                 case 'o':
 415                         outfile = optarg;
 416                         break;
 417                 case 'v':
 418                         verbose++;
 419                         break;
 420                 case 'V':
 421                         print_version();
 422                         return EXIT_SUCCESS;
 423                 case 'H':
 424                         print_help();
 425                         return EXIT_SUCCESS;
 426                 default:
 427                         print_usage(stderr);
 428                         return EXIT_FAILURE;
 429                 }
 430         }
 431
 432         if (!argv[optind]) {
 433                 fprintf(stderr, _("%s: error: must specify a filename\n"),
 434                                 progname);
 435                 print_usage(stderr);
 436                 return EXIT_FAILURE;
 437         }
 438
 439         if (optind + 1 < argc) {
 440                 fprintf(stderr, _("%s: error: excess command-line arguments\n"),
 441                                 progname);
 442                 print_usage(stderr);
 443                 return EXIT_FAILURE;
 444         }
 445
 446         gp = gerbv_create_project();
 447         if (!gp)
 448                 return EXIT_FAILURE;
 449
 450         gerbv_open_layer_from_filename(gp, argv[optind]);
 451         if (!gp->file[0]) {
 452                 ret = EXIT_FAILURE;
 453                 goto out;
 454         }
 455
 456         drill = gp->file[0]->image;
 457         if (drill->layertype != GERBV_LAYERTYPE_DRILL) {
 458                 fprintf(stderr, _("%s: %s: error: not a drill file\n"),
 459                                 progname, argv[optind]);
 460                 ret = EXIT_FAILURE;
 461                 goto out;
 462         }
 463
 464         if (slotify(drill) != 0) {
 465                 ret = EXIT_FAILURE;
 466                 goto out;
 467         }
 468
 469         if (!gerbv_export_drill_file_from_image(outfile, drill, NULL))
 470                 ret = EXIT_FAILURE;
 471 out:
 472         gerbv_destroy_project(gp);
 473         return ret;
 474 }