Index: trunk/src/Makefile.dep =================================================================== --- trunk/src/Makefile.dep (revision 15296) +++ trunk/src/Makefile.dep (revision 15297) @@ -1653,12 +1653,12 @@ buffer.h obj_subc_list.h obj_subc.h ../src_3rd/libminuid/libminuid.h \ rtree.h rtree2.h ../src_3rd/genrtree/genrtree_api.h rtree2_compat.h \ ht_subc.h vtpadstack.h obj_pstk_shape.h polygon.h vtpadstack_t.h \ - action_helper.h crosshair.h layer.h pcb-printf.h clip.h event.h error.h \ - plugins.h ../src_3rd/puplug/puplug.h ../src_3rd/puplug/libs.h \ - ../src_3rd/puplug/os_dep.h ../src_3rd/puplug/config.h \ - ../src_3rd/puplug/libs.h ../src_3rd/puplug/error.h safe_fs.h hid.h \ - hid_nogui.h hid_draw_helpers.h hid_cfg.h \ - ../src_plugins/hid_lesstif/lesstif.h hid_cfg_input.h \ + action_helper.h crosshair.h conf_hid.h layer.h pcb-printf.h clip.h \ + event.h error.h plugins.h ../src_3rd/puplug/puplug.h \ + ../src_3rd/puplug/libs.h ../src_3rd/puplug/os_dep.h \ + ../src_3rd/puplug/config.h ../src_3rd/puplug/libs.h \ + ../src_3rd/puplug/error.h safe_fs.h hid.h hid_nogui.h hid_draw_helpers.h \ + hid_cfg.h ../src_plugins/hid_lesstif/lesstif.h hid_cfg_input.h \ ../src_3rd/genht/htpp.h hid_cfg.h compat_nls.h board.h vtroutestyle.h \ library.h rats_patch.h board.h hid_attrib.h hid_helper.h hid_init.h \ hid_color.h hid_extents.h hid_flags.h hid_actions.h \ @@ -7220,13 +7220,14 @@ ht_subc.h vtpadstack.h obj_pstk_shape.h polygon.h vtpadstack_t.h draw.h \ remove.h search.h rats.h netlist.h route_style.h thermal.h undo.h \ ../src_3rd/libuundo/uundo.h undo_old.h compat_nls.h obj_all.h \ - obj_poly_draw.h polygon_offs.c + obj_poly_draw.h polygon_selfi.h polygon_offs.c polygon1.o: polygon1.c ../config.h rtree.h global_typedefs.h pcb_bool.h \ unit.h rtree2.h ../src_3rd/genrtree/genrtree_api.h rtree2_compat.h \ math_helper.h heap.h compat_cc.h pcb-printf.h \ ../src_3rd/genvector/gds_char.h ../src_3rd/genvector/genvector_impl.h \ ../src_3rd/genvector/genvector_undef.h polyarea.h obj_common.h flag.h \ - globalconst.h attrib.h data_parent.h macro.h box.h move.h misc_util.h + globalconst.h attrib.h data_parent.h macro.h box.h move.h misc_util.h \ + polygon_selfi.c polygon_selfi.h ../src_3rd/genvector/vtp0.h polygon_act.o: polygon_act.c ../config.h conf_core.h conf.h \ global_typedefs.h pcb_bool.h unit.h pcb-printf.h \ ../src_3rd/genvector/gds_char.h ../src_3rd/genvector/genvector_impl.h \ Index: trunk/src/polyarea.h =================================================================== --- trunk/src/polyarea.h (revision 15296) +++ trunk/src/polyarea.h (revision 15297) @@ -59,6 +59,7 @@ struct { unsigned int status:3; unsigned int mark:1; + unsigned int in_hub:1; } Flags; pcb_cvc_list_t *cvc_prev; pcb_cvc_list_t *cvc_next; Index: trunk/src/polygon.c =================================================================== --- trunk/src/polygon.c (revision 15296) +++ trunk/src/polygon.c (revision 15297) @@ -51,6 +51,7 @@ #include "compat_nls.h" #include "obj_all.h" #include "obj_poly_draw.h" +#include "polygon_selfi.h" #define ROUND(x) ((long)(((x) >= 0 ? (x) + 0.5 : (x) - 0.5))) @@ -250,7 +251,27 @@ pcb_poly_contour_inv(contour); assert(contour->Flags.orient == (hole ? PCB_PLF_INV : PCB_PLF_DIR)); - pcb_polyarea_contour_include(np, contour); + /* attempt to auto-correct simple self intersecting cases */ + if (0 && pcb_pline_is_selfint(contour)) { + vtp0_t islands; + int n; + + /* most probably self intersecting polygon - attempt to fix it */ + vtp0_init(&islands); + pcb_pline_split_selfint(contour, &islands); + for(n = 0; n < vtp0_len(&islands); n++) { + pcb_pline_t *pl = *vtp0_get(&islands, n, 0); + pcb_poly_contour_pre(pl, pcb_true); + if (pl->Flags.orient != (hole ? PCB_PLF_INV : PCB_PLF_DIR)) + pcb_poly_contour_inv(pl); + assert(pl->Flags.orient == (hole ? PCB_PLF_INV : PCB_PLF_DIR)); + pcb_polyarea_contour_include(np, pl); + } + vtp0_uninit(&islands); + free(contour); + } + else + pcb_polyarea_contour_include(np, contour); contour = NULL; assert(pcb_poly_valid(np)); Index: trunk/src/polygon1.c =================================================================== --- trunk/src/polygon1.c (revision 15296) +++ trunk/src/polygon1.c (revision 15297) @@ -3547,6 +3547,7 @@ } } +#include "polygon_selfi.c" /* how about expanding polygons so that edges can be arcs rather than * lines. Consider using the third coordinate to store the radius of the Index: trunk/src/polygon_selfi.c =================================================================== --- trunk/src/polygon_selfi.c (nonexistent) +++ trunk/src/polygon_selfi.c (revision 15297) @@ -0,0 +1,241 @@ +/* + * COPYRIGHT + * + * pcb-rnd, interactive printed circuit board design + * Copyright (C) 2018 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: email to pcb-rnd (at) igor2.repo.hu + * mailing list: pcb-rnd (at) list.repo.hu (send "subscribe") + */ + +#include "config.h" +#include "polygon_selfi.h" + +/* expect no more than this number of hubs in a complex polygon */ +#define MAX_HUB_TRIES 1024 + +#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 = 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) < ENDP_EPSILON) + return v; + if (pcb_vect_dist2(at, v->next->point) < 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; + vhub_t *h; + + for(n = 0, h = hubs->array[0]; n < vtp0_len(hubs); n++,h++) { + pcb_vnode_t *stored = *vtp0_get(&h->node, 0, 0); + /* found the hub at the specific location */ + if (pcb_vect_dist2(stored->point, v->point) < ENDP_EPSILON) { + for(m = 0; m < vtp0_len(&h->node); m++) { + stored = *vtp0_get(&h->node, m, 0); + 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; +} + +/* 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(vtp0_t *hubs, vtp0_t *out, vhub_t *h, pcb_vnode_t *start) +{ + pcb_vnode_t *v, *next; + pcb_pline_t *newpl = NULL; + pcb_cardinal_t cnt; + vhub_t *endh; + + for(v = start->next, cnt = 0; v->Flags.in_hub == 0; v = v->next) cnt++; + endh = hub_find(hubs, v, pcb_false); + if (h == endh) { /* forward loop */ + TRACE(" Fwd %ld!\n", (long)cnt); + newpl = pcb_poly_contour_new(start->point); + next = start->next; + pcb_poly_vertex_exclude(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(v); + pcb_poly_vertex_include(newpl->head.prev, v); + } +/* free(start);*/ + goto new_pl; + } + + for(v = start->prev, cnt = 0; v->Flags.in_hub == 0; v = v->prev) cnt++; + if (h == endh) { /* backward loop */ + TRACE(" Bwd %ld!\n", (long)cnt); + newpl = pcb_poly_contour_new(NULL); + newpl->head = *start; + pcb_poly_vertex_exclude(start); + for(v = start->prev; cnt > 0; v = next, cnt--) { + TRACE(" Append!\n"); + next = v->prev; + pcb_poly_vertex_exclude(v); + pcb_poly_vertex_include(start, v); + } + goto new_pl; + } + return 0; + + new_pl:; +TRACE("APPEND: %p %p\n", newpl, newpl->head.next); + vtp0_append(out, newpl); + return 1; +} + +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(pcb_pline_t *pl, vtp0_t *out) +{ + int n, t; + vtp0_t hubs; + pcb_vnode_t *va, *vb, *iva, *ivb; + + vtp0_init(&hubs); + + /* reset the in_hub flag */ + 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--)*/ { + + for(n = 0; n < vtp0_len(&hubs); n++) { + int m; + vhub_t *h = *vtp0_get(&hubs, n, 0); + pcb_vnode_t *v = *vtp0_get(&h->node, 0, 0); + 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(&hubs, out, h, v)) { + vtp0_remove(&h->node, m, 1); + m--; + if (vtp0_len(&h->node) == 0) { + vtp0_uninit(&h->node); + free(h); + vtp0_remove(&hubs, n, 1); + n--; + break; + } + } + } + TRACE("\n"); + } + } + + vtp0_uninit(&hubs); +} Index: trunk/src/polygon_selfi.h =================================================================== --- trunk/src/polygon_selfi.h (nonexistent) +++ trunk/src/polygon_selfi.h (revision 15297) @@ -0,0 +1,41 @@ +/* + * COPYRIGHT + * + * pcb-rnd, interactive printed circuit board design + * Copyright (C) 2018 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: email to pcb-rnd (at) igor2.repo.hu + * mailing list: pcb-rnd (at) list.repo.hu (send "subscribe") + */ + +/* Resolve polygon self intersections */ + +#include +#include "polyarea.h" + +/* 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. Converts the original pline into a version that has a point + on each intersection; O(n^2) */ +void pcb_pline_split_selfint(pcb_pline_t *pl, vtp0_t *out); + +