← Back to branch summary

~ubuntu-branches/ubuntu/precise/pcb/precise

« back to all changes in this revision

Viewing changes to src/intersect.c

  • Committer: Bazaar Package Importer
  • Author(s): Hamish Moffatt
  • Date: 2005-02-20 13:14:00 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20050220131400-pfz66g5vhx0azl8f
Tags: 1.99j+20050127-2
http://bugs.debian.org/295405
http://bugs.debian.org/295404
http://bugs.debian.org/269578
http://bugs.debian.org/294319
* Improved package description: (closes: #295405)
* Fixed dependency: tk84 -> tk8.4 (closes: #295404)
* Updated README.debian (closes: #269578)
* Applied patch to src/djopt.c to allow compilation with gcc-4.0
  (closes: #294319), thanks to Andreas Jochens for the patch.
* Prevent example files from being compressed

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/intersect.c
 
1
/* $Id: intersect.c,v 1.6 2005/01/03 12:56:59 danmc Exp $ */
 
2
 
 
3
/*
 
4
 *                            COPYRIGHT
 
5
 *
 
6
 *  PCB, interactive printed circuit board design
 
7
 *  Copyright (C) 1994,1995,1996 Thomas Nau
 
8
 *  Copyright (C) 1998,1999,2000,2001 harry eaton
 
9
 *
 
10
 *  This program is free software; you can redistribute it and/or modify
 
11
 *  it under the terms of the GNU General Public License as published by
 
12
 *  the Free Software Foundation; either version 2 of the License, or
 
13
 *  (at your option) any later version.
 
14
 *
 
15
 *  This program is distributed in the hope that it will be useful,
 
16
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
17
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
18
 *  GNU General Public License for more details.
 
19
 *
 
20
 *  You should have received a copy of the GNU General Public License
 
21
 *  along with this program; if not, write to the Free Software
 
22
 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 
23
 *
 
24
 *  Contact addresses for paper mail and Email:
 
25
 *  harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA
 
26
 *  haceaton@aplcomm.jhuapl.edu
 
27
 *
 
28
 */
 
29
 
 
30
/* this file, intersect.c, was written and is
 
31
 * Copyright (c) 2001 C. Scott Ananian
 
32
 */
 
33
 
 
34
/* rectangle intersection/union routines.
 
35
 */
 
36
 
 
37
#ifdef HAVE_CONFIG_H
 
38
#include "config.h"
 
39
#endif
 
40
 
 
41
#include <assert.h>
 
42
#include <stdlib.h>
 
43
 
 
44
#include "global.h"
 
45
 
 
46
#include "data.h"
 
47
#include "intersect.h"
 
48
#include "mymem.h"
 
49
 
 
50
#ifdef HAVE_LIBDMALLOC
 
51
#include <dmalloc.h>
 
52
#endif
 
53
 
 
54
RCSID("$Id: intersect.c,v 1.6 2005/01/03 12:56:59 danmc Exp $");
 
55
 
 
56
 
 
57
/* ---------------------------------------------------------------------------
 
58
 * some local prototypes
 
59
 */
 
60
static int compareleft (const void *ptr1, const void *ptr2);
 
61
static int compareright (const void *ptr1, const void *ptr2);
 
62
static int comparepos (const void *ptr1, const void *ptr2);
 
63
static int nextpwrof2 (int i);
 
64
 
 
65
/* ---------------------------------------------------------------------------
 
66
 * some local types
 
67
 */
 
68
typedef struct
 
69
{
 
70
  LocationType left, right;
 
71
  int covered;
 
72
  int area;
 
73
}
 
74
SegmentTreeNode;
 
75
 
 
76
typedef struct
 
77
{
 
78
  SegmentTreeNode *nodes;
 
79
  int size;
 
80
}
 
81
SegmentTree;
 
82
 
 
83
typedef struct
 
84
{
 
85
  LocationType *p;
 
86
  int size;
 
87
}
 
88
LocationList;
 
89
 
 
90
/* ---------------------------------------------------------------------------
 
91
 * Create a sorted list of unique y coords from a BoxList.
 
92
 */
 
93
static LocationList
 
94
createSortedYList (BoxListTypePtr boxlist)
 
95
{
 
96
  LocationList yCoords;
 
97
  LocationType last;
 
98
  int i, n;
 
99
  /* create sorted list of Y coordinates */
 
100
  yCoords.size = 2 * boxlist->BoxN;
 
101
  yCoords.p = MyCalloc (yCoords.size, sizeof (*yCoords.p),
 
102
                        "createSortedYList");
 
103
  for (i = 0; i < boxlist->BoxN; i++)
 
104
    {
 
105
      yCoords.p[2 * i] = boxlist->Box[i].Y1;
 
106
      yCoords.p[2 * i + 1] = boxlist->Box[i].Y2;
 
107
    }
 
108
  qsort (yCoords.p, yCoords.size, sizeof (*yCoords.p), comparepos);
 
109
  /* count uniq y coords */
 
110
  last = 0;
 
111
  for (n = 0, i = 0; i < yCoords.size; i++)
 
112
    if (i == 0 || yCoords.p[i] != last)
 
113
      yCoords.p[n++] = last = yCoords.p[i];
 
114
  yCoords.size = n;
 
115
  return yCoords;
 
116
}
 
117
 
 
118
/* ---------------------------------------------------------------------------
 
119
 * Create an empty segment tree from the given sorted list of uniq y coords.
 
120
 */
 
121
static SegmentTree
 
122
createSegmentTree (LocationType * yCoords, int N)
 
123
{
 
124
  SegmentTree st;
 
125
  int i;
 
126
  /* size is twice the nearest larger power of 2 */
 
127
  st.size = 2 * nextpwrof2 (N);
 
128
  st.nodes = MyCalloc (st.size, sizeof (*st.nodes), "createSegmentTree");
 
129
  /* initialize the rightmost leaf node */
 
130
  st.nodes[st.size - 1].left = (N > 0) ? yCoords[--N] : 10;
 
131
  st.nodes[st.size - 1].right = st.nodes[st.size - 1].left + 1;
 
132
  /* initialize the rest of the leaf nodes */
 
133
  for (i = st.size - 2; i >= st.size / 2; i--)
 
134
    {
 
135
      st.nodes[i].right = st.nodes[i + 1].left;
 
136
      st.nodes[i].left = (N > 0) ? yCoords[--N] : st.nodes[i].right - 1;
 
137
    }
 
138
  /* initialize the internal nodes */
 
139
  for (; i > 0; i--)
 
140
    {                           /* node 0 is not used */
 
141
      st.nodes[i].right = st.nodes[2 * i + 1].right;
 
142
      st.nodes[i].left = st.nodes[2 * i].left;
 
143
    }
 
144
  /* done! */
 
145
  return st;
 
146
}
 
147
 
 
148
void
 
149
insertSegment (SegmentTree * st, int n, LocationType Y1, LocationType Y2)
 
150
{
 
151
  LocationType discriminant;
 
152
  if (st->nodes[n].left >= Y1 && st->nodes[n].right <= Y2)
 
153
    {
 
154
      st->nodes[n].covered++;
 
155
    }
 
156
  else
 
157
    {
 
158
      assert (n < st->size / 2);
 
159
      discriminant = st->nodes[n * 2 + 1 /*right */ ].left;
 
160
      if (Y1 < discriminant)
 
161
        insertSegment (st, n * 2, Y1, Y2);
 
162
      if (discriminant < Y2)
 
163
        insertSegment (st, n * 2 + 1, Y1, Y2);
 
164
    }
 
165
  /* fixup area */
 
166
  st->nodes[n].area = (st->nodes[n].covered > 0) ?
 
167
    (st->nodes[n].right - st->nodes[n].left) :
 
168
    (n >= st->size / 2) ? 0 :
 
169
    st->nodes[n * 2].area + st->nodes[n * 2 + 1].area;
 
170
}
 
171
 
 
172
void
 
173
deleteSegment (SegmentTree * st, int n, LocationType Y1, LocationType Y2)
 
174
{
 
175
  LocationType discriminant;
 
176
  if (st->nodes[n].left >= Y1 && st->nodes[n].right <= Y2)
 
177
    {
 
178
      assert (st->nodes[n].covered);
 
179
      --st->nodes[n].covered;
 
180
    }
 
181
  else
 
182
    {
 
183
      assert (n < st->size / 2);
 
184
      discriminant = st->nodes[n * 2 + 1 /*right */ ].left;
 
185
      if (Y1 < discriminant)
 
186
        deleteSegment (st, n * 2, Y1, Y2);
 
187
      if (discriminant < Y2)
 
188
        deleteSegment (st, n * 2 + 1, Y1, Y2);
 
189
    }
 
190
  /* fixup area */
 
191
  st->nodes[n].area = (st->nodes[n].covered > 0) ?
 
192
    (st->nodes[n].right - st->nodes[n].left) :
 
193
    (n >= st->size / 2) ? 0 :
 
194
    st->nodes[n * 2].area + st->nodes[n * 2 + 1].area;
 
195
}
 
196
 
 
197
/* ---------------------------------------------------------------------------
 
198
 * Compute the area of the intersection of the given rectangles; that is,
 
199
 * the area covered by more than one rectangle (counted twice if the area is
 
200
 * covered by three rectangles, three times if covered by four rectangles,
 
201
 * etc.).
 
202
 * Runs in O(N ln N) time.
 
203
 */
 
204
double
 
205
ComputeIntersectionArea (BoxListTypePtr boxlist)
 
206
{
 
207
  Cardinal i;
 
208
  double area = 0.0;
 
209
  /* first get the aggregate area. */
 
210
  for (i = 0; i < boxlist->BoxN; i++)
 
211
    area += (double)(boxlist->Box[i].X2 - boxlist->Box[i].X1) *
 
212
      (double) (boxlist->Box[i].Y2 - boxlist->Box[i].Y1);
 
213
  /* intersection area is aggregate - union. */
 
214
  return area * 0.0001 - ComputeUnionArea (boxlist);
 
215
}
 
216
 
 
217
/* ---------------------------------------------------------------------------
 
218
 * Compute the area of the union of the given rectangles.
 
219
 * O(N ln N) time.
 
220
 */
 
221
double
 
222
ComputeUnionArea (BoxListTypePtr boxlist)
 
223
{
 
224
  BoxTypePtr *rectLeft, *rectRight;
 
225
  Cardinal i, j;
 
226
  LocationList yCoords;
 
227
  SegmentTree segtree;
 
228
  LocationType lastX;
 
229
  double area = 0.0;
 
230
  /* create sorted list of Y coordinates */
 
231
  yCoords = createSortedYList (boxlist);
 
232
  /* now create empty segment tree */
 
233
  segtree = createSegmentTree (yCoords.p, yCoords.size);
 
234
  free (yCoords.p);
 
235
  /* create sorted list of left and right X coordinates of rectangles */
 
236
  rectLeft = MyCalloc (boxlist->BoxN, sizeof (*rectLeft),
 
237
                       "ComputeUnionArea(1)");
 
238
  rectRight = MyCalloc (boxlist->BoxN, sizeof (*rectRight),
 
239
                        "ComputeUnionArea(2)");
 
240
  for (i = 0; i < boxlist->BoxN; i++)
 
241
    {
 
242
      assert (boxlist->Box[i].X1 <= boxlist->Box[i].X2);
 
243
      assert (boxlist->Box[i].Y1 <= boxlist->Box[i].Y2);
 
244
      rectLeft[i] = rectRight[i] = &boxlist->Box[i];
 
245
    }
 
246
  qsort (rectLeft, boxlist->BoxN, sizeof (*rectLeft), compareleft);
 
247
  qsort (rectRight, boxlist->BoxN, sizeof (*rectRight), compareright);
 
248
  /* sweep through x segments from left to right */
 
249
  i = j = 0;
 
250
  lastX = rectLeft[0]->X1;
 
251
  while (j < boxlist->BoxN)
 
252
    {
 
253
      assert (i <= boxlist->BoxN);
 
254
      /* i will step through rectLeft, j will through rectRight */
 
255
      if (i == boxlist->BoxN || rectRight[j]->X2 < rectLeft[i]->X1)
 
256
        {
 
257
          /* right edge of rectangle */
 
258
          BoxTypePtr b = rectRight[j++];
 
259
          /* check lastX */
 
260
          if (b->X2 != lastX)
 
261
            {
 
262
              assert (lastX < b->X2);
 
263
              area += (double)(b->X2 - lastX) * segtree.nodes[1].area;
 
264
              lastX = b->X2;
 
265
            }
 
266
          /* remove a segment from the segment tree. */
 
267
          deleteSegment (&segtree, 1, b->Y1, b->Y2);
 
268
        }
 
269
      else
 
270
        {
 
271
          /* left edge of rectangle */
 
272
          BoxTypePtr b = rectLeft[i++];
 
273
          /* check lastX */
 
274
          if (b->X1 != lastX)
 
275
            {
 
276
              assert (lastX < b->X1);
 
277
              area += (double)(b->X1 - lastX) * segtree.nodes[1].area;
 
278
              lastX = b->X1;
 
279
            }
 
280
          /* add a segment from the segment tree. */
 
281
          insertSegment (&segtree, 1, b->Y1, b->Y2);
 
282
        }
 
283
    }
 
284
  free (rectLeft);
 
285
  free (rectRight);
 
286
  free (segtree.nodes);
 
287
  return area * 0.0001;
 
288
}
 
289
static int
 
290
compareleft (const void *ptr1, const void *ptr2)
 
291
{
 
292
  BoxTypePtr *b1 = (BoxTypePtr *) ptr1, *b2 = (BoxTypePtr *) ptr2;
 
293
  return (*b1)->X1 - (*b2)->X1;
 
294
}
 
295
static int
 
296
compareright (const void *ptr1, const void *ptr2)
 
297
{
 
298
  BoxTypePtr *b1 = (BoxTypePtr *) ptr1, *b2 = (BoxTypePtr *) ptr2;
 
299
  return (*b1)->X2 - (*b2)->X2;
 
300
}
 
301
static int
 
302
comparepos (const void *ptr1, const void *ptr2)
 
303
{
 
304
  return *((LocationType *) ptr1) - *((LocationType *) ptr2);
 
305
}
 
306
static int
 
307
nextpwrof2 (int n)
 
308
{
 
309
  int r = 1;
 
310
  while (n != 0)
 
311
    {
 
312
      n /= 2;
 
313
      r *= 2;
 
314
    }
 
315
  return r;
 
316
}