pcb 4.1.1
An interactive printed circuit board layout editor.

intersect.c

Go to the documentation of this file.
00001 
00037 #ifdef HAVE_CONFIG_H
00038 #include "config.h"
00039 #endif
00040 
00041 #include "global.h"
00042 
00043 #include <assert.h>
00044 
00045 #include "data.h"
00046 #include "intersect.h"
00047 #include "mymem.h"
00048 
00049 #ifdef HAVE_LIBDMALLOC
00050 #include <dmalloc.h>
00051 #endif
00052 
00053 /* ---------------------------------------------------------------------------
00054  * some local prototypes
00055  */
00056 static int compareleft (const void *ptr1, const void *ptr2);
00057 static int compareright (const void *ptr1, const void *ptr2);
00058 static int comparepos (const void *ptr1, const void *ptr2);
00059 static int nextpwrof2 (int i);
00060 
00061 /* ---------------------------------------------------------------------------
00062  * some local types
00063  */
00064 typedef struct
00065 {
00066   Coord left, right;
00067   int covered;
00068   Coord area;
00069 }
00070 SegmentTreeNode;
00071 
00072 typedef struct
00073 {
00074   SegmentTreeNode *nodes;
00075   int size;
00076 }
00077 SegmentTree;
00078 
00079 typedef struct
00080 {
00081   Coord *p;
00082   int size;
00083 }
00084 LocationList;
00085 
00089 static LocationList
00090 createSortedYList (BoxListType *boxlist)
00091 {
00092   LocationList yCoords;
00093   Coord last;
00094   int i, n;
00095   /* create sorted list of Y coordinates */
00096   yCoords.size = 2 * boxlist->BoxN;
00097   yCoords.p = (Coord *)calloc (yCoords.size, sizeof (*yCoords.p));
00098   for (i = 0; i < boxlist->BoxN; i++)
00099     {
00100       yCoords.p[2 * i] = boxlist->Box[i].Y1;
00101       yCoords.p[2 * i + 1] = boxlist->Box[i].Y2;
00102     }
00103   qsort (yCoords.p, yCoords.size, sizeof (*yCoords.p), comparepos);
00104   /* count uniq y coords */
00105   last = 0;
00106   for (n = 0, i = 0; i < yCoords.size; i++)
00107     if (i == 0 || yCoords.p[i] != last)
00108       yCoords.p[n++] = last = yCoords.p[i];
00109   yCoords.size = n;
00110   return yCoords;
00111 }
00112 
00117 static SegmentTree
00118 createSegmentTree (Coord * yCoords, int N)
00119 {
00120   SegmentTree st;
00121   int i;
00122   /* size is twice the nearest larger power of 2 */
00123   st.size = 2 * nextpwrof2 (N);
00124   st.nodes = (SegmentTreeNode *)calloc (st.size, sizeof (*st.nodes));
00125   /* initialize the rightmost leaf node */
00126   st.nodes[st.size - 1].left = (N > 0) ? yCoords[--N] : 10;
00127   st.nodes[st.size - 1].right = st.nodes[st.size - 1].left + 1;
00128   /* initialize the rest of the leaf nodes */
00129   for (i = st.size - 2; i >= st.size / 2; i--)
00130     {
00131       st.nodes[i].right = st.nodes[i + 1].left;
00132       st.nodes[i].left = (N > 0) ? yCoords[--N] : st.nodes[i].right - 1;
00133     }
00134   /* initialize the internal nodes */
00135   for (; i > 0; i--)
00136     {                           /* node 0 is not used */
00137       st.nodes[i].right = st.nodes[2 * i + 1].right;
00138       st.nodes[i].left = st.nodes[2 * i].left;
00139     }
00140   /* done! */
00141   return st;
00142 }
00143 
00144 void
00145 insertSegment (SegmentTree * st, int n, Coord Y1, Coord Y2)
00146 {
00147   Coord discriminant;
00148   if (st->nodes[n].left >= Y1 && st->nodes[n].right <= Y2)
00149     {
00150       st->nodes[n].covered++;
00151     }
00152   else
00153     {
00154       assert (n < st->size / 2);
00155       discriminant = st->nodes[n * 2 + 1 /*right */ ].left;
00156       if (Y1 < discriminant)
00157         insertSegment (st, n * 2, Y1, Y2);
00158       if (discriminant < Y2)
00159         insertSegment (st, n * 2 + 1, Y1, Y2);
00160     }
00161   /* fixup area */
00162   st->nodes[n].area = (st->nodes[n].covered > 0) ?
00163     (st->nodes[n].right - st->nodes[n].left) :
00164     (n >= st->size / 2) ? 0 :
00165     st->nodes[n * 2].area + st->nodes[n * 2 + 1].area;
00166 }
00167 
00168 void
00169 deleteSegment (SegmentTree * st, int n, Coord Y1, Coord Y2)
00170 {
00171   Coord discriminant;
00172   if (st->nodes[n].left >= Y1 && st->nodes[n].right <= Y2)
00173     {
00174       assert (st->nodes[n].covered);
00175       --st->nodes[n].covered;
00176     }
00177   else
00178     {
00179       assert (n < st->size / 2);
00180       discriminant = st->nodes[n * 2 + 1 /*right */ ].left;
00181       if (Y1 < discriminant)
00182         deleteSegment (st, n * 2, Y1, Y2);
00183       if (discriminant < Y2)
00184         deleteSegment (st, n * 2 + 1, Y1, Y2);
00185     }
00186   /* fixup area */
00187   st->nodes[n].area = (st->nodes[n].covered > 0) ?
00188     (st->nodes[n].right - st->nodes[n].left) :
00189     (n >= st->size / 2) ? 0 :
00190     st->nodes[n * 2].area + st->nodes[n * 2 + 1].area;
00191 }
00192 
00202 double
00203 ComputeIntersectionArea (BoxListType *boxlist)
00204 {
00205   Cardinal i;
00206   double area = 0.0;
00207   /* first get the aggregate area. */
00208   for (i = 0; i < boxlist->BoxN; i++)
00209     area += (double) (boxlist->Box[i].X2 - boxlist->Box[i].X1) *
00210       (double) (boxlist->Box[i].Y2 - boxlist->Box[i].Y1);
00211   /* intersection area is aggregate - union. */
00212   return area * 0.0001 - ComputeUnionArea (boxlist);
00213 }
00214 
00220 double
00221 ComputeUnionArea (BoxListType *boxlist)
00222 {
00223   BoxType **rectLeft, **rectRight;
00224   Cardinal i, j;
00225   LocationList yCoords;
00226   SegmentTree segtree;
00227   Coord lastX;
00228   double area = 0.0;
00229 
00230   if (boxlist->BoxN == 0)
00231     return 0.0;
00232   /* create sorted list of Y coordinates */
00233   yCoords = createSortedYList (boxlist);
00234   /* now create empty segment tree */
00235   segtree = createSegmentTree (yCoords.p, yCoords.size);
00236   free (yCoords.p);
00237   /* create sorted list of left and right X coordinates of rectangles */
00238   rectLeft = (BoxType **)calloc (boxlist->BoxN, sizeof (*rectLeft));
00239   rectRight = (BoxType **)calloc (boxlist->BoxN, sizeof (*rectRight));
00240   for (i = 0; i < boxlist->BoxN; i++)
00241     {
00242       assert (boxlist->Box[i].X1 <= boxlist->Box[i].X2);
00243       assert (boxlist->Box[i].Y1 <= boxlist->Box[i].Y2);
00244       rectLeft[i] = rectRight[i] = &boxlist->Box[i];
00245     }
00246   qsort (rectLeft, boxlist->BoxN, sizeof (*rectLeft), compareleft);
00247   qsort (rectRight, boxlist->BoxN, sizeof (*rectRight), compareright);
00248   /* sweep through x segments from left to right */
00249   i = j = 0;
00250   lastX = rectLeft[0]->X1;
00251   while (j < boxlist->BoxN)
00252     {
00253       assert (i <= boxlist->BoxN);
00254       /* i will step through rectLeft, j will through rectRight */
00255       if (i == boxlist->BoxN || rectRight[j]->X2 < rectLeft[i]->X1)
00256         {
00257           /* right edge of rectangle */
00258           BoxType *b = rectRight[j++];
00259           /* check lastX */
00260           if (b->X2 != lastX)
00261             {
00262               assert (lastX < b->X2);
00263               area += (double) (b->X2 - lastX) * segtree.nodes[1].area;
00264               lastX = b->X2;
00265             }
00266           /* remove a segment from the segment tree. */
00267           deleteSegment (&segtree, 1, b->Y1, b->Y2);
00268         }
00269       else
00270         {
00271           /* left edge of rectangle */
00272           BoxType *b = rectLeft[i++];
00273           /* check lastX */
00274           if (b->X1 != lastX)
00275             {
00276               assert (lastX < b->X1);
00277               area += (double) (b->X1 - lastX) * segtree.nodes[1].area;
00278               lastX = b->X1;
00279             }
00280           /* add a segment from the segment tree. */
00281           insertSegment (&segtree, 1, b->Y1, b->Y2);
00282         }
00283     }
00284   free (rectLeft);
00285   free (rectRight);
00286   free (segtree.nodes);
00287   return area * 0.0001;
00288 }
00289 
00290 static int
00291 compareleft (const void *ptr1, const void *ptr2)
00292 {
00293   BoxType **b1 = (BoxType **) ptr1;
00294   BoxType **b2 = (BoxType **) ptr2;
00295   return (*b1)->X1 - (*b2)->X1;
00296 }
00297 
00298 static int
00299 compareright (const void *ptr1, const void *ptr2)
00300 {
00301   BoxType **b1 = (BoxType **) ptr1;
00302   BoxType **b2 = (BoxType **) ptr2;
00303   return (*b1)->X2 - (*b2)->X2;
00304 }
00305 
00306 static int
00307 comparepos (const void *ptr1, const void *ptr2)
00308 {
00309   return *((Coord *) ptr1) - *((Coord *) ptr2);
00310 }
00311 
00312 static int
00313 nextpwrof2 (int n)
00314 {
00315   int r = 1;
00316   while (n != 0)
00317     {
00318       n /= 2;
00319       r *= 2;
00320     }
00321   return r;
00322 }