1 /*!
2 * \file src/rubberband.c
3 *
4 * \brief Functions used by 'rubberband moves'.
5 *
6 * <hr>
7 *
8 * <h1><b>Copyright.</b></h1>\n
9 *
10 * PCB, interactive printed circuit board design
11 *
12 * Copyright (C) 1994,1995,1996 Thomas Nau
13 *
14 * This program is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU General Public License as published by
16 * the Free Software Foundation; either version 2 of the License, or
17 * (at your option) any later version.
18 *
19 * This program is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU General Public License for more details.
23 *
24 * You should have received a copy of the GNU General Public License along
25 * with this program; if not, write to the Free Software Foundation, Inc.,
26 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
27 *
28 * Contact addresses for paper mail and Email:
29 *
30 * Thomas Nau, Schlehenweg 15, 88471 Baustetten, Germany
31 *
32 * Thomas.Nau@rz.uni-ulm.de
33 */
34
35
36 #ifdef HAVE_CONFIG_H
37 #include "config.h"
38 #endif
39
40 #include <stdlib.h>
41 #ifdef HAVE_STRING_H
42 #include <string.h>
43 #endif
44 #include <memory.h>
45 #include <math.h>
46 #ifdef HAVE_UNISTD_H
47 #include <unistd.h>
48 #endif
49
50 #include "global.h"
51
52 #include "create.h"
53 #include "data.h"
54 #include "error.h"
55 #include "misc.h"
56 #include "polygon.h"
57 #include "rubberband.h"
58 #include "rtree.h"
59 #include "search.h"
60
61 #ifdef HAVE_LIBDMALLOC
62 #include <dmalloc.h>
63 #endif
64
65 /* ---------------------------------------------------------------------------
66 * some local prototypes
67 */
68 static void CheckPadForRubberbandConnection (PadType *);
69 static void CheckPinForRubberbandConnection (PinType *);
70 static void CheckLinePointForRubberbandConnection (LayerType *,
71 LineType *,
72 PointType *,
73 bool);
74 static void CheckArcPointForRubberbandConnection (LayerType *Layer,
75 ArcType *Arc,
76 PointType *ArcPoint,
77 bool Exact);
78 static void CheckPolygonForRubberbandConnection (LayerType *,
79 PolygonType *);
80 static void CheckLinePointForRat (LayerType *, PointType *);
81 static int rubber_callback (const BoxType * b, void *cl);
82
83 struct rubber_info
84 {
85 Coord radius;
86 Coord X, Y;
87 LineType *line;
88 BoxType box;
89 LayerType *layer;
90 };
91
92 static int
rubber_callback(const BoxType * b,void * cl)93 rubber_callback (const BoxType * b, void *cl)
94 {
95 LineType *line = (LineType *) b;
96 struct rubber_info *i = (struct rubber_info *) cl;
97 double x, y, rad, dist1, dist2;
98 Coord t;
99 int touches = 0, n = 0 ;
100
101 t = line->Thickness / 2;
102
103 /* Check to see if the line is already in the rubberband list */
104 for (n = 0; n < Crosshair.AttachedObject.RubberbandN; n++)
105 if (Crosshair.AttachedObject.Rubberband[n].Line == line)
106 return 0;
107
108 if (TEST_FLAG (LOCKFLAG, line))
109 return 0;
110 if (line == i->line)
111 return 0;
112 /*
113 * Check to see if the line touches a rectangular region.
114 * To do this we need to look for the intersection of a circular
115 * region and a rectangular region.
116 */
117 if (i->radius == 0)
118 {
119 int found = 0;
120
121 if (line->Point1.X + t >= i->box.X1 && line->Point1.X - t <= i->box.X2
122 && line->Point1.Y + t >= i->box.Y1
123 && line->Point1.Y - t <= i->box.Y2)
124 {
125 if (((i->box.X1 <= line->Point1.X) &&
126 (line->Point1.X <= i->box.X2)) ||
127 ((i->box.Y1 <= line->Point1.Y) &&
128 (line->Point1.Y <= i->box.Y2)))
129 {
130 /*
131 * The circle is positioned such that the closest point
132 * on the rectangular region boundary is not at a corner
133 * of the rectangle. i.e. the shortest line from circle
134 * center to rectangle intersects the rectangle at 90
135 * degrees. In this case our first test is sufficient
136 */
137 touches = 1;
138 }
139 else
140 {
141 /*
142 * Now we must check the distance from the center of the
143 * circle to the corners of the rectangle since the
144 * closest part of the rectangular region is the corner.
145 */
146 x = MIN (abs (i->box.X1 - line->Point1.X),
147 abs (i->box.X2 - line->Point1.X));
148 x *= x;
149 y = MIN (abs (i->box.Y1 - line->Point1.Y),
150 abs (i->box.Y2 - line->Point1.Y));
151 y *= y;
152 x = x + y - (t * t);
153
154 if (x <= 0)
155 touches = 1;
156 }
157 if (touches)
158 {
159 CreateNewRubberbandEntry (i->layer, line, &line->Point1);
160 found++;
161 }
162 }
163 if (line->Point2.X + t >= i->box.X1 && line->Point2.X - t <= i->box.X2
164 && line->Point2.Y + t >= i->box.Y1
165 && line->Point2.Y - t <= i->box.Y2)
166 {
167 if (((i->box.X1 <= line->Point2.X) &&
168 (line->Point2.X <= i->box.X2)) ||
169 ((i->box.Y1 <= line->Point2.Y) &&
170 (line->Point2.Y <= i->box.Y2)))
171 {
172 touches = 1;
173 }
174 else
175 {
176 x = MIN (abs (i->box.X1 - line->Point2.X),
177 abs (i->box.X2 - line->Point2.X));
178 x *= x;
179 y = MIN (abs (i->box.Y1 - line->Point2.Y),
180 abs (i->box.Y2 - line->Point2.Y));
181 y *= y;
182 x = x + y - (t * t);
183
184 if (x <= 0)
185 touches = 1;
186 }
187 if (touches)
188 {
189 CreateNewRubberbandEntry (i->layer, line, &line->Point2);
190 found++;
191 }
192 }
193 return found;
194 }
195 /* circular search region */
196 if (i->radius < 0)
197 rad = 0; /* require exact match */
198 else
199 rad = SQUARE(i->radius + t);
200
201 x = (i->X - line->Point1.X);
202 x *= x;
203 y = (i->Y - line->Point1.Y);
204 y *= y;
205 dist1 = x + y - rad;
206
207 x = (i->X - line->Point2.X);
208 x *= x;
209 y = (i->Y - line->Point2.Y);
210 y *= y;
211 dist2 = x + y - rad;
212
213 if (dist1 > 0 && dist2 > 0)
214 return 0;
215
216 #ifdef CLOSEST_ONLY /* keep this to remind me */
217 if (dist1 < dist2)
218 CreateNewRubberbandEntry (i->layer, line, &line->Point1);
219 else
220 CreateNewRubberbandEntry (i->layer, line, &line->Point2);
221 #else
222 if (dist1 <= 0)
223 CreateNewRubberbandEntry (i->layer, line, &line->Point1);
224 if (dist2 <= 0)
225 CreateNewRubberbandEntry (i->layer, line, &line->Point2);
226 #endif
227 return 1;
228 }
229
230 /*!
231 * \brief Checks all visible lines which belong to the same layergroup
232 * as the passed pad.
233 *
234 * If one of the endpoints of the line lays inside the pad, the line is
235 * added to the 'rubberband' list.
236 */
237 static void
CheckPadForRubberbandConnection(PadType * Pad)238 CheckPadForRubberbandConnection (PadType *Pad)
239 {
240 Coord half = Pad->Thickness / 2;
241 Cardinal group;
242 struct rubber_info info;
243
244 info.box.X1 = MIN (Pad->Point1.X, Pad->Point2.X) - half;
245 info.box.Y1 = MIN (Pad->Point1.Y, Pad->Point2.Y) - half;
246 info.box.X2 = MAX (Pad->Point1.X, Pad->Point2.X) + half;
247 info.box.Y2 = MAX (Pad->Point1.Y, Pad->Point2.Y) + half;
248 info.radius = 0;
249 info.line = NULL;
250 group = GetLayerGroupNumberBySide (
251 TEST_FLAG (ONSOLDERFLAG, Pad) ? BOTTOM_SIDE : TOP_SIDE);
252
253 /* check all visible layers in the same group */
254 GROUP_LOOP (PCB->Data, group);
255 {
256 /* check all visible lines of the group member */
257 info.layer = layer;
258 if (info.layer->On)
259 {
260 r_search (info.layer->line_tree, &info.box, NULL, rubber_callback,
261 &info);
262 }
263 }
264 END_LOOP;
265 }
266
267 struct rinfo
268 {
269 int type;
270 Cardinal group;
271 PinType *pin;
272 PadType *pad;
273 PointType *point;
274 };
275
276 static int
rat_callback(const BoxType * box,void * cl)277 rat_callback (const BoxType * box, void *cl)
278 {
279 RatType *rat = (RatType *) box;
280 struct rinfo *i = (struct rinfo *) cl;
281
282 switch (i->type)
283 {
284 case PIN_TYPE:
285 if (rat->Point1.X == i->pin->X && rat->Point1.Y == i->pin->Y)
286 CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point1);
287 else if (rat->Point2.X == i->pin->X && rat->Point2.Y == i->pin->Y)
288 CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point2);
289 break;
290 case PAD_TYPE:
291 if (rat->Point1.X == i->pad->Point1.X &&
292 rat->Point1.Y == i->pad->Point1.Y && rat->group1 == i->group)
293 CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point1);
294 else
295 if (rat->Point2.X == i->pad->Point1.X &&
296 rat->Point2.Y == i->pad->Point1.Y && rat->group2 == i->group)
297 CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point2);
298 else
299 if (rat->Point1.X == i->pad->Point2.X &&
300 rat->Point1.Y == i->pad->Point2.Y && rat->group1 == i->group)
301 CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point1);
302 else
303 if (rat->Point2.X == i->pad->Point2.X &&
304 rat->Point2.Y == i->pad->Point2.Y && rat->group2 == i->group)
305 CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point2);
306 else
307 if (rat->Point1.X == (i->pad->Point1.X + i->pad->Point2.X) / 2 &&
308 rat->Point1.Y == (i->pad->Point1.Y + i->pad->Point2.Y) / 2 &&
309 rat->group1 == i->group)
310 CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point1);
311 else
312 if (rat->Point2.X == (i->pad->Point1.X + i->pad->Point2.X) / 2 &&
313 rat->Point2.Y == (i->pad->Point1.Y + i->pad->Point2.Y) / 2 &&
314 rat->group2 == i->group)
315 CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point2);
316 break;
317 case LINEPOINT_TYPE:
318 if (rat->group1 == i->group &&
319 rat->Point1.X == i->point->X && rat->Point1.Y == i->point->Y)
320 CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point1);
321 else
322 if (rat->group2 == i->group &&
323 rat->Point2.X == i->point->X && rat->Point2.Y == i->point->Y)
324 CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point2);
325 break;
326 default:
327 Message ("hace: bad rubber-rat lookup callback\n");
328 }
329 return 0;
330 }
331
332 static void
CheckPadForRat(PadType * Pad)333 CheckPadForRat (PadType *Pad)
334 {
335 struct rinfo info;
336
337 info.group = GetLayerGroupNumberBySide (
338 TEST_FLAG (ONSOLDERFLAG, Pad) ? BOTTOM_SIDE : TOP_SIDE);
339 info.pad = Pad;
340 info.type = PAD_TYPE;
341
342 r_search (PCB->Data->rat_tree, &Pad->BoundingBox, NULL, rat_callback,
343 &info);
344 }
345
346 static void
CheckPinForRat(PinType * Pin)347 CheckPinForRat (PinType *Pin)
348 {
349 struct rinfo info;
350
351 info.type = PIN_TYPE;
352 info.pin = Pin;
353 r_search (PCB->Data->rat_tree, &Pin->BoundingBox, NULL, rat_callback,
354 &info);
355 }
356
357 static void
CheckLinePointForRat(LayerType * Layer,PointType * Point)358 CheckLinePointForRat (LayerType *Layer, PointType *Point)
359 {
360 struct rinfo info;
361 info.group = GetLayerGroupNumberByPointer (Layer);
362 info.point = Point;
363 info.type = LINEPOINT_TYPE;
364
365 r_search (PCB->Data->rat_tree, (BoxType *) Point, NULL, rat_callback,
366 &info);
367 }
368
369 /*!
370 * \brief Checks all visible lines.
371 *
372 * If one of the endpoints of the line lays inside the pin, the line is
373 * added to the 'rubberband' list.
374 *
375 * Square pins are handled as if they were round.
376 *
377 * Speed and readability is more important then the few % of failures
378 * that are immediately recognized.
379 */
380 static void
CheckPinForRubberbandConnection(PinType * Pin)381 CheckPinForRubberbandConnection (PinType *Pin)
382 {
383 struct rubber_info info;
384 Cardinal n;
385 Coord t = Pin->Thickness / 2;
386
387 info.box.X1 = Pin->X - t;
388 info.box.X2 = Pin->X + t;
389 info.box.Y1 = Pin->Y - t;
390 info.box.Y2 = Pin->Y + t;
391 info.line = NULL;
392 if (TEST_FLAG (SQUAREFLAG, Pin))
393 info.radius = 0;
394 else
395 {
396 info.radius = t;
397 info.X = Pin->X;
398 info.Y = Pin->Y;
399 }
400
401 for (n = 0; n < max_copper_layer; n++)
402 {
403 info.layer = LAYER_PTR (n);
404 r_search (info.layer->line_tree, &info.box, NULL, rubber_callback,
405 &info);
406 }
407 }
408
409 /*!
410 * \brief Checks all visible lines which belong to the same group as the
411 * passed line.
412 *
413 * If one of the endpoints of the line lays * inside the passed line,
414 * the scanned line is added to the 'rubberband' list.
415 */
416 static void
CheckLinePointForRubberbandConnection(LayerType * Layer,LineType * Line,PointType * LinePoint,bool Exact)417 CheckLinePointForRubberbandConnection (LayerType *Layer,
418 LineType *Line,
419 PointType *LinePoint,
420 bool Exact)
421 {
422 Cardinal group;
423 struct rubber_info info;
424 Coord t = Line->Thickness / 2;
425
426 /* lookup layergroup and check all visible lines in this group */
427 info.radius = Exact ? -1 : MAX(Line->Thickness / 2, 1);
428 info.box.X1 = LinePoint->X - t;
429 info.box.X2 = LinePoint->X + t;
430 info.box.Y1 = LinePoint->Y - t;
431 info.box.Y2 = LinePoint->Y + t;
432 info.line = Line;
433 info.X = LinePoint->X;
434 info.Y = LinePoint->Y;
435 group = GetLayerGroupNumberByPointer (Layer);
436 GROUP_LOOP (PCB->Data, group);
437 {
438 /* check all visible lines of the group member */
439 if (layer->On)
440 {
441 info.layer = layer;
442 r_search (layer->line_tree, &info.box, NULL, rubber_callback, &info);
443 }
444 }
445 END_LOOP;
446 }
447
448 /*!
449 * \brief Checks all visible lines which belong to the same group as the
450 * passed arc.
451 *
452 * If one of the endpoints of the line lays inside the passed arc,
453 * the scanned line is added to the 'rubberband' list
454 */
455 static void
CheckArcPointForRubberbandConnection(LayerType * Layer,ArcType * Arc,PointType * ArcPoint,bool Exact)456 CheckArcPointForRubberbandConnection (LayerType *Layer,
457 ArcType *Arc,
458 PointType *ArcPoint,
459 bool Exact)
460 {
461 Cardinal group;
462 struct rubber_info info;
463 Coord t = Arc->Thickness / 2;
464
465 /* lookup layergroup and check all visible lines in this group */
466 info.radius = Exact ? -1 : MAX(Arc->Thickness / 2, 1);
467 info.box.X1 = ArcPoint->X - t;
468 info.box.X2 = ArcPoint->X + t;
469 info.box.Y1 = ArcPoint->Y - t;
470 info.box.Y2 = ArcPoint->Y + t;
471 info.line = NULL;
472 info.X = ArcPoint->X;
473 info.Y = ArcPoint->Y;
474 group = GetLayerGroupNumberByPointer (Layer);
475 GROUP_LOOP (PCB->Data, group);
476 {
477 /* check all visible lines of the group member */
478 if (layer->On)
479 {
480 info.layer = layer;
481 r_search (layer->line_tree, &info.box, NULL, rubber_callback, &info);
482 }
483 }
484 END_LOOP;
485 }
486
487 /* ---------------------------------------------------------------------------
488 * checks all visible lines which belong to the same group as the passed polygon.
489 * If one of the endpoints of the line lays inside the passed polygon,
490 * the scanned line is added to the 'rubberband' list.
491 */
492 static void
CheckPolygonForRubberbandConnection(LayerType * Layer,PolygonType * Polygon)493 CheckPolygonForRubberbandConnection (LayerType *Layer,
494 PolygonType *Polygon)
495 {
496 Cardinal group;
497
498 /* lookup layergroup and check all visible lines in this group */
499 group = GetLayerGroupNumberByPointer (Layer);
500 GROUP_LOOP (PCB->Data, group);
501 {
502 if (layer->On)
503 {
504 Coord thick;
505
506 /* the following code just stupidly compares the endpoints
507 * of the lines
508 */
509 LINE_LOOP (layer);
510 {
511 if (TEST_FLAG (LOCKFLAG, line))
512 continue;
513 if (TEST_FLAG (CLEARLINEFLAG, line))
514 continue;
515 thick = (line->Thickness + 1) / 2;
516 if (IsPointInPolygon (line->Point1.X, line->Point1.Y,
517 thick, Polygon))
518 CreateNewRubberbandEntry (layer, line, &line->Point1);
519 if (IsPointInPolygon (line->Point2.X, line->Point2.Y,
520 thick, Polygon))
521 CreateNewRubberbandEntry (layer, line, &line->Point2);
522 }
523 END_LOOP;
524 }
525 }
526 END_LOOP;
527 }
528
529 /*!
530 * \brief Lookup all lines that are connected to an object and save the
531 * data to 'Crosshair.AttachedObject.Rubberband'.
532 *
533 * Lookup is only done for visible layers.
534 */
535 void
LookupRubberbandLines(int Type,void * Ptr1,void * Ptr2,void * Ptr3)536 LookupRubberbandLines (int Type, void *Ptr1, void *Ptr2, void *Ptr3)
537 {
538
539 /* the function is only supported for some types
540 * check all visible lines;
541 * it is only necessary to check if one of the endpoints
542 * is connected
543 */
544 switch (Type)
545 {
546 case ELEMENT_TYPE:
547 {
548 ElementType *element = (ElementType *) Ptr1;
549
550 /* square pins are handled as if they are round. Speed
551 * and readability is more important then the few %
552 * of failures that are immediately recognized
553 */
554 PIN_LOOP (element);
555 {
556 CheckPinForRubberbandConnection (pin);
557 }
558 END_LOOP;
559 PAD_LOOP (element);
560 {
561 CheckPadForRubberbandConnection (pad);
562 }
563 END_LOOP;
564 break;
565 }
566
567 case LINE_TYPE:
568 {
569 LayerType *layer = (LayerType *) Ptr1;
570 LineType *line = (LineType *) Ptr2;
571 if (GetLayerNumber (PCB->Data, layer) < max_copper_layer)
572 {
573 CheckLinePointForRubberbandConnection (layer, line,
574 &line->Point1, false);
575 CheckLinePointForRubberbandConnection (layer, line,
576 &line->Point2, false);
577 }
578 break;
579 }
580
581 case LINEPOINT_TYPE:
582 if (GetLayerNumber (PCB->Data, (LayerType *) Ptr1) < max_copper_layer)
583 CheckLinePointForRubberbandConnection ((LayerType *) Ptr1,
584 (LineType *) Ptr2,
585 (PointType *) Ptr3, true);
586 break;
587
588 case ARC_TYPE:
589 {
590 LayerType *layer = (LayerType *) Ptr1;
591 ArcType *arc = (ArcType *) Ptr2;
592 if (GetLayerNumber (PCB->Data, layer) < max_copper_layer)
593 {
594 CheckArcPointForRubberbandConnection (layer, arc,
595 &arc->Point1, false);
596 CheckArcPointForRubberbandConnection (layer, arc,
597 &arc->Point2, false);
598 }
599 break;
600 }
601
602 case VIA_TYPE:
603 CheckPinForRubberbandConnection ((PinType *) Ptr1);
604 break;
605
606 case POLYGON_TYPE:
607 if (GetLayerNumber (PCB->Data, (LayerType *) Ptr1) < max_copper_layer)
608 CheckPolygonForRubberbandConnection ((LayerType *) Ptr1,
609 (PolygonType *) Ptr2);
610 break;
611 }
612 }
613
614 void
LookupRatLines(int Type,void * Ptr1,void * Ptr2,void * Ptr3)615 LookupRatLines (int Type, void *Ptr1, void *Ptr2, void *Ptr3)
616 {
617 switch (Type)
618 {
619 case ELEMENT_TYPE:
620 {
621 ElementType *element = (ElementType *) Ptr1;
622
623 PIN_LOOP (element);
624 {
625 CheckPinForRat (pin);
626 }
627 END_LOOP;
628 PAD_LOOP (element);
629 {
630 CheckPadForRat (pad);
631 }
632 END_LOOP;
633 break;
634 }
635
636 case LINE_TYPE:
637 {
638 LayerType *layer = (LayerType *) Ptr1;
639 LineType *line = (LineType *) Ptr2;
640
641 CheckLinePointForRat (layer, &line->Point1);
642 CheckLinePointForRat (layer, &line->Point2);
643 break;
644 }
645
646 case LINEPOINT_TYPE:
647 CheckLinePointForRat ((LayerType *) Ptr1, (PointType *) Ptr3);
648 break;
649
650 case VIA_TYPE:
651 CheckPinForRat ((PinType *) Ptr1);
652 break;
653 }
654 }
655