Index: trunk/scconfig/Rev.h =================================================================== --- trunk/scconfig/Rev.h (revision 34508) +++ trunk/scconfig/Rev.h (revision 34509) @@ -1 +1 @@ -static const int myrev = 34375; +static const int myrev = 34509; Index: trunk/scconfig/Rev.tab =================================================================== --- trunk/scconfig/Rev.tab (revision 34508) +++ trunk/scconfig/Rev.tab (revision 34509) @@ -1,3 +1,4 @@ +34509 configure librnd: moving box-box intersection code to librnd 34375 configure librnd: make sure the local .so symlinks are updated on make all so they don't point to old version .so's 34292 configure move djopt and puller menus from central menufile to plugin menu files 34078 configure new infrastructure: anyload Index: trunk/src/intersect.c =================================================================== --- trunk/src/intersect.c (revision 34508) +++ trunk/src/intersect.c (nonexistent) @@ -1,261 +0,0 @@ -/* - * COPYRIGHT - * - * pcb-rnd, interactive printed circuit board design - * (this file is based on PCB, interactive printed circuit board design) - * Copyright (C) 1994,1995,1996 Thomas Nau - * Copyright (C) 1998,1999,2000,2001 harry eaton - * Copyright (C) 2021 Tibor 'Igor2' Palinkas - * - * this file, intersect.c, was written and is - * Copyright (c) 2001 C. Scott Ananian - * - * 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") - * - * - * Old contact info: - * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA - * haceaton@aplcomm.jhuapl.edu - * - */ - -#include "config.h" - -#include -#include - -#include "intersect.h" -#include - -static int compareleft(const void *ptr1, const void *ptr2); -static int compareright(const void *ptr1, const void *ptr2); -static int comparepos(const void *ptr1, const void *ptr2); -static int nextpwrof2(int i); - -typedef struct { - rnd_coord_t left, right; - int covered; - rnd_coord_t area; -} seg_tree_node_t; - -typedef struct { - seg_tree_node_t *nodes; - int size; -} seg_tree_t; - -typedef struct { - rnd_coord_t *p; - int size; -} location_list_t; - -/* Create a sorted list of unique y coords from an array of boxes. */ -static location_list_t create_sorted_y_list(rnd_box_t *boxes, long len) -{ - location_list_t yCoords; - rnd_coord_t last; - int i, n; - /* create sorted list of Y coordinates */ - yCoords.size = 2 * len; - yCoords.p = (rnd_coord_t *) calloc(yCoords.size, sizeof(*yCoords.p)); - for (i = 0; i < len; i++) { - yCoords.p[2 * i] = boxes[i].Y1; - yCoords.p[2 * i + 1] = boxes[i].Y2; - } - qsort(yCoords.p, yCoords.size, sizeof(*yCoords.p), comparepos); - /* count uniq y coords */ - last = 0; - for (n = 0, i = 0; i < yCoords.size; i++) - if (i == 0 || yCoords.p[i] != last) - yCoords.p[n++] = last = yCoords.p[i]; - yCoords.size = n; - return yCoords; -} - -/* Create an empty segment tree from the given sorted list of uniq y coords. */ -static seg_tree_t createseg_tree_t(rnd_coord_t * yCoords, int N) -{ - seg_tree_t st; - int i; - /* size is twice the nearest larger power of 2 */ - st.size = 2 * nextpwrof2(N); - st.nodes = (seg_tree_node_t *) calloc(st.size, sizeof(*st.nodes)); - /* initialize the rightmost leaf node */ - st.nodes[st.size - 1].left = (N > 0) ? yCoords[--N] : 10; - st.nodes[st.size - 1].right = st.nodes[st.size - 1].left + 1; - /* initialize the rest of the leaf nodes */ - for (i = st.size - 2; i >= st.size / 2; i--) { - st.nodes[i].right = st.nodes[i + 1].left; - st.nodes[i].left = (N > 0) ? yCoords[--N] : st.nodes[i].right - 1; - } - /* initialize the internal nodes */ - for (; i > 0; i--) { /* node 0 is not used */ - st.nodes[i].right = st.nodes[2 * i + 1].right; - st.nodes[i].left = st.nodes[2 * i].left; - } - /* done! */ - return st; -} - -void insertSegment(seg_tree_t * st, int n, rnd_coord_t Y1, rnd_coord_t Y2) -{ - rnd_coord_t discriminant; - if (st->nodes[n].left >= Y1 && st->nodes[n].right <= Y2) { - st->nodes[n].covered++; - } - else { - assert(n < st->size / 2); - discriminant = st->nodes[n * 2 + 1 /*right */ ].left; - if (Y1 < discriminant) - insertSegment(st, n * 2, Y1, Y2); - if (discriminant < Y2) - insertSegment(st, n * 2 + 1, Y1, Y2); - } - /* fixup area */ - st->nodes[n].area = (st->nodes[n].covered > 0) ? - (st->nodes[n].right - st->nodes[n].left) : (n >= st->size / 2) ? 0 : st->nodes[n * 2].area + st->nodes[n * 2 + 1].area; -} - -void deleteSegment(seg_tree_t * st, int n, rnd_coord_t Y1, rnd_coord_t Y2) -{ - rnd_coord_t discriminant; - if (st->nodes[n].left >= Y1 && st->nodes[n].right <= Y2) { - assert(st->nodes[n].covered); - --st->nodes[n].covered; - } - else { - assert(n < st->size / 2); - discriminant = st->nodes[n * 2 + 1 /*right */ ].left; - if (Y1 < discriminant) - deleteSegment(st, n * 2, Y1, Y2); - if (discriminant < Y2) - deleteSegment(st, n * 2 + 1, Y1, Y2); - } - /* fixup area */ - st->nodes[n].area = (st->nodes[n].covered > 0) ? - (st->nodes[n].right - st->nodes[n].left) : (n >= st->size / 2) ? 0 : st->nodes[n * 2].area + st->nodes[n * 2 + 1].area; -} - -/* Compute the area of the intersection of the given rectangles; that is, - * the area covered by more than one rectangle (counted twice if the area is - * covered by three rectangles, three times if covered by four rectangles, - * etc.). - * Runs in O(N ln N) time. - */ -double pcb_intersect_box_box(rnd_box_t *boxes, long len) -{ - rnd_cardinal_t i; - double area = 0.0; - /* first get the aggregate area. */ - for (i = 0; i < len; i++) - area += (double)(boxes[i].X2 - boxes[i].X1) * (double)(boxes[i].Y2 - boxes[i].Y1); - /* intersection area is aggregate - union. */ - return area * 0.0001 - pcb_union_box_box(boxes, len); -} - -/* Compute the area of the union of the given rectangles. O(N ln N) time. */ -double pcb_union_box_box(rnd_box_t *boxes, long len) -{ - rnd_box_t **rectLeft, **rectRight; - rnd_cardinal_t i, j; - location_list_t yCoords; - seg_tree_t segtree; - rnd_coord_t lastX; - double area = 0.0; - - if (len == 0) - return 0.0; - /* create sorted list of Y coordinates */ - yCoords = create_sorted_y_list(boxes, len); - /* now create empty segment tree */ - segtree = createseg_tree_t(yCoords.p, yCoords.size); - free(yCoords.p); - /* create sorted list of left and right X coordinates of rectangles */ - rectLeft = (rnd_box_t **) calloc(len, sizeof(*rectLeft)); - rectRight = (rnd_box_t **) calloc(len, sizeof(*rectRight)); - for (i = 0; i < len; i++) { - assert(boxes[i].X1 <= boxes[i].X2); - assert(boxes[i].Y1 <= boxes[i].Y2); - rectLeft[i] = rectRight[i] = &boxes[i]; - } - qsort(rectLeft, len, sizeof(*rectLeft), compareleft); - qsort(rectRight, len, sizeof(*rectRight), compareright); - /* sweep through x segments from left to right */ - i = j = 0; - lastX = rectLeft[0]->X1; - while (j < len) { - assert(i <= len); - /* i will step through rectLeft, j will through rectRight */ - if (i == len || rectRight[j]->X2 < rectLeft[i]->X1) { - /* right edge of rectangle */ - rnd_box_t *b = rectRight[j++]; - /* check lastX */ - if (b->X2 != lastX) { - assert(lastX < b->X2); - area += (double) (b->X2 - lastX) * segtree.nodes[1].area; - lastX = b->X2; - } - /* remove a segment from the segment tree. */ - deleteSegment(&segtree, 1, b->Y1, b->Y2); - } - else { - /* left edge of rectangle */ - rnd_box_t *b = rectLeft[i++]; - /* check lastX */ - if (b->X1 != lastX) { - assert(lastX < b->X1); - area += (double) (b->X1 - lastX) * segtree.nodes[1].area; - lastX = b->X1; - } - /* add a segment from the segment tree. */ - insertSegment(&segtree, 1, b->Y1, b->Y2); - } - } - free(rectLeft); - free(rectRight); - free(segtree.nodes); - return area * 0.0001; -} - -static int compareleft(const void *ptr1, const void *ptr2) -{ - rnd_box_t **b1 = (rnd_box_t **) ptr1, **b2 = (rnd_box_t **) ptr2; - return (*b1)->X1 - (*b2)->X1; -} - -static int compareright(const void *ptr1, const void *ptr2) -{ - rnd_box_t **b1 = (rnd_box_t **) ptr1, **b2 = (rnd_box_t **) ptr2; - return (*b1)->X2 - (*b2)->X2; -} - -static int comparepos(const void *ptr1, const void *ptr2) -{ - return *((rnd_coord_t *) ptr1) - *((rnd_coord_t *) ptr2); -} - -static int nextpwrof2(int n) -{ - int r = 1; - while (n != 0) { - n /= 2; - r *= 2; - } - return r; -} Index: trunk/src/intersect.h =================================================================== --- trunk/src/intersect.h (revision 34508) +++ trunk/src/intersect.h (nonexistent) @@ -1,50 +0,0 @@ -/* - * COPYRIGHT - * - * pcb-rnd, interactive printed circuit board design - * (this file is based on PCB, interactive printed circuit board design) - * Copyright (C) 1994,1995,1996 Thomas Nau - * Copyright (C) 1998,1999,2000,2001 harry eaton - * Copyright (C) 2021 Tibor 'Igor2' Palinkas - * - * this file, intersect.h, was written and is - * Copyright (c) 2001 C. Scott Ananian. - * - * 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") - * - * - * Old contact info: - * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA - * haceaton@aplcomm.jhuapl.edu - * - */ - - -/* Box (rectangle) intersection/union routines. */ - -#ifndef PCB_INTERSECT_H -#define PCB_INTERSECT_H - -#include - -double pcb_intersect_box_box(rnd_box_t *boxes, long len); /* will sort boxlist */ -double pcb_union_box_box(rnd_box_t *boxes, long len); - -#endif Index: trunk/src/Makefile.dep =================================================================== --- trunk/src/Makefile.dep (revision 34508) +++ trunk/src/Makefile.dep (revision 34509) @@ -570,7 +570,7 @@ ../src_3rd/librnd-local/src/../src_3rd/genht/hash.h obj_pstk_list.h \ obj_pstk.h ../src_3rd/librnd-local/src/../src_3rd/genvector/vtp0.h \ vtpadstack.h obj_pstk_shape.h polygon.h vtpadstack_t.h draw.h layer.h \ - intersect.h move.h netlist.h remove.h operation.h rotate.h \ + move.h netlist.h remove.h operation.h rotate.h \ ../src_3rd/librnd-local/src/librnd/core/rotate.h obj_rat.h obj_term.h \ obj_pstk_inlines.h data.h thermal.h \ ../src_3rd/librnd-local/src/librnd/poly/polygon1_gen.h data_it.h @@ -13713,14 +13713,6 @@ obj_pstk.h vtpadstack.h obj_pstk_shape.h polygon.h vtpadstack_t.h \ select.h operation.h undo.h ../src_3rd/libuundo/uundo.h undo_old.h \ obj_line_op.h obj_arc_op.h obj_rat_op.h obj_poly_op.h -intersect.o: intersect.c ../config.h \ - ../src_3rd/librnd-local/src/librnd/config.h intersect.h \ - ../src_3rd/librnd-local/src/librnd/core/global_typedefs.h \ - ../src_3rd/librnd-local/src/librnd/core/rnd_bool.h \ - ../src_3rd/librnd-local/src/librnd/core/box.h \ - ../src_3rd/librnd-local/src/librnd/core/math_helper.h \ - ../src_3rd/librnd-local/src/librnd/core/misc_util.h \ - ../src_3rd/librnd-local/src/librnd/core/unit.h layer.o: layer.c ../config.h ../src_3rd/librnd-local/src/librnd/config.h \ board.h ../src_3rd/librnd-local/src/../src_3rd/genht/htsp.h \ ../src_3rd/librnd-local/src/../src_3rd/genht/ht.h \ Index: trunk/src/Makefile.in =================================================================== --- trunk/src/Makefile.in (revision 34508) +++ trunk/src/Makefile.in (revision 34509) @@ -63,7 +63,6 @@ ht_subc.o idpath.o insert.o - intersect.o layer.o layer_addr.o layer_grp.o Index: trunk/src_plugins/autoplace/autoplace.c =================================================================== --- trunk/src_plugins/autoplace/autoplace.c (revision 34508) +++ trunk/src_plugins/autoplace/autoplace.c (revision 34509) @@ -57,7 +57,7 @@ #include "draw.h" #include #include "layer.h" -#include "intersect.h" +#include #include #include "move.h" #include "netlist.h" @@ -371,9 +371,9 @@ /* now compute penalty function Wc which is proportional to * amount of overlap and congestion. */ /* delta1 is congestion penalty function */ - delta1 = CostParameter.congestion_penalty * sqrt(fabs(pcb_intersect_box_box(bounds.Box, bounds.BoxN))); + delta1 = CostParameter.congestion_penalty * sqrt(fabs(rnd_intersect_box_box(bounds.Box, bounds.BoxN))); #if 0 - printf("Wire Congestion Area: %f\n", pcb_intersect_box_box(bounds.Box, bounds.BoxN)); + printf("Wire Congestion Area: %f\n", rnd_intersect_box_box(bounds.Box, bounds.BoxN)); #endif /* free bounding rectangles */ pcb_box_free(&bounds); @@ -437,10 +437,10 @@ PCB_END_LOOP; /* compute intersection area of module areas box list */ - delta2 = sqrt(fabs(pcb_intersect_box_box(solderside.Box, solderside.BoxN) + pcb_intersect_box_box(componentside.Box, componentside.BoxN))) * (CostParameter.overlap_penalty_min + (1 - (T / T0)) * CostParameter.overlap_penalty_max); + delta2 = sqrt(fabs(rnd_intersect_box_box(solderside.Box, solderside.BoxN) + rnd_intersect_box_box(componentside.Box, componentside.BoxN))) * (CostParameter.overlap_penalty_min + (1 - (T / T0)) * CostParameter.overlap_penalty_max); #if 0 - printf("Module Overlap Area (solder): %f\n", pcb_intersect_box_box(solderside.Box, solderside.BoxN)); - printf("Module Overlap Area (component): %f\n", pcb_intersect_box_box(componentside.Box, componentside.BoxN)); + printf("Module Overlap Area (solder): %f\n", rnd_intersect_box_box(solderside.Box, solderside.BoxN)); + printf("Module Overlap Area (component): %f\n", rnd_intersect_box_box(componentside.Box, componentside.BoxN)); #endif pcb_box_free(&solderside); pcb_box_free(&componentside);