Index: trunk/src/Makefile.dep =================================================================== --- trunk/src/Makefile.dep (revision 29284) +++ trunk/src/Makefile.dep (revision 29285) @@ -3631,7 +3631,7 @@ ../src_3rd/genrtree/genrtree_api.h ht_subc.h ../src_3rd/genht/ht.h \ ../src_3rd/genht/hash.h obj_pstk_list.h obj_pstk.h vtpadstack.h \ obj_pstk_shape.h polygon.h vtpadstack_t.h \ - ../src_plugins/io_autotrax/write.h layer.h librnd/poly/polygon_offs.h \ + ../src_plugins/io_autotrax/write.h layer.h librnd/poly/offset.h \ ../src_plugins/io_autotrax/../lib_polyhelp/polyhelp.h obj_poly.h \ ../src_plugins/lib_compat_help/pstk_compat.h obj_pstk.h ../src_plugins/io_dsn/io_dsn.o: ../src_plugins/io_dsn/io_dsn.c \ @@ -3678,7 +3678,7 @@ vtpadstack_t.h plug_io.h librnd/core/conf.h librnd/core/pcb-printf.h \ ../src_3rd/liblihata/lihata.h librnd/core/list_conf.h \ librnd/core/safe_fs.h librnd/core/compat_misc.h layer_grp.h conf_core.h \ - librnd/core/actions.h netlist.h librnd/poly/polygon_offs.h \ + librnd/core/actions.h netlist.h librnd/poly/offset.h \ ../src_plugins/io_dsn/read.h ../src_plugins/io_dsn/write.o: ../src_plugins/io_dsn/write.c ../config.h \ plug_io.h librnd/core/global_typedefs.h librnd/core/pcb_bool.h \ @@ -5789,7 +5789,7 @@ librnd/core/pcb-printf.h ../src_3rd/genvector/gds_char.h \ ../src_3rd/genvector/genvector_impl.h \ ../src_3rd/genvector/genvector_undef.h librnd/core/unit.h obj_line.h \ - librnd/core/box.h librnd/core/misc_util.h librnd/poly/polygon_offs.h \ + librnd/core/box.h librnd/core/misc_util.h librnd/poly/offset.h \ ../src_3rd/genvector/vtp0.h librnd/core/hid_dad.h \ librnd/core/compat_misc.h librnd/core/hid_attrib.h librnd/core/hid.h \ ../src_3rd/liblihata/dom.h ../src_3rd/liblihata/lihata.h \ @@ -8279,7 +8279,7 @@ ../src_3rd/genht/ht.h ../src_3rd/genht/hash.h obj_pstk_list.h obj_pstk.h \ ../src_3rd/genvector/vtp0.h vtpadstack.h obj_pstk_shape.h polygon.h \ vtpadstack_t.h undo.h ../src_3rd/libuundo/uundo.h undo_old.h \ - librnd/poly/polygon1_gen.h librnd/poly/polygon_offs.h rotate.h librnd/core/rotate.h \ + librnd/poly/polygon1_gen.h librnd/poly/offset.h rotate.h librnd/core/rotate.h \ librnd/core/compat_misc.h search.h librnd/core/hid_inlines.h conf_core.h \ librnd/core/conf.h librnd/core/pcb-printf.h \ ../src_3rd/liblihata/lihata.h librnd/core/list_conf.h obj_poly_op.h \ @@ -8318,7 +8318,7 @@ draw.h draw_wireframe.h obj_pstk_draw.h obj_pstk_inlines.h thermal.h \ librnd/poly/polygon1_gen.h obj_pstk_op.h operation.h obj_subc_parent.h obj_hash.h \ librnd/core/compat_misc.h search.h undo.h ../src_3rd/libuundo/uundo.h \ - undo_old.h librnd/core/event.h librnd/core/hid_inlines.h librnd/poly/polygon_offs.h \ + undo_old.h librnd/core/event.h librnd/core/hid_inlines.h librnd/poly/offset.h \ obj_pstk_op.c rotate.h librnd/core/rotate.h obj_pstk_act.o: obj_pstk_act.c ../config.h obj_pstk.h \ ../src_3rd/genlist/gendlist.h ../src_3rd/genvector/vtp0.h \ @@ -8382,7 +8382,7 @@ obj_pstk_shape.h polygon.h vtpadstack_t.h data_list.h obj_pstk_inlines.h \ thermal.h librnd/poly/polygon1_gen.h rotate.h librnd/core/rotate.h undo.h \ ../src_3rd/libuundo/uundo.h undo_old.h obj_hash.h funchash_core.h \ - librnd/core/funchash.h funchash_core_list.h librnd/poly/polygon_offs.h + librnd/core/funchash.h funchash_core_list.h librnd/poly/offset.h obj_rat.o: obj_rat.c ../config.h board.h ../src_3rd/genht/htsp.h \ ../src_3rd/genht/ht.h librnd/core/global_typedefs.h \ librnd/core/pcb_bool.h vtroutestyle.h librnd/core/unit.h \ @@ -8536,7 +8536,7 @@ ../src_3rd/genht/ht.h ../src_3rd/genht/hash.h obj_pstk_list.h obj_pstk.h \ ../src_3rd/genvector/vtp0.h vtpadstack.h obj_pstk_shape.h polygon.h \ vtpadstack_t.h librnd/core/hid_inlines.h undo.h \ - ../src_3rd/libuundo/uundo.h undo_old.h librnd/poly/polygon_offs.h \ + ../src_3rd/libuundo/uundo.h undo_old.h librnd/poly/offset.h \ librnd/core/event.h obj_text_op.h operation.h obj_poly_draw.h draw.h \ obj_arc_draw.h obj_subc_parent.h obj_hash.h obj_line_draw.h \ obj_text_draw.h conf_core.h librnd/core/conf.h librnd/core/pcb-printf.h \ @@ -8738,8 +8738,8 @@ ../src_3rd/genht/hash.h obj_pstk_list.h obj_pstk.h vtpadstack.h \ obj_pstk_shape.h polygon.h vtpadstack_t.h draw.h remove.h search.h \ thermal.h librnd/poly/polygon1_gen.h undo.h ../src_3rd/libuundo/uundo.h undo_old.h \ - obj_poly_draw.h obj_text_draw.h librnd/poly/polygon_selfi.h librnd/core/event.h \ - librnd/core/compat_misc.h librnd/poly/polygon_offs.h + obj_poly_draw.h obj_text_draw.h librnd/poly/self_isc.h librnd/core/event.h \ + librnd/core/compat_misc.h librnd/poly/offset.h polygon1.o: polygon1.c ../config.h librnd/poly/rtree.h librnd/core/global_typedefs.h \ librnd/core/pcb_bool.h ../src_3rd/genrtree/genrtree_api.h \ librnd/core/math_helper.h librnd/core/heap.h librnd/core/compat_cc.h librnd/core/pcb-printf.h \ @@ -8747,7 +8747,7 @@ ../src_3rd/genvector/genvector_undef.h librnd/core/unit.h librnd/poly/polyarea.h \ obj_common.h flag.h librnd/core/globalconst.h librnd/core/attrib.h \ data_parent.h macro.h librnd/core/box.h librnd/core/misc_util.h \ - rtree2_compat.h polygon_selfi.c librnd/poly/polygon_selfi.h \ + rtree2_compat.h polygon_selfi.c librnd/poly/self_isc.h \ ../src_3rd/genvector/vtp0.h polygon1_gen.o: polygon1_gen.c ../config.h librnd/core/global_typedefs.h \ librnd/core/pcb_bool.h librnd/poly/polyarea.h librnd/core/math_helper.h \ Index: trunk/src/Makefile.in =================================================================== --- trunk/src/Makefile.in (revision 29284) +++ trunk/src/Makefile.in (revision 29285) @@ -109,8 +109,8 @@ put /local/pcb/OBJS_POLYLIB [@ $(LIBRND)/poly/polyarea.o $(LIBRND)/poly/polygon1_gen.o - $(LIBRND)/poly/polygon_offs.o - $(LIBRND)/poly/polygon_selfi.o + $(LIBRND)/poly/offset.o + $(LIBRND)/poly/self_isc.o $(LIBRND)/poly/rtree.o @] Index: trunk/src/librnd/poly/polygon_offs.c =================================================================== --- trunk/src/librnd/poly/polygon_offs.c (revision 29284) +++ trunk/src/librnd/poly/polygon_offs.c (nonexistent) @@ -1,428 +0,0 @@ -/* - * COPYRIGHT - * - * pcb-rnd, interactive printed circuit board design - * Copyright (C) 2017,2019 Tibor 'Igor2' Palinkas - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Contact: - * Project page: http://repo.hu/projects/pcb-rnd - * lead developer: http://repo.hu/projects/pcb-rnd/contact.html - * mailing list: pcb-rnd (at) list.repo.hu (send "subscribe") - */ - -/* Polygon contour offset calculation */ - -#include -#include -#include -#include -#include - -#if 0 -#define pcbo_trace pcb_trace -#else -static void pcbo_trace(char *fmt, ...) {} -#endif - -void pcb_polo_norm(double *nx, double *ny, pcb_coord_t x1, pcb_coord_t y1, pcb_coord_t x2, pcb_coord_t y2) -{ - double dx = x2 - x1, dy = y2 - y1, len = sqrt(dx*dx + dy*dy); - *nx = -dy / len; - *ny = dx / len; -} - -void pcb_polo_normd(double *nx, double *ny, double x1, double y1, double x2, double y2) -{ - double dx = x2 - x1, dy = y2 - y1, len = sqrt(dx*dx + dy*dy); - *nx = -dy / len; - *ny = dx / len; -} - -static long warp(long n, long len) -{ - if (n < 0) n += len; - else if (n >= len) n -= len; - return n; -} - -void pcb_polo_edge_shift(double offs, - double *x0, double *y0, double nx, double ny, - double *x1, double *y1, - double prev_x, double prev_y, double prev_nx, double prev_ny, - double next_x, double next_y, double next_nx, double next_ny) -{ - double ax, ay, al, a1l, a1x, a1y; - - offs = -offs; - - /* previous edge's endpoint offset */ - ax = (*x0) - prev_x; - ay = (*y0) - prev_y; - al = sqrt(ax*ax + ay*ay); - ax /= al; - ay /= al; - a1l = ax*nx + ay*ny; - a1x = offs / a1l * ax; - a1y = offs / a1l * ay; - - (*x0) += a1x; - (*y0) += a1y; - - /* next edge's endpoint offset */ - ax = next_x - (*x1); - ay = next_y - (*y1); - al = sqrt(ax*ax + ay*ay); - ax /= al; - ay /= al; - - a1l = ax*nx + ay*ny; - a1x = offs / a1l * ax; - a1y = offs / a1l * ay; - - (*x1) += a1x; - (*y1) += a1y; -} - -void pcb_polo_offs(double offs, pcb_polo_t *pcsh, long num_pts) -{ - long n; - - for(n = 0; n < num_pts; n++) { - long np = warp(n-1, num_pts), nn1 = warp(n+1, num_pts), nn2 = warp(n+2, num_pts); - pcb_polo_edge_shift(offs, - &pcsh[n].x, &pcsh[n].y, pcsh[n].nx, pcsh[n].ny, - &pcsh[nn1].x, &pcsh[nn1].y, - pcsh[np].x, pcsh[np].y, pcsh[np].nx, pcsh[np].ny, - pcsh[nn2].x, pcsh[nn2].y, pcsh[nn2].nx, pcsh[nn2].ny - ); - } -} - - -void pcb_polo_norms(pcb_polo_t *pcsh, long num_pts) -{ - long n; - - for(n = 0; n < num_pts; n++) { - long nn = warp(n+1, num_pts); - pcb_polo_normd(&pcsh[n].nx, &pcsh[n].ny, pcsh[n].x, pcsh[n].y, pcsh[nn].x, pcsh[nn].y); - } -} - -double pcb_polo_2area(pcb_polo_t *pcsh, long num_pts) -{ - double a = 0; - long n; - - for(n = 0; n < num_pts-1; n++) { - long nn = warp(n+1, num_pts); - a += pcsh[n].x * pcsh[nn].y; - a -= pcsh[n].y * pcsh[nn].x; - } - return a; -} - -void pcb_pline_dup_offsets(vtp0_t *dst, const pcb_pline_t *src, pcb_coord_t offs) -{ - const pcb_vnode_t *v; - pcb_vector_t tmp; - pcb_pline_t *res = NULL; - long num_pts, n, from; - pcb_polo_t *pcsh; - - /* count corners */ - v = src->head; - num_pts = 0; - do { - num_pts++; - } while((v = v->next) != src->head); - - /* allocate the cache and copy all data */ - pcsh = malloc(sizeof(pcb_polo_t) * num_pts); - for(n = 0, v = src->head; n < num_pts; n++, v = v->next) { - pcsh[n].x = v->point[0]; - pcsh[n].y = v->point[1]; - pcb_polo_norm(&pcsh[n].nx, &pcsh[n].ny, v->point[0], v->point[1], v->next->point[0], v->next->point[1]); - } - - /* offset the cache */ - pcb_polo_offs(offs, pcsh, num_pts); - - - /* create a new pline by copying the cache */ - tmp[0] = pcb_round(pcsh[0].x); - tmp[1] = pcb_round(pcsh[0].y); - res = pcb_poly_contour_new(tmp); - for(n = 1; n < num_pts; n++) { - tmp[0] = pcb_round(pcsh[n].x); - tmp[1] = pcb_round(pcsh[n].y); - pcb_poly_vertex_include(res->head->prev, pcb_poly_node_create(tmp)); - } - - free(pcsh); - - from = dst->used; - if (pcb_pline_is_selfint(res)) { - pcb_pline_split_selfint(res, dst); - pcb_poly_contour_del(&res); - } - else - vtp0_append(dst, res); - - for(n = from; n < dst->used; n++) { - res = dst->array[n]; - pcb_poly_contour_pre(res, 1); - pcb_pline_keepout_offs(res, src, offs); /* avoid self-intersection */ - res->tree = pcb_poly_make_edge_tree(res); - dst->array[n] = res; - } -} - -pcb_pline_t *pcb_pline_dup_offset(const pcb_pline_t *src, pcb_coord_t offs) -{ - vtp0_t selfi; - pcb_pline_t *res = NULL; - int n; - double best = 0; - - vtp0_init(&selfi); - pcb_pline_dup_offsets(&selfi, src, offs); - - for(n = 0; n < selfi.used; n++) { - pcb_pline_t *pl = selfi.array[n]; - if (pl->area > best) { - best = pl->area; - res = pl; - } - } - pcbo_trace("best area: %f out of %d\n", best, selfi.used); - for(n = 0; n < selfi.used; n++) { - pcb_pline_t *pl = selfi.array[n]; - if (res != pl) - pcb_poly_contour_del(&pl); - } - vtp0_uninit(&selfi); - return res; -} - - -TODO("this should be coming from gengeo2d"); -/* Return the square of distance between point x0;y0 and line x1;y1 - x2;y2 */ -static double dist_line_to_pt(double x0, double y0, double x1, double y1, double x2, double y2, double *odx, double *ody) -{ - double ax = x0 - x1, ay = y0 - y1; - double dx = x2 - x1, dy = y2 - y1; - double len = sqrt(dx*dx+dy*dy); - double o, dxn, dyn; - double tmp1, d2; - - - dxn = dx / len; - dyn = dy / len; - - o = (ax * dxn + ay * dyn) / len; - if (o <= 0.0) { - /* beyond x1;y1 */ - return ax * ax + ay * ay; - } - if (o >= 1.0) { - /* beyond x1;y1 */ - double bx = x0 - x2, by = y0 - y2; - return bx * bx + by * by; - } - - /* in range: normal line-point dist */ - tmp1 = dy*x0 - dx*y0 + x2*y1 - y2*x1; - d2 = dx*dx + dy*dy; - - *odx = dxn; - *ody = dyn; - return (tmp1 * tmp1) / d2; -} - -/* Modify v, pulling it back toward vp so that the distance to line ldx;ldy is increased by tune */ -PCB_INLINE int pull_back(pcb_vnode_t *v, const pcb_vnode_t *vp, double tune, double ldx, double ldy, double prjx, double prjy, int inside) -{ - pcb_coord_t ox, oy; - double c, vx, vy, vlen, prx, pry, prlen; - - vx = v->point[0] - vp->point[0]; - vy = v->point[1] - vp->point[1]; - if ((vx == 0) && (vy == 0)) - return -1; - - vlen = sqrt(vx*vx + vy*vy); - vx /= vlen; - vy /= vlen; - - prx = v->point[0] - prjx; - pry = v->point[1] - prjy; - prlen = sqrt(prx*prx + pry*pry); - prx /= prlen; - pry /= prlen; - - c = (ldy * vx - ldx * vy); - if ((c < 0.0001) && (c > -0.0001)) { - pcbo_trace(" par1: vp=%.12mm;%.12mm v=%.12mm;%.12mm\n", vp->point[0], vp->point[1], v->point[0], v->point[1]); - pcbo_trace(" par2: vx=%f;%f ld=%f;%f\n", vx, vy, ldx, ldy); - return -1; /* perpendicular; no pullbakc could help */ - } - - c = tune * ((-pry * ldx + prx * ldy) / c); - - pcbo_trace(" vect: vp=%mm;%mm v=%mm;%mm\n", vp->point[0], vp->point[1], v->point[0], v->point[1]); - pcbo_trace(" vect: vx=%f;%f prx=%f;%f tune=%.012mm\n", vx, vy, prx, pry, (pcb_coord_t)tune); - pcbo_trace(" MOVE: c=%.012mm (%f) %mm;%mm\n", (pcb_coord_t)c, c, (pcb_coord_t)(v->point[0] + c * vx), (pcb_coord_t)(v->point[1] + c * vy)); - - if (c < 0) { - v->point[0] = vp->point[0]; - v->point[1] = vp->point[1]; - return 0; /* not enough room - cut back line to zero length so it gets removed */ - } - - if (inside) - c = -c; - ox = v->point[0]; oy = v->point[1]; - v->point[0] = pcb_round(v->point[0] + c * vx); - v->point[1] = pcb_round(v->point[1] + c * vy); - - if ((ox == v->point[0]) && (oy == v->point[1])) - return -1; /* too close, can't pull any more */ - - return 0; -} - -void pcb_pline_keepout_offs(pcb_pline_t *dst, const pcb_pline_t *src, pcb_coord_t offs) -{ - pcb_vnode_t *v; - double offs2 = (double)offs * (double)offs; - int negoffs = offs < 0; - - if (offs < 0) - offs = -offs; - - if (offs2 > dst->area) - return; /* degenerate case: polygon too small */ - - /* there are two ways dst can get too close to src: */ - - /* case #1: a point in dst is too close to a line in src */ - v = dst->head; - do { - pcb_rtree_it_t it; - pcb_rtree_box_t pb; - void *seg; - int inside = 0; - - - retry:; - pb.x1 = v->point[0] - offs+1; pb.y1 = v->point[1] - offs+1; - pb.x2 = v->point[0] + offs-1; pb.y2 = v->point[1] + offs-1; - if (!negoffs) - inside = pcb_poly_contour_inside(src, v->point); - - for(seg = pcb_rtree_first(&it, src->tree, &pb); seg != NULL; seg = pcb_rtree_next(&it)) { - pcb_coord_t x1, y1, x2, y2; - double dist, tune, prjx, prjy, dx, dy, ax, ay, dotp, prevx, prevy, prevl; - - pcb_polyarea_get_tree_seg(seg, &x1, &y1, &x2, &y2); - dist = dist_line_to_pt(v->point[0], v->point[1], x1, y1, x2, y2, &dx, &dy); - if ((offs2 - dist) > 10) { - pcb_vector_t nv_; - pcb_vnode_t *nv; - - /* calculate x0;y0 projected onto the line */ - ax = v->point[0] - x1; - ay = v->point[1] - y1; - dotp = ax * dx + ay * dy; - prjx = x1 + dx * dotp; - prjy = y1 + dy * dotp; - pcbo_trace("dotp=%f dx=%f dy=%f res: %mm %mm inside=%d\n", dotp, dx, dy, (pcb_coord_t)prjx, (pcb_coord_t)prjy, inside); - - /* this is how much the point needs to be moved away from the line */ - if (inside) - tune = offs + sqrt(dist); - else - tune = offs - sqrt(dist); - if (tune < 5) - continue; - - pcbo_trace("close: %mm;%mm to %mm;%mm %mm;%mm: tune=%.012mm prj: %mm;%mm\n", v->point[0], v->point[1], x1, y1, x2, y2, (pcb_coord_t)tune, (pcb_coord_t)prjx, (pcb_coord_t)prjy); - pcbo_trace(" tune=%.012mm dist=%.012mm\n", (pcb_coord_t)tune, (pcb_coord_t)sqrt(dist)); - - - /* corner case: if next segment is parallel to what we are compesing to - (chamfed V with bottom horizontal being too close to target horizontal line), - do not insert a new point because that would retain the horizontal line - which can not be moved because it is parallel to the target line */ - prevx = v->prev->point[0] - v->point[0]; - prevy = v->prev->point[1] - v->point[1]; - prevl = sqrt(prevx*prevx + prevy*prevy); - prevx /= prevl; - prevy /= prevl; - - if (((prevx == dx) || (prevx == -dx)) && ((prevy == dy) || (prevy == -dy))) { - /* apply direct shift of the whole parallel line */ - v->point[0] = pcb_round(v->point[0] + prjx * tune); - v->point[1] = pcb_round(v->point[1] + prjy * tune); - v->prev->point[0] = pcb_round(v->prev->point[0] + prjx * tune); - v->prev->point[1] = pcb_round(v->prev->point[1] + prjy * tune); - v = v->next; - goto retry; - } - - nv_[0] = v->point[0]; - nv_[1] = v->point[1]; - nv = pcb_poly_node_create(nv_); - pcb_poly_vertex_include_force(v, nv); - - if (pull_back(v, v->prev, tune, dx, dy, prjx, prjy, inside) != 0) { - pcb_poly_vertex_exclude(dst, nv); - v = v->next; - goto retry; - } - - if (pull_back(nv, nv->next, tune, dx, dy, prjx, prjy, inside) != 0) { - pcb_poly_vertex_exclude(dst, nv); - v = v->next; - goto retry; - } - - v = v->next; - goto retry; - } - } - } while((v = v->next) != dst->head); - - /* case #2: a line in dst is too close to a point in src */ - - - /* cleanup: remove redundant points */ - v = dst->head; - do { - if ((v->prev->point[0] == v->point[0]) && (v->prev->point[1] == v->point[1])) { - if (v->prev == dst->head) { - pcb_vnode_t *nv = v->next; - pcb_poly_vertex_exclude(dst, v); - v = nv; - continue; - } - pcb_poly_vertex_exclude(dst, v->prev); - } - } while((v = v->next) != dst->head); -} - Index: trunk/src/librnd/poly/polygon_selfi.c =================================================================== --- trunk/src/librnd/poly/polygon_selfi.c (revision 29284) +++ trunk/src/librnd/poly/polygon_selfi.c (nonexistent) @@ -1,336 +0,0 @@ -/* - * COPYRIGHT - * - * pcb-rnd, interactive printed circuit board design - * Copyright (C) 2018,2019 Tibor 'Igor2' Palinkas - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Contact: - * Project page: http://repo.hu/projects/pcb-rnd - * lead developer: http://repo.hu/projects/pcb-rnd/contact.html - * mailing list: pcb-rnd (at) list.repo.hu (send "subscribe") - */ - -#include "config.h" -#include -#include -#include -#include -#include - -/* expect no more than this number of hubs in a complex polygon */ -#define MAX_HUB_TRIES 1024 - -TODO("convert this into an enum") -#define UNKNWN 0 - - -#if 0 -# define TRACE pcb_trace -#else - void TRACE(const char *fmt, ...) {} -#endif - -typedef struct { - vtp0_t node; -} vhub_t; - -static pcb_vnode_t *pcb_pline_split(pcb_vnode_t *v, pcb_vector_t at) -{ - pcb_vnode_t *v2 = pcb_poly_node_add_single(v, at); - - v2 = pcb_poly_node_create(at); - assert(v2 != NULL); - v2->cvc_prev = v2->cvc_next = NULL; - v2->Flags.status = UNKNWN; - - /* link in */ - v->next->prev = v2; - v2->next = v->next; - v2->prev = v; - v->next = v2; - - return v2; -} - -static pcb_vnode_t *pcb_pline_end_at(pcb_vnode_t *v, pcb_vector_t at) -{ - if (pcb_vect_dist2(at, v->point) < PCB_POLY_ENDP_EPSILON) - return v; - if (pcb_vect_dist2(at, v->next->point) < PCB_POLY_ENDP_EPSILON) - return v->next; - return NULL; -} - -static vhub_t *hub_find(vtp0_t *hubs, pcb_vnode_t *v, pcb_bool insert) -{ - int n, m; - - for(n = 0; n < vtp0_len(hubs); n++) { - vhub_t *h = *vtp0_get(hubs, n, 0); - pcb_vnode_t *stored, **st; - st = (pcb_vnode_t **)vtp0_get(&h->node, 0, 0); - if (st == NULL) continue; - stored = *st; - /* found the hub at the specific location */ - if (pcb_vect_dist2(stored->point, v->point) < PCB_POLY_ENDP_EPSILON) { - for(m = 0; m < vtp0_len(&h->node); m++) { - st = (pcb_vnode_t **)vtp0_get(&h->node, m, 0); - if (st != NULL) { - stored = *st; - if (stored == v) /* already on the list */ - return h; - } - } - /* not found on the hub's list, maybe insert */ - if (insert) { - vtp0_append(&h->node, v); - return h; - } - return NULL; /* there is only one hub per point - if the coord matched and the node is not on, it's not going to be on any other hub's list */ - } - } - return NULL; -} - -/* remove v from h; if h has only one node, remove that too */ -static void remove_from_hub(vhub_t *h, pcb_vnode_t *v) -{ - int m; - pcb_vnode_t *stored, **st; - - for(m = 0; m < vtp0_len(&h->node); m++) { - st = (pcb_vnode_t **)vtp0_get(&h->node, m, 0); - if (st == NULL) { - vtp0_remove(&h->node, m, 1); - m--; - continue; - } - stored = *st; - if (stored == v) { - vtp0_remove(&h->node, m, 1); - m--; - v->Flags.in_hub = 0; - } - } - - /* only one node remains: this is no longer a hub! */ - if (h->node.used == 1) { - stored = *vtp0_get(&h->node, 0, 0); /* the previous loop guarantees it can not be NULL */ - vtp0_remove(&h->node, 0, 1); - stored->Flags.in_hub = 0; - } -} - -/* returns 1 if a new intersection is mapped */ -static int pcb_pline_add_isectp(vtp0_t *hubs, pcb_vnode_t *v) -{ - vhub_t *h; - - assert(v != NULL); - - v->Flags.in_hub = 1; - if (hubs->array != NULL) { - if (hub_find(hubs, v, pcb_true) != NULL) /* already on the list (... by now) */ - return 0; - } - - h = malloc(sizeof(vhub_t)); - vtp0_append(hubs, h); - vtp0_init(&h->node); - vtp0_append(&h->node, v); - return 1; -} - -static int pline_split_off_loop_new(pcb_pline_t *pl, vtp0_t *out, vhub_t *h, pcb_vnode_t *start, pcb_cardinal_t cnt) -{ - pcb_pline_t *newpl = NULL; - pcb_vnode_t *v, *next, *tmp; - - newpl = pcb_poly_contour_new(start->point); - next = start->next; - remove_from_hub(h, start); - pcb_poly_vertex_exclude(pl, start); - for(v = next; cnt > 0; v = next, cnt--) { - TRACE(" Append %mm %mm!\n", v->point[0], v->point[1]); - next = v->next; - pcb_poly_vertex_exclude(pl, v); - tmp = pcb_poly_node_create(v->point); - pcb_poly_vertex_include(newpl->head->prev, tmp); - } - -TRACE("APPEND: %p %p\n", newpl, newpl->head->next); - vtp0_append(out, newpl); - return 1; -} - -static int pline_split_off_loop(pcb_pline_t *pl, vtp0_t *hubs, vtp0_t *out, vhub_t *h, pcb_vnode_t *start) -{ - pcb_vnode_t *v; - pcb_cardinal_t cnt; - - for(v = start->next, cnt = 0;; v = v->next) { - if (v->Flags.in_hub) { - if (pcb_vect_dist2(start->point, v->point) < PCB_POLY_ENDP_EPSILON) - break; /* found a matching hub point */ - goto skip_to_backward; /* found a different hub point, skip */ - } - cnt++; - } - - /* forward loop */ - TRACE(" Fwd %ld!\n", (long)cnt); - return pline_split_off_loop_new(pl, out, h, start, cnt); - - skip_to_backward:; - for(v = start->prev, cnt = 0;; v = v->prev) { - if (v->Flags.in_hub) { - if (pcb_vect_dist2(start->point, v->point) < PCB_POLY_ENDP_EPSILON) { - start = v; - break; /* found a matching hub point */ - } - return 0; /* found a different hub point, skip */ - } - cnt++; - } - - TRACE(" Bwd %ld!\n", (long)cnt); - return pline_split_off_loop_new(pl, out, h, start, cnt); -} - -pcb_bool pcb_pline_is_selfint(pcb_pline_t *pl) -{ - pcb_vnode_t *va, *vb; - - va = (pcb_vnode_t *)pl->head; - do { - for(vb = va->next->next; vb->next != va; vb = vb->next) { - pcb_vector_t i, tmp; - if (pcb_vect_inters2(va->point, va->next->point, vb->point, vb->next->point, i, tmp) > 0) - return pcb_true; - } - va = va->next; - } while (va != pl->head); - return pcb_false; -} - - -void pcb_pline_split_selfint(const pcb_pline_t *pl_in, vtp0_t *out) -{ - int n; - vtp0_t hubs; - pcb_pline_t *pl = NULL; - pcb_vnode_t *va, *vb, *iva, *ivb; - - vtp0_init(&hubs); - - /* copy the pline and reset the in_hub flag */ - pcb_poly_contour_copy(&pl, pl_in); - va = (pcb_vnode_t *)pl->head; - do { - va->Flags.in_hub = 0; - va = va->next; - } while (va != pl->head); - - /* insert corners at intersections, collect a list of intersection hubs */ - va = (pcb_vnode_t *)pl->head; - do { - for(vb = va->next->next; vb->next != va; vb = vb->next) { - pcb_vector_t i, tmp; - if (pcb_vect_inters2(va->point, va->next->point, vb->point, vb->next->point, i, tmp) > 0) { - iva = pcb_pline_end_at(va, i); - if (iva == NULL) - iva = pcb_pline_split(va, i); - ivb = pcb_pline_end_at(vb, i); - if (ivb == NULL) - ivb = pcb_pline_split(vb, i); - if (pcb_pline_add_isectp(&hubs, iva) || pcb_pline_add_isectp(&hubs, ivb)) - TRACE("Intersect at %mm;%mm\n", i[0], i[1]); - } - } - va = va->next; - } while (va != pl->head); - - /*for(t = MAX_HUB_TRIES; t > 0; t--)*/ { - retry:; - for(n = 0; n < vtp0_len(&hubs); n++) { - int m; - vhub_t *h = *vtp0_get(&hubs, n, 0); - pcb_vnode_t *v, **v_ = (pcb_vnode_t **)vtp0_get(&h->node, 0, 0); - if (v_ == NULL) continue; - v = *v_; - TRACE("hub %p at %mm;%mm:\n", h, v->point[0], v->point[1]); - for(m = 0; m < vtp0_len(&h->node); m++) { - v = *vtp0_get(&h->node, m, 0); - TRACE(" %d=%p\n", m, v); - /* try to split off a leaf loop from the hub */ - - if (pline_split_off_loop(pl, &hubs, out, h, v)) - goto retry; - } - TRACE("\n"); - } - } - - /* what's left by now is a single loop, with all hubs already removed */ - vtp0_append(out, pl); - -TODO("leak: remove the unused hubs"); - vtp0_uninit(&hubs); -} - -pcb_cardinal_t pcb_polyarea_split_selfint(pcb_polyarea_t *pa) -{ - pcb_pline_t *pl, *next, *pln, *prev = NULL; - pcb_cardinal_t cnt = 0; - - for(pl = pa->contours; pl != NULL; pl = next) { - next = pl->next; - if (pcb_pline_is_selfint(pl)) { - vtp0_t pls; - int n; - cnt++; - vtp0_init(&pls); - pcb_pline_split_selfint(pl, &pls); - - - if (prev != NULL) - prev->next = next; - else - pa->contours = next; - - for(n = 0; n < pls.used; n++) { - pln = (pcb_pline_t *)pls.array[n]; - pcb_poly_contour_pre(pln, pcb_true); - if (pln->Flags.orient != pl->Flags.orient) - pcb_poly_contour_inv(pln); - pcb_poly_contour_pre(pln, 0); - pln->tree = pcb_poly_make_edge_tree(pln); - pcb_polyarea_contour_include(pa, pln); - cnt++; - } - - pcb_poly_contour_del(&pl); - cnt--; - - vtp0_uninit(&pls); - } - else - prev = pl; - } - - return cnt; -} Index: trunk/src/librnd/poly/polygon_offs.h =================================================================== --- trunk/src/librnd/poly/polygon_offs.h (revision 29284) +++ trunk/src/librnd/poly/polygon_offs.h (nonexistent) @@ -1,67 +0,0 @@ -/* - * COPYRIGHT - * - * pcb-rnd, interactive printed circuit board design - * Copyright (C) 2017,2019 Tibor 'Igor2' Palinkas - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Contact: - * Project page: http://repo.hu/projects/pcb-rnd - * lead developer: http://repo.hu/projects/pcb-rnd/contact.html - * mailing list: pcb-rnd (at) list.repo.hu (send "subscribe") - */ - -/* Polygon contour offset calculation */ - -#include - - -/* Calculate the offset plines of src and append the resulting plines to dst. - Yields multiple islands in some corner cases. */ -void pcb_pline_dup_offsets(vtp0_t *dst, const pcb_pline_t *src, pcb_coord_t offs); - -/* Same, but returns the largest island only */ -pcb_pline_t *pcb_pline_dup_offset(const pcb_pline_t *src, pcb_coord_t offs); - - -/* low level */ - -typedef struct { - double x, y, nx, ny; -} pcb_polo_t; - -/* Calculate the normal vectors of a cache */ -void pcb_polo_norms(pcb_polo_t *pcsh, long num_pts); - -/* Calculate and return the double of the area of a cached polygon */ -double pcb_polo_2area(pcb_polo_t *pcsh, long num_pts); - -/* Ortho-shift all edges of a polygon. Positive offset means grow. */ -void pcb_polo_offs(double offs, pcb_polo_t *pcsh, long num_pts); - -/* modify dst so it is at least offs far from any point or line of src */ -void pcb_pline_keepout_offs(pcb_pline_t *dst, const pcb_pline_t *src, pcb_coord_t offs); - -/* Orhto-shift an edge specified by x0;y0 and x1;y1. Calculate the new - edge points by extending/shrinking the previous and next line segment. - Modifies the target edge's start and end coords. Requires cached normals - Positive offset means grow. */ -void pcb_polo_edge_shift(double offs, - double *x0, double *y0, double nx, double ny, - double *x1, double *y1, - double prev_x, double prev_y, double prev_nx, double prev_ny, - double next_x, double next_y, double next_nx, double next_ny); - Index: trunk/src/librnd/poly/polygon_selfi.h =================================================================== --- trunk/src/librnd/poly/polygon_selfi.h (revision 29284) +++ trunk/src/librnd/poly/polygon_selfi.h (nonexistent) @@ -1,43 +0,0 @@ -/* - * COPYRIGHT - * - * pcb-rnd, interactive printed circuit board design - * Copyright (C) 2018,2019 Tibor 'Igor2' Palinkas - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Contact: - * Project page: http://repo.hu/projects/pcb-rnd - * lead developer: http://repo.hu/projects/pcb-rnd/contact.html - * mailing list: pcb-rnd (at) list.repo.hu (send "subscribe") - */ - -/* Resolve polygon self intersections */ - -#include -#include - -/* Returns whether a polyline is self-intersecting. O(n^2) */ -pcb_bool pcb_pline_is_selfint(pcb_pline_t *pl); - -/* Assume pl is self-intersecting split it up into a list of freshly allocated - plines in out. O(n^2) */ -void pcb_pline_split_selfint(const pcb_pline_t *pl, vtp0_t *out); - - -pcb_cardinal_t pcb_polyarea_split_selfint(pcb_polyarea_t *pa); - - - Index: trunk/src/librnd/poly/offset.c =================================================================== --- trunk/src/librnd/poly/offset.c (nonexistent) +++ trunk/src/librnd/poly/offset.c (revision 29285) @@ -0,0 +1,428 @@ +/* + * COPYRIGHT + * + * pcb-rnd, interactive printed circuit board design + * Copyright (C) 2017,2019 Tibor 'Igor2' Palinkas + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Contact: + * Project page: http://repo.hu/projects/pcb-rnd + * lead developer: http://repo.hu/projects/pcb-rnd/contact.html + * mailing list: pcb-rnd (at) list.repo.hu (send "subscribe") + */ + +/* Polygon contour offset calculation */ + +#include +#include +#include +#include +#include + +#if 0 +#define pcbo_trace pcb_trace +#else +static void pcbo_trace(char *fmt, ...) {} +#endif + +void pcb_polo_norm(double *nx, double *ny, pcb_coord_t x1, pcb_coord_t y1, pcb_coord_t x2, pcb_coord_t y2) +{ + double dx = x2 - x1, dy = y2 - y1, len = sqrt(dx*dx + dy*dy); + *nx = -dy / len; + *ny = dx / len; +} + +void pcb_polo_normd(double *nx, double *ny, double x1, double y1, double x2, double y2) +{ + double dx = x2 - x1, dy = y2 - y1, len = sqrt(dx*dx + dy*dy); + *nx = -dy / len; + *ny = dx / len; +} + +static long warp(long n, long len) +{ + if (n < 0) n += len; + else if (n >= len) n -= len; + return n; +} + +void pcb_polo_edge_shift(double offs, + double *x0, double *y0, double nx, double ny, + double *x1, double *y1, + double prev_x, double prev_y, double prev_nx, double prev_ny, + double next_x, double next_y, double next_nx, double next_ny) +{ + double ax, ay, al, a1l, a1x, a1y; + + offs = -offs; + + /* previous edge's endpoint offset */ + ax = (*x0) - prev_x; + ay = (*y0) - prev_y; + al = sqrt(ax*ax + ay*ay); + ax /= al; + ay /= al; + a1l = ax*nx + ay*ny; + a1x = offs / a1l * ax; + a1y = offs / a1l * ay; + + (*x0) += a1x; + (*y0) += a1y; + + /* next edge's endpoint offset */ + ax = next_x - (*x1); + ay = next_y - (*y1); + al = sqrt(ax*ax + ay*ay); + ax /= al; + ay /= al; + + a1l = ax*nx + ay*ny; + a1x = offs / a1l * ax; + a1y = offs / a1l * ay; + + (*x1) += a1x; + (*y1) += a1y; +} + +void pcb_polo_offs(double offs, pcb_polo_t *pcsh, long num_pts) +{ + long n; + + for(n = 0; n < num_pts; n++) { + long np = warp(n-1, num_pts), nn1 = warp(n+1, num_pts), nn2 = warp(n+2, num_pts); + pcb_polo_edge_shift(offs, + &pcsh[n].x, &pcsh[n].y, pcsh[n].nx, pcsh[n].ny, + &pcsh[nn1].x, &pcsh[nn1].y, + pcsh[np].x, pcsh[np].y, pcsh[np].nx, pcsh[np].ny, + pcsh[nn2].x, pcsh[nn2].y, pcsh[nn2].nx, pcsh[nn2].ny + ); + } +} + + +void pcb_polo_norms(pcb_polo_t *pcsh, long num_pts) +{ + long n; + + for(n = 0; n < num_pts; n++) { + long nn = warp(n+1, num_pts); + pcb_polo_normd(&pcsh[n].nx, &pcsh[n].ny, pcsh[n].x, pcsh[n].y, pcsh[nn].x, pcsh[nn].y); + } +} + +double pcb_polo_2area(pcb_polo_t *pcsh, long num_pts) +{ + double a = 0; + long n; + + for(n = 0; n < num_pts-1; n++) { + long nn = warp(n+1, num_pts); + a += pcsh[n].x * pcsh[nn].y; + a -= pcsh[n].y * pcsh[nn].x; + } + return a; +} + +void pcb_pline_dup_offsets(vtp0_t *dst, const pcb_pline_t *src, pcb_coord_t offs) +{ + const pcb_vnode_t *v; + pcb_vector_t tmp; + pcb_pline_t *res = NULL; + long num_pts, n, from; + pcb_polo_t *pcsh; + + /* count corners */ + v = src->head; + num_pts = 0; + do { + num_pts++; + } while((v = v->next) != src->head); + + /* allocate the cache and copy all data */ + pcsh = malloc(sizeof(pcb_polo_t) * num_pts); + for(n = 0, v = src->head; n < num_pts; n++, v = v->next) { + pcsh[n].x = v->point[0]; + pcsh[n].y = v->point[1]; + pcb_polo_norm(&pcsh[n].nx, &pcsh[n].ny, v->point[0], v->point[1], v->next->point[0], v->next->point[1]); + } + + /* offset the cache */ + pcb_polo_offs(offs, pcsh, num_pts); + + + /* create a new pline by copying the cache */ + tmp[0] = pcb_round(pcsh[0].x); + tmp[1] = pcb_round(pcsh[0].y); + res = pcb_poly_contour_new(tmp); + for(n = 1; n < num_pts; n++) { + tmp[0] = pcb_round(pcsh[n].x); + tmp[1] = pcb_round(pcsh[n].y); + pcb_poly_vertex_include(res->head->prev, pcb_poly_node_create(tmp)); + } + + free(pcsh); + + from = dst->used; + if (pcb_pline_is_selfint(res)) { + pcb_pline_split_selfint(res, dst); + pcb_poly_contour_del(&res); + } + else + vtp0_append(dst, res); + + for(n = from; n < dst->used; n++) { + res = dst->array[n]; + pcb_poly_contour_pre(res, 1); + pcb_pline_keepout_offs(res, src, offs); /* avoid self-intersection */ + res->tree = pcb_poly_make_edge_tree(res); + dst->array[n] = res; + } +} + +pcb_pline_t *pcb_pline_dup_offset(const pcb_pline_t *src, pcb_coord_t offs) +{ + vtp0_t selfi; + pcb_pline_t *res = NULL; + int n; + double best = 0; + + vtp0_init(&selfi); + pcb_pline_dup_offsets(&selfi, src, offs); + + for(n = 0; n < selfi.used; n++) { + pcb_pline_t *pl = selfi.array[n]; + if (pl->area > best) { + best = pl->area; + res = pl; + } + } + pcbo_trace("best area: %f out of %d\n", best, selfi.used); + for(n = 0; n < selfi.used; n++) { + pcb_pline_t *pl = selfi.array[n]; + if (res != pl) + pcb_poly_contour_del(&pl); + } + vtp0_uninit(&selfi); + return res; +} + + +TODO("this should be coming from gengeo2d"); +/* Return the square of distance between point x0;y0 and line x1;y1 - x2;y2 */ +static double dist_line_to_pt(double x0, double y0, double x1, double y1, double x2, double y2, double *odx, double *ody) +{ + double ax = x0 - x1, ay = y0 - y1; + double dx = x2 - x1, dy = y2 - y1; + double len = sqrt(dx*dx+dy*dy); + double o, dxn, dyn; + double tmp1, d2; + + + dxn = dx / len; + dyn = dy / len; + + o = (ax * dxn + ay * dyn) / len; + if (o <= 0.0) { + /* beyond x1;y1 */ + return ax * ax + ay * ay; + } + if (o >= 1.0) { + /* beyond x1;y1 */ + double bx = x0 - x2, by = y0 - y2; + return bx * bx + by * by; + } + + /* in range: normal line-point dist */ + tmp1 = dy*x0 - dx*y0 + x2*y1 - y2*x1; + d2 = dx*dx + dy*dy; + + *odx = dxn; + *ody = dyn; + return (tmp1 * tmp1) / d2; +} + +/* Modify v, pulling it back toward vp so that the distance to line ldx;ldy is increased by tune */ +PCB_INLINE int pull_back(pcb_vnode_t *v, const pcb_vnode_t *vp, double tune, double ldx, double ldy, double prjx, double prjy, int inside) +{ + pcb_coord_t ox, oy; + double c, vx, vy, vlen, prx, pry, prlen; + + vx = v->point[0] - vp->point[0]; + vy = v->point[1] - vp->point[1]; + if ((vx == 0) && (vy == 0)) + return -1; + + vlen = sqrt(vx*vx + vy*vy); + vx /= vlen; + vy /= vlen; + + prx = v->point[0] - prjx; + pry = v->point[1] - prjy; + prlen = sqrt(prx*prx + pry*pry); + prx /= prlen; + pry /= prlen; + + c = (ldy * vx - ldx * vy); + if ((c < 0.0001) && (c > -0.0001)) { + pcbo_trace(" par1: vp=%.12mm;%.12mm v=%.12mm;%.12mm\n", vp->point[0], vp->point[1], v->point[0], v->point[1]); + pcbo_trace(" par2: vx=%f;%f ld=%f;%f\n", vx, vy, ldx, ldy); + return -1; /* perpendicular; no pullbakc could help */ + } + + c = tune * ((-pry * ldx + prx * ldy) / c); + + pcbo_trace(" vect: vp=%mm;%mm v=%mm;%mm\n", vp->point[0], vp->point[1], v->point[0], v->point[1]); + pcbo_trace(" vect: vx=%f;%f prx=%f;%f tune=%.012mm\n", vx, vy, prx, pry, (pcb_coord_t)tune); + pcbo_trace(" MOVE: c=%.012mm (%f) %mm;%mm\n", (pcb_coord_t)c, c, (pcb_coord_t)(v->point[0] + c * vx), (pcb_coord_t)(v->point[1] + c * vy)); + + if (c < 0) { + v->point[0] = vp->point[0]; + v->point[1] = vp->point[1]; + return 0; /* not enough room - cut back line to zero length so it gets removed */ + } + + if (inside) + c = -c; + ox = v->point[0]; oy = v->point[1]; + v->point[0] = pcb_round(v->point[0] + c * vx); + v->point[1] = pcb_round(v->point[1] + c * vy); + + if ((ox == v->point[0]) && (oy == v->point[1])) + return -1; /* too close, can't pull any more */ + + return 0; +} + +void pcb_pline_keepout_offs(pcb_pline_t *dst, const pcb_pline_t *src, pcb_coord_t offs) +{ + pcb_vnode_t *v; + double offs2 = (double)offs * (double)offs; + int negoffs = offs < 0; + + if (offs < 0) + offs = -offs; + + if (offs2 > dst->area) + return; /* degenerate case: polygon too small */ + + /* there are two ways dst can get too close to src: */ + + /* case #1: a point in dst is too close to a line in src */ + v = dst->head; + do { + pcb_rtree_it_t it; + pcb_rtree_box_t pb; + void *seg; + int inside = 0; + + + retry:; + pb.x1 = v->point[0] - offs+1; pb.y1 = v->point[1] - offs+1; + pb.x2 = v->point[0] + offs-1; pb.y2 = v->point[1] + offs-1; + if (!negoffs) + inside = pcb_poly_contour_inside(src, v->point); + + for(seg = pcb_rtree_first(&it, src->tree, &pb); seg != NULL; seg = pcb_rtree_next(&it)) { + pcb_coord_t x1, y1, x2, y2; + double dist, tune, prjx, prjy, dx, dy, ax, ay, dotp, prevx, prevy, prevl; + + pcb_polyarea_get_tree_seg(seg, &x1, &y1, &x2, &y2); + dist = dist_line_to_pt(v->point[0], v->point[1], x1, y1, x2, y2, &dx, &dy); + if ((offs2 - dist) > 10) { + pcb_vector_t nv_; + pcb_vnode_t *nv; + + /* calculate x0;y0 projected onto the line */ + ax = v->point[0] - x1; + ay = v->point[1] - y1; + dotp = ax * dx + ay * dy; + prjx = x1 + dx * dotp; + prjy = y1 + dy * dotp; + pcbo_trace("dotp=%f dx=%f dy=%f res: %mm %mm inside=%d\n", dotp, dx, dy, (pcb_coord_t)prjx, (pcb_coord_t)prjy, inside); + + /* this is how much the point needs to be moved away from the line */ + if (inside) + tune = offs + sqrt(dist); + else + tune = offs - sqrt(dist); + if (tune < 5) + continue; + + pcbo_trace("close: %mm;%mm to %mm;%mm %mm;%mm: tune=%.012mm prj: %mm;%mm\n", v->point[0], v->point[1], x1, y1, x2, y2, (pcb_coord_t)tune, (pcb_coord_t)prjx, (pcb_coord_t)prjy); + pcbo_trace(" tune=%.012mm dist=%.012mm\n", (pcb_coord_t)tune, (pcb_coord_t)sqrt(dist)); + + + /* corner case: if next segment is parallel to what we are compesing to + (chamfed V with bottom horizontal being too close to target horizontal line), + do not insert a new point because that would retain the horizontal line + which can not be moved because it is parallel to the target line */ + prevx = v->prev->point[0] - v->point[0]; + prevy = v->prev->point[1] - v->point[1]; + prevl = sqrt(prevx*prevx + prevy*prevy); + prevx /= prevl; + prevy /= prevl; + + if (((prevx == dx) || (prevx == -dx)) && ((prevy == dy) || (prevy == -dy))) { + /* apply direct shift of the whole parallel line */ + v->point[0] = pcb_round(v->point[0] + prjx * tune); + v->point[1] = pcb_round(v->point[1] + prjy * tune); + v->prev->point[0] = pcb_round(v->prev->point[0] + prjx * tune); + v->prev->point[1] = pcb_round(v->prev->point[1] + prjy * tune); + v = v->next; + goto retry; + } + + nv_[0] = v->point[0]; + nv_[1] = v->point[1]; + nv = pcb_poly_node_create(nv_); + pcb_poly_vertex_include_force(v, nv); + + if (pull_back(v, v->prev, tune, dx, dy, prjx, prjy, inside) != 0) { + pcb_poly_vertex_exclude(dst, nv); + v = v->next; + goto retry; + } + + if (pull_back(nv, nv->next, tune, dx, dy, prjx, prjy, inside) != 0) { + pcb_poly_vertex_exclude(dst, nv); + v = v->next; + goto retry; + } + + v = v->next; + goto retry; + } + } + } while((v = v->next) != dst->head); + + /* case #2: a line in dst is too close to a point in src */ + + + /* cleanup: remove redundant points */ + v = dst->head; + do { + if ((v->prev->point[0] == v->point[0]) && (v->prev->point[1] == v->point[1])) { + if (v->prev == dst->head) { + pcb_vnode_t *nv = v->next; + pcb_poly_vertex_exclude(dst, v); + v = nv; + continue; + } + pcb_poly_vertex_exclude(dst, v->prev); + } + } while((v = v->next) != dst->head); +} + Index: trunk/src/librnd/poly/offset.h =================================================================== --- trunk/src/librnd/poly/offset.h (nonexistent) +++ trunk/src/librnd/poly/offset.h (revision 29285) @@ -0,0 +1,67 @@ +/* + * COPYRIGHT + * + * pcb-rnd, interactive printed circuit board design + * Copyright (C) 2017,2019 Tibor 'Igor2' Palinkas + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Contact: + * Project page: http://repo.hu/projects/pcb-rnd + * lead developer: http://repo.hu/projects/pcb-rnd/contact.html + * mailing list: pcb-rnd (at) list.repo.hu (send "subscribe") + */ + +/* Polygon contour offset calculation */ + +#include + + +/* Calculate the offset plines of src and append the resulting plines to dst. + Yields multiple islands in some corner cases. */ +void pcb_pline_dup_offsets(vtp0_t *dst, const pcb_pline_t *src, pcb_coord_t offs); + +/* Same, but returns the largest island only */ +pcb_pline_t *pcb_pline_dup_offset(const pcb_pline_t *src, pcb_coord_t offs); + + +/* low level */ + +typedef struct { + double x, y, nx, ny; +} pcb_polo_t; + +/* Calculate the normal vectors of a cache */ +void pcb_polo_norms(pcb_polo_t *pcsh, long num_pts); + +/* Calculate and return the double of the area of a cached polygon */ +double pcb_polo_2area(pcb_polo_t *pcsh, long num_pts); + +/* Ortho-shift all edges of a polygon. Positive offset means grow. */ +void pcb_polo_offs(double offs, pcb_polo_t *pcsh, long num_pts); + +/* modify dst so it is at least offs far from any point or line of src */ +void pcb_pline_keepout_offs(pcb_pline_t *dst, const pcb_pline_t *src, pcb_coord_t offs); + +/* Orhto-shift an edge specified by x0;y0 and x1;y1. Calculate the new + edge points by extending/shrinking the previous and next line segment. + Modifies the target edge's start and end coords. Requires cached normals + Positive offset means grow. */ +void pcb_polo_edge_shift(double offs, + double *x0, double *y0, double nx, double ny, + double *x1, double *y1, + double prev_x, double prev_y, double prev_nx, double prev_ny, + double next_x, double next_y, double next_nx, double next_ny); + Index: trunk/src/librnd/poly/self_isc.c =================================================================== --- trunk/src/librnd/poly/self_isc.c (nonexistent) +++ trunk/src/librnd/poly/self_isc.c (revision 29285) @@ -0,0 +1,336 @@ +/* + * COPYRIGHT + * + * pcb-rnd, interactive printed circuit board design + * Copyright (C) 2018,2019 Tibor 'Igor2' Palinkas + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Contact: + * Project page: http://repo.hu/projects/pcb-rnd + * lead developer: http://repo.hu/projects/pcb-rnd/contact.html + * mailing list: pcb-rnd (at) list.repo.hu (send "subscribe") + */ + +#include "config.h" +#include +#include +#include +#include +#include + +/* expect no more than this number of hubs in a complex polygon */ +#define MAX_HUB_TRIES 1024 + +TODO("convert this into an enum") +#define UNKNWN 0 + + +#if 0 +# define TRACE pcb_trace +#else + void TRACE(const char *fmt, ...) {} +#endif + +typedef struct { + vtp0_t node; +} vhub_t; + +static pcb_vnode_t *pcb_pline_split(pcb_vnode_t *v, pcb_vector_t at) +{ + pcb_vnode_t *v2 = pcb_poly_node_add_single(v, at); + + v2 = pcb_poly_node_create(at); + assert(v2 != NULL); + v2->cvc_prev = v2->cvc_next = NULL; + v2->Flags.status = UNKNWN; + + /* link in */ + v->next->prev = v2; + v2->next = v->next; + v2->prev = v; + v->next = v2; + + return v2; +} + +static pcb_vnode_t *pcb_pline_end_at(pcb_vnode_t *v, pcb_vector_t at) +{ + if (pcb_vect_dist2(at, v->point) < PCB_POLY_ENDP_EPSILON) + return v; + if (pcb_vect_dist2(at, v->next->point) < PCB_POLY_ENDP_EPSILON) + return v->next; + return NULL; +} + +static vhub_t *hub_find(vtp0_t *hubs, pcb_vnode_t *v, pcb_bool insert) +{ + int n, m; + + for(n = 0; n < vtp0_len(hubs); n++) { + vhub_t *h = *vtp0_get(hubs, n, 0); + pcb_vnode_t *stored, **st; + st = (pcb_vnode_t **)vtp0_get(&h->node, 0, 0); + if (st == NULL) continue; + stored = *st; + /* found the hub at the specific location */ + if (pcb_vect_dist2(stored->point, v->point) < PCB_POLY_ENDP_EPSILON) { + for(m = 0; m < vtp0_len(&h->node); m++) { + st = (pcb_vnode_t **)vtp0_get(&h->node, m, 0); + if (st != NULL) { + stored = *st; + if (stored == v) /* already on the list */ + return h; + } + } + /* not found on the hub's list, maybe insert */ + if (insert) { + vtp0_append(&h->node, v); + return h; + } + return NULL; /* there is only one hub per point - if the coord matched and the node is not on, it's not going to be on any other hub's list */ + } + } + return NULL; +} + +/* remove v from h; if h has only one node, remove that too */ +static void remove_from_hub(vhub_t *h, pcb_vnode_t *v) +{ + int m; + pcb_vnode_t *stored, **st; + + for(m = 0; m < vtp0_len(&h->node); m++) { + st = (pcb_vnode_t **)vtp0_get(&h->node, m, 0); + if (st == NULL) { + vtp0_remove(&h->node, m, 1); + m--; + continue; + } + stored = *st; + if (stored == v) { + vtp0_remove(&h->node, m, 1); + m--; + v->Flags.in_hub = 0; + } + } + + /* only one node remains: this is no longer a hub! */ + if (h->node.used == 1) { + stored = *vtp0_get(&h->node, 0, 0); /* the previous loop guarantees it can not be NULL */ + vtp0_remove(&h->node, 0, 1); + stored->Flags.in_hub = 0; + } +} + +/* returns 1 if a new intersection is mapped */ +static int pcb_pline_add_isectp(vtp0_t *hubs, pcb_vnode_t *v) +{ + vhub_t *h; + + assert(v != NULL); + + v->Flags.in_hub = 1; + if (hubs->array != NULL) { + if (hub_find(hubs, v, pcb_true) != NULL) /* already on the list (... by now) */ + return 0; + } + + h = malloc(sizeof(vhub_t)); + vtp0_append(hubs, h); + vtp0_init(&h->node); + vtp0_append(&h->node, v); + return 1; +} + +static int pline_split_off_loop_new(pcb_pline_t *pl, vtp0_t *out, vhub_t *h, pcb_vnode_t *start, pcb_cardinal_t cnt) +{ + pcb_pline_t *newpl = NULL; + pcb_vnode_t *v, *next, *tmp; + + newpl = pcb_poly_contour_new(start->point); + next = start->next; + remove_from_hub(h, start); + pcb_poly_vertex_exclude(pl, start); + for(v = next; cnt > 0; v = next, cnt--) { + TRACE(" Append %mm %mm!\n", v->point[0], v->point[1]); + next = v->next; + pcb_poly_vertex_exclude(pl, v); + tmp = pcb_poly_node_create(v->point); + pcb_poly_vertex_include(newpl->head->prev, tmp); + } + +TRACE("APPEND: %p %p\n", newpl, newpl->head->next); + vtp0_append(out, newpl); + return 1; +} + +static int pline_split_off_loop(pcb_pline_t *pl, vtp0_t *hubs, vtp0_t *out, vhub_t *h, pcb_vnode_t *start) +{ + pcb_vnode_t *v; + pcb_cardinal_t cnt; + + for(v = start->next, cnt = 0;; v = v->next) { + if (v->Flags.in_hub) { + if (pcb_vect_dist2(start->point, v->point) < PCB_POLY_ENDP_EPSILON) + break; /* found a matching hub point */ + goto skip_to_backward; /* found a different hub point, skip */ + } + cnt++; + } + + /* forward loop */ + TRACE(" Fwd %ld!\n", (long)cnt); + return pline_split_off_loop_new(pl, out, h, start, cnt); + + skip_to_backward:; + for(v = start->prev, cnt = 0;; v = v->prev) { + if (v->Flags.in_hub) { + if (pcb_vect_dist2(start->point, v->point) < PCB_POLY_ENDP_EPSILON) { + start = v; + break; /* found a matching hub point */ + } + return 0; /* found a different hub point, skip */ + } + cnt++; + } + + TRACE(" Bwd %ld!\n", (long)cnt); + return pline_split_off_loop_new(pl, out, h, start, cnt); +} + +pcb_bool pcb_pline_is_selfint(pcb_pline_t *pl) +{ + pcb_vnode_t *va, *vb; + + va = (pcb_vnode_t *)pl->head; + do { + for(vb = va->next->next; vb->next != va; vb = vb->next) { + pcb_vector_t i, tmp; + if (pcb_vect_inters2(va->point, va->next->point, vb->point, vb->next->point, i, tmp) > 0) + return pcb_true; + } + va = va->next; + } while (va != pl->head); + return pcb_false; +} + + +void pcb_pline_split_selfint(const pcb_pline_t *pl_in, vtp0_t *out) +{ + int n; + vtp0_t hubs; + pcb_pline_t *pl = NULL; + pcb_vnode_t *va, *vb, *iva, *ivb; + + vtp0_init(&hubs); + + /* copy the pline and reset the in_hub flag */ + pcb_poly_contour_copy(&pl, pl_in); + va = (pcb_vnode_t *)pl->head; + do { + va->Flags.in_hub = 0; + va = va->next; + } while (va != pl->head); + + /* insert corners at intersections, collect a list of intersection hubs */ + va = (pcb_vnode_t *)pl->head; + do { + for(vb = va->next->next; vb->next != va; vb = vb->next) { + pcb_vector_t i, tmp; + if (pcb_vect_inters2(va->point, va->next->point, vb->point, vb->next->point, i, tmp) > 0) { + iva = pcb_pline_end_at(va, i); + if (iva == NULL) + iva = pcb_pline_split(va, i); + ivb = pcb_pline_end_at(vb, i); + if (ivb == NULL) + ivb = pcb_pline_split(vb, i); + if (pcb_pline_add_isectp(&hubs, iva) || pcb_pline_add_isectp(&hubs, ivb)) + TRACE("Intersect at %mm;%mm\n", i[0], i[1]); + } + } + va = va->next; + } while (va != pl->head); + + /*for(t = MAX_HUB_TRIES; t > 0; t--)*/ { + retry:; + for(n = 0; n < vtp0_len(&hubs); n++) { + int m; + vhub_t *h = *vtp0_get(&hubs, n, 0); + pcb_vnode_t *v, **v_ = (pcb_vnode_t **)vtp0_get(&h->node, 0, 0); + if (v_ == NULL) continue; + v = *v_; + TRACE("hub %p at %mm;%mm:\n", h, v->point[0], v->point[1]); + for(m = 0; m < vtp0_len(&h->node); m++) { + v = *vtp0_get(&h->node, m, 0); + TRACE(" %d=%p\n", m, v); + /* try to split off a leaf loop from the hub */ + + if (pline_split_off_loop(pl, &hubs, out, h, v)) + goto retry; + } + TRACE("\n"); + } + } + + /* what's left by now is a single loop, with all hubs already removed */ + vtp0_append(out, pl); + +TODO("leak: remove the unused hubs"); + vtp0_uninit(&hubs); +} + +pcb_cardinal_t pcb_polyarea_split_selfint(pcb_polyarea_t *pa) +{ + pcb_pline_t *pl, *next, *pln, *prev = NULL; + pcb_cardinal_t cnt = 0; + + for(pl = pa->contours; pl != NULL; pl = next) { + next = pl->next; + if (pcb_pline_is_selfint(pl)) { + vtp0_t pls; + int n; + cnt++; + vtp0_init(&pls); + pcb_pline_split_selfint(pl, &pls); + + + if (prev != NULL) + prev->next = next; + else + pa->contours = next; + + for(n = 0; n < pls.used; n++) { + pln = (pcb_pline_t *)pls.array[n]; + pcb_poly_contour_pre(pln, pcb_true); + if (pln->Flags.orient != pl->Flags.orient) + pcb_poly_contour_inv(pln); + pcb_poly_contour_pre(pln, 0); + pln->tree = pcb_poly_make_edge_tree(pln); + pcb_polyarea_contour_include(pa, pln); + cnt++; + } + + pcb_poly_contour_del(&pl); + cnt--; + + vtp0_uninit(&pls); + } + else + prev = pl; + } + + return cnt; +} Index: trunk/src/librnd/poly/self_isc.h =================================================================== --- trunk/src/librnd/poly/self_isc.h (nonexistent) +++ trunk/src/librnd/poly/self_isc.h (revision 29285) @@ -0,0 +1,43 @@ +/* + * COPYRIGHT + * + * pcb-rnd, interactive printed circuit board design + * Copyright (C) 2018,2019 Tibor 'Igor2' Palinkas + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Contact: + * Project page: http://repo.hu/projects/pcb-rnd + * lead developer: http://repo.hu/projects/pcb-rnd/contact.html + * mailing list: pcb-rnd (at) list.repo.hu (send "subscribe") + */ + +/* Resolve polygon self intersections */ + +#include +#include + +/* Returns whether a polyline is self-intersecting. O(n^2) */ +pcb_bool pcb_pline_is_selfint(pcb_pline_t *pl); + +/* Assume pl is self-intersecting split it up into a list of freshly allocated + plines in out. O(n^2) */ +void pcb_pline_split_selfint(const pcb_pline_t *pl, vtp0_t *out); + + +pcb_cardinal_t pcb_polyarea_split_selfint(pcb_polyarea_t *pa); + + + Index: trunk/src/obj_poly.c =================================================================== --- trunk/src/obj_poly.c (revision 29284) +++ trunk/src/obj_poly.c (revision 29285) @@ -36,7 +36,7 @@ #include "undo.h" #include "polygon.h" #include -#include +#include #include "rotate.h" #include "search.h" #include Index: trunk/src/obj_pstk.c =================================================================== --- trunk/src/obj_pstk.c (revision 29284) +++ trunk/src/obj_pstk.c (revision 29285) @@ -48,7 +48,7 @@ #include "vtpadstack.h" #include #include -#include +#include #define SQR(o) ((o)*(o)) Index: trunk/src/obj_pstk_proto.c =================================================================== --- trunk/src/obj_pstk_proto.c (revision 29284) +++ trunk/src/obj_pstk_proto.c (revision 29285) @@ -41,7 +41,7 @@ #include "vtpadstack_t.h" #include "obj_hash.h" #include "funchash_core.h" -#include +#include static const char core_proto_cookie[] = "padstack prototypes"; Index: trunk/src/obj_text.c =================================================================== --- trunk/src/obj_text.c (revision 29284) +++ trunk/src/obj_text.c (revision 29285) @@ -38,7 +38,7 @@ #include #include "undo.h" #include "polygon.h" -#include +#include #include #include "layer.h" Index: trunk/src/polygon.c =================================================================== --- trunk/src/polygon.c (revision 29284) +++ trunk/src/polygon.c (revision 29285) @@ -50,7 +50,7 @@ #include "layer.h" #include "obj_poly_draw.h" #include "obj_text_draw.h" -#include +#include #include #include Index: trunk/src_plugins/io_autotrax/write.c =================================================================== --- trunk/src_plugins/io_autotrax/write.c (revision 29284) +++ trunk/src_plugins/io_autotrax/write.c (revision 29285) @@ -35,7 +35,7 @@ #include "data.h" #include "write.h" #include "layer.h" -#include +#include #include "../lib_polyhelp/polyhelp.h" #include "../src_plugins/lib_compat_help/pstk_compat.h" Index: trunk/src_plugins/io_dsn/read.c =================================================================== --- trunk/src_plugins/io_dsn/read.c (revision 29284) +++ trunk/src_plugins/io_dsn/read.c (revision 29285) @@ -45,7 +45,7 @@ #include #include #include "netlist.h" -#include +#include #include "read.h" Index: trunk/src_plugins/lib_polyhelp/polyhelp.c =================================================================== --- trunk/src_plugins/lib_polyhelp/polyhelp.c (revision 29284) +++ trunk/src_plugins/lib_polyhelp/polyhelp.c (revision 29285) @@ -35,7 +35,7 @@ #include #include "obj_line.h" #include -#include +#include #include #include "topoly.h"