1 /*!
2 * \file src/find.c
3 *
4 * \brief Routines to find connections between pins, vias, lines ...
5 *
6 * Short description:\n
7 * <ul>
8 * <li> Lists for pins and vias, lines, arcs, pads and for polygons are
9 * created.\n
10 * Every object that has to be checked is added to its list.\n
11 * Coarse searching is accomplished with the data rtrees.</li>
12 * <li> There's no 'speed-up' mechanism for polygons because they are
13 * not used as often as other objects.</li>
14 * <li> The maximum distance between line and pin ... would depend on
15 * the angle between them. To speed up computation the limit is set
16 * to one half of the thickness of the objects (cause of square
17 * pins).</li>
18 * </ul>
19 *
20 * PV: means pin or via (objects that connect layers).\n
21 * LO: all non PV objects (layer objects like lines, arcs, polygons,
22 * pads).
23 *
24 * <ol>
25 * <li> First, the LO or PV at the given coordinates is looked
26 * up.</li>
27 * <li> All LO connections to that PV are looked up next.</li>
28 * <li> Lookup of all LOs connected to LOs from (2).\n
29 * This step is repeated until no more new connections are found.</li>
30 * <li> Lookup all PVs connected to the LOs from (2) and (3).</li>
31 * <li> Start again with (1) for all new PVs from (4).</li>
32 * </ol>
33 *
34 * Intersection of line <--> circle:\n
35 * <ul>
36 * <li> Calculate the signed distance from the line to the center,
37 * return false if abs(distance) > R.</li>
38 * <li> Get the distance from the line <--> distancevector intersection
39 * to (X1,Y1) in range [0,1], return true if 0 <= distance <= 1.</li>
40 * <li> Depending on (r > 1.0 or r < 0.0) check the distance of X2,Y2 or
41 * X1,Y1 to X,Y.</li>
42 * </ul>
43 *
44 * Intersection of line <--> line:\n
45 * <ul>
46 * <li> See the description of 'LineLineIntersect()'.</li>
47 * </ul>
48 *
49 * <hr>
50 *
51 * <h1><b>Copyright.</b></h1>\n
52 *
53 * PCB, interactive printed circuit board design
54 *
55 * Copyright (C) 1994,1995,1996, 2005 Thomas Nau
56 *
57 * This program is free software; you can redistribute it and/or modify
58 * it under the terms of the GNU General Public License as published by
59 * the Free Software Foundation; either version 2 of the License, or
60 * (at your option) any later version.
61 *
62 * This program is distributed in the hope that it will be useful,
63 * but WITHOUT ANY WARRANTY; without even the implied warranty of
64 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
65 * GNU General Public License for more details.
66 *
67 * You should have received a copy of the GNU General Public License
68 * along with this program; if not, write to the Free Software
69 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
70 *
71 * Contact addresses for paper mail and Email:
72 * Thomas Nau, Schlehenweg 15, 88471 Baustetten, Germany
73 * Thomas.Nau@rz.uni-ulm.de
74 */
75
76 #ifdef HAVE_CONFIG_H
77 #include "config.h"
78 #endif
79
80 #include <setjmp.h>
81 #include <assert.h>
82
83 #include "global.h"
84
85 #include "data.h"
86 #include "draw.h"
87 #include "drc/drc.h"
88 #include "error.h"
89 #include "find.h"
90 #include "flags.h"
91 #include "misc.h"
92 #include "rtree.h"
93 #include "polygon.h"
94 #include "pcb-printf.h"
95 #include "search.h"
96 #include "set.h"
97 #include "undo.h"
98 #include "rats.h"
99
100 #ifdef HAVE_LIBDMALLOC
101 #include <dmalloc.h>
102 #endif
103
104 #undef DEBUG
105
106 /* ---------------------------------------------------------------------------
107 * some local macros
108 */
109
110 #define SEPARATE(FP) \
111 { \
112 int i; \
113 fputc('#', (FP)); \
114 for (i = Settings.CharPerLine; i; i--) \
115 fputc('=', (FP)); \
116 fputc('\n', (FP)); \
117 }
118
119 /* ----------------------------------------------------------------------- *
120 *
121 * Global State
122 *
123 * ----------------------------------------------------------------------- */
124
125 /* Bloat is used to change the size of objects before checking for overlaps.
126 * This is used in the DRC check to detect things that are too close, or
127 * don't overlap enough.*/
128 static Coord Bloat = 0;
129
130 /*!< Whether to stop if finding something not found.
131 *
132 * Ultimately, this global state variable needs to disappear, along with the calls to set thing 1
133 * and thing 2.
134 */
135 static bool drc = false;
136
137 /* ---------------------------------------------------------------------------
138 * some local prototypes
139 */
140 static bool LookupLOConnectionsToLine (LineType *, Cardinal, int, bool, bool);
141 static bool LookupLOConnectionsToPad (PadType *, Cardinal, int, bool);
142 static bool LookupLOConnectionsToPolygon (PolygonType *, Cardinal, int, bool);
143 static bool LookupLOConnectionsToArc (ArcType *, Cardinal, int, bool);
144 static bool LookupLOConnectionsToRatEnd (PointType *, Cardinal, int);
145 static bool PrepareNextLoop (FILE *);
146 static void DrawNewConnections (void);
147
148
149 /* ----------------------------------------------------------------------- *
150 *
151 * Object Lists and Function Stuff
152 *
153 * ----------------------------------------------------------------------- */
154
155 #define LIST_ENTRY(list,I) (((AnyObjectType **)list->Data)[(I)])
156 #define PADLIST_ENTRY(L,I) (((PadType **)PadList[(L)].Data)[(I)])
157 #define LINELIST_ENTRY(L,I) (((LineType **)LineList[(L)].Data)[(I)])
158 #define ARCLIST_ENTRY(L,I) (((ArcType **)ArcList[(L)].Data)[(I)])
159 #define RATLIST_ENTRY(I) (((RatType **)RatList.Data)[(I)])
160 #define POLYGONLIST_ENTRY(L,I) (((PolygonType **)PolygonList[(L)].Data)[(I)])
161 #define PVLIST_ENTRY(I) (((PinType **)PVList.Data)[(I)])
162
163 /*!
164 * \brief Some local types.
165 *
166 * The two 'dummy' structs for PVs and Pads are necessary for creating
167 * connection lists which include the element's name.
168 */
169 typedef struct
170 {
171 void **Data; /*!< Pointer to index data. */
172 Cardinal Location, /*!< Currently used position. */
173 DrawLocation, Number, /*!< Number of objects in list. */
174 Size;
175 } ListType;
176
177 static Cardinal TotalP, TotalV;
178 static ListType LineList[MAX_LAYER], /*!< List of objects to. */
179 PolygonList[MAX_LAYER], ArcList[MAX_LAYER], PadList[2], RatList, PVList;
180
181 /*
182 * Add an object to the specified list.
183 *
184 * Returning true will (always?) abort the algorithm, false will allow it to
185 * continue.
186 *
187 */
188 static bool
add_object_to_list(ListType * list,int type,void * ptr1,void * ptr2,void * ptr3,int flag)189 add_object_to_list (ListType *list, int type, void *ptr1, void *ptr2, void *ptr3, int flag)
190 {
191 AnyObjectType *object = (AnyObjectType *)ptr2;
192
193 /* Set the appropriate flag to indicate the object appears in one of the
194 * lists. This is how we later compare runs.
195 */
196 AddObjectToFlagUndoList (type, ptr1, ptr2, ptr3);
197 SET_FLAG (flag, object);
198
199 /* Add the object to the list. */
200 LIST_ENTRY (list, list->Number) = object;
201 list->Number++;
202
203 #ifdef DEBUG
204 if (list->Number > list->Size)
205 printf ("add_object_to_list overflow! type=%i num=%d size=%d\n", type, list->Number, list->Size);
206 #endif
207
208 /* if drc is true, then we want to abort the algorithm if a new object is
209 * found. The first time through, the SELECTEDFLAG is set on all objects
210 * that are found. So, if SELECTEDFLAG is set, then the object is already
211 * known.
212 *
213 * TODO: This is not very flexible and requires pre-ordained knowledge of
214 * how to use the SELECTEDFLAG.
215 */
216 if (drc && !TEST_FLAG (SELECTEDFLAG, object))
217 return (SetThing (2, type, ptr1, ptr2, ptr3));
218 return false;
219 }
220
221 static bool
ADD_PV_TO_LIST(PinType * Pin,int flag)222 ADD_PV_TO_LIST (PinType *Pin, int flag)
223 {
224 return add_object_to_list (&PVList, Pin->Element ? PIN_TYPE : VIA_TYPE,
225 Pin->Element ? Pin->Element : Pin, Pin, Pin, flag);
226 }
227
228 static bool
ADD_PAD_TO_LIST(Cardinal L,PadType * Pad,int flag)229 ADD_PAD_TO_LIST (Cardinal L, PadType *Pad, int flag)
230 {
231 return add_object_to_list (&PadList[L], PAD_TYPE, Pad->Element, Pad, Pad, flag);
232 }
233
234 static bool
ADD_LINE_TO_LIST(Cardinal L,LineType * Ptr,int flag)235 ADD_LINE_TO_LIST (Cardinal L, LineType *Ptr, int flag)
236 {
237 return add_object_to_list (&LineList[L], LINE_TYPE, LAYER_PTR (L), Ptr, Ptr, flag);
238 }
239
240 static bool
ADD_ARC_TO_LIST(Cardinal L,ArcType * Ptr,int flag)241 ADD_ARC_TO_LIST (Cardinal L, ArcType *Ptr, int flag)
242 {
243 return add_object_to_list (&ArcList[L], ARC_TYPE, LAYER_PTR (L), Ptr, Ptr, flag);
244 }
245
246 static bool
ADD_RAT_TO_LIST(RatType * Ptr,int flag)247 ADD_RAT_TO_LIST (RatType *Ptr, int flag)
248 {
249 return add_object_to_list (&RatList, RATLINE_TYPE, Ptr, Ptr, Ptr, flag);
250 }
251
252 static bool
ADD_POLYGON_TO_LIST(Cardinal L,PolygonType * Ptr,int flag)253 ADD_POLYGON_TO_LIST (Cardinal L, PolygonType *Ptr, int flag)
254 {
255 return add_object_to_list (&PolygonList[L], POLYGON_TYPE, LAYER_PTR (L), Ptr, Ptr, flag);
256 }
257
258 /*!
259 * \brief Checks if all lists of new objects are handled.
260 */
261 static bool
ListsEmpty(bool AndRats)262 ListsEmpty (bool AndRats)
263 {
264 bool empty;
265 int i;
266
267 empty = (PVList.Location >= PVList.Number);
268 if (AndRats)
269 empty = empty && (RatList.Location >= RatList.Number);
270 for (i = 0; i < max_copper_layer && empty; i++)
271 if (!LAYER_PTR (i)->no_drc)
272 empty = empty && LineList[i].Location >= LineList[i].Number
273 && ArcList[i].Location >= ArcList[i].Number
274 && PolygonList[i].Location >= PolygonList[i].Number;
275 return (empty);
276 }
277
278 /*!
279 * \brief Add the starting object to the list of found objects.
280 */
281 /*static*/ bool
ListStart(int type,void * ptr1,void * ptr2,void * ptr3,int flag)282 ListStart (int type, void *ptr1, void *ptr2, void *ptr3, int flag)
283 {
284 DumpList ();
285 switch (type)
286 {
287 case PIN_TYPE:
288 case VIA_TYPE:
289 {
290 if (ADD_PV_TO_LIST ((PinType *) ptr2, flag))
291 return true;
292 break;
293 }
294
295 case RATLINE_TYPE:
296 {
297 if (ADD_RAT_TO_LIST ((RatType *) ptr1, flag))
298 return true;
299 break;
300 }
301
302 case LINE_TYPE:
303 {
304 int layer = GetLayerNumber (PCB->Data,
305 (LayerType *) ptr1);
306
307 if (ADD_LINE_TO_LIST (layer, (LineType *) ptr2, flag))
308 return true;
309 break;
310 }
311
312 case ARC_TYPE:
313 {
314 int layer = GetLayerNumber (PCB->Data,
315 (LayerType *) ptr1);
316
317 if (ADD_ARC_TO_LIST (layer, (ArcType *) ptr2, flag))
318 return true;
319 break;
320 }
321
322 case POLYGON_TYPE:
323 {
324 int layer = GetLayerNumber (PCB->Data,
325 (LayerType *) ptr1);
326
327 if (ADD_POLYGON_TO_LIST (layer, (PolygonType *) ptr2, flag))
328 return true;
329 break;
330 }
331
332 case PAD_TYPE:
333 {
334 PadType *pad = (PadType *) ptr2;
335 if (ADD_PAD_TO_LIST
336 (TEST_FLAG
337 (ONSOLDERFLAG, pad) ? BOTTOM_SIDE : TOP_SIDE, pad, flag))
338 return true;
339 break;
340 }
341 }
342 return (false);
343 }
344
345
346 /*!
347 * \brief Dumps the list contents.
348 */
349 /* static */ void
DumpList(void)350 DumpList (void)
351 {
352 Cardinal i;
353
354 for (i = 0; i < 2; i++)
355 {
356 PadList[i].Number = 0;
357 PadList[i].Location = 0;
358 PadList[i].DrawLocation = 0;
359 }
360
361 PVList.Number = 0;
362 PVList.Location = 0;
363
364 for (i = 0; i < max_copper_layer; i++)
365 {
366 LineList[i].Location = 0;
367 LineList[i].DrawLocation = 0;
368 LineList[i].Number = 0;
369 ArcList[i].Location = 0;
370 ArcList[i].DrawLocation = 0;
371 ArcList[i].Number = 0;
372 PolygonList[i].Location = 0;
373 PolygonList[i].DrawLocation = 0;
374 PolygonList[i].Number = 0;
375 }
376 RatList.Number = 0;
377 RatList.Location = 0;
378 RatList.DrawLocation = 0;
379 }
380
381 /*!
382 * \brief Allocates memory for component related stacks ...
383 *
384 * Initializes index and sorts it by X1 and X2.
385 */
386 static void
InitComponentLookup(void)387 InitComponentLookup (void)
388 {
389 Cardinal NumberOfPads[2];
390 Cardinal i;
391
392 /* initialize pad data; start by counting the total number
393 * on each of the two possible layers
394 */
395 NumberOfPads[TOP_SIDE] = NumberOfPads[BOTTOM_SIDE] = 0;
396 ALLPAD_LOOP (PCB->Data);
397 {
398 if (TEST_FLAG (ONSOLDERFLAG, pad))
399 NumberOfPads[BOTTOM_SIDE]++;
400 else
401 NumberOfPads[TOP_SIDE]++;
402 }
403 ENDALL_LOOP;
404 for (i = 0; i < 2; i++)
405 {
406 /* allocate memory for working list */
407 PadList[i].Data = (void **)calloc (NumberOfPads[i], sizeof (PadType *));
408
409 /* clear some struct members */
410 PadList[i].Location = 0;
411 PadList[i].DrawLocation = 0;
412 PadList[i].Number = 0;
413 PadList[i].Size = NumberOfPads[i];
414 }
415 }
416
417 /*!
418 * \brief Allocates memory for layout related stacks ...
419 *
420 * Initializes index and sorts it by X1 and X2.
421 */
422 static void
InitLayoutLookup(void)423 InitLayoutLookup (void)
424 {
425 Cardinal i;
426
427 /* initialize line arc and polygon data */
428 for (i = 0; i < max_copper_layer; i++)
429 {
430 LayerType *layer = LAYER_PTR (i);
431
432 if (layer->LineN)
433 {
434 /* allocate memory for line pointer lists */
435 LineList[i].Data = (void **)calloc (layer->LineN, sizeof (LineType *));
436 LineList[i].Size = layer->LineN;
437 }
438 if (layer->ArcN)
439 {
440 ArcList[i].Data = (void **)calloc (layer->ArcN, sizeof (ArcType *));
441 ArcList[i].Size = layer->ArcN;
442 }
443
444
445 /* allocate memory for polygon list */
446 if (layer->PolygonN)
447 {
448 PolygonList[i].Data = (void **)calloc (layer->PolygonN, sizeof (PolygonType *));
449 PolygonList[i].Size = layer->PolygonN;
450 }
451
452 /* clear some struct members */
453 LineList[i].Location = 0;
454 LineList[i].DrawLocation = 0;
455 LineList[i].Number = 0;
456 ArcList[i].Location = 0;
457 ArcList[i].DrawLocation = 0;
458 ArcList[i].Number = 0;
459 PolygonList[i].Location = 0;
460 PolygonList[i].DrawLocation = 0;
461 PolygonList[i].Number = 0;
462 }
463
464 if (PCB->Data->pin_tree)
465 TotalP = PCB->Data->pin_tree->size;
466 else
467 TotalP = 0;
468 if (PCB->Data->via_tree)
469 TotalV = PCB->Data->via_tree->size;
470 else
471 TotalV = 0;
472 /* allocate memory for 'new PV to check' list and clear struct */
473 PVList.Data = (void **)calloc (TotalP + TotalV, sizeof (PinType *));
474 PVList.Size = TotalP + TotalV;
475 PVList.Location = 0;
476 PVList.DrawLocation = 0;
477 PVList.Number = 0;
478 /* Initialize ratline data */
479 RatList.Data = (void **)calloc (PCB->Data->RatN, sizeof (RatType *));
480 RatList.Size = PCB->Data->RatN;
481 RatList.Location = 0;
482 RatList.DrawLocation = 0;
483 RatList.Number = 0;
484 }
485
486 void
InitConnectionLookup(void)487 InitConnectionLookup (void)
488 {
489 InitComponentLookup ();
490 InitLayoutLookup ();
491 }
492
493 /*!
494 * \brief Releases all allocated memory.
495 */
496 static void
FreeLayoutLookupMemory(void)497 FreeLayoutLookupMemory (void)
498 {
499 Cardinal i;
500
501 for (i = 0; i < max_copper_layer; i++)
502 {
503 free (LineList[i].Data);
504 LineList[i].Data = NULL;
505 free (ArcList[i].Data);
506 ArcList[i].Data = NULL;
507 free (PolygonList[i].Data);
508 PolygonList[i].Data = NULL;
509 }
510 free (PVList.Data);
511 PVList.Data = NULL;
512 free (RatList.Data);
513 RatList.Data = NULL;
514 }
515
516
517 static void
FreeComponentLookupMemory(void)518 FreeComponentLookupMemory (void)
519 {
520 free (PadList[0].Data);
521 PadList[0].Data = NULL;
522 free (PadList[1].Data);
523 PadList[1].Data = NULL;
524 }
525
526 void
FreeConnectionLookupMemory(void)527 FreeConnectionLookupMemory (void)
528 {
529 FreeComponentLookupMemory ();
530 FreeLayoutLookupMemory ();
531 }
532
533 /* ----------------------------------------------------------------------- *
534 *
535 * Geometry Stuff
536 *
537 * ----------------------------------------------------------------------- */
538
539 #define IS_PV_ON_RAT(PV, Rat) \
540 (IsPointOnLineEnd((PV)->X,(PV)->Y, (Rat)))
541
542 #define IS_PV_ON_ARC(PV, Arc) \
543 (TEST_FLAG(SQUAREFLAG, (PV)) ? \
544 IsArcInRectangle( \
545 (PV)->X -MAX(((PV)->Thickness+1)/2,0), (PV)->Y -MAX(((PV)->Thickness+1)/2,0), \
546 (PV)->X +MAX(((PV)->Thickness+1)/2,0), (PV)->Y +MAX(((PV)->Thickness+1)/2,0), \
547 (Arc)) : \
548 IsPointOnArc((PV)->X,(PV)->Y,MAX((PV)->Thickness/2.0 + Bloat,0.0), (Arc)))
549
550 #define IS_PV_ON_PAD(PV,Pad) \
551 ( IsPointInPad((PV)->X, (PV)->Y, MAX((PV)->Thickness/2 +Bloat,0), (Pad)))
552
553
554 static bool IsRatPointOnLineEnd (PointType *, LineType *);
555 static bool ArcArcIntersect (ArcType *, ArcType *);
556 /*!
557 * \brief.
558 *
559 * Some of the 'pad' routines are the same as for lines because the 'pad'
560 * struct starts with a line struct. See global.h for details.
561 */
562 bool
LinePadIntersect(LineType * Line,PadType * Pad)563 LinePadIntersect (LineType *Line, PadType *Pad)
564 {
565 return LineLineIntersect ((Line), (LineType *)Pad);
566 }
567
568 bool
ArcPadIntersect(ArcType * Arc,PadType * Pad)569 ArcPadIntersect (ArcType *Arc, PadType *Pad)
570 {
571 return LineArcIntersect ((LineType *) (Pad), (Arc));
572 }
573
574
575 static BoxType
expand_bounds(BoxType * box_in)576 expand_bounds (BoxType *box_in)
577 {
578 BoxType box_out = *box_in;
579
580 if (Bloat > 0)
581 {
582 box_out.X1 -= Bloat;
583 box_out.X2 += Bloat;
584 box_out.Y1 -= Bloat;
585 box_out.Y2 += Bloat;
586 }
587
588 return box_out;
589 }
590
591 bool
PinLineIntersect(PinType * PV,LineType * Line)592 PinLineIntersect (PinType *PV, LineType *Line)
593 {
594 /* IsLineInRectangle already has Bloat factor */
595 return TEST_FLAG (SQUAREFLAG,
596 PV) ? IsLineInRectangle (PV->X - (PIN_SIZE (PV) + 1) / 2,
597 PV->Y - (PIN_SIZE (PV) + 1) / 2,
598 PV->X + (PIN_SIZE (PV) + 1) / 2,
599 PV->Y + (PIN_SIZE (PV) + 1) / 2,
600 Line) : IsPointInPad (PV->X,
601 PV->Y,
602 MAX (PIN_SIZE (PV)
603 /
604 2.0 +
605 Bloat,
606 0.0),
607 (PadType *)Line);
608 }
609
610 bool
BoxBoxIntersection(BoxType * b1,BoxType * b2)611 BoxBoxIntersection (BoxType *b1, BoxType *b2)
612 {
613 if (b2->X2 < b1->X1 || b2->X1 > b1->X2)
614 return false;
615 if (b2->Y2 < b1->Y1 || b2->Y1 > b1->Y2)
616 return false;
617 return true;
618 }
619
620 static bool
PadPadIntersect(PadType * p1,PadType * p2)621 PadPadIntersect (PadType *p1, PadType *p2)
622 {
623 return LinePadIntersect ((LineType *) p1, p2);
624 }
625
626 static inline bool
PV_TOUCH_PV(PinType * PV1,PinType * PV2)627 PV_TOUCH_PV (PinType *PV1, PinType *PV2)
628 {
629 double t1, t2;
630 BoxType b1, b2;
631
632 t1 = MAX (PV1->Thickness / 2.0 + Bloat, 0);
633 t2 = MAX (PV2->Thickness / 2.0 + Bloat, 0);
634 if (IsPointOnPin (PV1->X, PV1->Y, t1, PV2)
635 || IsPointOnPin (PV2->X, PV2->Y, t2, PV1))
636 return true;
637 if (!TEST_FLAG (SQUAREFLAG, PV1) || !TEST_FLAG (SQUAREFLAG, PV2))
638 return false;
639 /* check for square/square overlap */
640 b1.X1 = PV1->X - t1;
641 b1.X2 = PV1->X + t1;
642 b1.Y1 = PV1->Y - t1;
643 b1.Y2 = PV1->Y + t1;
644 t2 = PV2->Thickness / 2.0;
645 b2.X1 = PV2->X - t2;
646 b2.X2 = PV2->X + t2;
647 b2.Y1 = PV2->Y - t2;
648 b2.Y2 = PV2->Y + t2;
649 return BoxBoxIntersection (&b1, &b2);
650 }
651
652 /*!
653 * \brief Reduce arc start angle and delta to 0..360.
654 */
655 static void
normalize_angles(Angle * sa,Angle * d)656 normalize_angles (Angle *sa, Angle *d)
657 {
658 if (*d < 0)
659 {
660 *sa += *d;
661 *d = - *d;
662 }
663 if (*d > 360) /* full circle */
664 *d = 360;
665 *sa = NormalizeAngle (*sa);
666 }
667
668 static int
radius_crosses_arc(double x,double y,ArcType * arc)669 radius_crosses_arc (double x, double y, ArcType *arc)
670 {
671 double alpha = atan2 (y - arc->Y, -x + arc->X) * RAD_TO_DEG;
672 Angle sa = arc->StartAngle, d = arc->Delta;
673
674 normalize_angles (&sa, &d);
675 if (alpha < 0)
676 alpha += 360;
677 if (sa <= alpha)
678 return (sa + d) >= alpha;
679 return (sa + d - 360) >= alpha;
680 }
681
682 static void
get_arc_ends(Coord * box,ArcType * arc)683 get_arc_ends (Coord *box, ArcType *arc)
684 {
685 box[0] = arc->X - arc->Width * cos (M180 * arc->StartAngle);
686 box[1] = arc->Y + arc->Height * sin (M180 * arc->StartAngle);
687 box[2] = arc->X - arc->Width * cos (M180 * (arc->StartAngle + arc->Delta));
688 box[3] = arc->Y + arc->Height * sin (M180 * (arc->StartAngle + arc->Delta));
689 }
690
691 /*!
692 * \brief Check if two arcs intersect.
693 *
694 * First we check for circle intersections,
695 * then find the actual points of intersection
696 * and test them to see if they are on arcs.
697 *
698 * Consider a, the distance from the center of arc 1
699 * to the point perpendicular to the intersecting points.
700 *
701 * \ta = (r1^2 - r2^2 + l^2)/(2l)
702 *
703 * The perpendicular distance to the point of intersection
704 * is then:
705 *
706 * \td = sqrt(r1^2 - a^2)
707 *
708 * The points of intersection would then be:
709 *
710 * \tx = X1 + a/l dx +- d/l dy
711 *
712 * \ty = Y1 + a/l dy -+ d/l dx
713 *
714 * Where dx = X2 - X1 and dy = Y2 - Y1.
715 */
716 static bool
ArcArcIntersect(ArcType * Arc1,ArcType * Arc2)717 ArcArcIntersect (ArcType *Arc1, ArcType *Arc2)
718 {
719 double x, y, dx, dy, r1, r2, a, d, l, t, t1, t2, dl;
720 Coord pdx, pdy;
721 Coord box[8];
722
723 t = MAX (0.5 * Arc1->Thickness + Bloat, 0);
724 t2 = 0.5 * Arc2->Thickness;
725 t1 = MAX (t2 + Bloat, 0);
726
727 /* too thin arc */
728 if (t < 0 || t1 < 0)
729 return false;
730
731 /* try the end points first */
732 get_arc_ends (&box[0], Arc1);
733 get_arc_ends (&box[4], Arc2);
734 if (IsPointOnArc (box[0], box[1], t, Arc2)
735 || IsPointOnArc (box[2], box[3], t, Arc2)
736 || IsPointOnArc (box[4], box[5], t, Arc1)
737 || IsPointOnArc (box[6], box[7], t, Arc1))
738 return true;
739
740 pdx = Arc2->X - Arc1->X;
741 pdy = Arc2->Y - Arc1->Y;
742 dl = Distance (Arc1->X, Arc1->Y, Arc2->X, Arc2->Y);
743 /* concentric arcs, simpler intersection conditions */
744 if (dl < 0.5)
745 {
746 if ((Arc1->Width - t >= Arc2->Width - t2
747 && Arc1->Width - t <= Arc2->Width + t2)
748 || (Arc1->Width + t >= Arc2->Width - t2
749 && Arc1->Width + t <= Arc2->Width + t2))
750 {
751 Angle sa1 = Arc1->StartAngle, d1 = Arc1->Delta;
752 Angle sa2 = Arc2->StartAngle, d2 = Arc2->Delta;
753 /* NB the endpoints have already been checked,
754 so we just compare the angles */
755
756 normalize_angles (&sa1, &d1);
757 normalize_angles (&sa2, &d2);
758 /* sa1 == sa2 was caught when checking endpoints */
759 if (sa1 > sa2)
760 if (sa1 < sa2 + d2 || sa1 + d1 - 360 > sa2)
761 return true;
762 if (sa2 > sa1)
763 if (sa2 < sa1 + d1 || sa2 + d2 - 360 > sa1)
764 return true;
765 }
766 return false;
767 }
768 r1 = Arc1->Width;
769 r2 = Arc2->Width;
770 /* arcs centerlines are too far or too near */
771 if (dl > r1 + r2 || dl + r1 < r2 || dl + r2 < r1)
772 {
773 /* check the nearest to the other arc's center point */
774 dx = pdx * r1 / dl;
775 dy = pdy * r1 / dl;
776 if (dl + r1 < r2) /* Arc1 inside Arc2 */
777 {
778 dx = - dx;
779 dy = - dy;
780 }
781
782 if (radius_crosses_arc (Arc1->X + dx, Arc1->Y + dy, Arc1)
783 && IsPointOnArc (Arc1->X + dx, Arc1->Y + dy, t, Arc2))
784 return true;
785
786 dx = - pdx * r2 / dl;
787 dy = - pdy * r2 / dl;
788 if (dl + r2 < r1) /* Arc2 inside Arc1 */
789 {
790 dx = - dx;
791 dy = - dy;
792 }
793
794 if (radius_crosses_arc (Arc2->X + dx, Arc2->Y + dy, Arc2)
795 && IsPointOnArc (Arc2->X + dx, Arc2->Y + dy, t1, Arc1))
796 return true;
797 return false;
798 }
799
800 l = dl * dl;
801 r1 *= r1;
802 r2 *= r2;
803 a = 0.5 * (r1 - r2 + l) / l;
804 r1 = r1 / l;
805 d = r1 - a * a;
806 /* the circles are too far apart to touch or probably just touch:
807 check the nearest point */
808 if (d < 0)
809 d = 0;
810 else
811 d = sqrt (d);
812 x = Arc1->X + a * pdx;
813 y = Arc1->Y + a * pdy;
814 dx = d * pdx;
815 dy = d * pdy;
816 if (radius_crosses_arc (x + dy, y - dx, Arc1)
817 && IsPointOnArc (x + dy, y - dx, t, Arc2))
818 return true;
819 if (radius_crosses_arc (x + dy, y - dx, Arc2)
820 && IsPointOnArc (x + dy, y - dx, t1, Arc1))
821 return true;
822
823 if (radius_crosses_arc (x - dy, y + dx, Arc1)
824 && IsPointOnArc (x - dy, y + dx, t, Arc2))
825 return true;
826 if (radius_crosses_arc (x - dy, y + dx, Arc2)
827 && IsPointOnArc (x - dy, y + dx, t1, Arc1))
828 return true;
829 return false;
830 }
831
832 /*!
833 * \brief Tests if point is same as line end point.
834 */
835 static bool
IsRatPointOnLineEnd(PointType * Point,LineType * Line)836 IsRatPointOnLineEnd (PointType *Point, LineType *Line)
837 {
838 if ((Point->X == Line->Point1.X
839 && Point->Y == Line->Point1.Y)
840 || (Point->X == Line->Point2.X && Point->Y == Line->Point2.Y))
841 return (true);
842 return (false);
843 }
844
845 /*!
846 * \brief Writes vertices of a squared line.
847 */
848 static void
form_slanted_rectangle(PointType p[4],LineType * l)849 form_slanted_rectangle (PointType p[4], LineType *l)
850 {
851 double dwx = 0, dwy = 0;
852 if (l->Point1.Y == l->Point2.Y)
853 dwx = l->Thickness / 2.0;
854 else if (l->Point1.X == l->Point2.X)
855 dwy = l->Thickness / 2.0;
856 else
857 {
858 Coord dX = l->Point2.X - l->Point1.X;
859 Coord dY = l->Point2.Y - l->Point1.Y;
860 double r = Distance (l->Point1.X, l->Point1.Y, l->Point2.X, l->Point2.Y);
861 dwx = l->Thickness / 2.0 / r * dX;
862 dwy = l->Thickness / 2.0 / r * dY;
863 }
864 p[0].X = l->Point1.X - dwx + dwy; p[0].Y = l->Point1.Y - dwy - dwx;
865 p[1].X = l->Point1.X - dwx - dwy; p[1].Y = l->Point1.Y - dwy + dwx;
866 p[2].X = l->Point2.X + dwx - dwy; p[2].Y = l->Point2.Y + dwy + dwx;
867 p[3].X = l->Point2.X + dwx + dwy; p[3].Y = l->Point2.Y + dwy - dwx;
868 }
869
870 /*!
871 * \brief Checks if two lines intersect.
872 *
873 * <pre>
874 * From news FAQ:
875 *
876 * Let A,B,C,D be 2-space position vectors.
877 *
878 * Then the directed line segments AB & CD are given by:
879 *
880 * AB=A+r(B-A), r in [0,1]
881 *
882 * CD=C+s(D-C), s in [0,1]
883 *
884 * If AB & CD intersect, then
885 *
886 * A+r(B-A)=C+s(D-C), or
887 *
888 * XA+r(XB-XA)=XC+s*(XD-XC)
889 *
890 * YA+r(YB-YA)=YC+s(YD-YC) for some r,s in [0,1]
891 *
892 * Solving the above for r and s yields
893 *
894 * (YA-YC)(XD-XC)-(XA-XC)(YD-YC)
895 * r = ----------------------------- (eqn 1)
896 * (XB-XA)(YD-YC)-(YB-YA)(XD-XC)
897 *
898 * (YA-YC)(XB-XA)-(XA-XC)(YB-YA)
899 * s = ----------------------------- (eqn 2)
900 * (XB-XA)(YD-YC)-(YB-YA)(XD-XC)
901 *
902 * Let I be the position vector of the intersection point, then:
903 *
904 * I=A+r(B-A) or
905 *
906 * XI=XA+r(XB-XA)
907 *
908 * YI=YA+r(YB-YA)
909 *
910 * By examining the values of r & s, you can also determine some
911 * other limiting conditions:
912 *
913 * If 0<=r<=1 & 0<=s<=1, intersection exists
914 *
915 * r<0 or r>1 or s<0 or s>1 line segments do not intersect
916 *
917 * If the denominator in eqn 1 is zero, AB & CD are parallel
918 *
919 * If the numerator in eqn 1 is also zero, AB & CD are coincident
920 *
921 * If the intersection point of the 2 lines are needed (lines in this
922 * context mean infinite lines) regardless whether the two line
923 * segments intersect, then
924 *
925 * If r>1, I is located on extension of AB
926 * If r<0, I is located on extension of BA
927 * If s>1, I is located on extension of CD
928 * If s<0, I is located on extension of DC
929 *
930 * Also note that the denominators of eqn 1 & 2 are identical.
931 * </pre>
932 */
933 bool
LineLineIntersect(LineType * Line1,LineType * Line2)934 LineLineIntersect (LineType *Line1, LineType *Line2)
935 {
936 double s, r;
937 double line1_dx, line1_dy, line2_dx, line2_dy,
938 point1_dx, point1_dy;
939 if (TEST_FLAG (SQUAREFLAG, Line1))/* pretty reckless recursion */
940 {
941 PointType p[4];
942 form_slanted_rectangle (p, Line1);
943 return IsLineInQuadrangle (p, Line2);
944 }
945 /* here come only round Line1 because IsLineInQuadrangle()
946 calls LineLineIntersect() with first argument rounded*/
947 if (TEST_FLAG (SQUAREFLAG, Line2))
948 {
949 PointType p[4];
950 form_slanted_rectangle (p, Line2);
951 return IsLineInQuadrangle (p, Line1);
952 }
953 /* now all lines are round */
954
955 /* Check endpoints: this provides a quick exit, catches
956 * cases where the "real" lines don't intersect but the
957 * thick lines touch, and ensures that the dx/dy business
958 * below does not cause a divide-by-zero. */
959 if (IsPointInPad (Line2->Point1.X, Line2->Point1.Y,
960 MAX (Line2->Thickness / 2 + Bloat, 0),
961 (PadType *) Line1)
962 || IsPointInPad (Line2->Point2.X, Line2->Point2.Y,
963 MAX (Line2->Thickness / 2 + Bloat, 0),
964 (PadType *) Line1)
965 || IsPointInPad (Line1->Point1.X, Line1->Point1.Y,
966 MAX (Line1->Thickness / 2 + Bloat, 0),
967 (PadType *) Line2)
968 || IsPointInPad (Line1->Point2.X, Line1->Point2.Y,
969 MAX (Line1->Thickness / 2 + Bloat, 0),
970 (PadType *) Line2))
971 return true;
972
973 /* setup some constants */
974 line1_dx = Line1->Point2.X - Line1->Point1.X;
975 line1_dy = Line1->Point2.Y - Line1->Point1.Y;
976 line2_dx = Line2->Point2.X - Line2->Point1.X;
977 line2_dy = Line2->Point2.Y - Line2->Point1.Y;
978 point1_dx = Line1->Point1.X - Line2->Point1.X;
979 point1_dy = Line1->Point1.Y - Line2->Point1.Y;
980
981 /* If either line is a point, we have failed already, since the
982 * endpoint check above will have caught an "intersection". */
983 if ((line1_dx == 0 && line1_dy == 0)
984 || (line2_dx == 0 && line2_dy == 0))
985 return false;
986
987 /* set s to cross product of Line1 and the line
988 * Line1.Point1--Line2.Point1 (as vectors) */
989 s = point1_dy * line1_dx - point1_dx * line1_dy;
990
991 /* set r to cross product of both lines (as vectors) */
992 r = line1_dx * line2_dy - line1_dy * line2_dx;
993
994 /* No cross product means parallel lines, or maybe Line2 is
995 * zero-length. In either case, since we did a bounding-box
996 * check before getting here, the above IsPointInPad() checks
997 * will have caught any intersections. */
998 if (r == 0.0)
999 return false;
1000
1001 s /= r;
1002 r = (point1_dy * line2_dx - point1_dx * line2_dy) / r;
1003
1004 /* intersection is at least on AB */
1005 if (r >= 0.0 && r <= 1.0)
1006 return (s >= 0.0 && s <= 1.0);
1007
1008 /* intersection is at least on CD */
1009 /* [removed this case since it always returns false --asp] */
1010 return false;
1011 }
1012
1013 /*!
1014 * \brief Check for line intersection with an arc.
1015 *
1016 * Mostly this is like the circle/line intersection
1017 * found in IsPointOnLine (search.c) see the detailed
1018 * discussion for the basics there.
1019 *
1020 * Some definitions (as in search.c:IsPointOnLine):
1021 *
1022 * Q - The point on the line segment where a line perpendicular to the
1023 * segment would intersect the center of the circle.
1024 *
1025 * D1 - The distance along the line from the first point to Q.
1026 *
1027 * D2 - The perpendicular distance from Q to the center of the circle.
1028 *
1029 * L - The length of the line segment.
1030 *
1031 * delta - the distance along the line segment from Q to the location where
1032 * the circle intersects the line.
1033 *
1034 * Since this is only an arc, not a full circle we need
1035 * to find the actual points of intersection with the
1036 * circle, and see if they are on the arc. To do this, we translate along the
1037 * line from the point Q plus or minus delta:
1038 *
1039 * delta = sqrt(Radius^2 - D2^2)
1040 *
1041 * The coordinates of the points of intersection can be calculated using
1042 * similar triangles:
1043 *
1044 * Px = X1 + (D1 +/- delta)(X2 - X1) / L
1045 * Py = Y1 + (D1 +/- delta)(Y2 - Y1) / L
1046 *
1047 *
1048 * The math below makes some substitutions:
1049 *
1050 * r = D1
1051 * d = D2 * L
1052 * r2 = delta = sqrt(Radius^2 * L^2 - d^2) / L^2
1053 *
1054 * Some older comments...
1055 *
1056 * <pre>
1057 * The projection is now of the form:
1058 *
1059 * Px = X1 + (r +- r2)(X2 - X1)
1060 * Py = Y1 + (r +- r2)(Y2 - Y1)
1061 * </pre>
1062 *
1063 * Where r2 sqrt(Radius^2 l^2 - d^2)/l^2
1064 * note that this is the variable d, not the symbol d described in
1065 * IsPointOnLine (variable d = symbol d * l).
1066 *
1067 * The end points are hell so they are checked individually.
1068 */
1069 bool
LineArcIntersect(LineType * Line,ArcType * Arc)1070 LineArcIntersect (LineType *Line, ArcType *Arc)
1071 {
1072 double dx, dy, dx1, dy1, l, d, r, r2, Radius;
1073 BoxType *box;
1074
1075 dx = Line->Point2.X - Line->Point1.X;
1076 dy = Line->Point2.Y - Line->Point1.Y;
1077 dx1 = Line->Point1.X - Arc->X;
1078 dy1 = Line->Point1.Y - Arc->Y;
1079
1080 /* length of the line, squared */
1081 l = dx * dx + dy * dy;
1082
1083 /* minimum distance from the line to the center of the arc, times the
1084 * length of the line (D2*L from search.c equations) */
1085 d = dx * dy1 - dy * dx1;
1086 d *= d; /* (D2*L)^2 */
1087
1088 /* Check the outer edge of the arc first.
1089 * Note: I'm not not entirely sure that this is the right way to
1090 * incorporate the line thickness...
1091 * */
1092 Radius =
1093 Arc->Width + MAX (0.5 * (Arc->Thickness + Line->Thickness) + Bloat, 0.0);
1094 Radius *= Radius;
1095
1096 /* If the argument to the square root is negative, then the arc is too far
1097 * away to be able to intersect the line.
1098 * */
1099 r2 = Radius * l - d;
1100 if (r2 < 0)
1101 return (false);
1102
1103 /* check the ends of the line in case the projected point */
1104 /* of intersection is beyond the line end */
1105 if (IsPointOnArc
1106 (Line->Point1.X, Line->Point1.Y,
1107 MAX (0.5 * Line->Thickness + Bloat, 0.0), Arc))
1108 return (true);
1109 if (IsPointOnArc
1110 (Line->Point2.X, Line->Point2.Y,
1111 MAX (0.5 * Line->Thickness + Bloat, 0.0), Arc))
1112 return (true);
1113
1114 /* Zero length lines have some thickness, so, could still intersect.
1115 * However, they would have been caught by the previous tests. So, at this
1116 * point zero length means no intersection.
1117 * */
1118 if (l == 0.0)
1119 return (false);
1120
1121 /* Okay, fine... I guess we have to do some math.
1122 * */
1123 r2 = sqrt (r2); /* delta * L^2 */
1124 Radius = -(dx * dx1 + dy * dy1); /* Actually D1*L */
1125 r = (Radius + r2) / l; /* (D1*L + delta*L^2) / L = (D1 + delta*L) */
1126
1127 /* r is now (supposed to be) the distance from the first point to the
1128 * further intersection, normalized to the length of the segment.
1129 * If r < 0, we're behind the segment, and if r > 1 we're beyond the segment.
1130 * */
1131 if (r >= 0 && r <= 1
1132 && IsPointOnArc (Line->Point1.X + r * dx,
1133 Line->Point1.Y + r * dy,
1134 MAX (0.5 * Line->Thickness + Bloat, 0.0), Arc))
1135 return (true);
1136
1137 /* Now check the other side.
1138 * */
1139 r = (Radius - r2) / l;
1140 if (r >= 0 && r <= 1
1141 && IsPointOnArc (Line->Point1.X + r * dx,
1142 Line->Point1.Y + r * dy,
1143 MAX (0.5 * Line->Thickness + Bloat, 0.0), Arc))
1144 return (true);
1145
1146 /* check arc end points */
1147 box = GetArcEnds (Arc);
1148 if (IsPointInPad (box->X1, box->Y1, Arc->Thickness * 0.5 + Bloat, (PadType *)Line))
1149 return true;
1150 if (IsPointInPad (box->X2, box->Y2, Arc->Thickness * 0.5 + Bloat, (PadType *)Line))
1151 return true;
1152 return false;
1153 }
1154
1155 /*!
1156 * \brief Checks if an arc has a connection to a polygon.
1157 *
1158 * - first check if the arc can intersect with the polygon by
1159 * evaluating the bounding boxes.
1160 * - check the two end points of the arc. If none of them matches
1161 * - check all segments of the polygon against the arc.
1162 */
1163 /*static*/ bool
IsArcInPolygon(ArcType * Arc,PolygonType * Polygon)1164 IsArcInPolygon (ArcType *Arc, PolygonType *Polygon)
1165 {
1166 BoxType *Box = (BoxType *) Arc;
1167
1168 /* arcs with clearance never touch polys */
1169 if (TEST_FLAG (CLEARPOLYFLAG, Polygon) && TEST_FLAG (CLEARLINEFLAG, Arc))
1170 return false;
1171 if (!Polygon->Clipped)
1172 return false;
1173 if (Box->X1 <= Polygon->Clipped->contours->xmax + Bloat
1174 && Box->X2 >= Polygon->Clipped->contours->xmin - Bloat
1175 && Box->Y1 <= Polygon->Clipped->contours->ymax + Bloat
1176 && Box->Y2 >= Polygon->Clipped->contours->ymin - Bloat)
1177 {
1178 POLYAREA *ap;
1179
1180 if (!(ap = ArcPoly (Arc, Arc->Thickness + Bloat)))
1181 return false; /* error */
1182 return isects (ap, Polygon, true);
1183 }
1184 return false;
1185 }
1186
1187 /*!
1188 * \brief Checks if a line has a connection to a polygon.
1189 *
1190 * - first check if the line can intersect with the polygon by
1191 * evaluating the bounding boxes
1192 * - check the two end points of the line. If none of them matches
1193 * - check all segments of the polygon against the line.
1194 */
1195 /*static*/ bool
IsLineInPolygon(LineType * Line,PolygonType * Polygon)1196 IsLineInPolygon (LineType *Line, PolygonType *Polygon)
1197 {
1198 BoxType *Box = (BoxType *) Line;
1199 POLYAREA *lp;
1200
1201 /* lines with clearance never touch polygons */
1202 if (TEST_FLAG (CLEARPOLYFLAG, Polygon) && TEST_FLAG (CLEARLINEFLAG, Line))
1203 return false;
1204 if (!Polygon->Clipped)
1205 return false;
1206 if (TEST_FLAG(SQUAREFLAG,Line) /* Line has square ends */
1207 && ( Line->Point1.X==Line->Point2.X /* Line is vertical */
1208 || Line->Point1.Y==Line->Point2.Y)) /* Line is horizontal */
1209 {
1210 /* Then a rectangle check will do. */
1211 /* This condition is often the case with the pads of elements. */
1212 Coord wid = (Line->Thickness + Bloat + 1) / 2;
1213 Coord x1, x2, y1, y2;
1214
1215 x1 = MIN (Line->Point1.X, Line->Point2.X) - wid;
1216 y1 = MIN (Line->Point1.Y, Line->Point2.Y) - wid;
1217 x2 = MAX (Line->Point1.X, Line->Point2.X) + wid;
1218 y2 = MAX (Line->Point1.Y, Line->Point2.Y) + wid;
1219 return IsRectangleInPolygon (x1, y1, x2, y2, Polygon);
1220 }
1221 if (Box->X1 <= Polygon->Clipped->contours->xmax + Bloat
1222 && Box->X2 >= Polygon->Clipped->contours->xmin - Bloat
1223 && Box->Y1 <= Polygon->Clipped->contours->ymax + Bloat
1224 && Box->Y2 >= Polygon->Clipped->contours->ymin - Bloat)
1225 {
1226 if (!(lp = LinePoly (Line, Line->Thickness + Bloat)))
1227 return FALSE; /* error */
1228 return isects (lp, Polygon, true);
1229 }
1230 return false;
1231 }
1232
1233 /*!
1234 * \brief Checks if a pad connects to a non-clearing polygon.
1235 *
1236 * The polygon is assumed to already have been proven non-clearing.
1237 */
1238 /*static*/ bool
IsPadInPolygon(PadType * pad,PolygonType * polygon)1239 IsPadInPolygon (PadType *pad, PolygonType *polygon)
1240 {
1241 return IsLineInPolygon ((LineType *) pad, polygon);
1242 }
1243
1244 /*!
1245 * \brief Checks if a polygon has a connection to a second one.
1246 *
1247 * First check all points out of P1 against P2 and vice versa.
1248 * If both fail check all lines of P1 against the ones of P2.
1249 */
1250 /*static*/ bool
IsPolygonInPolygon(PolygonType * P1,PolygonType * P2)1251 IsPolygonInPolygon (PolygonType *P1, PolygonType *P2)
1252 {
1253 if (!P1->Clipped || !P2->Clipped)
1254 return false;
1255 assert (P1->Clipped->contours);
1256 assert (P2->Clipped->contours);
1257
1258 /* first check if both bounding boxes intersect. If not, return quickly */
1259 if (P1->Clipped->contours->xmin - Bloat > P2->Clipped->contours->xmax ||
1260 P1->Clipped->contours->xmax + Bloat < P2->Clipped->contours->xmin ||
1261 P1->Clipped->contours->ymin - Bloat > P2->Clipped->contours->ymax ||
1262 P1->Clipped->contours->ymax + Bloat < P2->Clipped->contours->ymin)
1263 return false;
1264
1265 /* first check un-bloated case */
1266 if (isects (P1->Clipped, P2, false))
1267 return TRUE;
1268
1269 /* now the difficult case of bloated */
1270 if (Bloat > 0)
1271 {
1272 PLINE *c;
1273 for (c = P1->Clipped->contours; c; c = c->next)
1274 {
1275 LineType line;
1276 VNODE *v = &c->head;
1277 if (c->xmin - Bloat <= P2->Clipped->contours->xmax &&
1278 c->xmax + Bloat >= P2->Clipped->contours->xmin &&
1279 c->ymin - Bloat <= P2->Clipped->contours->ymax &&
1280 c->ymax + Bloat >= P2->Clipped->contours->ymin)
1281 {
1282
1283 line.Point1.X = v->point[0];
1284 line.Point1.Y = v->point[1];
1285 line.Thickness = Bloat;
1286 /* Another Bloat is added by IsLineInPolygon, making the correct
1287 * 2x Bloat. Perhaps we should change it there, but doing so
1288 * breaks some other DRC checks which rely on the behaviour
1289 * in IsLineInPolygon.
1290 */
1291 line.Clearance = 0;
1292 line.Flags = NoFlags ();
1293 for (v = v->next; v != &c->head; v = v->next)
1294 {
1295 line.Point2.X = v->point[0];
1296 line.Point2.Y = v->point[1];
1297 SetLineBoundingBox (&line);
1298 if (IsLineInPolygon (&line, P2))
1299 return (true);
1300 line.Point1.X = line.Point2.X;
1301 line.Point1.Y = line.Point2.Y;
1302 }
1303 }
1304 }
1305 }
1306
1307 return (false);
1308 }
1309
1310
1311 /*!
1312 * \brief Checks if a pin connects to a non-clearing polygon.
1313 *
1314 * The polygon is assumed to already have been proven non-clearing.
1315 * The pin/via is assumed to have been checked to intersect the polygon's
1316 * layer.
1317 *
1318 */
1319 /*static*/ bool
IsPinInPolygon(PinType * pin,PolygonType * polygon)1320 IsPinInPolygon (PinType *pin, PolygonType *polygon)
1321 {
1322 double wide = MAX (0.5 * pin->Thickness + Bloat, 0);
1323 if (TEST_FLAG (SQUAREFLAG, pin))
1324 {
1325 Coord x1 = pin->X - (pin->Thickness + 1 + Bloat) / 2;
1326 Coord x2 = pin->X + (pin->Thickness + 1 + Bloat) / 2;
1327 Coord y1 = pin->Y - (pin->Thickness + 1 + Bloat) / 2;
1328 Coord y2 = pin->Y + (pin->Thickness + 1 + Bloat) / 2;
1329 if (IsRectangleInPolygon (x1, y1, x2, y2, polygon))
1330 return true;
1331 }
1332 else if (TEST_FLAG (OCTAGONFLAG, pin))
1333 {
1334 POLYAREA *oct = OctagonPoly (pin->X, pin->Y, pin->Thickness / 2);
1335 if (isects (oct, polygon, true))
1336 return true;
1337 }
1338 else if (IsPointInPolygon (pin->X, pin->Y, wide, polygon))
1339 return true;
1340
1341 return false;
1342 }
1343
1344
1345 /* ----------------------------------------------------------------------- *
1346 *
1347 * Connection Lookup Stuff
1348 *
1349 * ----------------------------------------------------------------------- */
1350
1351
1352 struct pv_info
1353 {
1354 Cardinal layer;
1355 PinType *pv;
1356 int flag;
1357 jmp_buf env;
1358 };
1359
1360 static int
LOCtoPVline_callback(const BoxType * b,void * cl)1361 LOCtoPVline_callback (const BoxType * b, void *cl)
1362 {
1363 LineType *line = (LineType *) b;
1364 struct pv_info *i = (struct pv_info *) cl;
1365
1366 if (!ViaIsOnLayerGroup (i->pv, GetLayerGroupNumberByNumber (i->layer)))
1367 return 0;
1368
1369 if (!TEST_FLAG (i->flag, line) && PinLineIntersect (i->pv, line) &&
1370 !TEST_FLAG (HOLEFLAG, i->pv))
1371 {
1372 if (ADD_LINE_TO_LIST (i->layer, line, i->flag))
1373 longjmp (i->env, 1);
1374 }
1375 return 0;
1376 }
1377
1378 static int
LOCtoPVarc_callback(const BoxType * b,void * cl)1379 LOCtoPVarc_callback (const BoxType * b, void *cl)
1380 {
1381 ArcType *arc = (ArcType *) b;
1382 struct pv_info *i = (struct pv_info *) cl;
1383
1384 if (!ViaIsOnLayerGroup (i->pv, GetLayerGroupNumberByNumber (i->layer)))
1385 return 0;
1386
1387 if (!TEST_FLAG (i->flag, arc) && IS_PV_ON_ARC (i->pv, arc) &&
1388 !TEST_FLAG (HOLEFLAG, i->pv))
1389 {
1390 if (ADD_ARC_TO_LIST (i->layer, arc, i->flag))
1391 longjmp (i->env, 1);
1392 }
1393 return 0;
1394 }
1395
1396 static int
LOCtoPVpad_callback(const BoxType * b,void * cl)1397 LOCtoPVpad_callback (const BoxType * b, void *cl)
1398 {
1399 PadType *pad = (PadType *) b;
1400 struct pv_info *i = (struct pv_info *) cl;
1401
1402 if (!ViaIsOnLayerGroup (i->pv, GetLayerGroupNumberBySide (TEST_FLAG (ONSOLDERFLAG, pad) ? BOTTOM_SIDE : TOP_SIDE)))
1403 return 0;
1404
1405 if (!TEST_FLAG (i->flag, pad) && IS_PV_ON_PAD (i->pv, pad) &&
1406 !TEST_FLAG (HOLEFLAG, i->pv) &&
1407 ADD_PAD_TO_LIST (TEST_FLAG (ONSOLDERFLAG, pad) ? BOTTOM_SIDE :
1408 TOP_SIDE, pad, i->flag))
1409 longjmp (i->env, 1);
1410 return 0;
1411 }
1412
1413 static int
LOCtoPVrat_callback(const BoxType * b,void * cl)1414 LOCtoPVrat_callback (const BoxType * b, void *cl)
1415 {
1416 RatType *rat = (RatType *) b;
1417 struct pv_info *i = (struct pv_info *) cl;
1418
1419 if (!TEST_FLAG (i->flag, rat) && IS_PV_ON_RAT (i->pv, rat) &&
1420 ADD_RAT_TO_LIST (rat, i->flag))
1421 longjmp (i->env, 1);
1422 return 0;
1423 }
1424
1425 static int
LOCtoPVpoly_callback(const BoxType * b,void * cl)1426 LOCtoPVpoly_callback (const BoxType * b, void *cl)
1427 {
1428 PolygonType *polygon = (PolygonType *) b;
1429 struct pv_info *i = (struct pv_info *) cl;
1430
1431 if (!ViaIsOnLayerGroup (i->pv, GetLayerGroupNumberByNumber (i->layer)))
1432 return 0;
1433
1434 /* if the pin doesn't have a therm and polygon is clearing
1435 * then it can't touch due to clearance, so skip the expensive
1436 * test. If it does have a therm, you still need to test
1437 * because it might not be inside the polygon, or it could
1438 * be on an edge such that it doesn't actually touch.
1439 */
1440 if (!TEST_FLAG (i->flag, polygon) && !TEST_FLAG (HOLEFLAG, i->pv)
1441 && (TEST_THERM (i->layer, i->pv)
1442 || !TEST_FLAG (CLEARPOLYFLAG, polygon)
1443 || !i->pv->Clearance)
1444 && IsPinInPolygon(i->pv, polygon)
1445 && ADD_POLYGON_TO_LIST (i->layer, polygon, i->flag))
1446 {
1447 longjmp (i->env, 1);
1448 }
1449 return 0;
1450 }
1451
1452 /*!
1453 * \brief Checks if a PV is connected to LOs, if it is, the LO is added
1454 * to the appropriate list and the 'used' flag is set.
1455 */
1456 static bool
LookupLOConnectionsToPVList(int flag,bool AndRats)1457 LookupLOConnectionsToPVList (int flag, bool AndRats)
1458 {
1459 Cardinal layer_no;
1460 struct pv_info info;
1461
1462 info.flag = flag;
1463
1464 /* loop over all PVs currently on list */
1465 while (PVList.Location < PVList.Number)
1466 {
1467 BoxType search_box;
1468
1469 /* get pointer to data */
1470 info.pv = PVLIST_ENTRY (PVList.Location);
1471 search_box = expand_bounds (&info.pv->BoundingBox);
1472
1473 /* Keep track of what item we started from for the drc. */
1474 if (drc) SetThing(1, info.pv->Element ? PIN_TYPE : VIA_TYPE, /* type */
1475 info.pv->Element ? info.pv->Element : info.pv, /* ptr1 */
1476 info.pv, info.pv); /* ptr2, ptr3 */
1477
1478 /* check pads */
1479 if (setjmp (info.env) == 0)
1480 r_search (PCB->Data->pad_tree, &search_box, NULL,
1481 LOCtoPVpad_callback, &info);
1482 else
1483 return true;
1484
1485 /* now all lines, arcs and polygons of the several layers */
1486 for (layer_no = 0; layer_no < max_copper_layer; layer_no++)
1487 {
1488 LayerType *layer = LAYER_PTR (layer_no);
1489
1490 if (layer->no_drc)
1491 continue;
1492
1493 info.layer = layer_no;
1494
1495 /* add touching lines */
1496 if (setjmp (info.env) == 0)
1497 r_search (layer->line_tree, &search_box,
1498 NULL, LOCtoPVline_callback, &info);
1499 else
1500 return true;
1501 /* add touching arcs */
1502 if (setjmp (info.env) == 0)
1503 r_search (layer->arc_tree, &search_box,
1504 NULL, LOCtoPVarc_callback, &info);
1505 else
1506 return true;
1507 /* check all polygons */
1508 if (setjmp (info.env) == 0)
1509 r_search (layer->polygon_tree, &search_box,
1510 NULL, LOCtoPVpoly_callback, &info);
1511 else
1512 return true;
1513 }
1514 /* Check for rat-lines that may intersect the PV */
1515 if (AndRats)
1516 {
1517 if (setjmp (info.env) == 0)
1518 r_search (PCB->Data->rat_tree, &search_box, NULL,
1519 LOCtoPVrat_callback, &info);
1520 else
1521 return true;
1522 }
1523 PVList.Location++;
1524 }
1525 return false;
1526 }
1527
1528 /*!
1529 * \brief Find all connections between LO at the current list position
1530 * and new LOs.
1531 */
1532 static bool
LookupLOConnectionsToLOList(int flag,bool AndRats)1533 LookupLOConnectionsToLOList (int flag, bool AndRats)
1534 {
1535 bool done;
1536 Cardinal i, group, layer, ratposition,
1537 lineposition[MAX_LAYER],
1538 polyposition[MAX_LAYER], arcposition[MAX_LAYER], padposition[2];
1539
1540 /* copy the current LO list positions; the original data is changed
1541 * by 'LookupPVConnectionsToLOList()' which has to check the same
1542 * list entries plus the new ones
1543 */
1544 for (i = 0; i < max_copper_layer; i++)
1545 {
1546 lineposition[i] = LineList[i].Location;
1547 polyposition[i] = PolygonList[i].Location;
1548 arcposition[i] = ArcList[i].Location;
1549 }
1550 for (i = 0; i < 2; i++)
1551 padposition[i] = PadList[i].Location;
1552 ratposition = RatList.Location;
1553
1554 /* loop over all new LOs in the list; recurse until no
1555 * more new connections in the layergroup were found
1556 */
1557 do
1558 {
1559 Cardinal *position;
1560 if (AndRats)
1561 {
1562 position = &ratposition;
1563 for (; *position < RatList.Number; (*position)++)
1564 {
1565 group = RATLIST_ENTRY (*position)->group1;
1566 if (LookupLOConnectionsToRatEnd
1567 (&(RATLIST_ENTRY (*position)->Point1), group, flag))
1568 return (true);
1569 group = RATLIST_ENTRY (*position)->group2;
1570 if (LookupLOConnectionsToRatEnd
1571 (&(RATLIST_ENTRY (*position)->Point2), group, flag))
1572 return (true);
1573 }
1574 }
1575 /* loop over all layergroups */
1576 for (group = 0; group < max_group; group++)
1577 {
1578 Cardinal entry;
1579
1580 for (entry = 0; entry < PCB->LayerGroups.Number[group]; entry++)
1581 {
1582 layer = PCB->LayerGroups.Entries[group][entry];
1583
1584 /* be aware that the layer number equal max_copper_layer
1585 * and max_copper_layer+1 have a special meaning for pads
1586 */
1587 if (layer < max_copper_layer)
1588 {
1589 LayerType * pLayer = LAYER_PTR(layer);
1590 /* try all new lines */
1591 position = &lineposition[layer];
1592 for (; *position < LineList[layer].Number; (*position)++)
1593 {
1594 LineType * line = LINELIST_ENTRY (layer, *position);
1595 /* Keep track of what item we started from for the drc. */
1596 if (drc) SetThing (1, LINE_TYPE, pLayer, line, line);
1597
1598 if (LookupLOConnectionsToLine (line, group, flag, true, AndRats))
1599 return (true);
1600 }
1601
1602 /* try all new arcs */
1603 position = &arcposition[layer];
1604 for (; *position < ArcList[layer].Number; (*position)++)
1605 {
1606 ArcType * arc = ARCLIST_ENTRY(layer, *position);
1607 /* Keep track of what item we started from for the drc. */
1608 if (drc) SetThing (1, ARC_TYPE, pLayer, arc, arc);
1609 if (LookupLOConnectionsToArc (arc, group, flag, AndRats))
1610 return (true);
1611 }
1612
1613 /* try all new polygons */
1614 position = &polyposition[layer];
1615 for (; *position < PolygonList[layer].Number; (*position)++)
1616 {
1617 PolygonType * poly = POLYGONLIST_ENTRY (layer, *position);
1618 /* Keep track of what item we started from for the drc. */
1619 if (drc) SetThing (1, POLYGON_TYPE, pLayer, poly, poly);
1620 if (LookupLOConnectionsToPolygon (poly, group, flag, AndRats))
1621 return (true);
1622 }
1623 }
1624 else
1625 {
1626 /* try all new pads */
1627 layer -= max_copper_layer;
1628 if (layer > 1)
1629 {
1630 Message (_("bad layer number %d max_copper_layer=%d in find.c\n"),
1631 layer, max_copper_layer);
1632 return false;
1633 }
1634 position = &padposition[layer];
1635 for (; *position < PadList[layer].Number; (*position)++)
1636 {
1637 PadType * pad = PADLIST_ENTRY (layer, *position);
1638 /* Keep track of what item we started from for the drc. */
1639 if (drc) SetThing (1, PAD_TYPE, pad->Element, pad, pad);
1640 if (LookupLOConnectionsToPad (pad, group, flag, AndRats))
1641 return (true);
1642 }
1643 }
1644 }
1645 }
1646
1647 /* check if all lists are done; Later for-loops
1648 * may have changed the prior lists
1649 */
1650 done = !AndRats || ratposition >= RatList.Number;
1651 done = done && padposition[0] >= PadList[0].Number &&
1652 padposition[1] >= PadList[1].Number;
1653 for (layer = 0; layer < max_copper_layer; layer++)
1654 done = done &&
1655 lineposition[layer] >= LineList[layer].Number &&
1656 arcposition[layer] >= ArcList[layer].Number &&
1657 polyposition[layer] >= PolygonList[layer].Number;
1658 } /* do */
1659 while (!done);
1660 return (false);
1661 }
1662
1663 /*
1664 * This function is an r_search callback. It's called to check if a pin or
1665 * via is overlapping with another pin or via.
1666 */
1667 static int
pv_pv_callback(const BoxType * b,void * cl)1668 pv_pv_callback (const BoxType * b, void *cl)
1669 {
1670 /* Cast the object found by the r_search, it's known to be a pin */
1671 PinType *pin = (PinType *) b;
1672 struct pv_info *i = (struct pv_info *) cl;
1673 bool pv_overlap = false;
1674 Cardinal l;
1675
1676 /* If both vias are buried, check if the layers of the found via (pin)
1677 * overlap with the layers of the original via (i->pv).
1678 *
1679 * TODO: Why isn't PinPinIntersect called here?
1680 * TODO: Why aren't we checking the other flags, like we do below?
1681 */
1682 if (VIA_IS_BURIED (pin) && VIA_IS_BURIED (i->pv))
1683 {
1684 for (l = pin->BuriedFrom ; l <= pin->BuriedTo; l++)
1685 {
1686 if (ViaIsOnLayerGroup (i->pv, GetLayerGroupNumberByNumber (l)))
1687 {
1688 pv_overlap = true;
1689 break;
1690 }
1691 }
1692 if (!pv_overlap)
1693 return 0;
1694 }
1695
1696 /* If either of the vias is a thru via, there is potential overlap. */
1697 if (!TEST_FLAG (i->flag, pin) && PV_TOUCH_PV (i->pv, pin))
1698 {
1699 /* If it's only a hole (no copper) then just issue a warning to the
1700 * log, and highlight the pin. It doesn't affect the netlist.
1701 */
1702 if (TEST_FLAG (HOLEFLAG, pin) || TEST_FLAG (HOLEFLAG, i->pv))
1703 {
1704 SET_FLAG (WARNFLAG, pin);
1705 Settings.RatWarn = true;
1706 if (pin->Element)
1707 Message (_("WARNING: Hole too close to pin.\n"));
1708 else
1709 Message (_("WARNING: Hole too close to via.\n"));
1710 }
1711 else if (ADD_PV_TO_LIST (pin, i->flag))
1712 longjmp (i->env, 1);
1713 }
1714 return 0;
1715 }
1716
1717 /*!
1718 * \brief Searches for new PVs that are connected to PVs on the list.
1719 */
1720 static bool
LookupPVConnectionsToPVList(int flag)1721 LookupPVConnectionsToPVList (int flag)
1722 {
1723 Cardinal save_place;
1724 struct pv_info info;
1725
1726 info.flag = flag;
1727
1728 /* loop over all PVs on list */
1729 save_place = PVList.Location;
1730 while (PVList.Location < PVList.Number)
1731 {
1732 BoxType search_box;
1733
1734 /* get pointer to data */
1735 info.pv = PVLIST_ENTRY (PVList.Location);
1736 search_box = expand_bounds ((BoxType *)info.pv);
1737
1738 /* Keep track of what item we started from for the drc. */
1739 if (drc) SetThing(1, info.pv->Element ? PIN_TYPE : VIA_TYPE, /* type */
1740 info.pv->Element ? info.pv->Element : info.pv, /* ptr1 */
1741 info.pv, info.pv); /* ptr2, ptr3 */
1742
1743
1744 if (setjmp (info.env) == 0)
1745 r_search (PCB->Data->via_tree, &search_box, NULL,
1746 pv_pv_callback, &info);
1747 else
1748 return true;
1749 if (setjmp (info.env) == 0)
1750 r_search (PCB->Data->pin_tree, &search_box, NULL,
1751 pv_pv_callback, &info);
1752 else
1753 return true;
1754 PVList.Location++;
1755 }
1756 PVList.Location = save_place;
1757 return (false);
1758 }
1759
1760 struct lo_info
1761 {
1762 Cardinal layer;
1763 LineType *line;
1764 PadType *pad;
1765 ArcType *arc;
1766 PolygonType *polygon;
1767 RatType *rat;
1768 int flag;
1769 jmp_buf env;
1770 };
1771
1772 static int
pv_line_callback(const BoxType * b,void * cl)1773 pv_line_callback (const BoxType * b, void *cl)
1774 {
1775 PinType *pv = (PinType *) b;
1776 struct lo_info *i = (struct lo_info *) cl;
1777
1778 if (!ViaIsOnLayerGroup (pv, GetLayerGroupNumberByNumber (i->layer)))
1779 return 0;
1780
1781 if (!TEST_FLAG (i->flag, pv) && PinLineIntersect (pv, i->line))
1782 {
1783 if (TEST_FLAG (HOLEFLAG, pv))
1784 {
1785 SET_FLAG (WARNFLAG, pv);
1786 Settings.RatWarn = true;
1787 Message (_("WARNING: Hole too close to line.\n"));
1788 }
1789 else if (ADD_PV_TO_LIST (pv, i->flag))
1790 longjmp (i->env, 1);
1791 }
1792 return 0;
1793 }
1794
1795 static int
pv_pad_callback(const BoxType * b,void * cl)1796 pv_pad_callback (const BoxType * b, void *cl)
1797 {
1798 PinType *pv = (PinType *) b;
1799 struct lo_info *i = (struct lo_info *) cl;
1800
1801 if (!ViaIsOnLayerGroup (pv, GetLayerGroupNumberBySide (i->layer)))
1802 return 0;
1803
1804 if (!TEST_FLAG (i->flag, pv) && IS_PV_ON_PAD (pv, i->pad))
1805 {
1806 if (TEST_FLAG (HOLEFLAG, pv))
1807 {
1808 SET_FLAG (WARNFLAG, pv);
1809 Settings.RatWarn = true;
1810 Message (_("WARNING: Hole too close to pad.\n"));
1811 }
1812 else if (ADD_PV_TO_LIST (pv, i->flag))
1813 longjmp (i->env, 1);
1814 }
1815 return 0;
1816 }
1817
1818 static int
pv_arc_callback(const BoxType * b,void * cl)1819 pv_arc_callback (const BoxType * b, void *cl)
1820 {
1821 PinType *pv = (PinType *) b;
1822 struct lo_info *i = (struct lo_info *) cl;
1823
1824 if (!ViaIsOnLayerGroup (pv, GetLayerGroupNumberByNumber (i->layer)))
1825 return 0;
1826
1827 if (!TEST_FLAG (i->flag, pv) && IS_PV_ON_ARC (pv, i->arc))
1828 {
1829 if (TEST_FLAG (HOLEFLAG, pv))
1830 {
1831 SET_FLAG (WARNFLAG, pv);
1832 Settings.RatWarn = true;
1833 Message (_("WARNING: Hole touches arc.\n"));
1834 }
1835 else if (ADD_PV_TO_LIST (pv, i->flag))
1836 longjmp (i->env, 1);
1837 }
1838 return 0;
1839 }
1840
1841 static int
pv_poly_callback(const BoxType * b,void * cl)1842 pv_poly_callback (const BoxType * b, void *cl)
1843 {
1844 PinType *pv = (PinType *) b;
1845 struct lo_info *i = (struct lo_info *) cl;
1846
1847 if (!ViaIsOnLayerGroup (pv, GetLayerGroupNumberByNumber (i->layer)))
1848 return 0;
1849
1850 /* note that holes in polygons are ok, so they don't generate warnings. */
1851 if (!TEST_FLAG (i->flag, pv) && !TEST_FLAG (HOLEFLAG, pv) &&
1852 (TEST_THERM (i->layer, pv) ||
1853 !TEST_FLAG (CLEARPOLYFLAG, i->polygon) ||
1854 !pv->Clearance))
1855 {
1856 if (TEST_FLAG (SQUAREFLAG, pv))
1857 {
1858 Coord x1, x2, y1, y2;
1859 x1 = pv->X - (PIN_SIZE (pv) + 1 + Bloat) / 2;
1860 x2 = pv->X + (PIN_SIZE (pv) + 1 + Bloat) / 2;
1861 y1 = pv->Y - (PIN_SIZE (pv) + 1 + Bloat) / 2;
1862 y2 = pv->Y + (PIN_SIZE (pv) + 1 + Bloat) / 2;
1863 if (IsRectangleInPolygon (x1, y1, x2, y2, i->polygon)
1864 && ADD_PV_TO_LIST (pv, i->flag))
1865 longjmp (i->env, 1);
1866 }
1867 else if (TEST_FLAG (OCTAGONFLAG, pv))
1868 {
1869 POLYAREA *oct = OctagonPoly (pv->X, pv->Y, PIN_SIZE (pv) / 2);
1870 if (isects (oct, i->polygon, true) && ADD_PV_TO_LIST (pv, i->flag))
1871 longjmp (i->env, 1);
1872 }
1873 else
1874 {
1875 if (IsPointInPolygon
1876 (pv->X, pv->Y, PIN_SIZE (pv) * 0.5 + Bloat, i->polygon)
1877 && ADD_PV_TO_LIST (pv, i->flag))
1878 longjmp (i->env, 1);
1879 }
1880 }
1881 return 0;
1882 }
1883
1884 static int
pv_rat_callback(const BoxType * b,void * cl)1885 pv_rat_callback (const BoxType * b, void *cl)
1886 {
1887 PinType *pv = (PinType *) b;
1888 struct lo_info *i = (struct lo_info *) cl;
1889
1890 /* rats can't cause DRC so there is no early exit */
1891 if (!TEST_FLAG (i->flag, pv) && IS_PV_ON_RAT (pv, i->rat))
1892 ADD_PV_TO_LIST (pv, i->flag);
1893 return 0;
1894 }
1895
1896 /*!
1897 * \brief Searches for new PVs that are connected to NEW LOs on the list.
1898 *
1899 * This routine updates the position counter of the lists too.
1900 */
1901 static bool
LookupPVConnectionsToLOList(int flag,bool AndRats)1902 LookupPVConnectionsToLOList (int flag, bool AndRats)
1903 {
1904 Cardinal layer_no;
1905 struct lo_info info;
1906
1907 info.flag = flag;
1908
1909 /* loop over all layers */
1910 for (layer_no = 0; layer_no < max_copper_layer; layer_no++)
1911 {
1912 LayerType *layer = LAYER_PTR (layer_no);
1913
1914 if (layer->no_drc)
1915 continue;
1916 /* do nothing if there are no PV's */
1917 if (TotalP + TotalV == 0)
1918 {
1919 LineList[layer_no].Location = LineList[layer_no].Number;
1920 ArcList[layer_no].Location = ArcList[layer_no].Number;
1921 PolygonList[layer_no].Location = PolygonList[layer_no].Number;
1922 continue;
1923 }
1924
1925 info.layer = layer_no;
1926 /* check all lines */
1927 while (LineList[layer_no].Location < LineList[layer_no].Number)
1928 {
1929 BoxType search_box;
1930
1931 info.line = LINELIST_ENTRY (layer_no, LineList[layer_no].Location);
1932
1933 /* Keep track of what item we started from for the drc. */
1934 if (drc) SetThing(1, LINE_TYPE, LAYER_PTR(layer_no), info.line, info.line);
1935
1936 search_box = expand_bounds ((BoxType *)info.line);
1937
1938 if (setjmp (info.env) == 0)
1939 r_search (PCB->Data->via_tree, &search_box, NULL,
1940 pv_line_callback, &info);
1941 else
1942 return true;
1943 if (setjmp (info.env) == 0)
1944 r_search (PCB->Data->pin_tree, &search_box, NULL,
1945 pv_line_callback, &info);
1946 else
1947 return true;
1948 LineList[layer_no].Location++;
1949 }
1950
1951 /* check all arcs */
1952 while (ArcList[layer_no].Location < ArcList[layer_no].Number)
1953 {
1954 BoxType search_box;
1955
1956 info.arc = ARCLIST_ENTRY (layer_no, ArcList[layer_no].Location);
1957
1958 /* Keep track of what item we started from for the drc. */
1959 if (drc) SetThing(1, ARC_TYPE, LAYER_PTR(layer_no), info.arc, info.arc);
1960
1961 search_box = expand_bounds ((BoxType *)info.arc);
1962
1963 if (setjmp (info.env) == 0)
1964 r_search (PCB->Data->via_tree, &search_box, NULL,
1965 pv_arc_callback, &info);
1966 else
1967 return true;
1968 if (setjmp (info.env) == 0)
1969 r_search (PCB->Data->pin_tree, &search_box, NULL,
1970 pv_arc_callback, &info);
1971 else
1972 return true;
1973 ArcList[layer_no].Location++;
1974 }
1975
1976 /* now all polygons */
1977 info.layer = layer_no;
1978 while (PolygonList[layer_no].Location < PolygonList[layer_no].Number)
1979 {
1980 BoxType search_box;
1981
1982 info.polygon = POLYGONLIST_ENTRY (layer_no, PolygonList[layer_no].Location);
1983
1984 /* Keep track of what item we started from for the drc. */
1985 if (drc) SetThing(1, POLYGON_TYPE, LAYER_PTR(layer_no), info.polygon, info.polygon);
1986
1987 search_box = expand_bounds ((BoxType *)info.polygon);
1988
1989 if (setjmp (info.env) == 0)
1990 r_search (PCB->Data->via_tree, &search_box, NULL,
1991 pv_poly_callback, &info);
1992 else
1993 return true;
1994 if (setjmp (info.env) == 0)
1995 r_search (PCB->Data->pin_tree, &search_box, NULL,
1996 pv_poly_callback, &info);
1997 else
1998 return true;
1999 PolygonList[layer_no].Location++;
2000 }
2001 }
2002
2003 /* loop over all pad-layers */
2004 for (layer_no = 0; layer_no < 2; layer_no++)
2005 {
2006 /* do nothing if there are no PV's */
2007 if (TotalP + TotalV == 0)
2008 {
2009 PadList[layer_no].Location = PadList[layer_no].Number;
2010 continue;
2011 }
2012
2013 /* check all pads; for a detailed description see
2014 * the handling of lines in this subroutine
2015 */
2016 while (PadList[layer_no].Location < PadList[layer_no].Number)
2017 {
2018 BoxType search_box;
2019
2020 info.layer = layer_no;
2021 info.pad = PADLIST_ENTRY (layer_no, PadList[layer_no].Location);
2022
2023 /* Keep track of what item we started from for the drc. */
2024 if (drc) SetThing(1, PAD_TYPE, info.pad->Element, info.pad, info.pad);
2025
2026 search_box = expand_bounds ((BoxType *)info.pad);
2027
2028 if (setjmp (info.env) == 0)
2029 r_search (PCB->Data->via_tree, &search_box, NULL,
2030 pv_pad_callback, &info);
2031 else
2032 return true;
2033 if (setjmp (info.env) == 0)
2034 r_search (PCB->Data->pin_tree, &search_box, NULL,
2035 pv_pad_callback, &info);
2036 else
2037 return true;
2038 PadList[layer_no].Location++;
2039 }
2040 }
2041
2042 /* do nothing if there are no PV's */
2043 if (TotalP + TotalV == 0)
2044 RatList.Location = RatList.Number;
2045
2046 /* check all rat-lines */
2047 if (AndRats)
2048 {
2049 while (RatList.Location < RatList.Number)
2050 {
2051 info.rat = RATLIST_ENTRY (RatList.Location);
2052 r_search_pt (PCB->Data->via_tree, & info.rat->Point1, 1, NULL,
2053 pv_rat_callback, &info);
2054 r_search_pt (PCB->Data->via_tree, & info.rat->Point2, 1, NULL,
2055 pv_rat_callback, &info);
2056 r_search_pt (PCB->Data->pin_tree, & info.rat->Point1, 1, NULL,
2057 pv_rat_callback, &info);
2058 r_search_pt (PCB->Data->pin_tree, & info.rat->Point2, 1, NULL,
2059 pv_rat_callback, &info);
2060
2061 RatList.Location++;
2062 }
2063 }
2064 return (false);
2065 }
2066
2067
2068 static int
LOCtoArcLine_callback(const BoxType * b,void * cl)2069 LOCtoArcLine_callback (const BoxType * b, void *cl)
2070 {
2071 LineType *line = (LineType *) b;
2072 struct lo_info *i = (struct lo_info *) cl;
2073
2074 if (!TEST_FLAG (i->flag, line) && LineArcIntersect (line, i->arc))
2075 {
2076 if (ADD_LINE_TO_LIST (i->layer, line, i->flag))
2077 longjmp (i->env, 1);
2078 }
2079 return 0;
2080 }
2081
2082 static int
LOCtoArcArc_callback(const BoxType * b,void * cl)2083 LOCtoArcArc_callback (const BoxType * b, void *cl)
2084 {
2085 ArcType *arc = (ArcType *) b;
2086 struct lo_info *i = (struct lo_info *) cl;
2087
2088 if (!arc->Thickness)
2089 return 0;
2090 if (!TEST_FLAG (i->flag, arc) && ArcArcIntersect (i->arc, arc))
2091 {
2092 if (ADD_ARC_TO_LIST (i->layer, arc, i->flag))
2093 longjmp (i->env, 1);
2094 }
2095 return 0;
2096 }
2097
2098 static int
LOCtoArcPad_callback(const BoxType * b,void * cl)2099 LOCtoArcPad_callback (const BoxType * b, void *cl)
2100 {
2101 PadType *pad = (PadType *) b;
2102 struct lo_info *i = (struct lo_info *) cl;
2103
2104 if (!TEST_FLAG (i->flag, pad) && i->layer ==
2105 (TEST_FLAG (ONSOLDERFLAG, pad) ? BOTTOM_SIDE : TOP_SIDE)
2106 && ArcPadIntersect (i->arc, pad) && ADD_PAD_TO_LIST (i->layer, pad, i->flag))
2107 longjmp (i->env, 1);
2108 return 0;
2109 }
2110
2111 /*!
2112 * \brief Searches all LOs that are connected to the given arc on the
2113 * given layergroup.
2114 *
2115 * All found connections are added to the list.
2116 *
2117 * The notation that is used is:\n
2118 * Xij means Xj at arc i.
2119 */
2120 static bool
LookupLOConnectionsToArc(ArcType * Arc,Cardinal LayerGroup,int flag,bool AndRats)2121 LookupLOConnectionsToArc (ArcType *Arc, Cardinal LayerGroup, int flag, bool AndRats)
2122 {
2123 Cardinal entry;
2124 struct lo_info info;
2125 BoxType search_box;
2126
2127 info.flag = flag;
2128 info.arc = Arc;
2129 search_box = expand_bounds ((BoxType *)info.arc);
2130
2131 /* loop over all layers of the group */
2132 for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
2133 {
2134 Cardinal layer_no;
2135 LayerType *layer;
2136 GList *i;
2137
2138 layer_no = PCB->LayerGroups.Entries[LayerGroup][entry];
2139 layer = LAYER_PTR (layer_no);
2140
2141
2142
2143 /* handle normal layers */
2144 if (layer_no < max_copper_layer)
2145 {
2146 info.layer = layer_no;
2147 /* add arcs */
2148 if (setjmp (info.env) == 0)
2149 r_search (layer->line_tree, &search_box,
2150 NULL, LOCtoArcLine_callback, &info);
2151 else
2152 return true;
2153
2154 if (setjmp (info.env) == 0)
2155 r_search (layer->arc_tree, &search_box,
2156 NULL, LOCtoArcArc_callback, &info);
2157 else
2158 return true;
2159
2160 /* now check all polygons */
2161 for (i = layer->Polygon; i != NULL; i = g_list_next (i))
2162 {
2163 PolygonType *polygon = i->data;
2164 if (!TEST_FLAG (flag, polygon) && IsArcInPolygon (Arc, polygon)
2165 && ADD_POLYGON_TO_LIST (layer_no, polygon, flag))
2166 return true;
2167 }
2168 }
2169 else
2170 {
2171 info.layer = layer_no - max_copper_layer;
2172 if (setjmp (info.env) == 0)
2173 r_search (PCB->Data->pad_tree, &search_box, NULL,
2174 LOCtoArcPad_callback, &info);
2175 else
2176 return true;
2177 }
2178 }
2179 return (false);
2180 }
2181
2182 static int
LOCtoLineLine_callback(const BoxType * b,void * cl)2183 LOCtoLineLine_callback (const BoxType * b, void *cl)
2184 {
2185 LineType *line = (LineType *) b;
2186 struct lo_info *i = (struct lo_info *) cl;
2187
2188 if (!TEST_FLAG (i->flag, line) && LineLineIntersect (i->line, line))
2189 {
2190 if (ADD_LINE_TO_LIST (i->layer, line, i->flag))
2191 longjmp (i->env, 1);
2192 }
2193 return 0;
2194 }
2195
2196 static int
LOCtoLineArc_callback(const BoxType * b,void * cl)2197 LOCtoLineArc_callback (const BoxType * b, void *cl)
2198 {
2199 ArcType *arc = (ArcType *) b;
2200 struct lo_info *i = (struct lo_info *) cl;
2201
2202 if (!arc->Thickness)
2203 return 0;
2204 if (!TEST_FLAG (i->flag, arc) && LineArcIntersect (i->line, arc))
2205 {
2206 if (ADD_ARC_TO_LIST (i->layer, arc, i->flag))
2207 longjmp (i->env, 1);
2208 }
2209 return 0;
2210 }
2211
2212 static int
LOCtoLineRat_callback(const BoxType * b,void * cl)2213 LOCtoLineRat_callback (const BoxType * b, void *cl)
2214 {
2215 RatType *rat = (RatType *) b;
2216 struct lo_info *i = (struct lo_info *) cl;
2217
2218 if (!TEST_FLAG (i->flag, rat))
2219 {
2220 if ((rat->group1 == i->layer)
2221 && IsRatPointOnLineEnd (&rat->Point1, i->line))
2222 {
2223 if (ADD_RAT_TO_LIST (rat, i->flag))
2224 longjmp (i->env, 1);
2225 }
2226 else if ((rat->group2 == i->layer)
2227 && IsRatPointOnLineEnd (&rat->Point2, i->line))
2228 {
2229 if (ADD_RAT_TO_LIST (rat, i->flag))
2230 longjmp (i->env, 1);
2231 }
2232 }
2233 return 0;
2234 }
2235
2236 static int
LOCtoLinePad_callback(const BoxType * b,void * cl)2237 LOCtoLinePad_callback (const BoxType * b, void *cl)
2238 {
2239 PadType *pad = (PadType *) b;
2240 struct lo_info *i = (struct lo_info *) cl;
2241
2242 if (!TEST_FLAG (i->flag, pad) && i->layer ==
2243 (TEST_FLAG (ONSOLDERFLAG, pad) ? BOTTOM_SIDE : TOP_SIDE)
2244 && LinePadIntersect (i->line, pad) && ADD_PAD_TO_LIST (i->layer, pad, i->flag))
2245 longjmp (i->env, 1);
2246 return 0;
2247 }
2248
2249 /*!
2250 * \brief Searches all LOs that are connected to the given line on the
2251 * given layergroup.
2252 *
2253 * All found connections are added to the list.
2254 *
2255 * The notation that is used is:
2256 * Xij means Xj at line i.
2257 */
2258 static bool
LookupLOConnectionsToLine(LineType * Line,Cardinal LayerGroup,int flag,bool PolysTo,bool AndRats)2259 LookupLOConnectionsToLine (LineType *Line, Cardinal LayerGroup,
2260 int flag, bool PolysTo, bool AndRats)
2261 {
2262 Cardinal entry;
2263 struct lo_info info;
2264 BoxType search_box;
2265
2266 info.flag = flag;
2267 info.layer = LayerGroup;
2268 info.line = Line;
2269 search_box = expand_bounds ((BoxType *)info.line);
2270
2271 if (AndRats)
2272 {
2273 /* add the new rat lines */
2274 if (setjmp (info.env) == 0)
2275 r_search (PCB->Data->rat_tree, &search_box, NULL,
2276 LOCtoLineRat_callback, &info);
2277 else
2278 return true;
2279 }
2280
2281 /* loop over all layers of the group */
2282 for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
2283 {
2284 Cardinal layer_no;
2285 LayerType *layer;
2286
2287 layer_no = PCB->LayerGroups.Entries[LayerGroup][entry];
2288 layer = LAYER_PTR (layer_no);
2289
2290 /* Note: for DRC, thing1 is set by the calling function, since this
2291 * function also handles pads with rounded ends.
2292 * */
2293
2294 /* handle normal layers */
2295 if (layer_no < max_copper_layer)
2296 {
2297 info.layer = layer_no;
2298 /* add lines */
2299 if (setjmp (info.env) == 0)
2300 r_search (layer->line_tree, &search_box,
2301 NULL, LOCtoLineLine_callback, &info);
2302 else
2303 return true;
2304 /* add arcs */
2305 if (setjmp (info.env) == 0)
2306 r_search (layer->arc_tree, &search_box,
2307 NULL, LOCtoLineArc_callback, &info);
2308 else
2309 return true;
2310 /* now check all polygons */
2311 if (PolysTo)
2312 {
2313 GList *i;
2314 for (i = layer->Polygon; i != NULL; i = g_list_next (i))
2315 {
2316 PolygonType *polygon = i->data;
2317 if (!TEST_FLAG (flag, polygon) && IsLineInPolygon (Line, polygon)
2318 && ADD_POLYGON_TO_LIST (layer_no, polygon, flag))
2319 return true;
2320 }
2321 }
2322 }
2323 else
2324 {
2325 /* handle special 'pad' layers */
2326 info.layer = layer_no - max_copper_layer;
2327 if (setjmp (info.env) == 0)
2328 r_search (PCB->Data->pad_tree, &search_box, NULL,
2329 LOCtoLinePad_callback, &info);
2330 else
2331 return true;
2332 }
2333 }
2334 return (false);
2335 }
2336
2337 struct rat_info
2338 {
2339 Cardinal layer;
2340 PointType *Point;
2341 int flag;
2342 jmp_buf env;
2343 };
2344
2345 static int
LOCtoRat_callback(const BoxType * b,void * cl)2346 LOCtoRat_callback (const BoxType * b, void *cl)
2347 {
2348 LineType *line = (LineType *) b;
2349 struct rat_info *i = (struct rat_info *) cl;
2350
2351 if (!TEST_FLAG (i->flag, line) &&
2352 ((line->Point1.X == i->Point->X &&
2353 line->Point1.Y == i->Point->Y) ||
2354 (line->Point2.X == i->Point->X && line->Point2.Y == i->Point->Y)))
2355 {
2356 if (ADD_LINE_TO_LIST (i->layer, line, i->flag))
2357 longjmp (i->env, 1);
2358 }
2359 return 0;
2360 }
2361 static int
PolygonToRat_callback(const BoxType * b,void * cl)2362 PolygonToRat_callback (const BoxType * b, void *cl)
2363 {
2364 PolygonType *polygon = (PolygonType *) b;
2365 struct rat_info *i = (struct rat_info *) cl;
2366
2367 if (!TEST_FLAG (i->flag, polygon) && polygon->Clipped &&
2368 (i->Point->X == polygon->Clipped->contours->head.point[0]) &&
2369 (i->Point->Y == polygon->Clipped->contours->head.point[1]))
2370 {
2371 if (ADD_POLYGON_TO_LIST (i->layer, polygon, i->flag))
2372 longjmp (i->env, 1);
2373 }
2374 return 0;
2375 }
2376
2377 static int
LOCtoPad_callback(const BoxType * b,void * cl)2378 LOCtoPad_callback (const BoxType * b, void *cl)
2379 {
2380 PadType *pad = (PadType *) b;
2381 struct rat_info *i = (struct rat_info *) cl;
2382
2383 if (!TEST_FLAG (i->flag, pad) && i->layer ==
2384 (TEST_FLAG (ONSOLDERFLAG, pad) ? BOTTOM_SIDE : TOP_SIDE) &&
2385 ((pad->Point1.X == i->Point->X && pad->Point1.Y == i->Point->Y) ||
2386 (pad->Point2.X == i->Point->X && pad->Point2.Y == i->Point->Y) ||
2387 ((pad->Point1.X + pad->Point2.X) / 2 == i->Point->X &&
2388 (pad->Point1.Y + pad->Point2.Y) / 2 == i->Point->Y)) &&
2389 ADD_PAD_TO_LIST (i->layer, pad, i->flag))
2390 longjmp (i->env, 1);
2391 return 0;
2392 }
2393
2394 /*!
2395 * \brief Searches all LOs that are connected to the given rat-line on
2396 * the given layergroup.
2397 *
2398 * All found connections are added to the list.
2399 *
2400 * The notation that is used is:
2401 * Xij means Xj at line i.
2402 */
2403 static bool
LookupLOConnectionsToRatEnd(PointType * Point,Cardinal LayerGroup,int flag)2404 LookupLOConnectionsToRatEnd (PointType *Point, Cardinal LayerGroup, int flag)
2405 {
2406 Cardinal entry;
2407 struct rat_info info;
2408
2409 info.flag = flag;
2410 info.Point = Point;
2411 /* loop over all layers of this group */
2412 for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
2413 {
2414 Cardinal layer_no;
2415 LayerType *layer;
2416
2417 layer_no = PCB->LayerGroups.Entries[LayerGroup][entry];
2418 layer = LAYER_PTR (layer_no);
2419 /* handle normal layers
2420 rats don't ever touch
2421 arcs by definition
2422 */
2423
2424 if (layer_no < max_copper_layer)
2425 {
2426 info.layer = layer_no;
2427 if (setjmp (info.env) == 0)
2428 r_search_pt (layer->line_tree, Point, 1, NULL,
2429 LOCtoRat_callback, &info);
2430 else
2431 return true;
2432 if (setjmp (info.env) == 0)
2433 r_search_pt (layer->polygon_tree, Point, 1,
2434 NULL, PolygonToRat_callback, &info);
2435 }
2436 else
2437 {
2438 /* handle special 'pad' layers */
2439 info.layer = layer_no - max_copper_layer;
2440 if (setjmp (info.env) == 0)
2441 r_search_pt (PCB->Data->pad_tree, Point, 1, NULL,
2442 LOCtoPad_callback, &info);
2443 else
2444 return true;
2445 }
2446 }
2447 return (false);
2448 }
2449
2450 static int
LOCtoPadLine_callback(const BoxType * b,void * cl)2451 LOCtoPadLine_callback (const BoxType * b, void *cl)
2452 {
2453 LineType *line = (LineType *) b;
2454 struct lo_info *i = (struct lo_info *) cl;
2455
2456 if (!TEST_FLAG (i->flag, line) && LinePadIntersect (line, i->pad))
2457 {
2458 if (ADD_LINE_TO_LIST (i->layer, line, i->flag))
2459 longjmp (i->env, 1);
2460 }
2461 return 0;
2462 }
2463
2464 static int
LOCtoPadArc_callback(const BoxType * b,void * cl)2465 LOCtoPadArc_callback (const BoxType * b, void *cl)
2466 {
2467 ArcType *arc = (ArcType *) b;
2468 struct lo_info *i = (struct lo_info *) cl;
2469
2470 if (!arc->Thickness)
2471 return 0;
2472 if (!TEST_FLAG (i->flag, arc) && ArcPadIntersect (arc, i->pad))
2473 {
2474 if (ADD_ARC_TO_LIST (i->layer, arc, i->flag))
2475 longjmp (i->env, 1);
2476 }
2477 return 0;
2478 }
2479
2480 static int
LOCtoPadPoly_callback(const BoxType * b,void * cl)2481 LOCtoPadPoly_callback (const BoxType * b, void *cl)
2482 {
2483 PolygonType *polygon = (PolygonType *) b;
2484 struct lo_info *i = (struct lo_info *) cl;
2485
2486
2487 if (!TEST_FLAG (i->flag, polygon) &&
2488 (!TEST_FLAG (CLEARPOLYFLAG, polygon) || !i->pad->Clearance))
2489 {
2490 if (IsPadInPolygon (i->pad, polygon) &&
2491 ADD_POLYGON_TO_LIST (i->layer, polygon, i->flag))
2492 longjmp (i->env, 1);
2493 }
2494 return 0;
2495 }
2496
2497 static int
LOCtoPadRat_callback(const BoxType * b,void * cl)2498 LOCtoPadRat_callback (const BoxType * b, void *cl)
2499 {
2500 RatType *rat = (RatType *) b;
2501 struct lo_info *i = (struct lo_info *) cl;
2502
2503 if (!TEST_FLAG (i->flag, rat))
2504 {
2505 if (rat->group1 == i->layer &&
2506 ((rat->Point1.X == i->pad->Point1.X && rat->Point1.Y == i->pad->Point1.Y) ||
2507 (rat->Point1.X == i->pad->Point2.X && rat->Point1.Y == i->pad->Point2.Y) ||
2508 (rat->Point1.X == (i->pad->Point1.X + i->pad->Point2.X) / 2 &&
2509 rat->Point1.Y == (i->pad->Point1.Y + i->pad->Point2.Y) / 2)))
2510 {
2511 if (ADD_RAT_TO_LIST (rat, i->flag))
2512 longjmp (i->env, 1);
2513 }
2514 else if (rat->group2 == i->layer &&
2515 ((rat->Point2.X == i->pad->Point1.X && rat->Point2.Y == i->pad->Point1.Y) ||
2516 (rat->Point2.X == i->pad->Point2.X && rat->Point2.Y == i->pad->Point2.Y) ||
2517 (rat->Point2.X == (i->pad->Point1.X + i->pad->Point2.X) / 2 &&
2518 rat->Point2.Y == (i->pad->Point1.Y + i->pad->Point2.Y) / 2)))
2519 {
2520 if (ADD_RAT_TO_LIST (rat, i->flag))
2521 longjmp (i->env, 1);
2522 }
2523 }
2524 return 0;
2525 }
2526
2527 static int
LOCtoPadPad_callback(const BoxType * b,void * cl)2528 LOCtoPadPad_callback (const BoxType * b, void *cl)
2529 {
2530 PadType *pad = (PadType *) b;
2531 struct lo_info *i = (struct lo_info *) cl;
2532
2533 if (!TEST_FLAG (i->flag, pad) && i->layer ==
2534 (TEST_FLAG (ONSOLDERFLAG, pad) ? BOTTOM_SIDE : TOP_SIDE)
2535 && PadPadIntersect (pad, i->pad) && ADD_PAD_TO_LIST (i->layer, pad, i->flag))
2536 longjmp (i->env, 1);
2537 return 0;
2538 }
2539
2540 /*!
2541 * \brief Searches all LOs that are connected to the given pad on the
2542 * given layergroup.
2543 *
2544 * All found connections are added to the list.
2545 */
2546 static bool
LookupLOConnectionsToPad(PadType * Pad,Cardinal LayerGroup,int flag,bool AndRats)2547 LookupLOConnectionsToPad (PadType *Pad, Cardinal LayerGroup, int flag, bool AndRats)
2548 {
2549 Cardinal entry;
2550 struct lo_info info;
2551 BoxType search_box;
2552
2553 info.flag = flag;
2554 info.pad = Pad;
2555
2556
2557 if (!TEST_FLAG (SQUAREFLAG, Pad))
2558 return (LookupLOConnectionsToLine ((LineType *) Pad, LayerGroup, flag, false, AndRats));
2559
2560 search_box = expand_bounds ((BoxType *)info.pad);
2561
2562 /* add the new rat lines */
2563 info.layer = LayerGroup;
2564
2565 if (AndRats)
2566 {
2567 if (setjmp (info.env) == 0)
2568 r_search (PCB->Data->rat_tree, &search_box, NULL,
2569 LOCtoPadRat_callback, &info);
2570 else
2571 return true;
2572 }
2573
2574 /* loop over all layers of the group */
2575 for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
2576 {
2577 Cardinal layer_no;
2578 LayerType *layer;
2579
2580 layer_no = PCB->LayerGroups.Entries[LayerGroup][entry];
2581 layer = LAYER_PTR (layer_no);
2582 /* handle normal layers */
2583 if (layer_no < max_copper_layer)
2584 {
2585 info.layer = layer_no;
2586 /* add lines */
2587 if (setjmp (info.env) == 0)
2588 r_search (layer->line_tree, &search_box,
2589 NULL, LOCtoPadLine_callback, &info);
2590 else
2591 return true;
2592 /* add arcs */
2593 if (setjmp (info.env) == 0)
2594 r_search (layer->arc_tree, &search_box,
2595 NULL, LOCtoPadArc_callback, &info);
2596 else
2597 return true;
2598 /* add polygons */
2599 if (setjmp (info.env) == 0)
2600 r_search (layer->polygon_tree, &search_box,
2601 NULL, LOCtoPadPoly_callback, &info);
2602 else
2603 return true;
2604 }
2605 else
2606 {
2607 /* handle special 'pad' layers */
2608 info.layer = layer_no - max_copper_layer;
2609 if (setjmp (info.env) == 0)
2610 r_search (PCB->Data->pad_tree, &search_box, NULL,
2611 LOCtoPadPad_callback, &info);
2612 else
2613 return true;
2614 }
2615
2616 }
2617 return (false);
2618 }
2619
2620 static int
LOCtoPolyLine_callback(const BoxType * b,void * cl)2621 LOCtoPolyLine_callback (const BoxType * b, void *cl)
2622 {
2623 LineType *line = (LineType *) b;
2624 struct lo_info *i = (struct lo_info *) cl;
2625
2626 if (!TEST_FLAG (i->flag, line) && IsLineInPolygon (line, i->polygon))
2627 {
2628 if (ADD_LINE_TO_LIST (i->layer, line, i->flag))
2629 longjmp (i->env, 1);
2630 }
2631 return 0;
2632 }
2633
2634 static int
LOCtoPolyArc_callback(const BoxType * b,void * cl)2635 LOCtoPolyArc_callback (const BoxType * b, void *cl)
2636 {
2637 ArcType *arc = (ArcType *) b;
2638 struct lo_info *i = (struct lo_info *) cl;
2639
2640 if (!arc->Thickness)
2641 return 0;
2642 if (!TEST_FLAG (i->flag, arc) && IsArcInPolygon (arc, i->polygon))
2643 {
2644 if (ADD_ARC_TO_LIST (i->layer, arc, i->flag))
2645 longjmp (i->env, 1);
2646 }
2647 return 0;
2648 }
2649
2650 static int
LOCtoPolyPad_callback(const BoxType * b,void * cl)2651 LOCtoPolyPad_callback (const BoxType * b, void *cl)
2652 {
2653 PadType *pad = (PadType *) b;
2654 struct lo_info *i = (struct lo_info *) cl;
2655
2656 if (!TEST_FLAG (i->flag, pad) && i->layer ==
2657 (TEST_FLAG (ONSOLDERFLAG, pad) ? BOTTOM_SIDE : TOP_SIDE)
2658 && IsPadInPolygon (pad, i->polygon))
2659 {
2660 if (ADD_PAD_TO_LIST (i->layer, pad, i->flag))
2661 longjmp (i->env, 1);
2662 }
2663 return 0;
2664 }
2665
2666 static int
LOCtoPolyRat_callback(const BoxType * b,void * cl)2667 LOCtoPolyRat_callback (const BoxType * b, void *cl)
2668 {
2669 RatType *rat = (RatType *) b;
2670 struct lo_info *i = (struct lo_info *) cl;
2671
2672 if (!TEST_FLAG (i->flag, rat))
2673 {
2674 if ((rat->Point1.X == (i->polygon->Clipped->contours->head.point[0]) &&
2675 rat->Point1.Y == (i->polygon->Clipped->contours->head.point[1]) &&
2676 rat->group1 == i->layer) ||
2677 (rat->Point2.X == (i->polygon->Clipped->contours->head.point[0]) &&
2678 rat->Point2.Y == (i->polygon->Clipped->contours->head.point[1]) &&
2679 rat->group2 == i->layer))
2680 if (ADD_RAT_TO_LIST (rat, i->flag))
2681 longjmp (i->env, 1);
2682 }
2683 return 0;
2684 }
2685
2686
2687 /*!
2688 * \brief Looks up LOs that are connected to the given polygon on the
2689 * given layergroup.
2690 *
2691 * All found connections are added to the list.
2692 */
2693 static bool
LookupLOConnectionsToPolygon(PolygonType * Polygon,Cardinal LayerGroup,int flag,bool AndRats)2694 LookupLOConnectionsToPolygon (PolygonType *Polygon, Cardinal LayerGroup, int flag, bool AndRats)
2695 {
2696 Cardinal entry;
2697 struct lo_info info;
2698 BoxType search_box;
2699
2700 if (!Polygon->Clipped)
2701 return false;
2702
2703 info.flag = flag;
2704 info.polygon = Polygon;
2705 search_box = expand_bounds ((BoxType *)info.polygon);
2706
2707 info.layer = LayerGroup;
2708
2709 /* check rats */
2710 if (AndRats)
2711 {
2712 if (setjmp (info.env) == 0)
2713 r_search (PCB->Data->rat_tree, &search_box, NULL,
2714 LOCtoPolyRat_callback, &info);
2715 else
2716 return true;
2717 }
2718
2719 /* loop over all layers of the group */
2720 for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
2721 {
2722 Cardinal layer_no;
2723 LayerType *layer;
2724
2725 layer_no = PCB->LayerGroups.Entries[LayerGroup][entry];
2726 layer = LAYER_PTR (layer_no);
2727
2728 /* handle normal layers */
2729 if (layer_no < max_copper_layer)
2730 {
2731 GList *i;
2732
2733 /* check all polygons */
2734 for (i = layer->Polygon; i != NULL; i = g_list_next (i))
2735 {
2736 PolygonType *polygon = i->data;
2737 if (!TEST_FLAG (flag, polygon)
2738 && IsPolygonInPolygon (polygon, Polygon)
2739 && ADD_POLYGON_TO_LIST (layer_no, polygon, flag))
2740 return true;
2741 }
2742
2743 info.layer = layer_no;
2744 /* check all lines */
2745 if (setjmp (info.env) == 0)
2746 r_search (layer->line_tree, &search_box,
2747 NULL, LOCtoPolyLine_callback, &info);
2748 else
2749 return true;
2750 /* check all arcs */
2751 if (setjmp (info.env) == 0)
2752 r_search (layer->arc_tree, &search_box,
2753 NULL, LOCtoPolyArc_callback, &info);
2754 else
2755 return true;
2756 }
2757 else
2758 {
2759 info.layer = layer_no - max_copper_layer;
2760 if (setjmp (info.env) == 0)
2761 r_search (PCB->Data->pad_tree, &search_box,
2762 NULL, LOCtoPolyPad_callback, &info);
2763 else
2764 return true;
2765 }
2766 }
2767 return (false);
2768 }
2769
2770
2771 static void
reassign_no_drc_flags(void)2772 reassign_no_drc_flags (void)
2773 {
2774 int layer;
2775
2776 for (layer = 0; layer < max_copper_layer; layer++)
2777 {
2778 LayerType *l = LAYER_PTR (layer);
2779 l->no_drc = AttributeGet (l, "PCB::skip-drc") != NULL;
2780 }
2781 }
2782
2783 /*!
2784 * \brief Loops till no more connections are found.
2785 */
2786 /*static*/ bool
DoIt(int flag,Coord bloat,bool AndRats,bool AndDraw,bool is_drc)2787 DoIt (int flag, Coord bloat, bool AndRats, bool AndDraw, bool is_drc)
2788 {
2789 bool newone = false;
2790 Bloat = bloat;
2791 drc = is_drc;
2792 reassign_no_drc_flags ();
2793 do
2794 {
2795 /* lookup connections; these are the steps (2) to (4)
2796 * from the description
2797 *
2798 * If anything is added to any of the lists, newone will be true. Any
2799 * new additions to the lists mean that there are potentially more things
2800 * to add to the list, things that might overlap with only the new
2801 * objects.
2802 */
2803 newone = LookupPVConnectionsToPVList (flag) ||
2804 LookupLOConnectionsToPVList (flag, AndRats) ||
2805 LookupLOConnectionsToLOList (flag, AndRats) ||
2806 LookupPVConnectionsToLOList (flag, AndRats);
2807 if (AndDraw)
2808 DrawNewConnections ();
2809 }
2810 /* Keep executing the lookup until no new objects are found. */
2811 while (!newone && !ListsEmpty (AndRats));
2812 if (AndDraw)
2813 Draw ();
2814 /* We should leave global state variables in a consistent state... */
2815 Bloat = 0;
2816 return (newone);
2817 }
2818
2819 /*!
2820 * \brief Resets some flags for looking up the next pin/pad.
2821 */
2822 static bool
PrepareNextLoop(FILE * FP)2823 PrepareNextLoop (FILE * FP)
2824 {
2825 Cardinal layer;
2826
2827 /* reset found LOs for the next pin */
2828 for (layer = 0; layer < max_copper_layer; layer++)
2829 {
2830 LineList[layer].Location = LineList[layer].Number = 0;
2831 ArcList[layer].Location = ArcList[layer].Number = 0;
2832 PolygonList[layer].Location = PolygonList[layer].Number = 0;
2833 }
2834
2835 /* reset found pads */
2836 for (layer = 0; layer < 2; layer++)
2837 PadList[layer].Location = PadList[layer].Number = 0;
2838
2839 /* reset PVs */
2840 PVList.Number = PVList.Location = 0;
2841 RatList.Number = RatList.Location = 0;
2842
2843 return (false);
2844 }
2845
2846
2847
2848 /* static */ void
start_do_it_and_dump(int type,void * ptr1,void * ptr2,void * ptr3,int flag,bool AndDraw,Coord bloat,bool is_drc)2849 start_do_it_and_dump (int type, void *ptr1, void *ptr2, void *ptr3,
2850 int flag, bool AndDraw,
2851 Coord bloat, bool is_drc)
2852 {
2853 ListStart (type, ptr1, ptr2, ptr3, flag);
2854 DoIt (flag, bloat, true, AndDraw, is_drc);
2855 DumpList ();
2856 }
2857
2858 /* ----------------------------------------------------------------------- *
2859 *
2860 * Ancillary Helper Functions
2861 *
2862 * ----------------------------------------------------------------------- */
2863
2864 /*!
2865 * \brief Writes the several names of an element to a file.
2866 */
2867 static void
PrintElementNameList(ElementType * Element,FILE * FP)2868 PrintElementNameList (ElementType *Element, FILE * FP)
2869 {
2870 static DynamicStringType cname, pname, vname;
2871
2872 CreateQuotedString (&cname, (char *)EMPTY (DESCRIPTION_NAME (Element)));
2873 CreateQuotedString (&pname, (char *)EMPTY (NAMEONPCB_NAME (Element)));
2874 CreateQuotedString (&vname, (char *)EMPTY (VALUE_NAME (Element)));
2875 fprintf (FP, "(%s %s %s)\n", cname.Data, pname.Data, vname.Data);
2876 }
2877
2878 /*!
2879 * \brief Writes the several names of an element to a file.
2880 */
2881 static void
PrintConnectionElementName(ElementType * Element,FILE * FP)2882 PrintConnectionElementName (ElementType *Element, FILE * FP)
2883 {
2884 fputs ("Element", FP);
2885 PrintElementNameList (Element, FP);
2886 fputs ("{\n", FP);
2887 }
2888
2889 /*!
2890 * \brief Prints one {pin,pad,via}/element entry of connection lists.
2891 */
2892 static void
PrintConnectionListEntry(char * ObjName,ElementType * Element,bool FirstOne,FILE * FP)2893 PrintConnectionListEntry (char *ObjName, ElementType *Element,
2894 bool FirstOne, FILE * FP)
2895 {
2896 static DynamicStringType oname;
2897
2898 CreateQuotedString (&oname, ObjName);
2899 if (FirstOne)
2900 fprintf (FP, "\t%s\n\t{\n", oname.Data);
2901 else
2902 {
2903 fprintf (FP, "\t\t%s ", oname.Data);
2904 if (Element)
2905 PrintElementNameList (Element, FP);
2906 else
2907 fputs ("(__VIA__)\n", FP);
2908 }
2909 }
2910
2911 /*!
2912 * \brief Prints all found connections of a pads to file FP
2913 * the connections are stacked in 'PadList'.
2914 */
2915 static void
PrintPadConnections(Cardinal Layer,FILE * FP,bool IsFirst)2916 PrintPadConnections (Cardinal Layer, FILE * FP, bool IsFirst)
2917 {
2918 Cardinal i;
2919 PadType *ptr;
2920
2921 if (!PadList[Layer].Number)
2922 return;
2923
2924 /* the starting pad */
2925 if (IsFirst)
2926 {
2927 ptr = PADLIST_ENTRY (Layer, 0);
2928 if (ptr != NULL)
2929 PrintConnectionListEntry ((char *)UNKNOWN (ptr->Name), NULL, true, FP);
2930 else
2931 printf ("Skipping NULL ptr in 1st part of PrintPadConnections\n");
2932 }
2933
2934 /* we maybe have to start with i=1 if we are handling the
2935 * starting-pad itself
2936 */
2937 for (i = IsFirst ? 1 : 0; i < PadList[Layer].Number; i++)
2938 {
2939 ptr = PADLIST_ENTRY (Layer, i);
2940 if (ptr != NULL)
2941 PrintConnectionListEntry ((char *)EMPTY (ptr->Name), (ElementType *)ptr->Element, false, FP);
2942 else
2943 printf ("Skipping NULL ptr in 2nd part of PrintPadConnections\n");
2944 }
2945 }
2946
2947 /*!
2948 * \brief Prints all found connections of a pin to file FP
2949 * the connections are stacked in 'PVList'.
2950 */
2951 static void
PrintPinConnections(FILE * FP,bool IsFirst)2952 PrintPinConnections (FILE * FP, bool IsFirst)
2953 {
2954 Cardinal i;
2955 PinType *pv;
2956
2957 if (!PVList.Number)
2958 return;
2959
2960 if (IsFirst)
2961 {
2962 /* the starting pin */
2963 pv = PVLIST_ENTRY (0);
2964 PrintConnectionListEntry ((char *)EMPTY (pv->Name), NULL, true, FP);
2965 }
2966
2967 /* we maybe have to start with i=1 if we are handling the
2968 * starting-pin itself
2969 */
2970 for (i = IsFirst ? 1 : 0; i < PVList.Number; i++)
2971 {
2972 /* get the elements name or assume that its a via */
2973 pv = PVLIST_ENTRY (i);
2974 PrintConnectionListEntry ((char *)EMPTY (pv->Name), (ElementType *)pv->Element, false, FP);
2975 }
2976 }
2977
2978 /*!
2979 * \brief Finds all connections to the pins of the passed element.
2980 *
2981 * The result is written to file FP.
2982 *
2983 * \return true if operation was aborted.
2984 */
2985 static bool
PrintElementConnections(ElementType * Element,FILE * FP,int flag,bool AndDraw)2986 PrintElementConnections (ElementType *Element, FILE * FP, int flag, bool AndDraw)
2987 {
2988 PrintConnectionElementName (Element, FP);
2989
2990 /* check all pins in element */
2991 PIN_LOOP (Element);
2992 {
2993 /* pin might have been checked before, add to list if not */
2994 if (TEST_FLAG (flag, pin))
2995 {
2996 PrintConnectionListEntry ((char *)EMPTY (pin->Name), NULL, true, FP);
2997 fputs ("\t\t__CHECKED_BEFORE__\n\t}\n", FP);
2998 continue;
2999 }
3000 if (ADD_PV_TO_LIST (pin, flag))
3001 return true;
3002 DoIt (flag, 0, true, AndDraw, false);
3003 /* printout all found connections */
3004 PrintPinConnections (FP, true);
3005 PrintPadConnections (TOP_SIDE, FP, false);
3006 PrintPadConnections (BOTTOM_SIDE, FP, false);
3007 fputs ("\t}\n", FP);
3008 if (PrepareNextLoop (FP))
3009 return (true);
3010 }
3011 END_LOOP;
3012
3013 /* check all pads in element */
3014 PAD_LOOP (Element);
3015 {
3016 Cardinal layer;
3017 /* pad might have been checked before, add to list if not */
3018 if (TEST_FLAG (flag, pad))
3019 {
3020 PrintConnectionListEntry ((char *)EMPTY (pad->Name), NULL, true, FP);
3021 fputs ("\t\t__CHECKED_BEFORE__\n\t}\n", FP);
3022 continue;
3023 }
3024 layer = TEST_FLAG (ONSOLDERFLAG, pad) ? BOTTOM_SIDE : TOP_SIDE;
3025 if (ADD_PAD_TO_LIST (layer, pad, flag))
3026 return true;
3027 DoIt (flag, 0, true, AndDraw, false);
3028 /* print all found connections */
3029 PrintPadConnections (layer, FP, true);
3030 PrintPadConnections (layer ==
3031 (TOP_SIDE ? BOTTOM_SIDE : TOP_SIDE),
3032 FP, false);
3033 PrintPinConnections (FP, false);
3034 fputs ("\t}\n", FP);
3035 if (PrepareNextLoop (FP))
3036 return (true);
3037 }
3038 END_LOOP;
3039 fputs ("}\n\n", FP);
3040 return (false);
3041 }
3042
3043 /*!
3044 * \brief Draws all new connections which have been found since the
3045 * routine was called the last time.
3046 */
3047 static void
DrawNewConnections(void)3048 DrawNewConnections (void)
3049 {
3050 int i;
3051 Cardinal position;
3052
3053 /* decrement 'i' to keep layerstack order */
3054 for (i = max_copper_layer - 1; i != -1; i--)
3055 {
3056 Cardinal layer = LayerStack[i];
3057
3058 if (PCB->Data->Layer[layer].On)
3059 {
3060 /* draw all new lines */
3061 position = LineList[layer].DrawLocation;
3062 for (; position < LineList[layer].Number; position++)
3063 DrawLine (LAYER_PTR (layer), LINELIST_ENTRY (layer, position));
3064 LineList[layer].DrawLocation = LineList[layer].Number;
3065
3066 /* draw all new arcs */
3067 position = ArcList[layer].DrawLocation;
3068 for (; position < ArcList[layer].Number; position++)
3069 DrawArc (LAYER_PTR (layer), ARCLIST_ENTRY (layer, position));
3070 ArcList[layer].DrawLocation = ArcList[layer].Number;
3071
3072 /* draw all new polygons */
3073 position = PolygonList[layer].DrawLocation;
3074 for (; position < PolygonList[layer].Number; position++)
3075 DrawPolygon (LAYER_PTR (layer), POLYGONLIST_ENTRY (layer, position));
3076 PolygonList[layer].DrawLocation = PolygonList[layer].Number;
3077 }
3078 }
3079
3080 /* draw all new pads */
3081 if (PCB->PinOn)
3082 for (i = 0; i < 2; i++)
3083 {
3084 position = PadList[i].DrawLocation;
3085
3086 for (; position < PadList[i].Number; position++)
3087 DrawPad (PADLIST_ENTRY (i, position));
3088 PadList[i].DrawLocation = PadList[i].Number;
3089 }
3090
3091 /* draw all new PVs; 'PVList' holds a list of pointers to the
3092 * sorted array pointers to PV data
3093 */
3094 while (PVList.DrawLocation < PVList.Number)
3095 {
3096 PinType *pv = PVLIST_ENTRY (PVList.DrawLocation);
3097
3098 if (TEST_FLAG (PINFLAG, pv))
3099 {
3100 if (PCB->PinOn)
3101 DrawPin (pv);
3102 }
3103 else if (PCB->ViaOn)
3104 DrawVia (pv);
3105 PVList.DrawLocation++;
3106 }
3107 /* draw the new rat-lines */
3108 if (PCB->RatOn)
3109 {
3110 position = RatList.DrawLocation;
3111 for (; position < RatList.Number; position++)
3112 DrawRat (RATLIST_ENTRY (position));
3113 RatList.DrawLocation = RatList.Number;
3114 }
3115 }
3116
3117
3118 /* ----------------------------------------------------------------------- *
3119 *
3120 * Entry Points
3121 *
3122 * ----------------------------------------------------------------------- */
3123
3124 /*!
3125 * \brief Set the specified flag on all objects that touch the object at
3126 * the given coordinates.
3127 *
3128 * The objects are re-drawn if AndDraw is true.
3129 */
3130 void
LookupConnection(Coord X,Coord Y,bool AndDraw,Coord Range,int flag,bool AndRats)3131 LookupConnection (Coord X, Coord Y, bool AndDraw, Coord Range, int flag,
3132 bool AndRats)
3133 {
3134 void *ptr1, *ptr2, *ptr3;
3135 char *name;
3136 int type;
3137
3138 /* check if there are any pins or pads at that position */
3139
3140 reassign_no_drc_flags ();
3141
3142 /* LOOKUP_FIRST = PIN_TYPE | PAD_TYPE */
3143 /* LOOKUP_MORE = Vias, lines, ratlines, polygons, arcs */
3144 /* SILK_TYPE = lines, arcs, polygons */
3145 type
3146 = SearchObjectByLocation (LOOKUP_FIRST, &ptr1, &ptr2, &ptr3, X, Y, Range);
3147 if (type == NO_TYPE)
3148 {
3149 type = SearchObjectByLocation (
3150 LOOKUP_MORE & ~(AndRats ? 0 : RATLINE_TYPE),
3151 &ptr1, &ptr2, &ptr3, X, Y, Range);
3152 if (type == NO_TYPE)
3153 return;
3154 if (type & SILK_TYPE)
3155 {
3156 int laynum = GetLayerNumber (PCB->Data,
3157 (LayerType *) ptr1);
3158
3159 /* don't mess with non-conducting objects! */
3160 if (laynum >= max_copper_layer || ((LayerType *)ptr1)->no_drc)
3161 return;
3162 }
3163 }
3164
3165 /* If the netlist window is open, this will highlight the entry
3166 * corresponding to net of the pin or pad we just found. It does not open
3167 * the window it is closed.
3168 */
3169 name = ConnectionName (type, ptr1, ptr2);
3170 hid_actionl ("NetlistShow", name, NULL);
3171
3172 InitConnectionLookup ();
3173
3174 /* now add the object to the appropriate list and start scanning
3175 * This is step (1) from the description
3176 */
3177 ListStart (type, ptr1, ptr2, ptr3, flag);
3178 DoIt (flag, 0, AndRats, AndDraw, false);
3179
3180 /* we are done */
3181 if (AndDraw)
3182 Draw ();
3183 if (AndDraw && Settings.RingBellWhenFinished)
3184 gui->beep ();
3185 FreeConnectionLookupMemory ();
3186 }
3187
3188 void
LookupConnectionByPin(int type,void * ptr1)3189 LookupConnectionByPin (int type, void *ptr1)
3190 {
3191 /* int TheFlag = FOUNDFLAG; */
3192
3193 LockUndo();
3194 InitConnectionLookup ();
3195 ListStart (type, NULL, ptr1, NULL, FOUNDFLAG);
3196 DoIt (FOUNDFLAG, 0, true, false, false);
3197 FreeConnectionLookupMemory ();
3198 UnlockUndo();
3199 }
3200
3201 /*!
3202 * \brief Find connections for rats nesting.
3203 *
3204 * Assumes InitConnectionLookup() has already been done.
3205 */
3206 void
RatFindHook(int type,void * ptr1,void * ptr2,void * ptr3,bool undo,int flag,bool AndRats)3207 RatFindHook (int type, void *ptr1, void *ptr2, void *ptr3,
3208 bool undo, int flag, bool AndRats)
3209 {
3210 if(!undo) LockUndo();
3211 DumpList ();
3212 ListStart (type, ptr1, ptr2, ptr3, flag);
3213 DoIt (flag, 0, AndRats, false, false);
3214 /* This is potentially problematic if there is a higher level function
3215 * that has locked the undo system. */
3216 UnlockUndo();
3217 }
3218
3219 /*!
3220 * \brief Prints all unused pins of an element to file FP.
3221 */
3222 static bool
PrintAndSelectUnusedPinsAndPadsOfElement(ElementType * Element,FILE * FP,int flag)3223 PrintAndSelectUnusedPinsAndPadsOfElement (ElementType *Element, FILE * FP, int flag)
3224 {
3225 bool first = true;
3226 Cardinal number;
3227 static DynamicStringType oname;
3228
3229 /* check all pins in element */
3230
3231 PIN_LOOP (Element);
3232 {
3233 if (!TEST_FLAG (HOLEFLAG, pin))
3234 {
3235 /* pin might have bee checked before, add to list if not */
3236 if (!TEST_FLAG (flag, pin) && FP)
3237 {
3238 int i;
3239 if (ADD_PV_TO_LIST (pin, flag))
3240 return true;
3241 DoIt (flag, 0, true, true, false);
3242 number = PadList[TOP_SIDE].Number
3243 + PadList[BOTTOM_SIDE].Number + PVList.Number;
3244 /* the pin has no connection if it's the only
3245 * list entry; don't count vias
3246 */
3247 for (i = 0; i < PVList.Number; i++)
3248 if (!PVLIST_ENTRY (i)->Element)
3249 number--;
3250 if (number == 1)
3251 {
3252 /* output of element name if not already done */
3253 if (first)
3254 {
3255 PrintConnectionElementName (Element, FP);
3256 first = false;
3257 }
3258
3259 /* write name to list and draw selected object */
3260 CreateQuotedString (&oname, (char *)EMPTY (pin->Name));
3261 fprintf (FP, "\t%s\n", oname.Data);
3262 SET_FLAG (SELECTEDFLAG, pin);
3263 DrawPin (pin);
3264 }
3265
3266 /* reset found objects for the next pin */
3267 if (PrepareNextLoop (FP))
3268 return (true);
3269 }
3270 }
3271 }
3272 END_LOOP;
3273
3274 /* check all pads in element */
3275 PAD_LOOP (Element);
3276 {
3277 /* lookup pad in list */
3278 /* pad might has bee checked before, add to list if not */
3279 if (!TEST_FLAG (flag, pad) && FP)
3280 {
3281 int i;
3282 if (ADD_PAD_TO_LIST (TEST_FLAG (ONSOLDERFLAG, pad)
3283 ? BOTTOM_SIDE : TOP_SIDE, pad, flag))
3284 return true;
3285 DoIt (flag, 0, true, true, false);
3286 number = PadList[TOP_SIDE].Number
3287 + PadList[BOTTOM_SIDE].Number + PVList.Number;
3288 /* the pin has no connection if it's the only
3289 * list entry; don't count vias
3290 */
3291 for (i = 0; i < PVList.Number; i++)
3292 if (!PVLIST_ENTRY (i)->Element)
3293 number--;
3294 if (number == 1)
3295 {
3296 /* output of element name if not already done */
3297 if (first)
3298 {
3299 PrintConnectionElementName (Element, FP);
3300 first = false;
3301 }
3302
3303 /* write name to list and draw selected object */
3304 CreateQuotedString (&oname, (char *)EMPTY (pad->Name));
3305 fprintf (FP, "\t%s\n", oname.Data);
3306 SET_FLAG (SELECTEDFLAG, pad);
3307 DrawPad (pad);
3308 }
3309
3310 /* reset found objects for the next pin */
3311 if (PrepareNextLoop (FP))
3312 return (true);
3313 }
3314 }
3315 END_LOOP;
3316
3317 /* print separator if element has unused pins or pads */
3318 if (!first)
3319 {
3320 fputs ("}\n\n", FP);
3321 SEPARATE (FP);
3322 }
3323 return (false);
3324 }
3325
3326
3327 /*!
3328 * \brief Find all unused pins of all elements.
3329 */
3330 void
LookupUnusedPins(FILE * FP)3331 LookupUnusedPins (FILE * FP)
3332 {
3333 /* reset all currently marked connections */
3334 ClearFlagOnAllObjects (FOUNDFLAG, true);
3335 InitConnectionLookup ();
3336
3337 ELEMENT_LOOP (PCB->Data);
3338 {
3339 /* break if abort dialog returned true;
3340 * passing NULL as filedescriptor discards the normal output
3341 */
3342 if (PrintAndSelectUnusedPinsAndPadsOfElement (element, FP, FOUNDFLAG))
3343 break;
3344 }
3345 END_LOOP;
3346
3347 if (Settings.RingBellWhenFinished)
3348 gui->beep ();
3349 FreeConnectionLookupMemory ();
3350 IncrementUndoSerialNumber ();
3351 Draw ();
3352 }
3353
3354 /*!
3355 * \brief Find all connections to pins within one element.
3356 */
3357 void
LookupElementConnections(ElementType * Element,FILE * FP)3358 LookupElementConnections (ElementType *Element, FILE * FP)
3359 {
3360 /* reset all currently marked connections */
3361 ClearFlagOnAllObjects (FOUNDFLAG, true);
3362 InitConnectionLookup ();
3363 PrintElementConnections (Element, FP, FOUNDFLAG, true);
3364 SetChangedFlag (true);
3365 if (Settings.RingBellWhenFinished)
3366 gui->beep ();
3367 FreeConnectionLookupMemory ();
3368 IncrementUndoSerialNumber ();
3369 Draw ();
3370 }
3371
3372 /*!
3373 * \brief Find all connections to pins of all element.
3374 *
3375 * This is called by an action to write out a list of all of the pins and
3376 * pads connected to each pin/pad of every element on the board. Kind of
3377 * an element oriented netlist.
3378 *
3379 * Since this runs to completion without any user interaction, and should
3380 * leave the database in the same state it was found, there's no reason to
3381 * add all of the overhead of making everything undo-able.
3382 */
3383 void
LookupConnectionsToAllElements(FILE * FP)3384 LookupConnectionsToAllElements (FILE * FP)
3385 {
3386 LockUndo();
3387 /* reset all currently marked connections */
3388 ClearFlagOnAllObjects (FOUNDFLAG, false);
3389
3390 InitConnectionLookup ();
3391
3392 ELEMENT_LOOP (PCB->Data);
3393 {
3394 /* break if abort dialog returned true */
3395 if (PrintElementConnections (element, FP, FOUNDFLAG, false))
3396 break;
3397 SEPARATE (FP);
3398 if (Settings.ResetAfterElement && n != 1)
3399 ClearFlagOnAllObjects (FOUNDFLAG, false);
3400 }
3401 END_LOOP;
3402 if (Settings.RingBellWhenFinished)
3403 gui->beep ();
3404 ClearFlagOnAllObjects (FOUNDFLAG, false);
3405 UnlockUndo();
3406 FreeConnectionLookupMemory ();
3407 Redraw ();
3408 }
3409
3410