1 /* -*- tab-width: 4 -*-
2 *
3 * Electric(tm) VLSI Design System
4 *
5 * File: dbmerge.c
6 * Box merging subsystem
7 * Written by Philip Attfield, Queens University, Kingston Ontario.
8 * Revised by Sid Penstone, Queens University, Kingston Ontario.
9 *
10 * Copyright (c) 2000 Static Free Software.
11 *
12 * Electric(tm) is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU General Public License as published by
14 * the Free Software Foundation; either version 2 of the License, or
15 * (at your option) any later version.
16 *
17 * Electric(tm) is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU General Public License for more details.
21 *
22 * You should have received a copy of the GNU General Public License
23 * along with Electric(tm); see the file COPYING. If not, write to
24 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
25 * Boston, Mass 02111-1307, USA.
26 *
27 * Static Free Software
28 * 4119 Alpine Road
29 * Portola Valley, California 94028
30 * info@staticfreesoft.com
31 */
32 #include "global.h"
33 #include "database.h"
34 #include "egraphics.h"
35 #include "tecart.h"
36 #include "tecgen.h"
37 #include <math.h>
38
39 /***************************************************************************
40 * Initially, call:
41 * mrginit()
42 *
43 * For every polygon, call:
44 * mrgstorebox(layer, tech, xsize, ysize, xcenter, ycenter)
45 * where "layer" is an integer layer number from technology "tech"; "xsize"
46 * and "ysize" are size of the box; "xcenter" and "ycenter" are the center
47 * of the box
48 *
49 * At end of cell, call:
50 * mrgdonecell(writepolygon)
51 * where "writepolygon" is a routine that will be called for every polygon with
52 * five parameters:
53 * (1) the layer number (INTBIG)
54 * (2) the technology
55 * (3) the X coordinate array (INTBIG array)
56 * (4) the Y coordinate array (INTBIG array)
57 * (5) the number of coordinates in each array (INTBIG)
58 *
59 * When done with merging, call:
60 * mrgterm()
61 ***************************************************************************
62 */
63
64 #define MAXNUMPTS 106 /* maximum allowable number of points on a polygon */
65 static INTBIG maxnumpts = MAXNUMPTS; /* apply default (PJA:920527) */
66 # define PTMATCH 2 /* point match */
67
68 /* polygon direction and box edge identifiers */
69 #define UP 0
70 #define RIGHT 1
71 #define DOWN 2
72 #define LEFT 3
73
74 static POLYLISTHEAD db_mrg_polycoordlist;
75 static POLYCOORD *db_mrg_free_poly_list;
76 static BOXPOLY *db_mrg_free_box_list;
77 static BOXLISTHEAD *db_mrg_free_boxhead_list;
78 static BOXLISTHEAD *db_mrg_curr_cell;
79
80 /* working storage for "db_mrg_write_polygon()" */
81 static INTBIG *db_mrgxbuf, *db_mrgybuf;
82 static INTBIG db_mrgbuflen = 0;
83
84 /* prototypes for local routines */
85 static BOOLEAN db_mrg_included(BOXPOLY*, BOXPOLY*);
86 static void db_mrg_remove_inclusion(BOXLISTHEAD*);
87 static void db_mrg_remove_overlap(BOXLISTHEAD*);
88 static BOXPOLY *db_mrg_breakbox(BOXPOLY*, BOXPOLY*, INTBIG*);
89 static BOXPOLY *db_mrg_do_break(BOXPOLY*, BOXPOLY*, INTBIG*);
90 static void db_mrg_write_lists(void(*)(INTBIG, TECHNOLOGY*, INTBIG*, INTBIG*, INTBIG));
91 static POLYCOORD *db_mrg_getpoly(void);
92 static BOOLEAN db_mrg_mergeboxwithpolygon(BOXPOLY*);
93 static INTBIG db_mrg_check_intersect(BOXPOLY*, POLYCOORD*, INTBIG*);
94 static INTBIG db_mrg_check_point(INTBIG[], INTBIG[], INTBIG[], INTBIG[]);
95 static void db_mrg_insert1(INTBIG, BOXPOLY*);
96 static void db_mrg_insert2(INTBIG, BOXPOLY*);
97 static void db_mrg_insert3(INTBIG, BOXPOLY*);
98 static void db_mrg_insert4(INTBIG, BOXPOLY*);
99 static void db_mrg_insert5(INTBIG, INTBIG, BOXPOLY*);
100 static void db_mrg_write_polygon(void(*)(INTBIG, TECHNOLOGY*, INTBIG*, INTBIG*, INTBIG), INTBIG, TECHNOLOGY*);
101 static INTBIG db_mrg_succ(INTBIG);
102 static INTBIG db_mrg_nxtside(INTBIG);
103 static INTBIG db_mrg_prevside(INTBIG);
104 static void db_mrg_assign_edge(POLYCOORD*, INTBIG[], INTBIG[]);
105 static void db_mrg_housekeeper(void);
106 static BOXPOLY *db_mrg_getbox(void);
107 static void db_mrg_trash(BOXPOLY*);
108 static void db_mrg_dump_free_box_list(void);
109 static void db_mrg_assign_box(BOXPOLY*, INTBIG, INTBIG, INTBIG, INTBIG);
110 static void db_mrg_killpoly(POLYCOORD*);
111 static void db_mrg_dump_free_poly_list(void);
112 static void db_mrg_remove_poly_list(void);
113 static BOXLISTHEAD *db_mrg_get_lay_head(void);
114 static void db_mrg_dump_free_boxhead_list(void);
115 static void db_mrg_remove_boxhead_list(void);
116
mrginit(void)117 void mrginit(void)
118 {
119 }
120
mrgterm(void)121 void mrgterm(void)
122 {
123 db_mrg_dump_free_poly_list();
124 db_mrg_dump_free_box_list();
125 db_mrg_dump_free_boxhead_list();
126 }
127
mrgdonecell(void (* writepolygon)(INTBIG,TECHNOLOGY *,INTBIG *,INTBIG *,INTBIG))128 void mrgdonecell(void (*writepolygon)(INTBIG, TECHNOLOGY*, INTBIG*, INTBIG*, INTBIG))
129 {
130 db_mrg_write_lists(writepolygon);
131 db_mrg_remove_boxhead_list();
132 }
133
mrgstorebox(INTBIG layer,TECHNOLOGY * tech,INTBIG length,INTBIG width,INTBIG xc,INTBIG yc)134 void mrgstorebox(INTBIG layer, TECHNOLOGY *tech, INTBIG length, INTBIG width,
135 INTBIG xc, INTBIG yc)
136 {
137 BOXLISTHEAD *layhead;
138 BOXPOLY *creatptr;
139 INTBIG left, right, top, bot;
140
141 for(layhead = db_mrg_curr_cell; layhead != NULL; layhead = layhead->nextlayer)
142 if (layhead->layer == layer && layhead->tech == tech) break;
143
144 if (layhead == NULL)
145 {
146 layhead = db_mrg_get_lay_head();
147 layhead->nextlayer = db_mrg_curr_cell; /* form link */
148 db_mrg_curr_cell = layhead; /* modify cell layer list header */
149 layhead->layer = layer;
150 layhead->tech = tech;
151 layhead->box = NULL;
152 }
153
154 /* layhead now points to the correct layer head descriptor */
155 creatptr = db_mrg_getbox();
156 creatptr->nextbox = layhead->box;
157 layhead->box = creatptr; /* insert new descriptor at top of list */
158 left = xc - (length/2);
159 right = xc + (length/2);
160 top = yc + (width/2);
161 bot = yc - (width/2);
162
163 /* assign box descriptor values */
164 db_mrg_assign_box(creatptr, left, right, top, bot);
165 }
166
167 /************************* INTERNAL ROUTINES *************************/
168
169 /*
170 * called once at initialization to set globals
171 */
db_mrgdatainit(void)172 void db_mrgdatainit(void)
173 {
174 db_mrg_free_poly_list = NULL;
175 db_mrg_free_box_list = NULL;
176 db_mrg_free_boxhead_list = NULL;
177 db_mrg_curr_cell = NULL;
178 }
179
180 /* checks inclusion */
db_mrg_included(BOXPOLY * me,BOXPOLY * him)181 BOOLEAN db_mrg_included(BOXPOLY *me, BOXPOLY *him)
182 {
183 if (him->left >= me->left && him->right <= me->right &&
184 him->top <= me->top && him->bot >= me->bot)
185 return(TRUE); /* him is an inclusion */
186 return(FALSE); /* him is NOT an inclusion */
187 }
188
189 /* removes inclusions which follow on list */
db_mrg_remove_inclusion(BOXLISTHEAD * lay_box)190 void db_mrg_remove_inclusion(BOXLISTHEAD *lay_box)
191 {
192 BOXPOLY *me, *him, *oldhim, *garbage;
193
194 me = lay_box->box;
195 garbage = NULL;
196
197 if (me->nextbox != NULL) /* if not a singular list */
198 {
199 for(; me->nextbox != NULL;)
200 {
201 oldhim = me;
202 for(him = me->nextbox; him != NULL;)
203 {
204 if (db_mrg_included(me, him)) /* if him is an inclusion of me */
205 {
206 garbage = him;
207 oldhim->nextbox = him->nextbox; /* bypass him on list */
208 him = him->nextbox;
209 garbage->nextbox = NULL;
210 db_mrg_trash(garbage);
211 } else /* not an inclusion */
212 {
213 oldhim = him;
214 him = him->nextbox;
215 }
216 } /* end for */
217
218 /* catches case where everyone on list after me was an */
219 me = me->nextbox;
220 if (me == NULL) break; /* inclusion */
221 } /* end for */
222 } /* end if */
223 }
224
db_mrg_remove_overlap(BOXLISTHEAD * layhead)225 void db_mrg_remove_overlap(BOXLISTHEAD *layhead)
226 {
227 BOXPOLY *me, *him, *oldme, *garbage, *broken, *temp,
228 *endptr;
229 BOOLEAN bugflag;
230 INTBIG rtc;
231
232 oldme = layhead->box;
233 me = oldme;
234 bugflag = FALSE;
235 garbage = NULL;
236
237 if (me->nextbox != NULL)
238 {
239 for(him = me->nextbox; me->nextbox != NULL;)
240 {
241 if (bugflag)
242 {
243 oldme = me;
244 garbage->nextbox = NULL;
245 db_mrg_trash(garbage);
246 bugflag = FALSE;
247 }
248
249 /* now check rtc for results */
250 broken = db_mrg_breakbox(me, him, &rtc);
251 if (rtc == 1) /* if inclusion, remove me from list */
252 {
253 garbage = me;
254 if (me == layhead->box) /* if me is first on list */
255 {
256 layhead->box = me->nextbox; /* bypass me on list */
257 oldme = me;
258 bugflag = TRUE;
259 } else /* me is not the first on list */
260 {
261 oldme->nextbox = me->nextbox;
262
263 /* back me up on list for correct entry on next iter. */
264 me = oldme;
265 garbage->nextbox = NULL;
266 db_mrg_trash(garbage);
267 }
268 } else if (rtc == 2) /* independent... do nothing */
269 {
270 /* EMPTY */
271 } else
272 {
273 /* rtc = 0, replace me on list with list returned by break */
274 garbage = me;
275 for(temp=broken; temp!=NULL; ) /*find eol */
276 {
277 endptr = temp;
278 temp = temp->nextbox;
279 }
280 if (me == layhead->box) /* if me is first on list */
281 layhead->box = broken;
282 else oldme->nextbox = broken;
283 endptr->nextbox = me->nextbox;
284 me = endptr;
285 garbage->nextbox = NULL;
286 db_mrg_trash(garbage);
287 }
288 oldme=me;
289 me=me->nextbox;
290 him=me->nextbox;
291 } /* end for */
292 } /* end if */
293 }
294
db_mrg_breakbox(BOXPOLY * me,BOXPOLY * him,INTBIG * rtc)295 BOXPOLY *db_mrg_breakbox(BOXPOLY *me, BOXPOLY *him, INTBIG *rtc)
296 {
297 BOXPOLY *list, *oldme, *newlist;
298 BOXPOLY *garbage, *temp, *endptr, *broken;
299 INTBIG retc, calrtc;
300 BOOLEAN notfinished = TRUE;
301
302 newlist = NULL;
303 while (notfinished)
304 {
305 list = db_mrg_do_break(me, him, &retc);
306 if (retc == 2) /* if independent, do again with him->next */
307 if (him->nextbox != NULL) him = him->nextbox; else
308 {
309 /* we are at the end of the him list and have nothing to return */
310 if (newlist == NULL)
311 {
312 *rtc = 2;
313 return(NULL);
314 }
315 } else if (retc == 1)
316 {
317 /* if an inclusion */
318 if (newlist == NULL)
319 {
320 /* if empty list, let this guy be eaten up */
321 *rtc = 1;
322 return(NULL);
323 } else
324 {
325 /* if we get here, we are in deep trouble */
326 /* EMPTY */
327 }
328 } else /* if we got here, a break occurred..do something with list */
329 {
330 if (newlist == NULL) /* it has to be anyway */
331 {
332 newlist = list;
333 if (him->nextbox == NULL) /* at end of hims, return code 0 */
334 {
335 *rtc = 0;
336 return(newlist);
337 } else /* must recurse across the list */
338 {
339 oldme = NULL;
340 for (me=newlist; me!=NULL; )
341 {
342 /* do a break */
343 broken = db_mrg_breakbox(me, him->nextbox, &calrtc);
344 if (calrtc == 2) /* no break done, look at next guy */
345 {
346 oldme = me;
347 me = me->nextbox;
348 } else if (calrtc == 1)
349 {
350 /* me is an inclusion... remove me */
351 garbage = me;
352 if (me == newlist) /* if me is first on list */
353 {
354 newlist = me->nextbox;
355 me = newlist; /* put me at top of loop again */
356 if (me == NULL)
357 {
358 /* if me was only one left and got eaten */
359 *rtc = 1;
360 garbage->nextbox = NULL;
361 db_mrg_trash(garbage);
362 return(NULL);
363 }
364 } else /* me was not first on list */
365 {
366 /* oldme still behind me */
367 oldme->nextbox = me->nextbox;
368 me = me->nextbox;
369 }
370 garbage->nextbox = NULL;
371 db_mrg_trash(garbage);
372 } else
373 {
374 /* calrct=0, add list after newlist or after oldme */
375 for(temp=broken;temp!=NULL;) /*get eol */
376 {
377 endptr=temp;
378 temp=temp->nextbox;
379 }
380 endptr->nextbox = me->nextbox;
381 if (me == newlist) /* if me is first on list */
382 {
383 garbage = me;
384 newlist = broken;
385 oldme = endptr;
386 me = endptr->nextbox;
387 garbage->nextbox = NULL;
388 db_mrg_trash(garbage);
389 } else /* me is not first on list */
390 {
391 garbage = me;
392 oldme->nextbox = broken;
393 oldme = endptr;
394 me = endptr->nextbox;
395 garbage->nextbox = NULL;
396 db_mrg_trash(garbage);
397 }
398 } /* end if calrtc=0 */
399 } /* end for */
400 *rtc = 0;
401 return(newlist);
402 }
403 }
404 }
405 } /* end while */
406 return(NULL);
407 }
408
db_mrg_do_break(BOXPOLY * me,BOXPOLY * him,INTBIG * rtc)409 BOXPOLY *db_mrg_do_break(BOXPOLY *me, BOXPOLY *him, INTBIG *rtc)
410 {
411 BOXPOLY *broken, *breakk, *temp;
412
413 /* check for disjointedness */
414 if (me->right <= him->left || me->top <= him->bot || me->left >= him->right ||
415 me->bot >= him->top)
416 {
417 *rtc = 2;
418 return(NULL);
419 }
420
421 /* check for inclusion */
422 if (me->top <= him->top && me->left >= him->left && me->bot >= him->bot &&
423 me->right <= him->right)
424 {
425 *rtc = 1;
426 return(NULL);
427 }
428
429 /* check for identical boxes */
430 if (me->top == him->top && me->bot == him->bot && me->left == him->left &&
431 me->right == him->right)
432 {
433 *rtc = 1;
434 return(NULL);
435 }
436
437 if (me->top > him->top && me->left < him->left && me->bot < him->bot
438 && me->right < him->right && me->right > him->left)
439 {
440 temp = db_mrg_getbox();
441 db_mrg_assign_box(temp,me->left,me->right,me->top,him->top);
442 broken = temp;
443 temp = db_mrg_getbox();
444 broken->nextbox = temp;
445 db_mrg_assign_box(temp,me->left,him->left,him->top,him->bot);
446 breakk = db_mrg_getbox();
447 temp->nextbox = breakk;
448 db_mrg_assign_box(breakk,me->left,me->right,him->bot,me->bot);
449 *rtc = 0;
450 return(broken);
451 }
452
453 if (me->bot < him->bot && me->left < him->left && me->right > him->right
454 && me->top > him->bot && me->top < him->top)
455 {
456 temp = db_mrg_getbox();
457 db_mrg_assign_box(temp,me->left,him->left,me->top,me->bot);
458 broken = temp;
459 temp = db_mrg_getbox();
460 broken->nextbox = temp;
461 db_mrg_assign_box(temp,him->left,him->right,him->bot,me->bot);
462 breakk = db_mrg_getbox();
463 temp->nextbox = breakk;
464 db_mrg_assign_box(breakk,him->right,me->right,me->top,me->bot);
465 *rtc = 0;
466 return(broken);
467 }
468
469 if (me->right > him->right && me->top > him->top && me->bot < him->bot
470 && me->left < him->right && me->left > him->left)
471 {
472 temp = db_mrg_getbox();
473 db_mrg_assign_box(temp,me->left,me->right,me->top,him->top);
474 broken = temp;
475 temp = db_mrg_getbox();
476 broken->nextbox = temp;
477 db_mrg_assign_box(temp,him->right,me->right,him->top,him->bot);
478 breakk = db_mrg_getbox();
479 temp->nextbox = breakk;
480 db_mrg_assign_box(breakk,me->left,me->right,him->bot,me->bot);
481 *rtc = 0;
482 return(broken);
483 }
484
485 if (me->left < him->left && me->right > him->right && me->top > him->top
486 && me->bot > him->bot && me->bot < him->top)
487 {
488 temp = db_mrg_getbox();
489 db_mrg_assign_box(temp,me->left,him->left,me->top,me->bot);
490 broken = temp;
491 temp = db_mrg_getbox();
492 broken->nextbox = temp;
493 db_mrg_assign_box(temp,him->left,him->right,me->top,him->top);
494 breakk = db_mrg_getbox();
495 temp->nextbox = breakk;
496 db_mrg_assign_box(breakk,him->right,me->right,me->top,me->bot);
497 *rtc = 0;
498 return(broken);
499 }
500
501 if (him->left <= me->left && him->top >= me->top && him->bot <= me->bot
502 && me->right > him->right && me->left < him->right)
503 {
504 broken = db_mrg_getbox();
505 db_mrg_assign_box(broken,him->right,me->right,me->top,me->bot);
506 *rtc = 0;
507 return(broken);
508 }
509
510 if (me->left < him->left && him->top >= me->top && him->bot <= me->bot
511 && him->right >= me->right && me->right > him->left)
512 {
513 broken = db_mrg_getbox();
514 db_mrg_assign_box(broken,me->left,him->left,me->top,me->bot);
515 *rtc = 0;
516 return(broken);
517 }
518
519 if (him->left <= me->left && him->right >= me->right && him->bot <= me->bot
520 && me->bot < him->top && me->top > him->top)
521 {
522 broken = db_mrg_getbox();
523 db_mrg_assign_box(broken,me->left,me->right,me->top,him->top);
524 *rtc = 0;
525 return(broken);
526 }
527
528 if (him->left <= me->left && him->right >= me->right && him->top >= me->top
529 && me->top > him->bot && me->bot < him->bot)
530 {
531 broken = db_mrg_getbox();
532 db_mrg_assign_box(broken,me->left,me->right,him->bot,me->bot);
533 *rtc = 0;
534 return(broken);
535 }
536
537 if (me->top > him->top && me->left < him->left && me->bot < him->top &&
538 me->bot >= him->bot && me->right > him->left && me->right <= him->right)
539 {
540 temp = db_mrg_getbox();
541 broken = temp;
542 db_mrg_assign_box(temp,me->left,me->right,me->top,him->top);
543 temp = db_mrg_getbox();
544 broken->nextbox = temp;
545 db_mrg_assign_box(temp,me->left,him->left,him->top,me->bot);
546 *rtc = 0;
547 return(broken);
548 }
549
550 if (me->top > him->top && me->right > him->right && me->left >= him->left
551 && me->left < him->right && me->bot < him->top && me->bot >= him->bot)
552 {
553 temp = db_mrg_getbox();
554 broken = temp;
555 db_mrg_assign_box(temp,me->left,me->right,me->top,him->top);
556 temp = db_mrg_getbox();
557 broken->nextbox = temp;
558 db_mrg_assign_box(temp,him->right,me->right,him->top,me->bot);
559 *rtc = 0;
560 return(broken);
561 }
562
563 if (me->right > him->right && me->bot < him->bot && me->left >= him->left
564 && me->left < him->right && me->top > him->bot && me->top <= him->top)
565 {
566 temp = db_mrg_getbox();
567 broken = temp;
568 db_mrg_assign_box(temp,him->right,me->right,me->top,him->bot);
569 temp = db_mrg_getbox();
570 broken->nextbox = temp;
571 db_mrg_assign_box(temp,me->left,me->right,him->bot,me->bot);
572 *rtc = 0;
573 return(broken);
574 }
575
576 if (me->left < him->left && me->bot < him->bot && me->top > him->bot &&
577 me->top <= him->top && me->right > him->left && me->right <= him->right)
578 {
579 temp = db_mrg_getbox();
580 broken = temp;
581 db_mrg_assign_box(temp,me->left,him->left,me->top,him->bot);
582 temp = db_mrg_getbox();
583 broken->nextbox = temp;
584 db_mrg_assign_box(temp,me->left,me->right,him->bot,me->bot);
585 *rtc = 0;
586 return(broken);
587 }
588
589 if (me->left < him->left && me->right > him->right
590 && him->top >= me->top && him->bot <= me->bot)
591 {
592 temp = db_mrg_getbox();
593 broken = temp;
594 db_mrg_assign_box(temp,me->left,him->left,me->top,me->bot);
595 temp = db_mrg_getbox();
596 broken->nextbox = temp;
597 db_mrg_assign_box(temp,him->right,me->right,me->top,me->bot);
598 *rtc = 0;
599 return(broken);
600 }
601
602 if (me->top > him->top && me->bot < him->bot
603 && me->left >= him->left && me->right <= him->right)
604 {
605 temp = db_mrg_getbox();
606 broken = temp;
607 db_mrg_assign_box(temp,me->left,me->right,me->top,him->top);
608 temp = db_mrg_getbox();
609 broken->nextbox = temp;
610 db_mrg_assign_box(temp,me->left,me->right,him->bot,me->bot);
611 *rtc = 0;
612 return(broken);
613 }
614
615 /* give the user a warning if this routine did not catch some case */
616 ttyputerr(_("Warning: merging done incorrectly"));
617 ttyputerr(x_("me: left = %ld, right = %ld, top = %ld, bot = %ld"),
618 me->left, me->right, me->top, me->bot);
619 ttyputerr(x_("him: left = %ld, right = %ld, top = %ld, bot = %ld"),
620 him->left, him->right, him->top, him->bot);
621
622 /* although this is in error, it will enable a completion of the write */
623 *rtc = 1;
624 return(NULL);
625 }
626
db_mrg_write_lists(void (* writepolygon)(INTBIG,TECHNOLOGY *,INTBIG *,INTBIG *,INTBIG))627 void db_mrg_write_lists(void (*writepolygon)(INTBIG, TECHNOLOGY*, INTBIG*, INTBIG*, INTBIG))
628 {
629 BOXLISTHEAD *lay_box;
630 BOXPOLY *boxscanptr, *garbage, *oldboxscan;
631 BOOLEAN lay_not_done, merged;
632
633 for(lay_box=db_mrg_curr_cell; lay_box!=NULL; lay_box=lay_box->nextlayer) /* for each layer... */
634 {
635 db_mrg_remove_inclusion(lay_box); /* remove inclusions down list */
636 db_mrg_remove_overlap(lay_box); /* break into nonoverlapping boxes */
637 db_mrg_remove_inclusion(lay_box);
638 lay_not_done = TRUE;
639 /* (*setlayer)(lay_box->layer, lay_box->tech); */
640 db_mrg_polycoordlist.firstpoly = NULL;
641 db_mrg_polycoordlist.numedge = 0;
642 while (lay_not_done)
643 {
644 db_mrg_polycoordlist.modified = 0;
645 for(boxscanptr=lay_box->box; boxscanptr != NULL; )
646 {
647 /* passing through list of boxes */
648 merged = db_mrg_mergeboxwithpolygon(boxscanptr);
649 if (merged) /* if list was modified */
650 {
651 /* set flag that we made a modification */
652 db_mrg_polycoordlist.modified = 1;
653 merged = FALSE; /* reset indicator flag */
654
655 /* if box is first on list */
656 if (boxscanptr == lay_box->box)
657 {
658 garbage = boxscanptr;
659 lay_box->box = boxscanptr->nextbox;
660 boxscanptr = lay_box->box;
661 garbage->nextbox = NULL;
662 db_mrg_trash(garbage);
663
664 /* if NULL list, we are done */
665 if (lay_box->box == NULL)
666 {
667 lay_not_done = FALSE;
668 break;
669 }
670 } else
671 {
672 /* not the first on list */
673 garbage = boxscanptr;
674
675 /* LINTED "oldboxscan" used in proper order */
676 oldboxscan->nextbox = boxscanptr->nextbox;
677 boxscanptr = boxscanptr->nextbox;
678 garbage->nextbox = NULL;
679 db_mrg_trash(garbage);
680 }
681 } else
682 {
683 /* no merge done, check next box */
684 oldboxscan = boxscanptr;
685 boxscanptr = boxscanptr->nextbox;
686 }
687
688 /* allow maxnumpts as a max */
689 if (db_mrg_polycoordlist.numedge > maxnumpts) break;
690 } /* end for */
691
692 /*
693 * write out box if: (1) entire pass yielded no merges
694 * (2) end of list (3) too many points on list
695 */
696 if ((!db_mrg_polycoordlist.modified) || (!lay_not_done) ||
697 (db_mrg_polycoordlist.numedge > maxnumpts))
698 {
699 db_mrg_write_polygon(writepolygon, lay_box->layer, lay_box->tech);
700 db_mrg_remove_poly_list(); /* dispose of polygon records */
701
702 /* re-initialize for next pass */
703 db_mrg_polycoordlist.firstpoly = NULL;
704 db_mrg_polycoordlist.numedge = 0;
705 db_mrg_polycoordlist.modified = 0;
706 }
707 } /* end while */
708 }
709 }
710
711 /* Macro to insert edge on polygon */
712 # define INSERT_EDGE(pred,tmp,copy,succ,dmaep1,dmaep2) \
713 tmp = db_mrg_getpoly(); \
714 tmp->nextpoly = succ; \
715 if (pred != NULL) {pred->nextpoly = tmp;} \
716 db_mrg_assign_edge(tmp, dmaep1, dmaep2); \
717 copy = tmp;
718
719 /* Macro to remove n edges (nedge) from polygon */
720 # define REMOVE_EDGE(pred,start,tmp,nedge) \
721 for (i = 0; i < nedge; i++) { \
722 tmp = start->nextpoly; \
723 pred->nextpoly = tmp; \
724 if (start == db_mrg_polycoordlist.firstpoly) { \
725 db_mrg_polycoordlist.firstpoly = tmp; \
726 } \
727 db_mrg_killpoly(start); \
728 start = tmp; \
729 }
730
db_mrg_mergeboxwithpolygon(BOXPOLY * boxptr)731 BOOLEAN db_mrg_mergeboxwithpolygon(BOXPOLY *boxptr)
732 {
733 POLYCOORD *polyptr,*creatptr,*backptr;
734 BOOLEAN pair, ok, one_con, err;
735 INTBIG i, firstcon, connect, auxx, ed_chk, j, ed_con;
736
737 pair = FALSE; /* flag to indicate a pair */
738 one_con = FALSE; /* flas to intdicate that intersection was found */
739 boxptr->numsides = 0;
740 ok = FALSE;
741 backptr = NULL;
742
743 /* initialise seen field if list exists */
744 if (db_mrg_polycoordlist.firstpoly != NULL)
745 {
746 /* initialize pointer to list */
747 polyptr = db_mrg_polycoordlist.firstpoly;
748 for(i=0; i!=db_mrg_polycoordlist.numedge;)
749 {
750 polyptr->seen = 1;
751 i++;
752 polyptr = polyptr->nextpoly;
753 }
754 }
755 for(i=0; i<4; i++)
756 {
757 boxptr->numint[i] = 0;
758 boxptr->polyint[i]=boxptr->auxpolyint[i] = NULL;
759 }
760 if (db_mrg_polycoordlist.firstpoly == NULL) /* if nothing on list */
761 {
762 /* make first edge (at head) */
763 INSERT_EDGE(backptr,creatptr,backptr,NULL,boxptr->ll,boxptr->ul)
764 db_mrg_polycoordlist.firstpoly = creatptr;
765
766 /* second edge */
767 INSERT_EDGE(backptr,creatptr,backptr,NULL,boxptr->ul,boxptr->ur)
768
769 /* third edge */
770 INSERT_EDGE(backptr,creatptr,backptr,NULL,boxptr->ur,boxptr->lr)
771
772 /* fourth edge (and form ring) */
773 INSERT_EDGE(backptr,creatptr,backptr,db_mrg_polycoordlist.firstpoly,boxptr->lr,boxptr->ll)
774
775 db_mrg_housekeeper(); /* set up edge numbers */;
776 return(TRUE); /* all done */
777 } else /* we have some edges already */
778 {
779 for(polyptr=db_mrg_polycoordlist.firstpoly; polyptr->seen; /* check for intersection to all edges */
780 polyptr=polyptr->nextpoly)
781 {
782 polyptr->seen = 0; /* indicate that we have been here */
783 connect = db_mrg_check_intersect(boxptr, polyptr, &ed_con);
784 if (connect == PTMATCH) /* if a point intersection was found */
785 return(FALSE); /* point intersections are not permitted */
786 if (connect) /* if connection was found */
787 {
788 one_con = TRUE; /* found at least 1 connection */
789
790 /* > 2 connections on one side */
791 if (boxptr->numint[ed_con] == 2) return(FALSE);
792 if (pair && boxptr->polyint[ed_con] != NULL) /* 2 pairs found */
793 return(FALSE);
794 if (boxptr->polyint[ed_con] == NULL) /* if first connection */
795 {
796 /* link edge to polygon descriptor */
797 boxptr->polyint[ed_con] = polyptr;
798 boxptr->numint[ed_con] += 1; /* increment count for side */
799
800 /* increment number sides intersected */
801 boxptr->numsides += 1;
802 } else /* second connection for one "first" edge */
803 {
804 /* link to poly descriptor */
805 boxptr->auxpolyint[ed_con] = polyptr;
806
807 /* increment side connection count */
808 boxptr->numint[ed_con] += 1;
809 pair = TRUE; /* we have found a pair */
810 }
811 } /* end if connect */
812 } /* end for */
813
814 if (!one_con) /* if no connections found */
815 return(FALSE);
816 else /* found at least one connection */
817 {
818 /* based on #sides of box which touched polygon */
819 switch (boxptr->numsides)
820 {
821 case 4: /* intersects on 4 edges */
822 if (pair) /* intersects 1 edge twice */
823 {
824 /* find edge which intersects twice */
825 for(i=0; boxptr->numint[i]!=2; i++)
826 ;
827 firstcon = i;
828 if ((boxptr->polyint[db_mrg_nxtside(i)]->indx) ==
829 db_mrg_succ(boxptr->polyint[i]->indx))
830 auxx = 0; /* check the statement below */
831 else if((boxptr->polyint[db_mrg_nxtside(i)]->indx) ==
832 db_mrg_succ(boxptr->auxpolyint[i]->indx))
833 auxx = 1;
834 else /* neither edge connection had next side with correct index number */
835 return(FALSE);
836 if (auxx) /* if auxiliary pointer is the start */
837 {
838 for(ed_chk=db_mrg_nxtside(i); ed_chk!=i;
839 ed_chk=db_mrg_nxtside(ed_chk))
840 if ((boxptr->polyint[db_mrg_nxtside(ed_chk)]->indx) ==
841 db_mrg_succ(boxptr->polyint[ed_chk]->indx))
842 continue;
843 else
844 /* successor had wrong index number */
845 return(FALSE);
846
847 /* if we got here all is well */
848 db_mrg_insert5(firstcon, auxx, boxptr);
849 } else /* auxx = 0 */
850 {
851 for(ed_chk=db_mrg_nxtside(i); ed_chk != i;
852 ed_chk=db_mrg_nxtside(ed_chk))
853 {
854 /* check for last edge */
855 if (ed_chk != db_mrg_prevside(firstcon))
856 {
857 if (boxptr->polyint[db_mrg_nxtside(
858 ed_chk)]->indx == db_mrg_succ(
859 boxptr->polyint[ed_chk]->indx))
860 continue;
861 return(FALSE); /* index numbers out of sequence */
862 } else
863 {
864 if ((boxptr->auxpolyint[db_mrg_nxtside(
865 ed_chk)]->indx) == (db_mrg_succ(
866 boxptr->polyint[ed_chk]->indx)))
867 continue;
868 return(FALSE); /* index numbers out of sequence */
869 }
870 }
871 db_mrg_insert5(firstcon, auxx, boxptr);
872 }
873 } else /* intersects 4 edges, 1 time each edge */
874 {
875 ok = FALSE;
876
877 /* find "start" edge of intersect sequence */
878 for(i=0;i<4;i++)
879 {
880 err = FALSE;
881 ed_chk = i;
882 for(j = 0; j < 3; j++)
883 {
884 if ((boxptr->polyint[db_mrg_nxtside(
885 ed_chk)]->indx) != (db_mrg_succ(
886 boxptr->polyint[ed_chk]->indx)))
887 err = TRUE; /* error found */
888 ed_chk = db_mrg_nxtside(ed_chk);
889 }
890 if (!err)
891 {
892 ok = TRUE;
893 break;
894 }
895 } /* end for */
896 if (ok) /* check if we found a correct sequence */
897 {
898 firstcon = i;
899 db_mrg_insert4(firstcon,boxptr);
900 } else
901 return(FALSE); /* index out of sequence */
902 }
903 break;
904
905 case 3:
906 /* if a pair of contacts on 1 edge of box ... loop found */
907 if (pair) return(FALSE);
908 else
909 {
910 /* i is index of edge which doesn't intersect polygon */
911 for(i = 0; i < 4; i++)
912 if (boxptr->polyint[i] == NULL) break;
913
914 /* index of first non null side */
915 firstcon = db_mrg_nxtside(i);
916 for(j = firstcon; j != db_mrg_prevside(i);
917 j = db_mrg_nxtside(j))
918 if ((boxptr->polyint[db_mrg_nxtside(j)]->indx) !=
919 (db_mrg_succ(boxptr->polyint[j]->indx)))
920 return(FALSE);
921 db_mrg_insert3(firstcon,boxptr);
922 }
923 break;
924
925 case 2: /* box has 2 edges which intersect polygon */
926 if (pair) /* the usual */
927 return(FALSE);
928 else
929 {
930 for(i = 0; i < 4; i++) /* find a NULL edge */
931 if (boxptr->polyint[i] == NULL) break;
932 for(j = i; boxptr->polyint[j] == NULL;
933 j = db_mrg_nxtside(j))
934 ;
935 firstcon = j; /* first edge connection */
936
937 /* have detected nonsadjacent pair of intersections */
938 if (boxptr->polyint[db_mrg_nxtside(firstcon)] == NULL)
939 return(FALSE);
940 if ((boxptr->polyint[db_mrg_nxtside(j)]->indx) !=
941 (db_mrg_succ(boxptr->polyint[j]->indx)))
942 return(FALSE); /* index numbers out of sequence... */
943 db_mrg_insert2(firstcon,boxptr);
944 }
945 break;
946
947 case 1: /* one edge intersects */
948 if (pair) /* if a pair, we have a loop */
949 return(FALSE);
950 else
951 {
952 /* find edge which intersects */
953 for(i=0; boxptr->polyint[i]==NULL; i++)
954 ;
955 firstcon = i;
956 db_mrg_insert1(firstcon,boxptr);
957 }
958 break;
959
960 default:
961 break;
962 } /* end switch */
963
964 db_mrg_housekeeper();
965 return(TRUE); /* successful addition of box to polygon */
966 } /* end else */
967 } /* end have edges already */
968 }
969
970 /* returns 0 if no intersection,else 1 (line intersection) or 2 (point intersection) */
db_mrg_check_intersect(BOXPOLY * boxptr,POLYCOORD * polyptr,INTBIG * ed_con)971 INTBIG db_mrg_check_intersect(BOXPOLY *boxptr, POLYCOORD *polyptr, INTBIG *ed_con)
972 {
973 switch (polyptr->ed_or)
974 {
975 case UP:
976 if (boxptr->right == polyptr->ed_val) /* may be colinear */
977 {
978 if ((boxptr->bot >= polyptr->ed_start[1] &&
979 boxptr->bot < polyptr->ed_end[1]) ||
980 (boxptr->top <= polyptr->ed_end[1] &&
981 boxptr->top > polyptr->ed_start[1]) ||
982 (boxptr->bot < polyptr->ed_start[1] &&
983 boxptr->top > polyptr->ed_end[1]))
984 {
985 *ed_con = DOWN;
986 return(1);
987 }
988 return(db_mrg_check_point(polyptr->ed_start,boxptr->ur,
989 polyptr->ed_end,boxptr->lr)); /* check for pt connect */
990 }
991 return(0);
992
993 case RIGHT:
994 if (boxptr->bot == polyptr->ed_val)
995 {
996 if ((boxptr->left >= polyptr->ed_start[0] &&
997 boxptr->left < polyptr->ed_end[0]) ||
998 (boxptr->right > polyptr->ed_start[0] &&
999 boxptr->right <= polyptr->ed_end[0]) ||
1000 (boxptr->left < polyptr->ed_start[0] &&
1001 boxptr->right > polyptr->ed_end[0]))
1002 {
1003 *ed_con = LEFT;
1004 return(1);
1005 }
1006 return(db_mrg_check_point(polyptr->ed_start,boxptr->lr,
1007 polyptr->ed_end,boxptr->ll));
1008 }
1009 return(0);
1010
1011 case DOWN:
1012 if (boxptr->left == polyptr->ed_val)
1013 {
1014 if ((boxptr->bot >= polyptr->ed_end[1] &&
1015 boxptr->bot < polyptr->ed_start[1]) ||
1016 (boxptr->top > polyptr->ed_end[1] &&
1017 boxptr->top <= polyptr->ed_start[1]) ||
1018 (boxptr->top > polyptr->ed_start[1] &&
1019 boxptr->bot < polyptr->ed_end[1]))
1020 {
1021 *ed_con = UP;
1022 return(1);
1023 }
1024 return(db_mrg_check_point(polyptr->ed_start,boxptr->ll,
1025 polyptr->ed_end,boxptr->ul));
1026 }
1027 return(0);
1028
1029 case LEFT:
1030 if (boxptr->top == polyptr->ed_val)
1031 {
1032 if ((boxptr->left >= polyptr->ed_end[0] &&
1033 boxptr->left < polyptr->ed_start[0]) ||
1034 (boxptr->right > polyptr->ed_end[0] &&
1035 boxptr->right <= polyptr->ed_start[0]) ||
1036 (boxptr->left < polyptr->ed_end[0] &&
1037 boxptr->right > polyptr->ed_start[0]))
1038 {
1039 *ed_con = RIGHT;
1040 return(1);
1041 }
1042 return(db_mrg_check_point(polyptr->ed_start,boxptr->ul,
1043 polyptr->ed_end,boxptr->ur));
1044 }
1045 return(0);
1046 } /* end switch */
1047 return(0);
1048 }
1049
1050 /* PoinT EQual macro */
1051
1052 # define PTEQ(x,y) \
1053 (((x)[0] == (y)[0]) && ((x)[1] == (y)[1]))
1054
1055 /* checks if points a1, a2 match or if points b1, b2 match */
db_mrg_check_point(INTBIG pointa1[],INTBIG pointa2[],INTBIG pointb1[],INTBIG pointb2[])1056 INTBIG db_mrg_check_point(INTBIG pointa1[], INTBIG pointa2[], INTBIG pointb1[],
1057 INTBIG pointb2[])
1058 {
1059 if (PTEQ(pointa1, pointa2) || PTEQ(pointb1, pointb2)) {
1060 return(PTMATCH); /* at least one pair matches */
1061 }
1062 return(0); /* neither pair matches */
1063 }
1064
db_mrg_insert1(INTBIG firstcon,BOXPOLY * boxptr)1065 void db_mrg_insert1(INTBIG firstcon, BOXPOLY *boxptr)
1066 {
1067 POLYCOORD *polyptr, *nextedge, *creatptr, *backptr;
1068 INTBIG *p0, *p1, *p2, *p3;
1069
1070 /* get pointer to edge of intersection */
1071 polyptr = boxptr->polyint[firstcon];
1072 nextedge = polyptr->nextpoly;
1073 for(backptr = db_mrg_polycoordlist.firstpoly; backptr->nextpoly != polyptr;
1074 backptr = backptr->nextpoly) /* gat pointer to edge before polyptr */
1075 ;
1076
1077 switch (polyptr->ed_or) { /* based on polygon edge orientation */
1078 case UP:
1079 /* p3 --- p1 |
1080 | \/ ^
1081 | \/ ^
1082 p2 --- p0 |
1083 */
1084 p0 = boxptr->lr;
1085 p1 = boxptr->ur;
1086 p2 = boxptr->ll;
1087 p3 = boxptr->ul;
1088 break;
1089
1090 case RIGHT:
1091 /* p2 --- p3
1092 | |
1093 | |
1094 p0 -<- p1
1095 --->>>---
1096 */
1097 p0 = boxptr->ll;
1098 p1 = boxptr->lr;
1099 p2 = boxptr->ul;
1100 p3 = boxptr->ur;
1101 break;
1102
1103 case DOWN:
1104 /* | p0 --- p2
1105 \/ ^ |
1106 \/ ^ |
1107 | p1 --- p3
1108 */
1109 p0 = boxptr->ul;
1110 p1 = boxptr->ll;
1111 p2 = boxptr->ur;
1112 p3 = boxptr->lr;
1113 break;
1114
1115 case LEFT:
1116 /* ---<<<---
1117 p1 ->- p0
1118 | |
1119 | |
1120 p3 --- p2
1121 */
1122 p0 = boxptr->ur;
1123 p1 = boxptr->ul;
1124 p2 = boxptr->lr;
1125 p3 = boxptr->ll;
1126 break;
1127
1128 default:
1129 break;
1130 } /* end switch */
1131 /*
1132 Generic code to handle case of 1 box edge touching 1 polygon edge
1133 p0: point on box which might intersect start point of edge
1134 p1: point on box which might intersect end point of edge
1135 p2: point on box which is diagonally opposite p1
1136 p3: point on box which is diagonally opposite p0
1137 */
1138
1139 /* if first point matches */
1140 if PTEQ(polyptr->ed_start, p0) {
1141 /* if second point matches */
1142 if PTEQ(polyptr->ed_end, p1) {
1143 /* both points match (adjust edge start/end points) */
1144 db_mrg_assign_edge(backptr, backptr->ed_start, p2);
1145 db_mrg_assign_edge(polyptr, p2, p3);
1146 db_mrg_assign_edge(nextedge, p3, nextedge->ed_end);
1147 }
1148 else { /* only first point matches (adjust 2 edges, add 2 edges) */
1149 db_mrg_assign_edge(backptr, backptr->ed_start, p2);
1150 db_mrg_assign_edge(polyptr, p2, p3);
1151 INSERT_EDGE(polyptr,creatptr,polyptr,nextedge, p3, p1)
1152 INSERT_EDGE(polyptr,creatptr,polyptr,nextedge, p1, nextedge->ed_start)
1153 }
1154 }
1155 else { /* first point does not match */
1156 /* if second point matches */
1157 if PTEQ(polyptr->ed_end, p1) {
1158 /* only second point matches (adjust 2 edges, add 2 edges) */
1159 db_mrg_assign_edge(polyptr,polyptr->ed_start, p0);
1160 db_mrg_assign_edge(nextedge, p3,nextedge->ed_end);
1161 INSERT_EDGE(polyptr,creatptr,polyptr,nextedge, p0, p2)
1162 INSERT_EDGE(polyptr,creatptr,polyptr,nextedge, p2, p3)
1163 }
1164 else {
1165 /* neither point matches (adjust first edge, add 4 new edges) */
1166 db_mrg_assign_edge(polyptr,polyptr->ed_start, p0);
1167 INSERT_EDGE(polyptr,creatptr,polyptr,nextedge, p0, p2)
1168 INSERT_EDGE(polyptr,creatptr,polyptr,nextedge, p2, p3)
1169 INSERT_EDGE(polyptr,creatptr,polyptr,nextedge, p3, p1)
1170 INSERT_EDGE(polyptr,creatptr,polyptr,nextedge, p1, nextedge->ed_start)
1171 }
1172 }
1173 }
1174
1175 /* inserts box into polygon where 2 edges touched */
db_mrg_insert2(INTBIG firstcon,BOXPOLY * boxptr)1176 void db_mrg_insert2(INTBIG firstcon, BOXPOLY *boxptr)
1177 {
1178 POLYCOORD *polyptr, *nextedge, *creatptr, *backptr;
1179 INTBIG *p0, *p1, *p2;
1180
1181 /* assign polyptr to first edge where intersection occurs */
1182 polyptr = boxptr->polyint[firstcon];
1183 nextedge = polyptr->nextpoly; /* get pointer to next edge */
1184
1185 switch (polyptr->ed_or) { /* based on polygon edge direction */
1186 case RIGHT:
1187 /*
1188 p2-p1 |
1189 | | ^
1190 p0-| ^
1191 |
1192 -->>--|
1193 */
1194 p0 = boxptr->ll;
1195 p1 = boxptr->ur;
1196 p2 = boxptr->ul;
1197 break;
1198
1199 case LEFT:
1200 /*
1201 --<<--
1202 | |--p0
1203 \/ | |
1204 \/ | |
1205 | p1-p2
1206 */
1207 p0 = boxptr->ur;
1208 p1 = boxptr->ll;
1209 p2 = boxptr->lr;
1210 break;
1211
1212 case UP:
1213 /*
1214 --<<--|
1215 |
1216 p1--| ^
1217 | | ^
1218 | | |
1219 p2-p0 |
1220 */
1221 p0 = boxptr->lr;
1222 p1 = boxptr->ul;
1223 p2 = boxptr->ll;
1224 break;
1225
1226 case DOWN:
1227 /*
1228 | p0--p2
1229 \/ | |
1230 \/ | |
1231 | |---p1
1232 |
1233 -->>----
1234 */
1235 p0 = boxptr->ul;
1236 p1 = boxptr->lr;
1237 p2 = boxptr->ur;
1238 break;
1239
1240 default:
1241 break;
1242 } /* end switch */
1243 /*
1244 Generic code to handle case of 2 box edges touching 2 polygon edges
1245 p0: point on box which might intersect start point of firsst polygon edge
1246 p1: point on box which might intersect end point of second polygon edge
1247 p2: point on box which is diagonally opposite "corner" of intersection of polygon edges
1248 */
1249
1250 /* if first point matches */
1251 if PTEQ(polyptr->ed_start, p0) {
1252 /* if second point matches */
1253 if PTEQ(nextedge->ed_end, p1) {
1254 /* both points match */
1255 db_mrg_assign_edge(polyptr,polyptr->ed_start,p2);
1256 db_mrg_assign_edge(nextedge,p2,nextedge->ed_end);
1257 }
1258 else {
1259 /* first matches only */
1260 for(backptr = db_mrg_polycoordlist.firstpoly;
1261 backptr->nextpoly != polyptr;
1262 backptr = backptr->nextpoly)
1263 ;
1264 db_mrg_assign_edge(backptr,backptr->ed_start,p2);
1265 db_mrg_assign_edge(polyptr,p2,p1);
1266 db_mrg_assign_edge(nextedge,p1,nextedge->ed_end);
1267 }
1268 }
1269 else { /* first point doesnt match */
1270 /* second point matches */
1271 if PTEQ(nextedge->ed_end, p1) {
1272 db_mrg_assign_edge(polyptr,polyptr->ed_start,p0);
1273 db_mrg_assign_edge(nextedge,p0,p2);
1274 nextedge = nextedge->nextpoly;
1275 db_mrg_assign_edge(nextedge,p2,nextedge->ed_end);
1276 }
1277 else {
1278 /* neither point touches */
1279 db_mrg_assign_edge(polyptr,polyptr->ed_start,p0);
1280 INSERT_EDGE(polyptr,creatptr,polyptr,nextedge,p0,p2)
1281 INSERT_EDGE(polyptr,creatptr,polyptr,nextedge,p2,p1)
1282 db_mrg_assign_edge(nextedge,p1,nextedge->ed_end);
1283 }
1284 }
1285 }
1286
db_mrg_insert3(INTBIG firstcon,BOXPOLY * boxptr)1287 void db_mrg_insert3(INTBIG firstcon, BOXPOLY *boxptr)
1288 {
1289 POLYCOORD *polyptr, *nextedge, *garbage, *backptr, *temp;
1290 INTBIG i;
1291 INTBIG *p0, *p1;
1292
1293 /* assign polyptr to first edge */
1294 polyptr = boxptr->polyint[firstcon];
1295 nextedge = polyptr->nextpoly;
1296 nextedge = nextedge->nextpoly; /* third edge which intersects */
1297 for(backptr = db_mrg_polycoordlist.firstpoly; backptr->nextpoly != polyptr;
1298 backptr = backptr->nextpoly) /* get back pointer */
1299 ;
1300
1301 switch (polyptr->ed_or) { /* based on polygon edge direction */
1302 case RIGHT:
1303 /*
1304 ---<<---|
1305 |
1306 p1----| |
1307 | | ^
1308 | | ^
1309 p0----| |
1310 |
1311 --->>---|
1312 */
1313 p0 = boxptr->ll;
1314 p1 = boxptr->ul;
1315 break;
1316
1317 case LEFT:
1318 /*
1319 |---<<---
1320 |
1321 | |----p0
1322 \/ | |
1323 \/ | |
1324 | |----p1
1325 |
1326 |--->>---
1327 */
1328 p0 = boxptr->ur;
1329 p1 = boxptr->lr;
1330 break;
1331
1332 case UP:
1333 /*
1334 |---<<----|
1335 | |
1336 | |-----| |
1337 \/ | | ^
1338 \/ | | ^
1339 | p1---p0 |
1340 | |
1341 */
1342 p0 = boxptr->lr;
1343 p1 = boxptr->ll;
1344 break;
1345
1346 case DOWN:
1347 /*
1348 | |
1349 | p0---p1 |
1350 \/ | | ^
1351 \/ | | ^
1352 | |-----| |
1353 | |
1354 |--->>----|
1355 */
1356 p0 = boxptr->ul;
1357 p1 = boxptr->ur;
1358 break;
1359
1360 default:
1361 break;
1362 } /* end switch */
1363 /*
1364 Generic code to handle case of 3 box edges touching 3 polygon edges
1365 p0: point on box which might intersect start point of first polygon edge
1366 p1: point on box which might intersect end point of third polygon edge
1367 */
1368
1369 /* if first point matches */
1370 if PTEQ(polyptr->ed_start, p0) {
1371 /* if second point matches */
1372 if PTEQ(nextedge->ed_end, p1) {
1373 /* both points match */
1374 nextedge = nextedge->nextpoly;
1375 db_mrg_assign_edge(backptr,backptr->ed_start,
1376 nextedge->ed_end);
1377 REMOVE_EDGE(backptr,polyptr,garbage,4) /* remove 4 edges beginning with polyptr */
1378 }
1379 else { /* first point matches only */
1380 db_mrg_assign_edge(backptr,backptr->ed_start,p1);
1381 db_mrg_assign_edge(nextedge,p1,nextedge->ed_end);
1382 REMOVE_EDGE(backptr,polyptr,garbage,2) /* remove 2 edges beginning with polyptr */
1383 }
1384 }
1385 else { /* first point doesn't match */
1386 if PTEQ(nextedge->ed_end, p1) {
1387 /* second point matches only */
1388 garbage = polyptr->nextpoly;
1389 nextedge = nextedge->nextpoly;
1390 db_mrg_assign_edge(polyptr,polyptr->ed_start,p0);
1391 db_mrg_assign_edge(nextedge,p0,nextedge->ed_end);
1392 REMOVE_EDGE(polyptr,garbage,temp,2) /* remove 2 edges beginning with garbage */
1393 }
1394 else { /* neither point matches */
1395 db_mrg_assign_edge(polyptr,polyptr->ed_start,p0);
1396 temp = polyptr->nextpoly;
1397 db_mrg_assign_edge(temp,p0,p1);
1398 db_mrg_assign_edge(nextedge,p1,nextedge->ed_end);
1399 }
1400 }
1401 }
1402
1403 /* inserts box where each edge intersected once */
db_mrg_insert4(INTBIG firstcon,BOXPOLY * boxptr)1404 void db_mrg_insert4(INTBIG firstcon, BOXPOLY *boxptr)
1405 {
1406 INTBIG i;
1407 POLYCOORD *polyptr, *nextedge, *garbage, *temp, *backptr;
1408 INTBIG *p0;
1409 INTBIG descendp; /* for the below/above/rightof/leftof case */
1410
1411 polyptr = boxptr->polyint[firstcon];
1412 nextedge = boxptr->polyint[db_mrg_prevside(firstcon)];
1413 for(backptr = db_mrg_polycoordlist.firstpoly; backptr->nextpoly != polyptr;
1414 backptr = backptr->nextpoly) /* get back pointer */
1415 ;
1416
1417 switch (polyptr->ed_or) { /* based on polygon edge direction */
1418 case RIGHT:
1419 /*
1420 |----<<---|
1421 | |
1422 \/ |-----| |
1423 \/ | | ^
1424 | | | ^
1425 p0----| |
1426 |
1427 --->>---|
1428 */
1429 p0 = boxptr->ll;
1430 descendp = ((nextedge->ed_end[1] < polyptr->ed_start[1]) ? 1 : 0);
1431 break;
1432
1433 case LEFT:
1434 /*
1435 |---<<---
1436 |
1437 | |----p0
1438 \/ | | |
1439 \/ | | ^
1440 | |-----| ^
1441 | |
1442 |--->>----|
1443 */
1444 p0 = boxptr->ur;
1445 descendp = ((nextedge->ed_end[1] > polyptr->ed_start[1]) ? 1 : 0);
1446 break;
1447
1448 case UP:
1449 /*
1450 |---<<----|
1451 | |
1452 | |-----| |
1453 \/ | | ^
1454 \/ | | ^
1455 | |----p0 |
1456 | |
1457 |--->>-
1458 */
1459 p0 = boxptr->lr;
1460 descendp = ((nextedge->ed_end[0] > polyptr->ed_start[0]) ? 1 : 0);
1461 break;
1462
1463 case DOWN:
1464 /*
1465 -<<---|
1466 | |
1467 | p0---p1 |
1468 \/ | | ^
1469 \/ | | ^
1470 | |-----| |
1471 | |
1472 |--->>----|
1473 */
1474 p0 = boxptr->ul;
1475 descendp = ((nextedge->ed_end[0] < polyptr->ed_start[0]) ? 1 : 0);
1476 break;
1477
1478 default:
1479 break;
1480 } /* end switch */
1481 /*
1482 Generic code to handle case where 4 polygon edges perfectly enclose
1483 (not necessarily fullythough) box
1484 p0: start point on box which intersects first edge on polygon
1485 */
1486
1487 /* if first point matches */
1488 if PTEQ(polyptr->ed_start, p0) {
1489 db_mrg_assign_edge(backptr,backptr->ed_start,nextedge->ed_end);
1490 REMOVE_EDGE(backptr,polyptr,garbage,4) /* remove 4 edges beginning with polyptr */
1491 }
1492 else if PTEQ(nextedge->ed_end, p0) { /* if second point */
1493 nextedge = nextedge->nextpoly;
1494 db_mrg_assign_edge(polyptr,polyptr->ed_start,nextedge->ed_end);
1495 temp = polyptr->nextpoly;
1496 REMOVE_EDGE(polyptr,temp,garbage,4) /* remove 4 edges following polyptr */
1497 }
1498 else if (descendp) {
1499 /* this is a weird case (next->end "below"/"above"/"rightof"/"leftof" p0) */
1500 db_mrg_assign_edge(nextedge,p0,nextedge->ed_end);
1501 db_mrg_assign_edge(polyptr,polyptr->ed_start,p0);
1502 temp = polyptr->nextpoly;
1503 REMOVE_EDGE(polyptr,temp,garbage,2) /* remove 2 edges following polyptr */
1504 }
1505 else { /* more normal case */
1506 db_mrg_assign_edge(polyptr,polyptr->ed_start,p0);
1507 temp = polyptr->nextpoly;
1508 db_mrg_assign_edge(nextedge,p0,nextedge->ed_end);
1509 REMOVE_EDGE(polyptr,temp,garbage,2) /* remove 2 edges following polyptr */
1510 }
1511 }
1512
1513 /* write polygon */
db_mrg_write_polygon(void (* writepolygon)(INTBIG,TECHNOLOGY *,INTBIG *,INTBIG *,INTBIG),INTBIG layer,TECHNOLOGY * tech)1514 void db_mrg_write_polygon(void (*writepolygon)(INTBIG, TECHNOLOGY*, INTBIG*, INTBIG*, INTBIG),
1515 INTBIG layer, TECHNOLOGY *tech)
1516 {
1517 POLYCOORD *polyptr;
1518 INTBIG i;
1519
1520 if (db_mrg_polycoordlist.numedge > db_mrgbuflen)
1521 {
1522 /* verify adequate buffer space */
1523 if (db_mrgbuflen != 0)
1524 {
1525 efree((CHAR *)db_mrgxbuf);
1526 efree((CHAR *)db_mrgybuf);
1527 }
1528 db_mrgbuflen = db_mrg_polycoordlist.numedge;
1529 db_mrgxbuf = (INTBIG *)emalloc((db_mrgbuflen * SIZEOFINTBIG), db_cluster);
1530 db_mrgybuf = (INTBIG *)emalloc((db_mrgbuflen * SIZEOFINTBIG), db_cluster);
1531 }
1532
1533 polyptr = db_mrg_polycoordlist.firstpoly;
1534 for(i=0; i<db_mrg_polycoordlist.numedge; i++)
1535 {
1536 db_mrgxbuf[i] = polyptr->ed_start[0];
1537 db_mrgybuf[i] = polyptr->ed_start[1];
1538 polyptr = polyptr->nextpoly; /* increment pointer */
1539 }
1540 (*writepolygon)(layer, tech, db_mrgxbuf, db_mrgybuf, db_mrg_polycoordlist.numedge);
1541 }
1542
1543 /* returns successor polygon edge # */
db_mrg_succ(INTBIG aindex)1544 INTBIG db_mrg_succ(INTBIG aindex)
1545 {
1546 if (aindex == (db_mrg_polycoordlist.numedge - 1))
1547 return(0);
1548 return(aindex + 1);
1549 }
1550
1551 /* returns index number of next edge on box, in CCW order */
db_mrg_nxtside(INTBIG aindex)1552 INTBIG db_mrg_nxtside(INTBIG aindex)
1553 {
1554 if (aindex == 0) return(3);
1555 return(aindex - 1);
1556 }
1557
1558 /* returns index number of previous edge on box */
db_mrg_prevside(INTBIG aindex)1559 INTBIG db_mrg_prevside(INTBIG aindex)
1560 {
1561 if (aindex == 3) return(0);
1562 return(aindex+1);
1563 }
1564
1565 /* assigns characteristics to polygon edge */
db_mrg_assign_edge(POLYCOORD * polyptr,INTBIG start[],INTBIG end[])1566 void db_mrg_assign_edge(POLYCOORD *polyptr, INTBIG start[], INTBIG end[])
1567 {
1568 INTBIG i;
1569
1570 if (start[0] == end[0]) /* if same in X */
1571 {
1572 polyptr->ed_val = start[0];
1573 if (start[1] < end[1]) polyptr->ed_or = UP;
1574 else polyptr->ed_or = DOWN;
1575 } else /* same in Y */
1576 {
1577 polyptr->ed_val = start[1];
1578 if (start[0] < end[0]) polyptr->ed_or = RIGHT;
1579 else polyptr->ed_or = LEFT;
1580 }
1581 for(i = 0; i < 2; i++)
1582 {
1583 polyptr->ed_start[i] = start[i];
1584 polyptr->ed_end[i] = end[i];
1585 }
1586 }
1587
1588 /* corrects for co-linear edges, and updates coordinate indices */
db_mrg_housekeeper(void)1589 void db_mrg_housekeeper(void)
1590 {
1591 POLYCOORD *polyptr, *garbage, *nextedge;
1592 INTBIG indx;
1593
1594 for(polyptr = db_mrg_polycoordlist.firstpoly;
1595 polyptr->nextpoly != db_mrg_polycoordlist.firstpoly;
1596 polyptr = polyptr->nextpoly)
1597 polyptr->seen = 1;
1598 polyptr->seen = 1; /* do last on one ring */
1599 polyptr = db_mrg_polycoordlist.firstpoly;
1600 for(nextedge = polyptr->nextpoly; polyptr->seen;)
1601 {
1602 if (polyptr->ed_or == nextedge->ed_or) /* if edge orientation is same */
1603 {
1604 garbage = nextedge;
1605 polyptr->ed_end[0] = nextedge->ed_end[0]; /* copy end point */
1606 polyptr->ed_end[1] = nextedge->ed_end[1];
1607
1608 /* if about to remove list head */
1609 if (nextedge == db_mrg_polycoordlist.firstpoly)
1610 db_mrg_polycoordlist.firstpoly = nextedge->nextpoly;
1611 polyptr->nextpoly = nextedge->nextpoly;
1612 nextedge = nextedge->nextpoly;
1613 garbage->nextpoly = NULL;
1614 db_mrg_killpoly(garbage);
1615 } else
1616 {
1617 /* not colinear, set as seen */
1618 polyptr->seen = 0;
1619 polyptr = nextedge;
1620 nextedge = nextedge->nextpoly;
1621 }
1622 } /* colinearities removed */
1623
1624 /* update sequence numbers */
1625 indx = 0;
1626 for(polyptr = db_mrg_polycoordlist.firstpoly; polyptr->nextpoly !=
1627 db_mrg_polycoordlist.firstpoly; polyptr = polyptr->nextpoly)
1628 {
1629 polyptr->indx = indx;
1630 indx += 1;
1631 }
1632 polyptr->indx = indx; /* do last one */
1633 db_mrg_polycoordlist.numedge = indx + 1; /* set number of edges */
1634 }
1635
1636 /* inserts box into polygon where intersected 5* */
db_mrg_insert5(INTBIG firstcon,INTBIG auxx,BOXPOLY * boxptr)1637 void db_mrg_insert5(INTBIG firstcon, INTBIG auxx, BOXPOLY *boxptr)
1638 {
1639 POLYCOORD *polyptr, *nextedge, *garbage, *temp;
1640 INTBIG i;
1641
1642 if (auxx) { /* if auxptr points to first intersection */
1643 polyptr = boxptr->auxpolyint[firstcon];
1644 nextedge = boxptr->polyint[firstcon];
1645 } else {
1646 polyptr = boxptr->polyint[firstcon];
1647 nextedge = boxptr->auxpolyint[firstcon];
1648 }
1649
1650 /* insertion position is independent of edge orientation */
1651 db_mrg_assign_edge(polyptr,polyptr->ed_start,nextedge->ed_end);
1652 temp = polyptr->nextpoly;
1653 REMOVE_EDGE(polyptr,temp,garbage,4) /* remove 4 edges following polyptr */
1654 }
1655
1656 /* some support stuff to do box poly descriptor mem management. */
db_mrg_getbox(void)1657 BOXPOLY *db_mrg_getbox(void)
1658 {
1659 BOXPOLY *b;
1660
1661 if (db_mrg_free_box_list == NULL) {
1662 b = (BOXPOLY *)emalloc(sizeof(BOXPOLY), db_cluster);
1663 if (b == 0) return(NULL);
1664 b->nextbox = NULL;
1665 return(b);
1666 }
1667 b = db_mrg_free_box_list;
1668 db_mrg_free_box_list = b->nextbox;
1669 b->nextbox = NULL;
1670 return(b);
1671 }
1672
db_mrg_trash(BOXPOLY * b)1673 void db_mrg_trash(BOXPOLY *b)
1674 {
1675 b->nextbox = db_mrg_free_box_list;
1676 db_mrg_free_box_list = b;
1677 }
1678
db_mrg_dump_free_box_list(void)1679 void db_mrg_dump_free_box_list(void)
1680 {
1681 BOXPOLY *b;
1682
1683 while (db_mrg_free_box_list != NULL) {
1684 b = db_mrg_free_box_list;
1685 db_mrg_free_box_list = b->nextbox;
1686 b->nextbox = NULL;
1687 efree((CHAR *)b);
1688 }
1689 }
1690
db_mrg_assign_box(BOXPOLY * ptr,INTBIG left,INTBIG right,INTBIG top,INTBIG bot)1691 void db_mrg_assign_box(BOXPOLY *ptr, INTBIG left, INTBIG right, INTBIG top, INTBIG bot)
1692 {
1693 ptr->ul[0] = ptr->ll[0] = ptr->left = left;
1694 ptr->ur[0] = ptr->lr[0] = ptr->right = right;
1695 ptr->ul[1] = ptr->ur[1] = ptr->top = top;
1696 ptr->ll[1] = ptr->lr[1] = ptr->bot = bot;
1697 if ((ptr->right - ptr->left) > (ptr->top - ptr->bot)) {
1698 ptr->ishor = 1;
1699 }
1700 else {
1701 ptr->ishor = 0;
1702 }
1703 }
1704
db_mrg_getpoly(void)1705 POLYCOORD *db_mrg_getpoly(void)
1706 {
1707 POLYCOORD *p;
1708
1709 if (db_mrg_free_poly_list == NULL) {
1710 p = (POLYCOORD *)emalloc(sizeof(POLYCOORD), db_cluster);
1711 if (p == 0) return(NULL);
1712 p->nextpoly = NULL;
1713 return(p);
1714 }
1715 p = db_mrg_free_poly_list;
1716 db_mrg_free_poly_list = p->nextpoly;
1717 p->nextpoly = NULL;
1718 return(p);
1719 }
1720
db_mrg_killpoly(POLYCOORD * p)1721 void db_mrg_killpoly(POLYCOORD *p)
1722 {
1723 p->nextpoly = db_mrg_free_poly_list;
1724 db_mrg_free_poly_list = p;
1725 }
1726
db_mrg_dump_free_poly_list(void)1727 void db_mrg_dump_free_poly_list(void)
1728 {
1729 POLYCOORD *p;
1730
1731 while (db_mrg_free_poly_list != NULL) {
1732 p = db_mrg_free_poly_list;
1733 db_mrg_free_poly_list = p->nextpoly;
1734 p->nextpoly = NULL;
1735 efree((CHAR *)p);
1736 }
1737 }
1738
db_mrg_remove_poly_list(void)1739 void db_mrg_remove_poly_list(void)
1740 {
1741 POLYCOORD *polyptr,*endptr;
1742
1743 /* find end of list and break ring */
1744 for(endptr = db_mrg_polycoordlist.firstpoly;
1745 endptr->nextpoly != db_mrg_polycoordlist.firstpoly;
1746 endptr = endptr->nextpoly)
1747 ;
1748
1749 /* ring is broken now */
1750 endptr->nextpoly = NULL;
1751 while (db_mrg_polycoordlist.firstpoly != NULL) {
1752 polyptr = db_mrg_polycoordlist.firstpoly;
1753 db_mrg_polycoordlist.firstpoly = polyptr->nextpoly;
1754 polyptr->nextpoly = NULL;
1755 db_mrg_killpoly(polyptr);
1756 }
1757 }
1758
db_mrg_get_lay_head(void)1759 BOXLISTHEAD *db_mrg_get_lay_head(void)
1760 {
1761 BOXLISTHEAD *bl;
1762
1763 if (db_mrg_free_boxhead_list == NULL) {
1764 bl = (BOXLISTHEAD *)emalloc(sizeof(BOXLISTHEAD), db_cluster);
1765 if (bl == 0) return(NULL);
1766 bl->nextlayer = NULL;
1767 return(bl);
1768 }
1769 bl = db_mrg_free_boxhead_list;
1770 db_mrg_free_boxhead_list = bl->nextlayer;
1771 bl->nextlayer = NULL;
1772 return(bl);
1773 }
1774
db_mrg_dump_free_boxhead_list(void)1775 void db_mrg_dump_free_boxhead_list(void)
1776 {
1777 BOXLISTHEAD *bl;
1778
1779 while (db_mrg_free_boxhead_list != NULL) {
1780 bl = db_mrg_free_boxhead_list;
1781 db_mrg_free_boxhead_list = bl->nextlayer;
1782 bl->nextlayer = NULL;
1783 bl->box = NULL;
1784 efree((CHAR *)bl);
1785 }
1786 }
1787
db_mrg_remove_boxhead_list(void)1788 void db_mrg_remove_boxhead_list(void)
1789 {
1790 BOXLISTHEAD *bl,*endptr;
1791
1792 if (db_mrg_curr_cell != NULL) {
1793 endptr = NULL;
1794 for(bl = db_mrg_curr_cell; bl != NULL;) {
1795 bl->box = NULL;
1796 endptr = bl;
1797 bl = bl->nextlayer;
1798 }
1799 endptr->nextlayer = db_mrg_free_boxhead_list;
1800 db_mrg_free_boxhead_list = db_mrg_curr_cell;
1801 db_mrg_curr_cell = NULL;
1802 }
1803 }
1804
1805 /***************************************************************************
1806 * Initially, call:
1807 * void *merge = mergenew(cluster);
1808 * where "cluster" is the memory arena for this merging operation.
1809 * The returned value is used in subsequent calls.
1810 *
1811 * For every polygon, call:
1812 * mergeaddpolygon(merge, layer, tech, poly);
1813 * where "layer" is an integer layer number from technology "tech"; "poly"
1814 * is a polygon to be added; "merge" is the returned value from "mergenew()".
1815 *
1816 * You can also subtract a polygon by calling:
1817 * mergesubpolygon(merge, layer, tech, poly);
1818 *
1819 * To combine two different merges, use:
1820 * mergeaddmerge(merge, addmerge, trans)
1821 * to add the merge information in "addmerge" (transformed by "trans")
1822 * to the merge in "merge"
1823 *
1824 * At end of merging, call:
1825 * mergeextract(merge, writepolygon)
1826 * where "writepolygon" is a routine that will be called for every polygon with
1827 * five parameters:
1828 * (1) the layer number (INTBIG)
1829 * (2) the technology
1830 * (3) the X coordinate array (INTBIG array)
1831 * (4) the Y coordinate array (INTBIG array)
1832 * (5) the number of coordinates in each array (INTBIG)
1833 *
1834 * And then call:
1835 * mergedelete(merge)
1836 * to deallocate the memory associated with "merge".
1837 *
1838 * You can also call
1839 * mergedescribe(merge) to return a string describing it
1840 *
1841 ***************************************************************************
1842 */
1843
1844 /***** MERGE POLYGON *****/
1845
1846 #define NOMPOLY ((MPOLY *)-1)
1847
1848 typedef struct Impoly
1849 {
1850 INTBIG layer; /* layer of this polygon */
1851 TECHNOLOGY *tech; /* technology of this polygon */
1852 INTBIG count; /* number of points in this polygon */
1853 INTBIG limit; /* space available in this polygon */
1854 INTBIG *x; /* X coordinates of this polygon */
1855 INTBIG *y; /* Y coordinates of this polygon */
1856 INTBIG *seen; /* whether the point has been visited */
1857 INTBIG *intersect; /* intersection information for the points */
1858 INTBIG lx, hx, ly, hy; /* bounding box of this polygon */
1859 struct Impoly *nextmpoly; /* next polygon in linked list */
1860 } MPOLY;
1861
1862 /***** MERGE OBJECT *****/
1863
1864 #define NOMERGE ((MERGE *)-1)
1865
1866 typedef struct Imerge
1867 {
1868 CLUSTER *clus; /* memory cluster associated with this merge */
1869 MPOLY *mpolylist; /* the list of active MPOLYs */
1870 MPOLY *newmp; /* temporary MPOLY for merging */
1871 BOOLEAN loopwarned; /* true if warned about loop errors */
1872
1873 /* for figuring out what to do at an intersection */
1874 INTBIG *intpol; /* polygon with intersection */
1875 INTBIG *intpt; /* point with intersection */
1876 INTBIG *intleaveangle; /* angle of intersection */
1877 INTBIG intcount; /* number of intersection */
1878 INTBIG inttotal; /* size of intersection arrays */
1879
1880 /* for walking around polygon edges */
1881 INTBIG seen; /* timestamp */
1882
1883 /* working memory for db_mergeaddintersectionpoints() */
1884 LISTINTBIG *yorder;
1885 LISTINTBIG *Oyorder;
1886 LISTINTBIG *ylist;
1887 LISTINTBIG *queue;
1888 LISTINTBIG *Oqueue;
1889
1890 /* next in linked list */
1891 struct Imerge *nextmerge;
1892 } MERGE;
1893
1894 static MPOLY *db_mergesortpoly; /* use of this is not parallelized yet!!! */
1895 static MPOLY *db_mpolyfree = NOMPOLY; /* the list of unused MPOLYs */
1896 static MERGE *db_mergefree = NOMERGE; /* the list of unused MERGEs */
1897 static void *db_polymergemutex = 0; /* mutex for polygon merging */
1898 static INTBIG db_mergeshowrightmost = 0;
1899
1900 static BOOLEAN db_mergeaddholetopoly(MERGE *merge, MPOLY *holemplist, MPOLY *newmp);
1901 static void db_mergeaddintersectionpoint(MERGE *merge, INTBIG polygon, INTBIG point);
1902 static BOOLEAN db_mergeaddintersectionpoints(MERGE *merge, MPOLY *mp, MPOLY *omp);
1903 static BOOLEAN db_mergeaddthisintersectionpoint(MERGE *merge, MPOLY *mp, INTBIG i,
1904 INTBIG ix, INTBIG iy, INTBIG intvalue);
1905 static MERGE *db_mergealloc(CLUSTER *cluster);
1906 static MPOLY *db_mergeallocpoly(MERGE *merge);
1907 static BOOLEAN db_mergecheckqueue(MERGE *merge, MPOLY *mp, LISTINTBIG *queue, LISTINTBIG *yorder,
1908 INTBIG startqueuepos, INTBIG fromline, MPOLY *omp, LISTINTBIG *Oqueue,
1909 LISTINTBIG *Oyorder, INTBIG ofromline, INTBIG intvalue);
1910 static BOOLEAN db_mergecopypoly(MERGE *merge, MPOLY *smp, MPOLY *dmp);
1911 static BOOLEAN db_mergeensurespace(MERGE *merge, MPOLY *mp, INTBIG count);
1912 static MPOLY *db_mergefindpolyandmerge(MERGE *merge, MPOLY *mp, BOOLEAN keepnew, BOOLEAN subtract);
1913 static INTBIG db_mergefindstartingpoint(MPOLY *mp, MPOLY *omp);
1914 static void db_mergefreepoly(MPOLY *mp);
1915 static BOOLEAN db_mergeinsertpoint(MERGE *merge, MPOLY *newmp, INTBIG *insert, INTBIG x, INTBIG y);
1916 static BOOLEAN db_mergeisinside(INTBIG x, INTBIG y, MPOLY *mp);
1917 static INTBIG db_mergelinesintersect(INTBIG fx, INTBIG fy, INTBIG tx, INTBIG ty,
1918 INTBIG ofx, INTBIG ofy, INTBIG otx, INTBIG oty, INTBIG *ix, INTBIG *iy);
1919 static BOOLEAN db_mergepoly(MERGE *merge, MPOLY *mp, MPOLY *omp, BOOLEAN subtract);
1920 static void db_mergeshowmpoly(INTBIG count, INTBIG *x, INTBIG *y,
1921 NODEPROTO *prim, INTBIG showXoff, INTBIG showYoff, INTBIG layer, TECHNOLOGY *tech);
1922 static void db_mergesimplifyandbbox(MPOLY *mp);
1923 static int db_mergesortiny(const void *e1, const void *e2);
1924 static BOOLEAN db_mergewalkedge(MERGE *merge, MPOLY *mp, INTBIG i, MPOLY *omp, MPOLY *newmp, BOOLEAN subtract);
1925
1926 /* debugging this module:
1927 * uncomment "SHOWRESULTS" to generate a step-by-step illustration of each new polygon that is merged
1928 * uncomment "SHOWMERGERESULTS" to generate a step-by-step illustration of each new merge that is merged
1929 * set "DESIREDLAYER" to the layer you want to watch
1930 * uncomment "SHOWTICKS" to draw tick marks around illustrations
1931 * uncomment "DEBUGWALK" to generate a step-by-step illustration of each new point traversed while adding a polygon
1932 */
1933 /* #define SHOWRESULTS 1 */ /* uncomment to show results of each "polygon" merge */
1934 /* #define SHOWMERGERESULTS 1*/ /* uncomment to show results of each "merge" merge */
1935 /* #define SHOWTICKS 1 */ /* uncomment to show coordinate values with results */
1936 /* #define DEBUGWALK 1 */ /* uncomment to debug polygon point traversal */
1937 /* #define SHOWHOLEGROWTH 1 */ /* uncomment to show results of hole growth in a merge */
1938 /* #define DESIREDLAYER 11 */ /* uncomment to select a specific layer (11=n-select) */
1939 #define RESULTSPACING 100 /* distance between result graphics */
1940
1941 /*
1942 * Routine to free all memory associated with this module.
1943 */
db_freemergememory(void)1944 void db_freemergememory(void)
1945 {
1946 REGISTER MPOLY *mp;
1947 REGISTER MERGE *merge;
1948
1949 /* free memory used by manhattan merger */
1950 if (db_mrgbuflen != 0)
1951 {
1952 efree((CHAR *)db_mrgxbuf);
1953 efree((CHAR *)db_mrgybuf);
1954 }
1955
1956 /* free all allocated merge structures */
1957 while (db_mergefree != NOMERGE)
1958 {
1959 merge = db_mergefree;
1960 db_mergefree = merge->nextmerge;
1961 if (merge->newmp != NOMPOLY) db_mergefreepoly(merge->newmp);
1962 if (merge->inttotal > 0)
1963 {
1964 efree((CHAR *)merge->intpol);
1965 efree((CHAR *)merge->intpt);
1966 efree((CHAR *)merge->intleaveangle);
1967 }
1968
1969 killintlistobj(merge->yorder);
1970 killintlistobj(merge->Oyorder);
1971 killintlistobj(merge->queue);
1972 killintlistobj(merge->Oqueue);
1973 killintlistobj(merge->ylist);
1974 efree((CHAR *)merge);
1975 }
1976
1977 /* free memory used by polygonal merger */
1978 while (db_mpolyfree != NOMPOLY)
1979 {
1980 mp = db_mpolyfree;
1981 db_mpolyfree = mp->nextmpoly;
1982 if (mp->limit > 0)
1983 {
1984 efree((CHAR *)mp->x);
1985 efree((CHAR *)mp->y);
1986 efree((CHAR *)mp->seen);
1987 efree((CHAR *)mp->intersect);
1988 }
1989 efree((CHAR *)mp);
1990 }
1991 }
1992
1993 /*
1994 * Routine to create a new "merge" object. After this call, multiple calls to
1995 * "mergeaddpolygon()" may be made, followed by a single call to "mergeextract()"
1996 * to obtain the merged geometry, and a call to "mergedelete()" to free this object.
1997 * Returns zero on error.
1998 */
mergenew(CLUSTER * cluster)1999 void *mergenew(CLUSTER *cluster)
2000 {
2001 MERGE *merge;
2002
2003 /* make sure mutual-exclusion object is created */
2004 if (ensurevalidmutex(&db_polymergemutex, TRUE)) return(0);
2005
2006 merge = db_mergealloc(cluster);
2007 if (merge == NOMERGE) return(0);
2008 merge->mpolylist = NOMPOLY;
2009 merge->seen = 0;
2010 merge->loopwarned = FALSE;
2011 return((void *)merge);
2012 }
2013
2014 /*
2015 * Routine to free memory associated with merge object "vmerge".
2016 */
mergedelete(void * vmerge)2017 void mergedelete(void *vmerge)
2018 {
2019 REGISTER MERGE *merge;
2020 REGISTER MPOLY *mp;
2021
2022 merge = (MERGE *)vmerge;
2023 while (merge->mpolylist != NOMPOLY)
2024 {
2025 mp = merge->mpolylist;
2026 merge->mpolylist = mp->nextmpoly;
2027 db_mergefreepoly(mp);
2028 }
2029
2030 if (db_multiprocessing) emutexlock(db_polymergemutex);
2031 merge->nextmerge = db_mergefree;
2032 db_mergefree = merge;
2033 if (db_multiprocessing) emutexunlock(db_polymergemutex);
2034 }
2035
2036 /*
2037 * Routine to add polygon "poly" to the merged collection. The polygon is on layer
2038 * "layer" of technology "tech".
2039 */
mergeaddpolygon(void * vmerge,INTBIG layer,TECHNOLOGY * tech,POLYGON * poly)2040 void mergeaddpolygon(void *vmerge, INTBIG layer, TECHNOLOGY *tech, POLYGON *poly)
2041 {
2042 REGISTER MERGE *merge;
2043 REGISTER MPOLY *mp, *omp, *ump, *lastmp;
2044 REGISTER INTBIG i;
2045 REGISTER BOOLEAN done;
2046 INTBIG lx, hx, ly, hy;
2047
2048 /* copy the polygon into a local structure */
2049 if (poly->count == 0) return;
2050 merge = (MERGE *)vmerge;
2051 mp = db_mergeallocpoly(merge);
2052 if (db_mergeensurespace(merge, mp, poly->count)) return;
2053 if (poly->style == FILLEDRECT || poly->style == CLOSEDRECT)
2054 {
2055 getbbox(poly, &lx, &hx, &ly, &hy);
2056 makerectpoly(lx, hx, ly, hy, poly);
2057 }
2058 if (areapoints(poly->count, poly->xv, poly->yv) < 0)
2059 {
2060 /* reverse direction of points while copying */
2061 for(i=0; i<poly->count; i++)
2062 {
2063 mp->x[i] = poly->xv[poly->count-i-1];
2064 mp->y[i] = poly->yv[poly->count-i-1];
2065 }
2066 } else
2067 {
2068 for(i=0; i<poly->count; i++)
2069 {
2070 mp->x[i] = poly->xv[i];
2071 mp->y[i] = poly->yv[i];
2072 }
2073 }
2074 mp->count = poly->count;
2075 mp->layer = layer;
2076 mp->tech = tech;
2077 db_mergesimplifyandbbox(mp);
2078
2079 /* now look for merges */
2080 omp = db_mergefindpolyandmerge(merge, mp, TRUE, FALSE);
2081 if (omp == NOMPOLY)
2082 {
2083 /* not merged: just add to the list */
2084 mp->nextmpoly = merge->mpolylist;
2085 merge->mpolylist = mp;
2086 } else
2087 {
2088 /* merged: delete this */
2089 db_mergefreepoly(mp);
2090
2091 /* see if any other merging can be done */
2092 done = FALSE;
2093 while (!done)
2094 {
2095 done = TRUE;
2096 mp = db_mergefindpolyandmerge(merge, omp, FALSE, FALSE);
2097 if (mp != NOMPOLY)
2098 {
2099 lastmp = NOMPOLY;
2100 for(ump = merge->mpolylist; ump != NOMPOLY; ump = ump->nextmpoly)
2101 {
2102 if (ump == mp) break;
2103 lastmp = ump;
2104 }
2105 if (lastmp == NOMPOLY) merge->mpolylist = mp->nextmpoly; else
2106 lastmp->nextmpoly = mp->nextmpoly;
2107 db_mergefreepoly(mp);
2108 done = FALSE;
2109 }
2110 }
2111 }
2112
2113 #ifdef SHOWRESULTS
2114
2115 # ifdef DESIREDLAYER
2116 if (layer == DESIREDLAYER)
2117 # endif
2118 {
2119 REGISTER NODEPROTO *cell;
2120 static INTBIG db_mergeshowxoff = 0;
2121
2122 db_mergeshowxoff += el_curlib->lambda[el_curtech->techindex] * RESULTSPACING;
2123 cell = getcurcell();
2124 if (cell == NONODEPROTO) return;
2125 db_mergeshowmpoly(poly->count, poly->xv, poly->yv, getnodeproto(x_("metal-2-node")),
2126 db_mergeshowxoff, 0, layer, tech);
2127
2128 /* show the merge it gets added to */
2129 mergeshow((void *)merge, getnodeproto(x_("metal-1-node")), db_mergeshowxoff, 0, x_("After adding polygon"));
2130 }
2131 #endif
2132 }
2133
2134 /*
2135 * Routine to subtract polygon "poly" from the merged collection. The polygon is on layer
2136 * "layer" of technology "tech".
2137 */
mergesubpolygon(void * vmerge,INTBIG layer,TECHNOLOGY * tech,POLYGON * poly)2138 void mergesubpolygon(void *vmerge, INTBIG layer, TECHNOLOGY *tech, POLYGON *poly)
2139 {
2140 REGISTER MERGE *merge;
2141 REGISTER MPOLY *mp, *omp;
2142 REGISTER INTBIG i;
2143 INTBIG lx, hx, ly, hy;
2144
2145 /* copy the polygon into a local structure */
2146 if (poly->count == 0) return;
2147 merge = (MERGE *)vmerge;
2148 mp = db_mergeallocpoly(merge);
2149 if (db_mergeensurespace(merge, mp, poly->count)) return;
2150 if (poly->style == FILLEDRECT || poly->style == CLOSEDRECT)
2151 {
2152 getbbox(poly, &lx, &hx, &ly, &hy);
2153 makerectpoly(lx, hx, ly, hy, poly);
2154 }
2155
2156 /* make the points go in the opposite direction for subtraction */
2157 if (areapoints(poly->count, poly->xv, poly->yv) > 0)
2158 {
2159 /* reverse direction of points while copying */
2160 for(i=0; i<poly->count; i++)
2161 {
2162 mp->x[i] = poly->xv[poly->count-i-1];
2163 mp->y[i] = poly->yv[poly->count-i-1];
2164 }
2165 } else
2166 {
2167 for(i=0; i<poly->count; i++)
2168 {
2169 mp->x[i] = poly->xv[i];
2170 mp->y[i] = poly->yv[i];
2171 }
2172 }
2173 mp->count = poly->count;
2174 mp->layer = layer;
2175 mp->tech = tech;
2176 db_mergesimplifyandbbox(mp);
2177
2178 /* merging will subtract since "mp" is reversed */
2179 omp = db_mergefindpolyandmerge(merge, mp, TRUE, TRUE);
2180
2181 /* now delete this */
2182 db_mergefreepoly(mp);
2183 }
2184
2185 /*
2186 * Routine to add merge object "addmerge" to the merged collection "merge", transforming
2187 * it by "trans".
2188 */
mergeaddmerge(void * vmerge,void * vaddmerge,XARRAY trans)2189 void mergeaddmerge(void *vmerge, void *vaddmerge, XARRAY trans)
2190 {
2191 REGISTER MERGE *merge, *addmerge;
2192 REGISTER MPOLY *amp, *mp, *omp, *ump, *lastmp;
2193 REGISTER BOOLEAN done;
2194 REGISTER INTBIG i, save, revi;
2195 #ifdef SHOWMERGERESULTS
2196 static INTBIG db_mergeshowxoff = 0;
2197 #endif
2198
2199 merge = (MERGE *)vmerge;
2200 addmerge = (MERGE *)vaddmerge;
2201 for(amp = addmerge->mpolylist; amp != NOMPOLY; amp = amp->nextmpoly)
2202 {
2203 mp = db_mergeallocpoly(merge);
2204 if (mp == NOMPOLY) return;
2205 mp->layer = amp->layer;
2206 mp->tech = amp->tech;
2207 db_mergecopypoly(merge, amp, mp);
2208
2209 /* transform it */
2210 for(i=0; i<mp->count; i++)
2211 xform(mp->x[i], mp->y[i], &mp->x[i], &mp->y[i], trans);
2212
2213 /* reverse direction of points if transform made it necessary */
2214 if (areapoints(mp->count, mp->x, mp->y) < 0)
2215 {
2216 for(i=0; i<mp->count/2; i++)
2217 {
2218 revi = mp->count-i-1;
2219 save = mp->x[i]; mp->x[i] = mp->x[revi]; mp->x[revi] = save;
2220 save = mp->y[i]; mp->y[i] = mp->y[revi]; mp->y[revi] = save;
2221 }
2222 }
2223 db_mergesimplifyandbbox(mp);
2224 #ifdef SHOWMERGERESULTS
2225 db_mergeshowmpoly(mp->count, mp->x, mp->y, getnodeproto(x_("metal-2-node")),
2226 db_mergeshowxoff, 0, mp->layer, mp->tech);
2227 #endif
2228 /* now look for merges */
2229 omp = db_mergefindpolyandmerge(merge, mp, TRUE, FALSE);
2230 if (omp == NOMPOLY)
2231 {
2232 /* not merged: just add to the list */
2233 mp->nextmpoly = merge->mpolylist;
2234 merge->mpolylist = mp;
2235 } else
2236 {
2237 /* merged: delete this */
2238 db_mergefreepoly(mp);
2239
2240 /* see if any other merging can be done */
2241 done = FALSE;
2242 while (done == 0)
2243 {
2244 done = TRUE;
2245 mp = db_mergefindpolyandmerge(merge, omp, FALSE, FALSE);
2246 if (mp != NOMPOLY)
2247 {
2248 lastmp = NOMPOLY;
2249 for(ump = merge->mpolylist; ump != NOMPOLY; ump = ump->nextmpoly)
2250 {
2251 if (ump == mp) break;
2252 lastmp = ump;
2253 }
2254 if (lastmp == NOMPOLY) merge->mpolylist = mp->nextmpoly; else
2255 lastmp->nextmpoly = mp->nextmpoly;
2256 db_mergefreepoly(mp);
2257 done = FALSE;
2258 }
2259 }
2260 }
2261 #ifdef SHOWMERGERESULTS
2262 mergeshow(merge, getnodeproto(x_("metal-1-node")), db_mergeshowxoff, 0, x_("after adding"));
2263 db_mergeshowxoff += el_curlib->lambda[el_curtech->techindex] * RESULTSPACING;
2264 #endif
2265 }
2266 }
2267
2268 /*
2269 * Routine to report all of the merged polygons in "vmerge" through
2270 * the callback routine "writepolygon()". The routine is given 5 parameters for
2271 * each merged polygon:
2272 * (1) the layer
2273 * (2) the technology
2274 * (3) the X coordinates
2275 * (4) the Y coordinates
2276 * (5) the number of coordinates
2277 */
mergeextract(void * vmerge,void (* writepolygon)(INTBIG,TECHNOLOGY *,INTBIG *,INTBIG *,INTBIG))2278 void mergeextract(void *vmerge, void (*writepolygon)(INTBIG, TECHNOLOGY*, INTBIG*, INTBIG*, INTBIG))
2279 {
2280 REGISTER MERGE *merge;
2281 REGISTER MPOLY *mp;
2282
2283 merge = (MERGE *)vmerge;
2284 for(mp = merge->mpolylist; mp != NOMPOLY; mp = mp->nextmpoly)
2285 {
2286 db_mergesimplifyandbbox(mp);
2287 (*writepolygon)(mp->layer, mp->tech, mp->x, mp->y, mp->count);
2288 }
2289 }
2290
2291 /*
2292 * Routine to return the bounding box of the merged polygon "vmerge" in (lx,hx,ly,hy).
2293 * Returns FALSE if there is no valid polygon.
2294 */
mergebbox(void * vmerge,INTBIG * lx,INTBIG * hx,INTBIG * ly,INTBIG * hy)2295 BOOLEAN mergebbox(void *vmerge, INTBIG *lx, INTBIG *hx, INTBIG *ly, INTBIG *hy)
2296 {
2297 REGISTER MERGE *merge;
2298 REGISTER MPOLY *mp;
2299 REGISTER BOOLEAN valid;
2300 REGISTER INTBIG i;
2301
2302 merge = (MERGE *)vmerge;
2303 valid = FALSE;
2304 for(mp = merge->mpolylist; mp != NOMPOLY; mp = mp->nextmpoly)
2305 {
2306 db_mergesimplifyandbbox(mp);
2307 if (mp->count < 3) continue;
2308 for(i=0; i<mp->count; i++)
2309 {
2310 if (valid)
2311 {
2312 if (mp->x[i] < *lx) *lx = mp->x[i];
2313 if (mp->x[i] > *hx) *hx = mp->x[i];
2314 if (mp->y[i] < *ly) *ly = mp->y[i];
2315 if (mp->y[i] > *hy) *hy = mp->y[i];
2316 } else
2317 {
2318 *lx = *hx = mp->x[i];
2319 *ly = *hy = mp->y[i];
2320 valid = TRUE;
2321 }
2322 }
2323 }
2324 return(valid);
2325 }
2326
2327 /*
2328 * Routine used only in debugging this module.
2329 * It returns a string describing the merge object "vmerge".
2330 */
mergedescribe(void * vmerge)2331 CHAR *mergedescribe(void *vmerge)
2332 {
2333 REGISTER MERGE *merge;
2334 REGISTER MPOLY *mp;
2335 void *infstr;
2336
2337 merge = (MERGE *)vmerge;
2338 infstr = initinfstr();
2339 for (mp = merge->mpolylist; mp != NOMPOLY; mp = mp->nextmpoly)
2340 {
2341 if (mp != merge->mpolylist) addstringtoinfstr(infstr, x_(", "));
2342 formatinfstr(infstr, x_("%ld PTS on LAYER %ld"), mp->count, mp->layer);
2343 }
2344 return(returninfstr(infstr));
2345 }
2346
2347 /*
2348 * Routine used only in debugging this module.
2349 * It displays "vmerge" using polygons of "prim", offset at (showXoff,showYoff).
2350 */
mergeshow(void * vmerge,NODEPROTO * prim,INTBIG showXoff,INTBIG showYoff,CHAR * title)2351 void mergeshow(void *vmerge, NODEPROTO *prim, INTBIG showXoff, INTBIG showYoff, CHAR *title)
2352 {
2353 REGISTER NODEPROTO *cell;
2354 REGISTER MPOLY *mp;
2355 REGISTER MERGE *merge;
2356 REGISTER NODEINST *ni;
2357 CHAR buf[200];
2358 REGISTER VARIABLE *var;
2359 REGISTER INTBIG i, lx, hx, ly, hy, cx, cy, *newlist;
2360
2361 merge = (MERGE *)vmerge;
2362 cell = getcurcell();
2363 if (cell == NONODEPROTO) return;
2364 for(mp = merge->mpolylist; mp != NOMPOLY; mp = mp->nextmpoly)
2365 {
2366 #ifdef DESIREDLAYER
2367 if (mp->layer != DESIREDLAYER) continue;
2368 #endif
2369 lx = hx = mp->x[0];
2370 ly = hy = mp->y[0];
2371 for(i=1; i<mp->count; i++)
2372 {
2373 if (mp->x[i] < lx) lx = mp->x[i];
2374 if (mp->x[i] > hx) hx = mp->x[i];
2375 if (mp->y[i] < ly) ly = mp->y[i];
2376 if (mp->y[i] > hy) hy = mp->y[i];
2377 }
2378 cx = (lx+hx) / 2; cy = (ly+hy) / 2;
2379 ni = newnodeinst(prim, lx+showXoff, hx+showXoff, ly+showYoff, hy+showYoff, 0, 0, cell);
2380 newlist = (INTBIG *)emalloc(mp->count * 2 * SIZEOFINTBIG, el_tempcluster);
2381 if (newlist == 0) return;
2382 for(i=0; i<mp->count; i++)
2383 {
2384 newlist[i*2] = mp->x[i] - cx;
2385 newlist[i*2+1] = mp->y[i] - cy;
2386 }
2387 (void)setvalkey((INTBIG)ni, VNODEINST, el_trace_key, (INTBIG)newlist,
2388 VINTEGER|VISARRAY|((mp->count*2)<<VLENGTHSH));
2389 esnprintf(buf, 200, x_("%ld/%s"), mp->layer, mp->tech->techname);
2390 setvalkey((INTBIG)ni, VNODEINST, el_node_name_key, (INTBIG)buf, VSTRING|VDISPLAY);
2391 endobjectchange((INTBIG)ni, VNODEINST);
2392 }
2393
2394 /* get bounds of the merge */
2395 for(mp = merge->mpolylist; mp != NOMPOLY; mp = mp->nextmpoly)
2396 {
2397 if (mp == merge->mpolylist)
2398 {
2399 lx = hx = mp->x[0];
2400 ly = hy = mp->y[0];
2401 }
2402 for(i=0; i<mp->count; i++)
2403 {
2404 if (mp->x[i] < lx) lx = mp->x[i];
2405 if (mp->x[i] > hx) hx = mp->x[i];
2406 if (mp->y[i] < ly) ly = mp->y[i];
2407 if (mp->y[i] > hy) hy = mp->y[i];
2408 }
2409 }
2410 cx = (lx + hx) / 2;
2411 ni = newnodeinst(gen_invispinprim, cx+showXoff, cx+showXoff, hy+showYoff, hy+showYoff, 0, 0, cell);
2412 var = setvalkey((INTBIG)ni, VNODEINST, art_messagekey, (INTBIG)title, VSTRING|VDISPLAY);
2413 if (var != NOVARIABLE)
2414 {
2415 TDSETPOS(var->textdescript, VTPOSUP);
2416 TDSETSIZE(var->textdescript, TXTSETQLAMBDA(64));
2417 }
2418
2419 #ifdef SHOWTICKS
2420 for(mp = merge->mpolylist; mp != NOMPOLY; mp = mp->nextmpoly)
2421 {
2422 REGISTER INTBIG j, lambda;
2423 extern NODEPROTO *gen_invispinprim;
2424
2425 lambda = el_curlib->lambda[el_curtech->techindex];
2426 for(i=0; i<mp->count; i++)
2427 {
2428 /* see if the X value has already been done */
2429 for(j=0; j<i; j++) if (mp->x[j] == mp->x[i]) break;
2430 if (j < i) continue;
2431 for(omp = merge->mpolylist; omp != mp; omp = omp->nextmpoly)
2432 {
2433 for(j=0; j<omp->count; j++)
2434 if (omp->x[j] == mp->x[i]) break;
2435 if (j < omp->count) break;
2436 }
2437 if (omp != mp) continue;
2438
2439 /* show the X coordinate */
2440 ni = newnodeinst(gen_invispinprim, mp->x[i]+showXoff, mp->x[i]+showXoff,
2441 ly-lambda*2+showYoff, ly-lambda*2+showYoff,
2442 0, 0, cell);
2443 if (ni != NONODEINST)
2444 {
2445 REGISTER VARIABLE *var;
2446 var = setvalkey((INTBIG)ni, VNODEINST, el_node_name_key, (INTBIG)latoa(mp->x[i], 0),
2447 VSTRING|VDISPLAY);
2448 if (var != NOVARIABLE)
2449 {
2450 TDSETPOS(var->textdescript, VTPOSDOWN);
2451 TDSETSIZE(var->textdescript, TXTSETQLAMBDA(4));
2452 }
2453 endobjectchange((INTBIG)ni, VNODEINST);
2454 }
2455 }
2456
2457 for(i=0; i<mp->count; i++)
2458 {
2459 /* see if the Y value has already been done */
2460 for(j=0; j<i; j++) if (mp->y[j] == mp->y[i]) break;
2461 if (j < i) continue;
2462 for(omp = merge->mpolylist; omp != mp; omp = omp->nextmpoly)
2463 {
2464 for(j=0; j<omp->count; j++)
2465 if (omp->y[j] == mp->y[i]) break;
2466 if (j < omp->count) break;
2467 }
2468 if (omp != mp) continue;
2469
2470 /* show the Y coordinate */
2471 ni = newnodeinst(gen_invispinprim, lx-lambda*2+showXoff,
2472 lx-lambda*2+showXoff, mp->y[i]+showYoff, mp->y[i]+showYoff, 0, 0, cell);
2473 if (ni != NONODEINST)
2474 {
2475 REGISTER VARIABLE *var;
2476 var = setvalkey((INTBIG)ni, VNODEINST, el_node_name_key, (INTBIG)latoa(mp->y[i], 0),
2477 VSTRING|VDISPLAY);
2478 if (var != NOVARIABLE)
2479 {
2480 TDSETPOS(var->textdescript, VTPOSLEFT);
2481 TDSETSIZE(var->textdescript, TXTSETQLAMBDA(4));
2482 }
2483 endobjectchange((INTBIG)ni, VNODEINST);
2484 }
2485 }
2486 }
2487 #endif
2488 }
2489
2490 /***** POLYGON MERGING SUPPORT *****/
2491
2492 /*
2493 * Routine used only in debugging this module.
2494 * It displays "count" points in (x,y) using polygons of "prim", offset at (showXoff,showYoff).
2495 */
db_mergeshowmpoly(INTBIG count,INTBIG * x,INTBIG * y,NODEPROTO * prim,INTBIG showXoff,INTBIG showYoff,INTBIG layer,TECHNOLOGY * tech)2496 void db_mergeshowmpoly(INTBIG count, INTBIG *x, INTBIG *y,
2497 NODEPROTO *prim, INTBIG showXoff, INTBIG showYoff, INTBIG layer, TECHNOLOGY *tech)
2498 {
2499 REGISTER INTBIG lx, hx, ly, hy, i, cx, cy;
2500 REGISTER NODEINST *ni;
2501 REGISTER INTBIG *newlist;
2502 REGISTER NODEPROTO *cell;
2503 CHAR buf[200];
2504
2505 cell = getcurcell();
2506 if (cell == NONODEPROTO) return;
2507 lx = hx = x[0];
2508 ly = hy = y[0];
2509 for(i=1; i<count; i++)
2510 {
2511 if (x[i] < lx) lx = x[i];
2512 if (x[i] > hx) hx = x[i];
2513 if (y[i] < ly) ly = y[i];
2514 if (y[i] > hy) hy = y[i];
2515 }
2516 if (hx+showXoff > db_mergeshowrightmost) db_mergeshowrightmost = hx+showXoff;
2517 cx = (lx+hx) / 2; cy = (ly+hy) / 2;
2518 ni = newnodeinst(prim, lx+showXoff, hx+showXoff, ly+showYoff, hy+showYoff, 0, 0, cell);
2519 newlist = (INTBIG *)emalloc(count * 2 * SIZEOFINTBIG, el_tempcluster);
2520 if (newlist == 0) return;
2521 for(i=0; i<count; i++)
2522 {
2523 newlist[i*2] = x[i] - cx;
2524 newlist[i*2+1] = y[i] - cy;
2525 }
2526 (void)setvalkey((INTBIG)ni, VNODEINST, el_trace_key, (INTBIG)newlist,
2527 VINTEGER|VISARRAY|((count*2)<<VLENGTHSH));
2528 esnprintf(buf, 200, x_("%ld/%s"), layer, tech->techname);
2529 setvalkey((INTBIG)ni, VNODEINST, el_node_name_key, (INTBIG)buf, VSTRING|VDISPLAY);
2530 endobjectchange((INTBIG)ni, VNODEINST);
2531 }
2532
2533 /*
2534 * Routine to merge "mp" into "merge". If "subtract" is true, this is a removal.
2535 */
db_mergefindpolyandmerge(MERGE * merge,MPOLY * mp,BOOLEAN keepnew,BOOLEAN subtract)2536 MPOLY *db_mergefindpolyandmerge(MERGE *merge, MPOLY *mp, BOOLEAN keepnew, BOOLEAN subtract)
2537 {
2538 REGISTER MPOLY *omp;
2539
2540 for(omp = merge->mpolylist; omp != NOMPOLY; omp = omp->nextmpoly)
2541 {
2542 if (omp == mp) continue;
2543
2544 /* reject immediately if they are on different layers */
2545 if (omp->tech != mp->tech || omp->layer != mp->layer) continue;
2546
2547 /* reject immediately if the bounding boxes don't intersect */
2548 if (omp->lx > mp->hx || omp->hx < mp->lx) continue;
2549 if (omp->ly > mp->hy || omp->hy < mp->ly) continue;
2550
2551 /* try to merge the polygons */
2552 if (keepnew)
2553 {
2554 if (db_mergepoly(merge, mp, omp, subtract)) break;
2555 } else
2556 {
2557 if (db_mergepoly(merge, omp, mp, subtract)) break;
2558 }
2559 }
2560 return(omp);
2561 }
2562
2563 /*
2564 * Helper routine to combine two polygons "mp" (the first polygon) and "omp" (the
2565 * second polygon). If they merge then the routine returns true and places the
2566 * merged polygon in "omp". If "subtract" is true, just subtract "mp" from "omp".
2567 */
db_mergepoly(MERGE * merge,MPOLY * mp,MPOLY * omp,BOOLEAN subtract)2568 BOOLEAN db_mergepoly(MERGE *merge, MPOLY *mp, MPOLY *omp, BOOLEAN subtract)
2569 {
2570 REGISTER INTBIG i, oi, j, startpol, startpt, intpoints;
2571 MPOLY *mps[2], *holepolylist, *holepoly;
2572 #ifdef DEBUGWALK
2573 void *infstr;
2574 #endif
2575
2576 /* reset intersection point information */
2577 for(i=0; i<mp->count; i++) mp->intersect[i] = 0;
2578 for(oi=0; oi<omp->count; oi++) omp->intersect[oi] = 0;
2579
2580 /* create additional points on each polygon at the intersections */
2581 if (db_mergeaddintersectionpoints(merge, mp, omp)) return(FALSE);
2582 if (db_mergeaddintersectionpoints(merge, mp, mp)) return(FALSE);
2583 if (db_mergeaddintersectionpoints(merge, omp, omp)) return(FALSE);
2584 #ifdef DEBUGWALK
2585 infstr = initinfstr();
2586 if (subtract) addstringtoinfstr(infstr, x_("Subtracting poly with intersection points added: "));
2587 else addstringtoinfstr(infstr, x_("First poly with intersection points added: "));
2588 for(i=0; i<mp->count; i++)
2589 formatinfstr(infstr, x_(" (%s,%s)"), latoa(mp->x[i], 0), latoa(mp->y[i], 0));
2590 ttyputmsg(x_("%s"), returninfstr(infstr));
2591
2592 infstr = initinfstr();
2593 addstringtoinfstr(infstr, x_("Second poly with intersection points added: "));
2594 for(i=0; i<omp->count; i++)
2595 formatinfstr(infstr, x_(" (%s,%s)"), latoa(omp->x[i], 0), latoa(omp->y[i], 0));
2596 ttyputmsg(x_("%s"), returninfstr(infstr));
2597 #endif
2598
2599 /* if there are no intersection points, see if one polygon is inside the other */
2600 intpoints = 0;
2601 for(i=0; i<mp->count; i++) if (mp->intersect[i] == 2) { intpoints++; break; }
2602 for(oi=0; oi<omp->count; oi++) if (omp->intersect[oi] == 2) { intpoints++; break; }
2603 if (intpoints == 0)
2604 {
2605 /* figure out which polygon is smaller */
2606 if (fabs(areapoints(mp->count, mp->x, mp->y)) <
2607 areapoints(omp->count, omp->x, omp->y))
2608 {
2609 /* if polygons don't intersect, stop */
2610 if (!db_mergeisinside(mp->x[0], mp->y[0], omp)) return(FALSE);
2611
2612 /* first polygon is smaller and covered by second */
2613 return(TRUE);
2614 } else
2615 {
2616 /* if polygons don't intersect, stop */
2617 if (!db_mergeisinside(omp->x[0], omp->y[0], mp)) return(FALSE);
2618
2619 if (subtract)
2620 {
2621 /* subtract polygon covers merge: delete the merge */
2622 omp->count = 0;
2623 } else
2624 {
2625 /* add polygon is larger, copy and use it */
2626 if (db_mergecopypoly(merge, mp, omp)) return(FALSE);
2627 db_mergesimplifyandbbox(omp);
2628 }
2629 return(TRUE);
2630 }
2631 }
2632
2633 /* find a starting point (one with no intersections and not inside the other) */
2634 if (subtract)
2635 {
2636 /* subtracting: only want starting points on "omp" */
2637 oi = db_mergefindstartingpoint(omp, mp);
2638 if (oi < 0)
2639 {
2640 /* all points are intersections: see if subtract is larger */
2641 if (fabs(areapoints(mp->count, mp->x, mp->y)) >
2642 areapoints(omp->count, omp->x, omp->y))
2643 {
2644 /* subtract polygon covers merge: delete the merge */
2645 omp->count = 0;
2646 }
2647 db_mergesimplifyandbbox(omp);
2648 return(TRUE);
2649 }
2650 startpol = 1;
2651 startpt = oi;
2652 } else
2653 {
2654 /* adding: find starting point on either polygon */
2655 i = db_mergefindstartingpoint(mp, omp);
2656 if (i >= 0)
2657 {
2658 startpol = 0;
2659 startpt = i;
2660 } else
2661 {
2662 oi = db_mergefindstartingpoint(omp, mp);
2663 if (oi < 0)
2664 {
2665 /* all points are intersections: return larger polygon */
2666 if (areapoints(mp->count, mp->x, mp->y) >
2667 areapoints(omp->count, omp->x, omp->y))
2668 {
2669 /* add polygon larger than merge: copy and use it */
2670 if (db_mergecopypoly(merge, mp, omp)) return(FALSE);
2671 }
2672 db_mergesimplifyandbbox(omp);
2673 return(TRUE);
2674 }
2675 startpol = 1;
2676 startpt = oi;
2677 }
2678 }
2679
2680 /* walk around the polygons */
2681 for(i=0; i<mp->count; i++) mp->seen[i] = 0;
2682 for(oi=0; oi<omp->count; oi++) omp->seen[oi] = 0;
2683 mps[0] = mp; mps[1] = omp;
2684 if (merge->newmp == NOMPOLY) merge->newmp = db_mergeallocpoly(merge);
2685 merge->newmp->count = 0;
2686 merge->newmp->layer = mp->layer;
2687 merge->newmp->tech = mp->tech;
2688 if (db_mergewalkedge(merge, mps[startpol], startpt, mps[1-startpol], merge->newmp, subtract))
2689 return(FALSE);
2690
2691 /* handle hole processing */
2692 holepolylist = NOMPOLY;
2693 if (subtract)
2694 {
2695 /* when subtracting, make sure all points on the original polygon are processed */
2696 for(oi=0; oi<omp->count; oi++)
2697 {
2698 if (omp->seen[oi] != 0) continue;
2699 if (omp->intersect[oi] != 0) continue;
2700 if (db_mergeisinside(omp->x[oi], omp->y[oi], mp)) continue;
2701 holepoly = db_mergeallocpoly(merge);
2702 holepoly->layer = mp->layer;
2703 holepoly->tech = mp->tech;
2704 if (db_mergewalkedge(merge, omp, oi, mp, holepoly, TRUE)) return(FALSE);
2705 holepoly->nextmpoly = holepolylist;
2706 holepolylist = holepoly;
2707 }
2708
2709 /* see if there are any points that didn't get seen and are not in the other polygon */
2710 for(oi=0; oi<omp->count; oi++)
2711 {
2712 if (omp->seen[oi] != 0) continue;
2713 for(j=0; j<omp->count; j++)
2714 if (omp->seen[j] != 0 && omp->x[j] == omp->x[oi] && omp->y[j] == omp->y[oi]) break;
2715 if (j < omp->count) continue;
2716 if (db_mergeisinside(omp->x[oi], omp->y[oi], mp)) continue;
2717 holepoly = db_mergeallocpoly(merge);
2718 holepoly->layer = mp->layer;
2719 holepoly->tech = mp->tech;
2720 if (db_mergewalkedge(merge, omp, oi, mp, holepoly, TRUE)) return(FALSE);
2721 holepoly->nextmpoly = holepolylist;
2722 holepolylist = holepoly;
2723 }
2724
2725 /* carve holes from polygon */
2726 if (db_mergeaddholetopoly(merge, holepolylist, merge->newmp)) return(FALSE);
2727 } else
2728 {
2729 /* handle hole processing if adding */
2730
2731 /* see if there are any nonintersection points that didn't get seen and are not in the other polygon */
2732 for(i=0; i<mp->count; i++)
2733 {
2734 if (mp->seen[i] != 0) continue;
2735 if (mp->intersect[i] != 0) continue;
2736 if (db_mergeisinside(mp->x[i], mp->y[i], omp)) continue;
2737 holepoly = db_mergeallocpoly(merge);
2738 holepoly->layer = mp->layer;
2739 holepoly->tech = mp->tech;
2740 if (db_mergewalkedge(merge, mp, i, omp, holepoly, FALSE)) return(FALSE);
2741 holepoly->nextmpoly = holepolylist;
2742 holepolylist = holepoly;
2743 }
2744 for(oi=0; oi<omp->count; oi++)
2745 {
2746 if (omp->seen[oi] != 0) continue;
2747 if (omp->intersect[oi] != 0) continue;
2748 if (db_mergeisinside(omp->x[oi], omp->y[oi], mp)) continue;
2749 holepoly = db_mergeallocpoly(merge);
2750 holepoly->layer = mp->layer;
2751 holepoly->tech = mp->tech;
2752 if (db_mergewalkedge(merge, omp, oi, mp, holepoly, FALSE)) return(FALSE);
2753 holepoly->nextmpoly = holepolylist;
2754 holepolylist = holepoly;
2755 }
2756
2757 /* see if there are any points that didn't get seen and are not in the other polygon */
2758 for(i=0; i<mp->count; i++)
2759 {
2760 if (mp->seen[i] != 0) continue;
2761 for(j=0; j<mp->count; j++)
2762 if (mp->seen[j] != 0 && mp->x[j] == mp->x[i] && mp->y[j] == mp->y[i]) break;
2763 if (j < mp->count) continue;
2764 if (db_mergeisinside(mp->x[i], mp->y[i], omp)) continue;
2765 holepoly = db_mergeallocpoly(merge);
2766 holepoly->layer = mp->layer;
2767 holepoly->tech = mp->tech;
2768 if (db_mergewalkedge(merge, mp, i, omp, holepoly, FALSE)) return(FALSE);
2769 holepoly->nextmpoly = holepolylist;
2770 holepolylist = holepoly;
2771 }
2772 for(oi=0; oi<omp->count; oi++)
2773 {
2774 if (omp->seen[oi] != 0) continue;
2775 for(j=0; j<omp->count; j++)
2776 if (omp->seen[j] != 0 && omp->x[j] == omp->x[oi] && omp->y[j] == omp->y[oi]) break;
2777 if (j < omp->count) continue;
2778 if (db_mergeisinside(omp->x[oi], omp->y[oi], mp)) continue;
2779 holepoly = db_mergeallocpoly(merge);
2780 holepoly->layer = mp->layer;
2781 holepoly->tech = mp->tech;
2782 if (db_mergewalkedge(merge, omp, oi, mp, holepoly, FALSE)) return(FALSE);
2783 holepoly->nextmpoly = holepolylist;
2784 holepolylist = holepoly;
2785 }
2786
2787 /* carve holes from polygon */
2788 if (db_mergeaddholetopoly(merge, holepolylist, merge->newmp)) return(FALSE);
2789 }
2790
2791 /* copy result back to second polygon */
2792 if (db_mergecopypoly(merge, merge->newmp, omp)) return(FALSE);
2793 db_mergesimplifyandbbox(omp);
2794 return(TRUE);
2795 }
2796
2797 /*
2798 * Routine to find a good starting point on polygon "mp" (the other one is "omp").
2799 * Looks for points with no intersection marks, preferably on the outside edge,
2800 * and not inside of the other polygon
2801 */
db_mergefindstartingpoint(MPOLY * mp,MPOLY * omp)2802 INTBIG db_mergefindstartingpoint(MPOLY *mp, MPOLY *omp)
2803 {
2804 REGISTER INTBIG i, lx, hx, ly, hy;
2805
2806 lx = hx = mp->x[0];
2807 ly = hy = mp->y[0];
2808 for(i=1; i<mp->count; i++)
2809 {
2810 if (mp->x[i] < lx) lx = mp->x[i];
2811 if (mp->x[i] > hx) hx = mp->x[i];
2812 if (mp->y[i] < ly) ly = mp->y[i];
2813 if (mp->y[i] > hy) hy = mp->y[i];
2814 }
2815
2816 /* look for points with no intersection, on edge, and not inside other */
2817 for(i=0; i<mp->count; i++)
2818 {
2819 if (mp->intersect[i] != 0) continue;
2820 if (mp->x[i] != lx && mp->x[i] != hx &&
2821 mp->y[i] != ly && mp->y[i] != hy) continue;
2822 if (db_mergeisinside(mp->x[i], mp->y[i], omp)) continue;
2823 return(i);
2824 }
2825
2826 /* accept points that aren't on the edge */
2827 for(i=0; i<mp->count; i++)
2828 {
2829 if (mp->intersect[i] != 0) continue;
2830 if (db_mergeisinside(mp->x[i], mp->y[i], omp)) continue;
2831 return(i);
2832 }
2833
2834 /* nothing found */
2835 return(-1);
2836 }
2837
2838 /*
2839 * Helper routine to add hole polygon "holemp" to the main polygon "newmp".
2840 * Finds the closest points on the two and adds the points.
2841 * Returns true on error.
2842 */
db_mergeaddholetopoly(MERGE * merge,MPOLY * holemplist,MPOLY * newmp)2843 BOOLEAN db_mergeaddholetopoly(MERGE *merge, MPOLY *holemplist, MPOLY *newmp)
2844 {
2845 REGISTER INTBIG j, k, l, dist, bestdist, hint, nint, nx, ny, hfx, hfy, htx, hty,
2846 nfx, nfy, ntx, nty, lastj, lastk, solved;
2847 INTBIG bestpos;
2848 MPOLY *holemp, *besthole, *lasthole, *bestlasthole;
2849
2850 /* keep adding holes until there are no more */
2851 while (holemplist != NOMPOLY)
2852 {
2853 solved = 0;
2854 lasthole = NOMPOLY;
2855 besthole = NOMPOLY;
2856
2857 /* mark points on the main polygon that are duplicated (can't attach holes there) */
2858 for(k=0; k<newmp->count; k++) newmp->seen[k] = 0;
2859 for(k=0; k<newmp->count; k++)
2860 {
2861 for(j=k+1; j<newmp->count; j++)
2862 {
2863 if (newmp->x[k] == newmp->x[j] && newmp->y[k] == newmp->y[j])
2864 newmp->seen[k] = newmp->seen[j] = 1;
2865 }
2866 }
2867
2868 /* examine every hole to find the next one to add */
2869 for(holemp = holemplist; holemp != NOMPOLY; holemp = holemp->nextmpoly)
2870 {
2871 /* find point on hole that is closest to a polygon point */
2872 for(j=0; j<holemp->count; j++)
2873 {
2874 /* get coordinates of the hole segment */
2875 if (j == 0) lastj = holemp->count - 1; else
2876 lastj = j - 1;
2877 hfx = holemp->x[lastj]; hfy = holemp->y[lastj];
2878 htx = holemp->x[j]; hty = holemp->y[j];
2879 for(k=0; k<newmp->count; k++)
2880 {
2881 /* get coordinates of the main polygon segment */
2882 if (k == 0) lastk = newmp->count - 1; else
2883 lastk = k - 1;
2884 nfx = newmp->x[lastk]; nfy = newmp->y[lastk];
2885 ntx = newmp->x[k]; nty = newmp->y[k];
2886
2887 /* see if they are colinear */
2888 if (hfx == htx && hfx == nfx && nfx == ntx)
2889 {
2890 /* vertically aligned */
2891 if (mini(hfy, hty) < maxi(nfy, nty) && maxi(hfy, hty) > mini(nfy, nty))
2892 {
2893 bestpos = k;
2894 l = lastj;
2895 for(;;)
2896 {
2897 l++;
2898 if (l >= holemp->count) l = 0;
2899 if (db_mergeinsertpoint(merge, newmp, &bestpos, holemp->x[l], holemp->y[l])) return(TRUE);
2900 #ifdef SHOWHOLEGROWTH
2901 ttyputmsg(x_(" Adding carveout point (%s,%s)"), latoa(holemp->x[l], 0), latoa(holemp->y[l], 0));
2902 #endif
2903 if (l == lastj) break;
2904 }
2905 besthole = holemp;
2906 bestlasthole = lasthole;
2907 solved = 1;
2908 break;
2909 }
2910 }
2911 if (hfy == hty && hfy == nfy && nfy == nty)
2912 {
2913 if (mini(hfx, htx) < maxi(nfx, ntx) && maxi(hfx, htx) > mini(nfx, ntx))
2914 {
2915 bestpos = k;
2916 l = lastj;
2917 for(;;)
2918 {
2919 l++;
2920 if (l >= holemp->count) l = 0;
2921 if (db_mergeinsertpoint(merge, newmp, &bestpos, holemp->x[l], holemp->y[l])) return(TRUE);
2922 if (l == lastj) break;
2923 }
2924 besthole = holemp;
2925 bestlasthole = lasthole;
2926 solved = 1;
2927 break;
2928 }
2929 }
2930
2931 /* not colinear: look for proximity */
2932 if (newmp->seen[k] == 0)
2933 {
2934 dist = computedistance(holemp->x[j], holemp->y[j], newmp->x[k], newmp->y[k]);
2935
2936 /* LINTED "bestdist" used in proper order */
2937 if (besthole == NOMPOLY || dist < bestdist)
2938 {
2939 bestdist = dist;
2940 hint = j;
2941 nint = k;
2942 besthole = holemp;
2943 bestlasthole = lasthole;
2944 }
2945 }
2946 }
2947 if (solved != 0) break;
2948 }
2949 lasthole = holemp;
2950 }
2951 if (solved == 0)
2952 {
2953 if (besthole == NOMPOLY)
2954 {
2955 ttyputerr(x_("ERROR merging polygon: cannot remove hole"));
2956 break;
2957 }
2958 bestpos = nint+1;
2959 nx = newmp->x[nint]; ny = newmp->y[nint];
2960 #ifdef SHOWHOLEGROWTH
2961 ttyputmsg(x_("Hole point %d (%s,%s) closest to polygon point %ld (%s,%s)"),hint, latoa(besthole->x[hint], 0),
2962 latoa(besthole->y[hint], 0), nint, latoa(nx), latoa(ny));
2963 #endif
2964 if (nx != besthole->x[hint] || ny != besthole->y[hint])
2965 {
2966 #ifdef SHOWHOLEGROWTH
2967 ttyputmsg(x_(" Adding bridge point (%s,%s)"), latoa(besthole->x[hint], 0), latoa(besthole->y[hint], 0));
2968 #endif
2969 if (db_mergeinsertpoint(merge, newmp, &bestpos, besthole->x[hint], besthole->y[hint])) return(TRUE);
2970 }
2971 j = hint;
2972 for(;;)
2973 {
2974 j++;
2975 if (j >= besthole->count) j = 0;
2976 if (db_mergeinsertpoint(merge, newmp, &bestpos, besthole->x[j], besthole->y[j])) return(TRUE);
2977 #ifdef SHOWHOLEGROWTH
2978 ttyputmsg(x_(" Adding point (%s,%s)"), latoa(besthole->x[j], 0), latoa(besthole->y[j], 0));
2979 #endif
2980 if (j == hint) break;
2981 }
2982 if (nx != besthole->x[hint] || ny != besthole->y[hint])
2983 {
2984 #ifdef SHOWHOLEGROWTH
2985 ttyputmsg(x_(" Adding bridge point (%s,%s)"), latoa(nx, 0), latoa(ny, 0));
2986 #endif
2987 if (db_mergeinsertpoint(merge, newmp, &bestpos, nx, ny)) return(TRUE);
2988 }
2989 }
2990
2991 #ifdef SHOWHOLEGROWTH
2992 {
2993 REGISTER NODEPROTO *cell, *prim;
2994 REGISTER NODEINST *ni;
2995 REGISTER INTBIG i, lx, hx, ly, hy, cx, cy, *newlist;
2996 static INTBIG db_mergeshowxoff = 0;
2997
2998 db_mergeshowxoff += el_curlib->lambda[el_curtech->techindex] * RESULTSPACING;
2999 cell = getcurcell();
3000 if (cell == NONODEPROTO) return(TRUE);
3001 prim = getnodeproto(x_("metal-2-node"));
3002 lx = hx = besthole->x[0];
3003 ly = hy = besthole->y[0];
3004 for(i=1; i<besthole->count; i++)
3005 {
3006 if (besthole->x[i] < lx) lx = besthole->x[i];
3007 if (besthole->x[i] > hx) hx = besthole->x[i];
3008 if (besthole->y[i] < ly) ly = besthole->y[i];
3009 if (besthole->y[i] > hy) hy = besthole->y[i];
3010 }
3011 cx = (lx+hx) / 2; cy = (ly+hy) / 2;
3012 ni = newnodeinst(prim, lx+db_mergeshowxoff, hx+db_mergeshowxoff, ly, hy, 0, 0, cell);
3013 newlist = (INTBIG *)emalloc(besthole->count * 2 * SIZEOFINTBIG, el_tempcluster);
3014 if (newlist == 0) return(TRUE);
3015 for(i=0; i<besthole->count; i++)
3016 {
3017 newlist[i*2] = besthole->x[i] - cx;
3018 newlist[i*2+1] = besthole->y[i] - cy;
3019 }
3020 (void)setvalkey((INTBIG)ni, VNODEINST, el_trace_key, (INTBIG)newlist,
3021 VINTEGER|VISARRAY|((besthole->count*2)<<VLENGTHSH));
3022 efree((CHAR *)newlist);
3023 endobjectchange((INTBIG)ni, VNODEINST);
3024
3025 prim = getnodeproto(x_("metal-1-node"));
3026 lx = hx = newmp->x[0];
3027 ly = hy = newmp->y[0];
3028 for(i=1; i<newmp->count; i++)
3029 {
3030 if (newmp->x[i] < lx) lx = newmp->x[i];
3031 if (newmp->x[i] > hx) hx = newmp->x[i];
3032 if (newmp->y[i] < ly) ly = newmp->y[i];
3033 if (newmp->y[i] > hy) hy = newmp->y[i];
3034 }
3035 cx = (lx+hx) / 2; cy = (ly+hy) / 2;
3036 ni = newnodeinst(prim, lx+db_mergeshowxoff, hx+db_mergeshowxoff, ly, hy, 0, 0, cell);
3037 newlist = (INTBIG *)emalloc(newmp->count * 2 * SIZEOFINTBIG, el_tempcluster);
3038 if (newlist == 0) return(TRUE);
3039 for(i=0; i<newmp->count; i++)
3040 {
3041 newlist[i*2] = newmp->x[i] - cx;
3042 newlist[i*2+1] = newmp->y[i] - cy;
3043 }
3044 (void)setvalkey((INTBIG)ni, VNODEINST, el_trace_key, (INTBIG)newlist,
3045 VINTEGER|VISARRAY|((newmp->count*2)<<VLENGTHSH));
3046 efree((CHAR *)newlist);
3047 endobjectchange((INTBIG)ni, VNODEINST);
3048 }
3049 #endif
3050 if (bestlasthole == NOMPOLY) holemplist = besthole->nextmpoly; else
3051 bestlasthole->nextmpoly = besthole->nextmpoly;
3052 db_mergefreepoly(besthole);
3053 }
3054 return(FALSE);
3055 }
3056
3057 /*
3058 * Helper routine to look for intersection points between the two polygons "mp" and "omp"
3059 * (which may be the same polygon, when looking for self-intersections). The intersection
3060 * points are added to the polygon and marked (1 for self-intersection, 2 for intersection
3061 * with the other polygon). Returns nonzero on error.
3062 */
db_mergesortiny(const void * e1,const void * e2)3063 int db_mergesortiny(const void *e1, const void *e2)
3064 {
3065 REGISTER INTBIG i1, i2, lasti1, lasti2, y1, y2;
3066
3067 i1 = *((INTBIG *)e1);
3068 i2 = *((INTBIG *)e2);
3069 if (i1 == 0) lasti1 = db_mergesortpoly->count - 1; else
3070 lasti1 = i1 - 1;
3071 if (i2 == 0) lasti2 = db_mergesortpoly->count - 1; else
3072 lasti2 = i2 - 1;
3073 y1 = mini(db_mergesortpoly->y[i1], db_mergesortpoly->y[lasti1]);
3074 y2 = mini(db_mergesortpoly->y[i2], db_mergesortpoly->y[lasti2]);
3075 return(y1 - y2);
3076 }
3077
db_mergeaddintersectionpoints(MERGE * merge,MPOLY * mp,MPOLY * omp)3078 BOOLEAN db_mergeaddintersectionpoints(MERGE *merge, MPOLY *mp, MPOLY *omp)
3079 {
3080 REGISTER INTBIG i, j, y, toty, oi, fy, ty, ofy, oty, last, olast,
3081 intvalue, cury, fromline, ofromline, startpos;
3082 REGISTER BOOLEAN keepon;
3083
3084 if (mp == omp) intvalue = 1; else intvalue = 2;
3085
3086 /* get list of line segments, sorted by low y */
3087 if (ensureintlistobj(merge->yorder, mp->count)) return(TRUE);
3088 if (ensureintlistobj(merge->Oyorder, omp->count)) return(TRUE);
3089 merge->yorder->count = mp->count;
3090 merge->Oyorder->count = omp->count;
3091 for(i=0; i<merge->yorder->count; i++) merge->yorder->list[i] = i;
3092 db_mergesortpoly = mp;
3093 esort(merge->yorder->list, merge->yorder->count, SIZEOFINTBIG, db_mergesortiny);
3094 if (omp == mp)
3095 {
3096 for(oi=0; oi<merge->Oyorder->count; oi++) merge->Oyorder->list[oi] = merge->yorder->list[oi];
3097 } else
3098 {
3099 for(oi=0; oi<merge->Oyorder->count; oi++) merge->Oyorder->list[oi] = oi;
3100 db_mergesortpoly = omp;
3101 esort(merge->Oyorder->list, merge->Oyorder->count, SIZEOFINTBIG, db_mergesortiny);
3102 }
3103
3104 /* get ordered list of relevant Y coordinates */
3105 toty = merge->yorder->count;
3106 if (omp != mp) toty += merge->Oyorder->count;
3107 if (ensureintlistobj(merge->ylist, toty)) return(TRUE);
3108 j = 0;
3109 for(i=0; i<merge->yorder->count; i++) merge->ylist->list[j++] = mp->y[i];
3110 if (omp != mp)
3111 for(oi=0; oi<merge->Oyorder->count; oi++) merge->ylist->list[j++] = omp->y[oi];
3112 esort(merge->ylist->list, toty, SIZEOFINTBIG, sort_intbigascending);
3113 j = 0;
3114 for(i=0; i<toty; i++)
3115 {
3116 if (j != 0 && merge->ylist->list[i] == merge->ylist->list[j-1]) continue;
3117 merge->ylist->list[j++] = merge->ylist->list[i];
3118 }
3119 toty = j;
3120
3121 /* clear the queue of active lines in each polygon */
3122 keepon = TRUE;
3123 while (keepon)
3124 {
3125 keepon = FALSE;
3126 fromline = 0;
3127 merge->queue->count = 0;
3128 ofromline = 0;
3129 merge->Oqueue->count = 0;
3130
3131 /* loop through relevant y coordinates */
3132 for(y=0; y<toty; y++)
3133 {
3134 cury = merge->ylist->list[y];
3135
3136 /* remove anything at or below "cury" from the active queues */
3137 for(j=0; j<merge->queue->count; j++)
3138 {
3139 i = merge->queue->list[j];
3140 if (i == 0) last = mp->count - 1; else
3141 last = i - 1;
3142 if (mp->y[i] < cury && mp->y[last] < cury)
3143 {
3144 merge->queue->list[j] = merge->queue->list[merge->queue->count-1];
3145 merge->queue->count--;
3146 j--;
3147 continue;
3148 }
3149 }
3150 for(j=0; j<merge->Oqueue->count; j++)
3151 {
3152 oi = merge->Oqueue->list[j];
3153 if (oi == 0) olast = omp->count - 1; else
3154 olast = oi - 1;
3155 if (omp->y[oi] < cury && omp->y[olast] < cury)
3156 {
3157 merge->Oqueue->list[j] = merge->Oqueue->list[merge->Oqueue->count-1];
3158 merge->Oqueue->count--;
3159 j--;
3160 continue;
3161 }
3162 }
3163
3164 /* add any new objects */
3165 while (fromline < merge->yorder->count)
3166 {
3167 i = merge->yorder->list[fromline];
3168 if (i == 0) last = mp->count - 1; else
3169 last = i - 1;
3170 fy = mp->y[last]; ty = mp->y[i];
3171 if (fy > cury && ty > cury) break;
3172
3173 if (addtointlistobj(merge->queue, i, FALSE)) return(TRUE);
3174 fromline++;
3175
3176 /* check and make merges of all new lines against existing list */
3177 startpos = merge->queue->count-1;
3178 while (db_mergecheckqueue(merge,
3179 mp, merge->queue, merge->yorder, startpos, fromline,
3180 omp, merge->Oqueue, merge->Oyorder, ofromline, intvalue));
3181 }
3182 if (merge->queue->count == 0 && fromline >= merge->yorder->count) break;
3183
3184 while (ofromline < merge->Oyorder->count)
3185 {
3186 oi = merge->Oyorder->list[ofromline];
3187 if (oi == 0) olast = omp->count - 1; else
3188 olast = oi - 1;
3189 ofy = omp->y[olast]; oty = omp->y[oi];
3190 if (ofy > cury && oty > cury) break;
3191 if (addtointlistobj(merge->Oqueue, oi, FALSE)) return(TRUE);
3192 ofromline++;
3193
3194 /* check and make merges of all new lines against existing list */
3195 startpos = merge->Oqueue->count-1;
3196 while (db_mergecheckqueue(merge,
3197 omp, merge->Oqueue, merge->Oyorder, startpos, ofromline,
3198 mp, merge->queue, merge->yorder, fromline, intvalue));
3199 }
3200 if (merge->Oqueue->count == 0 && ofromline >= merge->Oyorder->count) break;
3201 }
3202 }
3203 return(FALSE);
3204 }
3205
3206 /*
3207 * Routine to examine queued lines starting at "startqueuepos" and add
3208 * intersection points as necessary. When a point has been added, returns TRUE.
3209 */
db_mergecheckqueue(MERGE * merge,MPOLY * mp,LISTINTBIG * queue,LISTINTBIG * yorder,INTBIG startqueuepos,INTBIG fromline,MPOLY * omp,LISTINTBIG * Oqueue,LISTINTBIG * Oyorder,INTBIG ofromline,INTBIG intvalue)3210 BOOLEAN db_mergecheckqueue(MERGE *merge,
3211 MPOLY *mp, LISTINTBIG *queue, LISTINTBIG *yorder, INTBIG startqueuepos, INTBIG fromline,
3212 MPOLY *omp, LISTINTBIG *Oqueue, LISTINTBIG *Oyorder, INTBIG ofromline, INTBIG intvalue)
3213 {
3214 REGISTER INTBIG i, j, k, m, ic, fx, fy, tx, ty, ofx, ofy, otx, oty, last, olast, oi, icount,
3215 ix, iy, hasint, ohasint;
3216 INTBIG ixa[2], iya[2];
3217
3218 /* check new lines in this queue */
3219 for(m=startqueuepos; m < queue->count; m++)
3220 {
3221 i = queue->list[m];
3222 if (i == 0) last = mp->count - 1; else
3223 last = i - 1;
3224 fx = mp->x[last]; tx = mp->x[i];
3225 fy = mp->y[last]; ty = mp->y[i];
3226
3227 /* check against everything in the other queue */
3228 for(j=0; j < Oqueue->count; j++)
3229 {
3230 oi = Oqueue->list[j];
3231 if (oi == 0) olast = omp->count - 1; else
3232 olast = oi - 1;
3233 if (mp == omp && (i == oi || last == oi || olast == i)) continue;
3234 ofx = omp->x[olast]; otx = omp->x[oi];
3235 ofy = omp->y[olast]; oty = omp->y[oi];
3236 icount = db_mergelinesintersect(fx,fy, tx,ty, ofx,ofy, otx,oty, ixa,iya);
3237 for(ic=0; ic<icount; ic++)
3238 {
3239 ix = ixa[ic]; iy = iya[ic];
3240
3241 /* mark points that intersect */
3242 hasint = 0;
3243 if (ix == fx && iy == fy) { mp->intersect[last] = intvalue; hasint++; }
3244 if (ix == tx && iy == ty) { mp->intersect[i] = intvalue; hasint++; }
3245 if (hasint == 0)
3246 {
3247 if (db_mergeaddthisintersectionpoint(merge, mp, i, ix, iy, intvalue)) return(FALSE);
3248 for(k=fromline; k<yorder->count; k++)
3249 if (yorder->list[k] >= i) yorder->list[k]++;
3250 if (mp == omp)
3251 {
3252 for(k=ofromline; k<Oyorder->count; k++)
3253 if (Oyorder->list[k] >= i) Oyorder->list[k]++;
3254 }
3255 for(k=0; k < queue->count; k++)
3256 if (queue->list[k] >= i) queue->list[k]++;
3257 if (mp == omp)
3258 {
3259 for(k=0; k < Oqueue->count; k++)
3260 if (Oqueue->list[k] >= i) Oqueue->list[k]++;
3261 }
3262 if (addtointlistobj(queue, i, FALSE)) return(FALSE);
3263 return(TRUE);
3264 }
3265
3266 ohasint = 0;
3267 if (ix == ofx && iy == ofy) { omp->intersect[olast] = intvalue; ohasint++; }
3268 if (ix == otx && iy == oty) { omp->intersect[oi] = intvalue; ohasint++; }
3269 if (ohasint == 0)
3270 {
3271 if (db_mergeaddthisintersectionpoint(merge, omp, oi, ix, iy, intvalue)) return(FALSE);
3272 for(k=ofromline; k<Oyorder->count; k++)
3273 if (Oyorder->list[k] >= oi) Oyorder->list[k]++;
3274 if (mp == omp)
3275 {
3276 for(k=fromline; k<yorder->count; k++)
3277 if (yorder->list[k] >= oi) yorder->list[k]++;
3278 }
3279 for(k=0; k < Oqueue->count; k++)
3280 if (Oqueue->list[k] >= oi) Oqueue->list[k]++;
3281 if (mp == omp)
3282 {
3283 for(k=0; k < queue->count; k++)
3284 if (queue->list[k] >= i) queue->list[k]++;
3285 }
3286 if (addtointlistobj(Oqueue, oi, FALSE)) return(FALSE);
3287 return(TRUE);
3288 }
3289 }
3290 }
3291 }
3292 return(FALSE);
3293 }
3294
db_mergeaddthisintersectionpoint(MERGE * merge,MPOLY * mp,INTBIG i,INTBIG ix,INTBIG iy,INTBIG intvalue)3295 BOOLEAN db_mergeaddthisintersectionpoint(MERGE *merge, MPOLY *mp, INTBIG i, INTBIG ix, INTBIG iy, INTBIG intvalue)
3296 {
3297 /* add intersection point to the first polygon */
3298 if (db_mergeensurespace(merge, mp, mp->count+1)) return(TRUE);
3299 memmove(&mp->x[i+1], &mp->x[i], (mp->count-i)*SIZEOFINTBIG);
3300 memmove(&mp->y[i+1], &mp->y[i], (mp->count-i)*SIZEOFINTBIG);
3301 memmove(&mp->intersect[i+1], &mp->intersect[i], (mp->count-i)*SIZEOFINTBIG);
3302 mp->count++;
3303 mp->x[i] = ix;
3304 mp->y[i] = iy;
3305 mp->intersect[i] = intvalue;
3306 return(FALSE);
3307 }
3308
3309 /*
3310 * Helper routine to walk around the edge of polygon "mp", starting at point "i". If it hits
3311 * polygon "omp", merge it in. Resulting polygon is in "newmp". Returns true on error.
3312 */
db_mergewalkedge(MERGE * merge,MPOLY * mp,INTBIG i,MPOLY * omp,MPOLY * newmp,BOOLEAN subtract)3313 BOOLEAN db_mergewalkedge(MERGE *merge, MPOLY *mp, INTBIG i, MPOLY *omp, MPOLY *newmp, BOOLEAN subtract)
3314 {
3315 MPOLY *mps[2];
3316 REGISTER MPOLY *mp1, *mp2;
3317 REGISTER INTBIG enterangle, leaveangle;
3318 REGISTER INTBIG startpol, startpt, last, next, pol, pt, unseenpt,
3319 unseenthis, smallestthisangle, smallestotherangle;
3320 INTBIG insert;
3321
3322 #ifdef DEBUGWALK
3323 ttyputmsg(x_("Walking around edge, polygon 0 has %ld points, polygon 1 has %ld"), mp->count, omp->count);
3324 #endif
3325 merge->seen++;
3326 if (merge->seen == 0) merge->seen++;
3327 mps[0] = mp; mps[1] = omp;
3328 startpol = 0; startpt = i;
3329 pol = startpol; pt = startpt;
3330 insert = 0;
3331 for(;;)
3332 {
3333 /* include this point */
3334 mp1 = mps[pol];
3335 mp2 = mps[1-pol];
3336 mp1->seen[pt] = merge->seen;
3337 #ifdef DEBUGWALK
3338 ttyputmsg(x_(" Add (%s,%s) from polygon %ld"), latoa(mps[pol]->x[pt], 0), latoa(mps[pol]->y[pt], 0), pol);
3339 #endif
3340 if (db_mergeinsertpoint(merge, newmp, &insert, mps[pol]->x[pt], mps[pol]->y[pt]))
3341 return(TRUE);
3342 if (newmp->count == 5000)
3343 {
3344 if (!merge->loopwarned)
3345 {
3346 #ifdef SHOWRESULTS
3347 REGISTER INTBIG lambda;
3348 NODEINST *ni;
3349 NODEPROTO *cell, *prim;
3350
3351 lambda = el_curlib->lambda[el_curtech->techindex];
3352 prim = getnodeproto(x_("metal-3-node"));
3353 cell = getcurcell();
3354 if (cell != NONODEPROTO)
3355 {
3356 ni = newnodeinst(prim, db_mergeshowrightmost+lambda, db_mergeshowrightmost+lambda*5,
3357 cell->lowy, cell->highy, 0, 0, cell);
3358 }
3359 endobjectchange((INTBIG)ni, VNODEINST);
3360 #endif
3361 ttyputerr(_("Warning: loop detected while merging polygons on layer %s"),
3362 layername(mp->tech, mp->layer));
3363 merge->loopwarned = TRUE;
3364 }
3365 return(TRUE);
3366 }
3367
3368 /* see if there are intersection points on this or the other polygon */
3369 merge->intcount = 0;
3370 for(i=0; i<mp1->count; i++)
3371 {
3372 if (i == pt) continue;
3373 if (mp1->x[i] != mp1->x[pt] || mp1->y[i] != mp1->y[pt]) continue;
3374 db_mergeaddintersectionpoint(merge, pol, i);
3375 }
3376 for(i=0; i<mp2->count; i++)
3377 {
3378 if (mp2->x[i] != mp1->x[pt] || mp2->y[i] != mp1->y[pt]) continue;
3379 db_mergeaddintersectionpoint(merge, 1-pol, i);
3380 }
3381
3382 /* if point not on other polygon or elsewhere on this, keep walking around edge */
3383 if (merge->intcount == 0)
3384 {
3385 #ifdef DEBUGWALK
3386 ttyputmsg(x_(" Not an intersection point"));
3387 #endif
3388 pt++;
3389 if (pt >= mp1->count) pt = 0;
3390 if (pol == startpol && pt == startpt) break;
3391 continue;
3392 }
3393
3394 /* intersection point: figure out what to do */
3395 if (pt == 0) last = mp1->count-1; else last = pt-1;
3396 enterangle = figureangle(mp1->x[pt], mp1->y[pt], mp1->x[last], mp1->y[last]);
3397
3398 if (pt == mp1->count-1) next = 0; else next = pt+1;
3399 leaveangle = figureangle(mp1->x[pt], mp1->y[pt], mp1->x[next], mp1->y[next]);
3400 if (leaveangle > enterangle) leaveangle -= 3600;
3401 leaveangle = enterangle - leaveangle;
3402
3403 #ifdef DEBUGWALK
3404 ttyputmsg(x_(" Intersection point! enter at (%s,%s)=%ld, leave at (%s,%s)=%ld"),
3405 latoa(mp1->x[last], 0), latoa(mp1->y[last], 0), enterangle/10, latoa(mp1->x[next], 0), latoa(mp1->y[next], 0), leaveangle/10);
3406 #endif
3407 for(i=0; i<merge->intcount; i++)
3408 {
3409 if (merge->intpt[i] == mps[merge->intpol[i]]->count-1) next = 0; else next = merge->intpt[i]+1;
3410 merge->intleaveangle[i] = figureangle(mp1->x[pt], mp1->y[pt],
3411 mps[merge->intpol[i]]->x[next], mps[merge->intpol[i]]->y[next]);
3412 if (merge->intleaveangle[i] > enterangle) merge->intleaveangle[i] -= 3600;
3413 merge->intleaveangle[i] = enterangle - merge->intleaveangle[i];
3414 if (merge->intleaveangle[i] == 0) merge->intleaveangle[i] = 7200;
3415 #ifdef DEBUGWALK
3416 ttyputmsg(x_(" Point on %s polygon goes to (%s,%s), angle=%ld"),
3417 (merge->intpol[i] == pol ? x_("this") : x_("other")), latoa(mps[merge->intpol[i]]->x[next], 0),
3418 latoa(mps[merge->intpol[i]]->y[next], 0), merge->intleaveangle[i]/10);
3419 #endif
3420 }
3421
3422 smallestthisangle = 7200;
3423 unseenthis = -1;
3424 for(i=0; i<merge->intcount; i++)
3425 {
3426 if (merge->intpol[i] != pol) continue;
3427 if (merge->intleaveangle[i] > smallestthisangle) continue;
3428 smallestthisangle = merge->intleaveangle[i];
3429 unseenthis = merge->intpt[i];
3430 }
3431
3432 smallestotherangle = 7200;
3433 unseenpt = -1;
3434 for(i=0; i<merge->intcount; i++)
3435 {
3436 if (merge->intpol[i] == pol) continue;
3437 if (merge->intleaveangle[i] > smallestotherangle) continue;
3438 smallestotherangle = merge->intleaveangle[i];
3439 unseenpt = merge->intpt[i];
3440 }
3441 if (subtract)
3442 {
3443 if (smallestthisangle != 7200) smallestthisangle = 3600 - smallestthisangle;
3444 leaveangle = 3600 - leaveangle;
3445 if (smallestotherangle != 7200) smallestotherangle = 3600 - smallestotherangle;
3446 }
3447 #ifdef DEBUGWALK
3448 ttyputmsg(x_(" So smallestTHISangle=%ld, smallestOTHERangle=%ld, leaveangle=%ld"),
3449 smallestthisangle, smallestotherangle, leaveangle);
3450 #endif
3451 if (smallestthisangle < leaveangle && smallestthisangle < smallestotherangle)
3452 {
3453 /* staying on the same polygon but jumping to a new point */
3454 #ifdef DEBUGWALK
3455 ttyputmsg(x_(" Stay on same polygon, jump to new point"));
3456 #endif
3457 pt = unseenthis;
3458 if (pol == startpol && pt == startpt) break;
3459 mp1->seen[pt] = merge->seen;
3460
3461 /* advance to the next point */
3462 pt++;
3463 if (pt >= mp1->count) pt = 0;
3464 if (pol == startpol && pt == startpt) break;
3465 continue;
3466 }
3467 if (leaveangle <= smallestthisangle && leaveangle <= smallestotherangle)
3468 {
3469 /* stay on the current polygon */
3470 #ifdef DEBUGWALK
3471 ttyputmsg(x_(" Stay on same polygon"));
3472 #endif
3473 pt++;
3474 if (pt >= mp1->count) pt = 0;
3475 } else
3476 {
3477 /* switch to the other polygon */
3478 #ifdef DEBUGWALK
3479 ttyputmsg(x_(" Switch to other polygon"));
3480 #endif
3481 pt = unseenpt;
3482 pol = 1 - pol;
3483 if (pol == startpol && pt == startpt) break;
3484 mp2->seen[pt] = merge->seen;
3485
3486 /* advance to the next point */
3487 pt++;
3488 if (pt >= mp2->count) pt = 0;
3489 }
3490 if (pol == startpol && pt == startpt) break;
3491 }
3492 return(FALSE);
3493 }
3494
3495 /*
3496 * Helper routine to insert the point (x, y) at "insert" in polygon "mp".
3497 * Returns true on error.
3498 */
db_mergeinsertpoint(MERGE * merge,MPOLY * mp,INTBIG * insert,INTBIG x,INTBIG y)3499 BOOLEAN db_mergeinsertpoint(MERGE *merge, MPOLY *mp, INTBIG *insert, INTBIG x, INTBIG y)
3500 {
3501 REGISTER INTBIG index;
3502
3503 if (db_mergeensurespace(merge, mp, mp->count+1)) return(TRUE);
3504 index = *insert;
3505 if (index <= 0 || mp->x[index-1] != x || mp->y[index-1] != y)
3506 {
3507 memmove(&mp->x[index+1], &mp->x[index], (mp->count - index)*SIZEOFINTBIG);
3508 memmove(&mp->y[index+1], &mp->y[index], (mp->count - index)*SIZEOFINTBIG);
3509 mp->x[index] = x;
3510 mp->y[index] = y;
3511 mp->count++;
3512 (*insert)++;
3513 }
3514 return(FALSE);
3515 }
3516
3517 /*
3518 * Routine to add polygon "polygon" and point "point" to the global arrays of
3519 * intersection points.
3520 */
db_mergeaddintersectionpoint(MERGE * merge,INTBIG polygon,INTBIG point)3521 void db_mergeaddintersectionpoint(MERGE *merge, INTBIG polygon, INTBIG point)
3522 {
3523 REGISTER INTBIG i, newtotal, *newpol, *newpt, *newangle;
3524
3525 if (merge->intcount >= merge->inttotal)
3526 {
3527 newtotal = merge->inttotal * 2;
3528 if (newtotal <= 0) newtotal = 10;
3529 newpol = (INTBIG *)emalloc(newtotal * SIZEOFINTBIG, merge->clus);
3530 if (newpol == 0) return;
3531 newpt = (INTBIG *)emalloc(newtotal * SIZEOFINTBIG, merge->clus);
3532 if (newpt == 0) return;
3533 newangle = (INTBIG *)emalloc(newtotal * SIZEOFINTBIG, merge->clus);
3534 if (newangle == 0) return;
3535 for(i=0; i<merge->intcount; i++)
3536 {
3537 newpol[i] = merge->intpol[i];
3538 newpt[i] = merge->intpt[i];
3539 newangle[i] = merge->intleaveangle[i];
3540 }
3541 if (merge->inttotal > 0)
3542 {
3543 efree((CHAR *)merge->intpol);
3544 efree((CHAR *)merge->intpt);
3545 efree((CHAR *)merge->intleaveangle);
3546 }
3547 merge->intpol = newpol;
3548 merge->intpt = newpt;
3549 merge->intleaveangle = newangle;
3550 merge->inttotal = newtotal;
3551 }
3552 merge->intpol[merge->intcount] = polygon;
3553 merge->intpt[merge->intcount] = point;
3554 merge->intcount++;
3555 }
3556
3557 /*
3558 * Helper routine to determine whether the line segement (fx,fy)-(tx,ty)
3559 * intersects the line segment (ofx,ofy)-(otx,oty). If it does, the intersection
3560 * point(s) are placed in (ix,iy) and the routine returns the number of intersections
3561 * (parallel lines that are offset can have 2 intersection points).
3562 */
db_mergelinesintersect(INTBIG fx,INTBIG fy,INTBIG tx,INTBIG ty,INTBIG ofx,INTBIG ofy,INTBIG otx,INTBIG oty,INTBIG * ix,INTBIG * iy)3563 INTBIG db_mergelinesintersect(INTBIG fx, INTBIG fy, INTBIG tx, INTBIG ty,
3564 INTBIG ofx, INTBIG ofy, INTBIG otx, INTBIG oty, INTBIG *ix, INTBIG *iy)
3565 {
3566 double fa1, fb1, fc1, fa2, fb2, fc2, fswap, fiy, ang, oang, hang, ohang;
3567 REGISTER INTBIG maxx, maxy, minx, miny, omaxx, omaxy, ominx, ominy, intpoints;
3568
3569 /* quick check to see if lines don't intersect */
3570 if (fx > tx) { maxx = fx; minx = tx; } else { maxx = tx; minx = fx; }
3571 if (fy > ty) { maxy = fy; miny = ty; } else { maxy = ty; miny = fy; }
3572 if (ofx > otx) { omaxx = ofx; ominx = otx; } else { omaxx = otx; ominx = ofx; }
3573 if (ofy > oty) { omaxy = ofy; ominy = oty; } else { omaxy = oty; ominy = ofy; }
3574 if (minx > omaxx) return(0);
3575 if (maxx < ominx) return(0);
3576 if (miny > omaxy) return(0);
3577 if (maxy < ominy) return(0);
3578
3579 /* determine the angle of the lines */
3580 ang = atan2((double)(ty-fy), (double)(tx-fx));
3581 if (ang < 0.0) ang += EPI*2.0;
3582 oang = atan2((double)(oty-ofy), (double)(otx-ofx));
3583 if (oang < 0.0) oang += EPI*2.0;
3584
3585 /* special case if they are at the same angle */
3586 intpoints = 0;
3587 hang = fmod(ang, EPI);
3588 ohang = fmod(oang, EPI);
3589 if (fabs(hang - ohang) < 0.0001)
3590 {
3591 /* lines are parallel: see if they make intersections on the other */
3592 if (fx >= ominx && fx <= omaxx && fy >= ominy && fy <= omaxy)
3593 {
3594 /* see if (fx,fy) is an intersection point on the other line */
3595 if ((fx != otx || fy != oty) && (fx != ofx || fy != ofy))
3596 {
3597 if (isonline(ofx, ofy, otx, oty, fx, fy))
3598 {
3599 ix[intpoints] = fx;
3600 iy[intpoints] = fy;
3601 intpoints++;
3602 }
3603
3604 }
3605 }
3606 if (tx >= ominx && tx <= omaxx && ty >= ominy && ty <= omaxy)
3607 {
3608 /* see if (fx,fy) is an intersection point on the other line */
3609 if ((tx != otx || ty != oty) && (tx != ofx || ty != ofy))
3610 {
3611 if (isonline(ofx, ofy, otx, oty, tx, ty))
3612 {
3613 ix[intpoints] = tx;
3614 iy[intpoints] = ty;
3615 intpoints++;
3616 }
3617
3618 }
3619 }
3620
3621 if (otx >= minx && otx <= maxx && oty >= miny && oty <= maxy)
3622 {
3623 /* see if (fx,fy) is an intersection point on the other line */
3624 if ((tx != tx || oty != ty) && (otx != fx || oty != fy))
3625 {
3626 if (isonline(fx, fy, tx, ty, otx, oty))
3627 {
3628 ix[intpoints] = otx;
3629 iy[intpoints] = oty;
3630 intpoints++;
3631 }
3632
3633 }
3634 }
3635 if (ofx >= minx && ofx <= maxx && ofy >= miny && ofy <= maxy)
3636 {
3637 /* see if (fx,fy) is an intersection point on the other line */
3638 if ((ofx != tx || ofy != ty) && (ofx != fx || ofy != fy))
3639 {
3640 if (isonline(fx, fy, tx, ty, ofx, ofy))
3641 {
3642 ix[intpoints] = ofx;
3643 iy[intpoints] = ofy;
3644 intpoints++;
3645 }
3646
3647 }
3648 }
3649 return(intpoints);
3650 }
3651
3652 fa1 = sin(ang); fb1 = -cos(ang);
3653 fc1 = -fa1 * ((double)fx) - fb1 * ((double)fy);
3654 fa2 = sin(oang); fb2 = -cos(oang);
3655 fc2 = -fa2 * ((double)ofx) - fb2 * ((double)ofy);
3656 if (fabs(fa1) < fabs(fa2))
3657 {
3658 fswap = fa1; fa1 = fa2; fa2 = fswap;
3659 fswap = fb1; fb1 = fb2; fb2 = fswap;
3660 fswap = fc1; fc1 = fc2; fc2 = fswap;
3661 }
3662 fiy = (fa2 * fc1 / fa1 - fc2) / (fb2 - fa2*fb1/fa1);
3663 *iy = rounddouble(fiy);
3664 *ix = rounddouble((-fb1 * fiy - fc1) / fa1);
3665
3666 /* make sure the intersection is on the lines */
3667 if (*ix < minx || *ix < ominx) return(FALSE);
3668 if (*ix > maxx || *ix > omaxx) return(FALSE);
3669 if (*iy < miny || *iy < ominy) return(FALSE);
3670 if (*iy > maxy || *iy > omaxy) return(FALSE);
3671 return(1);
3672 }
3673
3674 /*
3675 * Helper routine to simplify polygon "mp", removing redundant and colinear points,
3676 * and recomputing its bounding box.
3677 */
db_mergesimplifyandbbox(MPOLY * mp)3678 void db_mergesimplifyandbbox(MPOLY *mp)
3679 {
3680 REGISTER INTBIG i, j, prev, next;
3681
3682 /* remove redundant points */
3683 for(i=1; i<mp->count; i++)
3684 {
3685 if (mp->x[i] == mp->x[i-1] && mp->y[i] == mp->y[i-1])
3686 {
3687 for(j=i; j<mp->count; j++)
3688 {
3689 mp->x[j-1] = mp->x[j];
3690 mp->y[j-1] = mp->y[j];
3691 }
3692 mp->count--;
3693 i--;
3694 continue;
3695 }
3696 }
3697 while (mp->count >= 2 && mp->x[0] == mp->x[mp->count-1] && mp->y[0] == mp->y[mp->count-1])
3698 mp->count--;
3699
3700 /* remove colinear points (only manhattan!!!) */
3701 for(i=0; i<mp->count; i++)
3702 {
3703 if (i == 0) prev = mp->count-1; else prev = i-1;
3704 if (i == mp->count-1) next = 0; else next = i+1;
3705 if ((mp->x[prev] == mp->x[i] && mp->x[i] == mp->x[next]) ||
3706 (mp->y[prev] == mp->y[i] && mp->y[i] == mp->y[next]))
3707 {
3708 for(j=i+1; j<mp->count; j++)
3709 {
3710 mp->x[j-1] = mp->x[j];
3711 mp->y[j-1] = mp->y[j];
3712 }
3713 mp->count--;
3714 i--;
3715 continue;
3716 }
3717 }
3718
3719 /* get bounding box */
3720 mp->lx = mp->hx = mp->x[0];
3721 mp->ly = mp->hy = mp->y[0];
3722 for(i=1; i<mp->count; i++)
3723 {
3724 if (mp->x[i] < mp->lx) mp->lx = mp->x[i];
3725 if (mp->x[i] > mp->hx) mp->hx = mp->x[i];
3726 if (mp->y[i] < mp->ly) mp->ly = mp->y[i];
3727 if (mp->y[i] > mp->hy) mp->hy = mp->y[i];
3728 }
3729 }
3730
3731 /*
3732 * Helper routine to return true if point (x,y) is inside of polygon "mp".
3733 */
db_mergeisinside(INTBIG x,INTBIG y,MPOLY * mp)3734 BOOLEAN db_mergeisinside(INTBIG x, INTBIG y, MPOLY *mp)
3735 {
3736 REGISTER INTBIG i, ang, lastp, tang, thisp;
3737
3738 /* general polygon containment by summing angles to vertices */
3739 ang = 0;
3740 if (x == mp->x[mp->count-1] && y == mp->y[mp->count-1]) return(TRUE);
3741 lastp = figureangle(x, y, mp->x[mp->count-1], mp->y[mp->count-1]);
3742 for(i=0; i<mp->count; i++)
3743 {
3744 if (x == mp->x[i] && y == mp->y[i]) return(TRUE);
3745 thisp = figureangle(x, y, mp->x[i], mp->y[i]);
3746 tang = lastp - thisp;
3747 if (tang < -1800) tang += 3600;
3748 if (tang > 1800) tang -= 3600;
3749 ang += tang;
3750 lastp = thisp;
3751 }
3752 if (abs(ang) <= mp->count) return(FALSE);
3753 return(TRUE);
3754 }
3755
3756 /*
3757 * Helper routine to copy polygon "smp" to polygon "dmp".
3758 * Returns true on error.
3759 */
db_mergecopypoly(MERGE * merge,MPOLY * smp,MPOLY * dmp)3760 BOOLEAN db_mergecopypoly(MERGE *merge, MPOLY *smp, MPOLY *dmp)
3761 {
3762 REGISTER INTBIG i;
3763
3764 if (db_mergeensurespace(merge, dmp, smp->count)) return(TRUE);
3765 for(i=0; i<smp->count; i++)
3766 {
3767 dmp->x[i] = smp->x[i];
3768 dmp->y[i] = smp->y[i];
3769 }
3770 dmp->count = smp->count;
3771 dmp->layer = smp->layer;
3772 return(FALSE);
3773 }
3774
3775 /*
3776 * Helper routine to make sure that polygon "mp" has room for "count" points.
3777 * Returns true on error.
3778 */
db_mergeensurespace(MERGE * merge,MPOLY * mp,INTBIG count)3779 BOOLEAN db_mergeensurespace(MERGE *merge, MPOLY *mp, INTBIG count)
3780 {
3781 REGISTER INTBIG i, *newx, *newy, *newseen, *newintersect, newlimit;
3782
3783 if (count <= mp->limit) return(FALSE);
3784 newlimit = mp->limit * 2;
3785 if (newlimit < count) newlimit = count+4;
3786 newx = (INTBIG *)emalloc(newlimit * SIZEOFINTBIG, merge->clus);
3787 if (newx == 0) return(TRUE);
3788 newy = (INTBIG *)emalloc(newlimit * SIZEOFINTBIG, merge->clus);
3789 if (newy == 0) return(TRUE);
3790 newseen = (INTBIG *)emalloc(newlimit * SIZEOFINTBIG, merge->clus);
3791 if (newseen == 0) return(TRUE);
3792 newintersect = (INTBIG *)emalloc(newlimit * SIZEOFINTBIG, merge->clus);
3793 if (newintersect == 0) return(TRUE);
3794 for(i=0; i<mp->count; i++)
3795 {
3796 newx[i] = mp->x[i];
3797 newy[i] = mp->y[i];
3798 newseen[i] = mp->seen[i];
3799 newintersect[i] = mp->intersect[i];
3800 }
3801 if (mp->limit > 0)
3802 {
3803 efree((CHAR *)mp->x);
3804 efree((CHAR *)mp->y);
3805 efree((CHAR *)mp->seen);
3806 efree((CHAR *)mp->intersect);
3807 }
3808 mp->limit = newlimit;
3809 mp->x = newx;
3810 mp->y = newy;
3811 mp->seen = newseen;
3812 mp->intersect = newintersect;
3813 return(FALSE);
3814 }
3815
db_mergealloc(CLUSTER * cluster)3816 MERGE *db_mergealloc(CLUSTER *cluster)
3817 {
3818 REGISTER MERGE *merge;
3819
3820 merge = NOMERGE;
3821 if (db_multiprocessing) emutexlock(db_polymergemutex);
3822 if (db_mergefree != NOMERGE)
3823 {
3824 merge = db_mergefree;
3825 db_mergefree = db_mergefree->nextmerge;
3826 }
3827 if (db_multiprocessing) emutexunlock(db_polymergemutex);
3828 if (merge == NOMERGE)
3829 {
3830 merge = (MERGE *)emalloc(sizeof (MERGE), cluster);
3831 if (merge == 0) return(NOMERGE);
3832 merge->clus = cluster;
3833 merge->newmp = NOMPOLY;
3834 merge->inttotal = 0;
3835 merge->yorder = newintlistobj(cluster);
3836 merge->Oyorder = newintlistobj(cluster);
3837 merge->queue = newintlistobj(cluster);
3838 merge->Oqueue = newintlistobj(cluster);
3839 merge->ylist = newintlistobj(cluster);
3840 }
3841 return(merge);
3842 }
3843
3844 /*
3845 * Helper routine to allocate a new polygon.
3846 * Returns NOMPOLY on error.
3847 */
db_mergeallocpoly(MERGE * merge)3848 MPOLY *db_mergeallocpoly(MERGE *merge)
3849 {
3850 REGISTER MPOLY *mp;
3851
3852 mp = NOMPOLY;
3853 if (db_multiprocessing) emutexlock(db_polymergemutex);
3854 if (db_mpolyfree != NOMPOLY)
3855 {
3856 mp = db_mpolyfree;
3857 db_mpolyfree = mp->nextmpoly;
3858 }
3859 if (db_multiprocessing) emutexunlock(db_polymergemutex);
3860
3861 if (mp == NOMPOLY)
3862 {
3863 mp = (MPOLY *)emalloc(sizeof (MPOLY), merge->clus);
3864 if (mp == 0) return(NOMPOLY);
3865 mp->limit = 0;
3866 }
3867 mp->count = 0;
3868 return(mp);
3869 }
3870
3871 /*
3872 * Helper routine to free polygon "mp".
3873 */
db_mergefreepoly(MPOLY * mp)3874 void db_mergefreepoly(MPOLY *mp)
3875 {
3876 if (db_multiprocessing) emutexlock(db_polymergemutex);
3877 mp->nextmpoly = db_mpolyfree;
3878 db_mpolyfree = mp;
3879 if (db_multiprocessing) emutexunlock(db_polymergemutex);
3880 }
3881