1
2 #ifndef lint
3 static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/utils/maxrect.c,v 1.4 2010/09/24 19:53:20 tim Exp $";
4 #endif
5
6 #include <sys/types.h>
7 #include <stdio.h>
8 #include <string.h> /* for memcpy() */
9
10 #include "utils/maxrect.h"
11 #include "utils/malloc.h"
12
13 /*
14 *-------------------------------------------------------------------------
15 *
16 * genCanonicalMaxwidth - checks to see that at least one dimension of a
17 * rectangular region does not exceed some amount. Searches on all
18 * tiles of types in "mask", unless mask is NULL, in which case it
19 * searches over all tiles whose client record matches that of the
20 * start tile.
21 *
22 * Side Effects:
23 * None.
24 *
25 *-------------------------------------------------------------------------
26 */
27
28 MaxRectsData *
genCanonicalMaxwidth(bbox,starttile,plane,mask)29 genCanonicalMaxwidth(bbox, starttile, plane, mask)
30 Rect *bbox; /* Bounding box of geometry to search */
31 Tile *starttile; /* Any point in the geometry to search */
32 Plane *plane; /* Plane being searched */
33 TileTypeBitMask *mask; /* Mask of types to check */
34 {
35 int s;
36 Tile *tile, *tp;
37 TileTypeBitMask wrongtypes;
38 static MaxRectsData *mrd = (MaxRectsData *)NULL;
39 Rect boundorig;
40
41 /* Generate an initial array size of 8 for rlist and swap. */
42 if (mrd == (MaxRectsData *)NULL)
43 {
44 mrd = (MaxRectsData *)mallocMagic(sizeof(MaxRectsData));
45 mrd->rlist = (Rect *)mallocMagic(8 * sizeof(Rect));
46 mrd->swap = (Rect *)mallocMagic(8 * sizeof(Rect));
47 mrd->listdepth = 8;
48 }
49 if (mask == NULL)
50 mrd->match = starttile->ti_client;
51 else
52 mrd->match = CLIENTDEFAULT;
53
54 mrd->rlist[0] = *bbox;
55 boundorig = *bbox;
56
57 /* Do an area search on boundrect to find all materials not */
58 /* in oktypes. Each such tile clips or subdivides */
59 /* boundrect. Due to the way FindMaxRects is written for */
60 /* the DRC maxwidth rule, maxdist = 1 is required to avoid */
61 /* creating degenerate (zero size) areas. */
62
63 mrd->entries = 1;
64 mrd->maxdist = 1;
65 if (mask != NULL)
66 TTMaskCom2(&wrongtypes, mask);
67 else
68 TTMaskSetMask(&wrongtypes, &DBAllTypeBits);
69
70 DBSrPaintArea(starttile, plane, &boundorig, &wrongtypes, FindMaxRects, mrd);
71 if (mrd->entries == 0)
72 return NULL;
73 else
74 return (MaxRectsData *)mrd;
75 }
76
77 /*
78 *-------------------------------------------------------------------------
79 *
80 * FindMaxRects ---
81 *
82 * Procedure used to split an area up into multiple sets of possible
83 * convex rectangles.
84 *
85 * Results:
86 * Return 0 to keep the search going.
87 *
88 * Side effects:
89 * Adds data to structure mrd; possibly expanding its memory allocation.
90 *
91 * Notes:
92 * This routine does *not* handle non-Manhattan geometry.
93 *
94 *-------------------------------------------------------------------------
95 */
96
97 int
FindMaxRects(tile,mrd)98 FindMaxRects(tile, mrd)
99 Tile *tile;
100 MaxRectsData *mrd;
101 {
102 Rect area;
103 Rect *rlist, *sr, *tmp;
104 int s, entries;
105
106 if (mrd->match != CLIENTDEFAULT)
107 if (tile->ti_client == mrd->match)
108 return 0;
109
110 entries = 0;
111 TiToRect(tile, &area);
112
113 rlist = mrd->swap;
114 for (s = 0; s < mrd->entries; s++)
115 {
116 /* Watch out for (M)INFINITY values! */
117
118 sr = &(mrd->rlist[s]);
119 if (GEO_OVERLAP(sr, &area))
120 {
121 /* Top */
122 if (area.r_ytop < INFINITY - 2)
123 if (sr->r_ytop >= area.r_ytop + mrd->maxdist)
124 {
125 rlist[entries] = *sr;
126 rlist[entries].r_ybot = area.r_ytop;
127 entries++;
128 }
129 /* Bottom */
130 if (area.r_ybot > MINFINITY + 2)
131 if (sr->r_ybot <= area.r_ybot - mrd->maxdist)
132 {
133 rlist[entries] = *sr;
134 rlist[entries].r_ytop = area.r_ybot;
135 entries++;
136 }
137 /* Left */
138 if (area.r_xbot > MINFINITY + 2)
139 if (sr->r_xbot <= area.r_xbot - mrd->maxdist)
140 {
141 rlist[entries] = *sr;
142 rlist[entries].r_xtop = area.r_xbot;
143 entries++;
144 }
145 /* Right */
146 if (area.r_xtop < INFINITY - 2)
147 if (sr->r_xtop >= area.r_xtop + mrd->maxdist)
148 {
149 rlist[entries] = *sr;
150 rlist[entries].r_xbot = area.r_xtop;
151 entries++;
152 }
153
154 }
155 else
156 {
157 /* Copy sr to the new list */
158 rlist[entries] = *sr;
159 entries++;
160 }
161
162 /* If we have more rectangles than we allocated space for, */
163 /* double the list size and continue. */
164
165 if (entries > (mrd->listdepth - 4)) // was entries == mrd->listdepth
166 {
167 Rect *newrlist;
168
169 mrd->listdepth <<= 1; /* double the list size */
170
171 newrlist = (Rect *)mallocMagic(mrd->listdepth * sizeof(Rect));
172 memcpy((void *)newrlist, (void *)mrd->rlist,
173 (size_t)mrd->entries * sizeof(Rect));
174 // for (s = 0; s < entries; s++)
175 // newrlist[s] = mrd->rlist[s];
176 freeMagic(mrd->rlist);
177 mrd->rlist = newrlist;
178
179 newrlist = (Rect *)mallocMagic(mrd->listdepth * sizeof(Rect));
180 memcpy((void *)newrlist, (void *)mrd->swap,
181 (size_t)entries * sizeof(Rect));
182 // for (s = 0; s < entries; s++)
183 // newrlist[s] = mrd->swap[s];
184 freeMagic(mrd->swap);
185 mrd->swap = newrlist;
186
187 rlist = mrd->swap;
188 }
189 }
190
191 /* Sort areas and remove areas enclosed by other areas */
192 /* Is this routine too time-consuming (short answer: yes)? */
193
194 /*
195 for (s = 0; s < entries - 1; s++)
196 {
197 int r, t;
198 for (t = s + 1, r = 0; t < entries; t++)
199 {
200 if (GEO_SURROUND(&rlist[t], &rlist[s]))
201 {
202 rlist[s] = rlist[t];
203 r++;
204 }
205 else if (GEO_SURROUND(&rlist[s], &rlist[t]))
206 r++;
207 else if (r > 0)
208 rlist[t - r] = rlist[t];
209 }
210 entries -= r;
211 }
212 */
213
214 /* copy rlist back to mrd by swapping "rlist" and "swap" */
215 mrd->entries = entries;
216 tmp = mrd->rlist;
217 mrd->rlist = rlist;
218 mrd->swap = tmp;
219
220 if (entries > 0)
221 return 0; /* keep the search going */
222 else
223 return 1; /* no more max size areas; stop the search */
224 }
225
226 /*
227 *-------------------------------------------------------------------------
228 *
229 * FindMaxRectangle ---
230 *
231 * This is a general-purpose routine to be called from anywhere
232 * that expands an area to the largest area rectangle containing
233 * tiles connected to the given types list. It can be called, for
234 * example, from the router code to expand a point label into the
235 * maximum size rectangular terminal.
236 *
237 * If expandtypes is NULL, then searching is done over tiles that
238 * match by the ClientData record instead of types.
239 *
240 * Results:
241 * Pointer to a rectangle containing the maximum size area found.
242 * This pointer should not be deallocated!
243 *
244 *-------------------------------------------------------------------------
245 */
246
247 Rect *
FindMaxRectangle(bbox,startpoint,plane,expandtypes)248 FindMaxRectangle(bbox, startpoint, plane, expandtypes)
249 Rect *bbox; /* bounding box of area searched */
250 Point *startpoint;
251 Plane *plane; /* plane of types to expand */
252 TileTypeBitMask *expandtypes; /* types to expand in */
253 {
254 MaxRectsData *mrd;
255 Tile *starttile;
256 TileType tt;
257 int rectArea;
258 int maxarea = 0;
259 int s, sidx = -1;
260
261 /* Find tile in def that surrounds or touches startpoint */
262 starttile = plane->pl_hint;
263 GOTOPOINT(starttile, startpoint);
264 mrd = genCanonicalMaxwidth(bbox, starttile, plane, NULL);
265
266 /* Return only the largest rectangle found */
267
268 for (s = 0; s < mrd->entries; s++)
269 {
270 rectArea = (mrd->rlist[s].r_xtop - mrd->rlist[s].r_xbot) *
271 (mrd->rlist[s].r_ytop - mrd->rlist[s].r_ybot);
272 if (rectArea > maxarea)
273 {
274 maxarea = rectArea;
275 sidx = s;
276 }
277 }
278
279 if (sidx < 0)
280 {
281 Rect origrect;
282
283 TiToRect(starttile, &origrect);
284 sidx = 0;
285 mrd->rlist[0] = origrect;
286 }
287 return &(mrd->rlist[sidx]);
288 }
289
290 /*
291 *-------------------------------------------------------------------------
292 *
293 * FindMaxRectangle2 ---
294 *
295 * This routine differs from FindMaxRectangle in passing a starting
296 * tile to the routine.
297 *
298 * Results:
299 * Pointer to a rectangle containing the maximum size area found.
300 * This pointer should not be deallocated!
301 *
302 *-------------------------------------------------------------------------
303 */
304
305 Rect *
FindMaxRectangle2(bbox,starttile,plane,expandtypes)306 FindMaxRectangle2(bbox, starttile, plane, expandtypes)
307 Rect *bbox; /* bounding box of area searched */
308 Tile *starttile; /* use this tile to start */
309 Plane *plane; /* plane of types to expand */
310 TileTypeBitMask *expandtypes; /* types to expand in, may be NULL */
311 {
312 MaxRectsData *mrd;
313 TileType tt;
314 int rectArea;
315 int maxarea = 0;
316 int s, sidx = -1;
317
318 /* Find tile in def that surrounds or touches startpoint */
319 mrd = genCanonicalMaxwidth(bbox, starttile, plane, expandtypes);
320
321 /* Return only the largest rectangle found */
322
323 for (s = 0; s < mrd->entries; s++)
324 {
325 rectArea = (mrd->rlist[s].r_xtop - mrd->rlist[s].r_xbot) *
326 (mrd->rlist[s].r_ytop - mrd->rlist[s].r_ybot);
327 if (rectArea > maxarea)
328 {
329 maxarea = rectArea;
330 sidx = s;
331 }
332 }
333
334 if (sidx < 0)
335 {
336 Rect origrect;
337
338 TiToRect(starttile, &origrect);
339 sidx = 0;
340 mrd->rlist[0] = origrect;
341 }
342 return &(mrd->rlist[sidx]);
343 }
344
345