6 * PCB, interactive printed circuit board design
7 * Copyright (C) 1994,1995,1996 Thomas Nau
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; either version 2 of the License, or
12 * (at your option) any later version.
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software
21 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
23 * Contact addresses for paper mail and Email:
24 * Thomas Nau, Schlehenweg 15, 88471 Baustetten, Germany
25 * Thomas.Nau@rz.uni-ulm.de
32 Here's a brief tour of the data and life of a polygon, courtesy of Ben
35 A PCB PolygonType contains an array of points outlining the polygon.
36 This is what is manipulated by the UI and stored in the saved PCB.
38 A PolygonType also contains a POLYAREA called 'Clipped' which is
39 computed dynamically by InitClip every time a board is loaded. The
40 point array is coverted to a POLYAREA by original_poly and then holes
41 are cut in it by clearPoly. After that it is maintained dynamically
42 as parts are added, moved or removed (this is why sometimes bugs can
43 be fixed by just re-loading the board).
45 A POLYAREA consists of a linked list of PLINE structures. The head of
46 that list is POLYAREA.contours. The first contour is an outline of a
47 filled region. All of the subsequent PLINEs are holes cut out of that
48 first contour. POLYAREAs are in a doubly-linked list and each member
49 of the list is an independent (non-overlapping) area with its own
50 outline and holes. The function biggest() finds the largest POLYAREA
51 so that PolygonType.Clipped points to that shape. The rest of the
52 polygon still exists, it's just ignored when turning the polygon into
55 The first POLYAREA in PolygonType.Clipped is what is used for the vast
56 majority of Polygon related tests. The basic logic for an
57 intersection is "is the target shape inside POLYAREA.contours and NOT
58 fully enclosed in any of POLYAREA.contours.next... (the holes)".
60 The polygon dicer (NoHolesPolygonDicer and r_NoHolesPolygonDicer)
61 emits a series of "simple" PLINE shapes. That is, the PLINE isn't
62 linked to any other "holes" oulines). That's the meaning of the first
63 test in r_NoHolesPolygonDicer. It is testing to see if the PLINE
64 contour (the first, making it a solid outline) has a valid next
65 pointer (which would point to one or more holes). The dicer works by
66 recursively chopping the polygon in half through the first hole it
67 sees (which is guaranteed to eliminate at least that one hole). The
68 dicer output is used for HIDs which cannot render things with holes
69 (which would require erasure).
73 /* special polygon editing routines
88 #include "crosshair.h"
103 #ifdef HAVE_LIBDMALLOC
109 #define ROUND(x) ((long)(((x) >= 0 ? (x) + 0.5 : (x) - 0.5)))
111 #define UNSUBTRACT_BLOAT 10
113 /* ---------------------------------------------------------------------------
118 static double circleVerticies
[] = {
120 0.98480775301221, 0.17364817766693,
125 biggest (POLYAREA
* p
)
127 POLYAREA
*n
, *top
= NULL
;
136 if (n
->contours
->area
< PCB
->IsleArea
)
140 poly_DelContour (&n
->contours
);
151 if (n
->contours
->area
> big
)
154 big
= n
->contours
->area
;
157 while ((n
= n
->f
) != p
);
162 top
->contours
= p
->contours
;
171 ContourToPoly (PLINE
* contour
)
174 poly_PreContour (contour
, TRUE
);
175 assert (contour
->Flags
.orient
== PLF_DIR
);
176 if (!(p
= poly_Create ()))
178 poly_InclContour (p
, contour
);
179 assert (poly_Valid (p
));
184 original_poly (PolygonType
* p
)
186 PLINE
*contour
= NULL
;
190 /* first make initial polygon contour */
191 POLYGONPOINT_LOOP (p
);
197 if ((contour
= poly_NewContour (v
)) == NULL
)
202 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
206 poly_PreContour (contour
, TRUE
);
207 /* make sure it is a positive contour */
208 if ((contour
->Flags
.orient
) != PLF_DIR
)
209 poly_InvContour (contour
);
210 assert ((contour
->Flags
.orient
) == PLF_DIR
);
211 if ((np
= poly_Create ()) == NULL
)
213 poly_InclContour (np
, contour
);
214 assert (poly_Valid (np
));
219 ClipOriginal (PolygonType
* poly
)
221 POLYAREA
*p
, *result
;
224 p
= original_poly (poly
);
225 r
= poly_Boolean_free (poly
->Clipped
, p
, &result
, PBO_ISECT
);
228 fprintf (stderr
, "Error while clipping PBO_ISECT: %d\n", r
);
230 poly
->Clipped
= NULL
;
233 poly
->Clipped
= biggest (result
);
234 assert (!poly
->Clipped
|| poly_Valid (poly
->Clipped
));
239 RectPoly (LocationType x1
, LocationType x2
, LocationType y1
, LocationType y2
)
241 PLINE
*contour
= NULL
;
248 if ((contour
= poly_NewContour (v
)) == NULL
)
252 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
255 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
258 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
259 return ContourToPoly (contour
);
263 OctagonPoly (LocationType x
, LocationType y
, BDimension radius
)
265 PLINE
*contour
= NULL
;
268 v
[0] = x
+ ROUND (radius
* 0.5);
269 v
[1] = y
+ ROUND (radius
* TAN_22_5_DEGREE_2
);
270 if ((contour
= poly_NewContour (v
)) == NULL
)
272 v
[0] = x
+ ROUND (radius
* TAN_22_5_DEGREE_2
);
273 v
[1] = y
+ ROUND (radius
* 0.5);
274 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
275 v
[0] = x
- (v
[0] - x
);
276 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
277 v
[0] = x
- ROUND (radius
* 0.5);
278 v
[1] = y
+ ROUND (radius
* TAN_22_5_DEGREE_2
);
279 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
280 v
[1] = y
- (v
[1] - y
);
281 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
282 v
[0] = x
- ROUND (radius
* TAN_22_5_DEGREE_2
);
283 v
[1] = y
- ROUND (radius
* 0.5);
284 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
285 v
[0] = x
- (v
[0] - x
);
286 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
287 v
[0] = x
+ ROUND (radius
* 0.5);
288 v
[1] = y
- ROUND (radius
* TAN_22_5_DEGREE_2
);
289 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
290 return ContourToPoly (contour
);
293 /* add verticies in a fractional-circle starting from v
294 * centered at X, Y and going counter-clockwise
295 * does not include the first point
296 * last argument is 1 for a full circle
297 * 2 for a half circle
298 * or 4 for a quarter circle
301 frac_circle (PLINE
* c
, LocationType X
, LocationType Y
, Vector v
, int range
)
306 poly_InclVertex (c
->head
.prev
, poly_CreateNode (v
));
307 /* move vector to origin */
311 range
= range
== 1 ? CIRC_SEGS
-1 : (CIRC_SEGS
/ range
);
312 for (i
= 0; i
< range
; i
++)
314 /* rotate the vector */
315 t1
= e1
* circleVerticies
[2] - e2
* circleVerticies
[3];
316 e2
= e1
* circleVerticies
[3] + e2
* circleVerticies
[2];
318 v
[0] = X
+ ROUND (e1
);
319 v
[1] = Y
+ ROUND (e2
);
320 poly_InclVertex (c
->head
.prev
, poly_CreateNode (v
));
324 #define COARSE_CIRCLE 0
325 /* create a 35-vertex circle approximation */
327 CirclePoly (LocationType x
, LocationType y
, BDimension radius
)
336 if ((contour
= poly_NewContour (v
)) == NULL
)
338 frac_circle (contour
, x
, y
, v
, 1);
339 return ContourToPoly (contour
);
342 /* make a rounded-corner rectangle with radius t beyond x1,x2,y1,y2 rectangle */
344 RoundRect (LocationType x1
, LocationType x2
, LocationType y1
, LocationType y2
,
347 PLINE
*contour
= NULL
;
354 if ((contour
= poly_NewContour (v
)) == NULL
)
356 frac_circle (contour
, x1
, y1
, v
, 4);
359 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
360 frac_circle (contour
, x2
, y1
, v
, 4);
363 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
364 frac_circle (contour
, x2
, y2
, v
, 4);
367 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
368 frac_circle (contour
, x1
, y2
, v
, 4);
369 return ContourToPoly (contour
);
374 ArcPolyNoIntersect (ArcType
* a
, BDimension thick
)
376 PLINE
*contour
= NULL
;
381 double ang
, da
, rx
, ry
;
388 a
->StartAngle
+= a
->Delta
;
389 a
->Delta
= -a
->Delta
;
391 half
= (thick
+ 1) / 2;
392 ends
= GetArcEnds (a
);
393 /* start with inner radius */
394 rx
= MAX (a
->Width
- half
, 0);
395 ry
= MAX (a
->Height
- half
, 0);
396 segs
= a
->Delta
/ ARC_ANGLE
;
398 da
= (1.0 * a
->Delta
) / segs
;
399 v
[0] = a
->X
- rx
* cos (ang
* M180
);
400 v
[1] = a
->Y
+ ry
* sin (ang
* M180
);
401 if ((contour
= poly_NewContour (v
)) == NULL
)
403 for (i
= 0; i
< segs
- 1; i
++)
406 v
[0] = a
->X
- rx
* cos (ang
* M180
);
407 v
[1] = a
->Y
+ ry
* sin (ang
* M180
);
408 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
410 /* find last point */
411 ang
= a
->StartAngle
+ a
->Delta
;
412 v
[0] = a
->X
- rx
* cos (ang
* M180
);
413 v
[1] = a
->Y
+ ry
* sin (ang
* M180
);
414 /* add the round cap at the end */
415 frac_circle (contour
, ends
->X2
, ends
->Y2
, v
, 2);
416 /* and now do the outer arc (going backwards) */
417 rx
= a
->Width
+ half
;
418 ry
= a
->Width
+ half
;
420 for (i
= 0; i
< segs
; i
++)
422 v
[0] = a
->X
- rx
* cos (ang
* M180
);
423 v
[1] = a
->Y
+ ry
* sin (ang
* M180
);
424 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
427 /* now add other round cap */
429 v
[0] = a
->X
- rx
* cos (ang
* M180
);
430 v
[1] = a
->Y
+ ry
* sin (ang
* M180
);
431 frac_circle (contour
, ends
->X1
, ends
->Y1
, v
, 2);
432 /* now we have the whole contour */
433 if (!(np
= ContourToPoly (contour
)))
438 #define MIN_CLEARANCE_BEFORE_BISECT 10.
440 ArcPoly (ArcType
* a
, BDimension thick
)
444 POLYAREA
*tmp1
, *tmp2
, *res
;
446 delta
= (a
->Delta
< 0) ? -a
->Delta
: a
->Delta
;
448 /* If the arc segment would self-intersect, we need to construct it as the union of
449 two non-intersecting segments */
451 if (2 * M_PI
* a
->Width
* (1. - (double)delta
/ 360.) - thick
< MIN_CLEARANCE_BEFORE_BISECT
)
453 int half_delta
= a
->Delta
/ 2;
456 seg1
.Delta
= half_delta
;
457 seg2
.Delta
-= half_delta
;
458 seg2
.StartAngle
+= half_delta
;
460 tmp1
= ArcPolyNoIntersect (&seg1
, thick
);
461 tmp2
= ArcPolyNoIntersect (&seg2
, thick
);
462 poly_Boolean_free (tmp1
, tmp2
, &res
, PBO_UNITE
);
466 return ArcPolyNoIntersect (a
, thick
);
470 LinePoly (LineType
* L
, BDimension thick
)
472 PLINE
*contour
= NULL
;
476 long half
;LineType _l
=*L
,*l
=&_l
;
480 half
= (thick
+ 1) / 2;
482 sqrt (SQUARE (l
->Point1
.X
- l
->Point2
.X
) +
483 SQUARE (l
->Point1
.Y
- l
->Point2
.Y
));
484 if (!TEST_FLAG (SQUAREFLAG
,l
))
485 if (d
== 0) /* line is a point */
486 return CirclePoly (l
->Point1
.X
, l
->Point1
.Y
, half
);
490 dx
= (l
->Point1
.Y
- l
->Point2
.Y
) * d
;
491 dy
= (l
->Point2
.X
- l
->Point1
.X
) * d
;
498 if (TEST_FLAG (SQUAREFLAG
,l
))/* take into account the ends */
505 v
[0] = l
->Point1
.X
- dx
;
506 v
[1] = l
->Point1
.Y
- dy
;
507 if ((contour
= poly_NewContour (v
)) == NULL
)
509 v
[0] = l
->Point2
.X
- dx
;
510 v
[1] = l
->Point2
.Y
- dy
;
511 if (TEST_FLAG (SQUAREFLAG
,l
))
512 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
514 frac_circle (contour
, l
->Point2
.X
, l
->Point2
.Y
, v
, 2);
515 v
[0] = l
->Point2
.X
+ dx
;
516 v
[1] = l
->Point2
.Y
+ dy
;
517 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
518 v
[0] = l
->Point1
.X
+ dx
;
519 v
[1] = l
->Point1
.Y
+ dy
;
520 if (TEST_FLAG (SQUAREFLAG
,l
))
521 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
523 frac_circle (contour
, l
->Point1
.X
, l
->Point1
.Y
, v
, 2);
524 /* now we have the line contour */
525 if (!(np
= ContourToPoly (contour
)))
530 /* make a rounded-corner rectangle */
532 SquarePadPoly (PadType
* pad
, BDimension clear
)
534 PLINE
*contour
= NULL
;
540 PadType _t
=*pad
,*t
=&_t
;
541 PadType _c
=*pad
,*c
=&_c
;
542 int halfthick
= (pad
->Thickness
+ 1) / 2;
543 int halfclear
= (clear
+ 1) / 2;
546 sqrt (SQUARE (pad
->Point1
.X
- pad
->Point2
.X
) +
547 SQUARE (pad
->Point1
.Y
- pad
->Point2
.Y
));
550 double a
= halfthick
/ d
;
551 tx
= (t
->Point1
.Y
- t
->Point2
.Y
) * a
;
552 ty
= (t
->Point2
.X
- t
->Point1
.X
) * a
;
554 cx
= (c
->Point1
.Y
- c
->Point2
.Y
) * a
;
555 cy
= (c
->Point2
.X
- c
->Point1
.X
) * a
;
579 v
[0] = c
->Point1
.X
- tx
;
580 v
[1] = c
->Point1
.Y
- ty
;
581 if ((contour
= poly_NewContour (v
)) == NULL
)
583 frac_circle (contour
, (t
->Point1
.X
- tx
), (t
->Point1
.Y
- ty
), v
, 4);
585 v
[0] = t
->Point2
.X
- cx
;
586 v
[1] = t
->Point2
.Y
- cy
;
587 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
588 frac_circle (contour
, (t
->Point2
.X
- tx
), (t
->Point2
.Y
- ty
), v
, 4);
590 v
[0] = c
->Point2
.X
+ tx
;
591 v
[1] = c
->Point2
.Y
+ ty
;
592 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
593 frac_circle (contour
, (t
->Point2
.X
+ tx
), (t
->Point2
.Y
+ ty
), v
, 4);
595 v
[0] = t
->Point1
.X
+ cx
;
596 v
[1] = t
->Point1
.Y
+ cy
;
597 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
598 frac_circle (contour
, (t
->Point1
.X
+ tx
), (t
->Point1
.Y
+ ty
), v
, 4);
600 /* now we have the line contour */
601 if (!(np
= ContourToPoly (contour
)))
606 /* clear np1 from the polygon */
608 Subtract (POLYAREA
* np1
, PolygonType
* p
, Boolean fnp
)
610 POLYAREA
*merged
= NULL
, *np
= np1
;
620 assert (poly_Valid (p
->Clipped
));
621 assert (poly_Valid (np
));
623 x
= poly_Boolean_free (p
->Clipped
, np
, &merged
, PBO_SUB
);
626 x
= poly_Boolean (p
->Clipped
, np
, &merged
, PBO_SUB
);
627 poly_Free (&p
->Clipped
);
629 assert (!merged
|| poly_Valid (merged
));
632 fprintf (stderr
, "Error while clipping PBO_SUB: %d\n", x
);
637 p
->Clipped
= biggest (merged
);
638 assert (!p
->Clipped
|| poly_Valid (p
->Clipped
));
640 Message ("Polygon cleared out of existence near (%d, %d)\n",
641 (p
->BoundingBox
.X1
+ p
->BoundingBox
.X2
) / 2,
642 (p
->BoundingBox
.Y1
+ p
->BoundingBox
.Y2
) / 2);
646 /* create a polygon of the pin clearance */
648 PinPoly (PinType
* pin
, BDimension thick
, BDimension clear
)
652 if (TEST_FLAG (SQUAREFLAG
, pin
))
654 size
= (thick
+ 1) / 2;
655 return RoundRect (pin
->X
- size
, pin
->X
+ size
, pin
->Y
- size
,
656 pin
->Y
+ size
, (clear
+ 1) / 2);
660 size
= (thick
+ clear
+ 1) / 2;
661 if (TEST_FLAG (OCTAGONFLAG
, pin
))
663 return OctagonPoly (pin
->X
, pin
->Y
, size
+ size
);
666 return CirclePoly (pin
->X
, pin
->Y
, size
);
670 BoxPolyBloated (BoxType
*box
, BDimension bloat
)
672 return RectPoly (box
->X1
- bloat
, box
->X2
+ bloat
,
673 box
->Y1
- bloat
, box
->Y2
+ bloat
);
676 /* remove the pin clearance from the polygon */
678 SubtractPin (DataType
* d
, PinType
* pin
, LayerType
* l
, PolygonType
* p
)
683 if (pin
->Clearance
== 0)
685 i
= GetLayerNumber (d
, l
);
686 if (TEST_THERM (i
, pin
))
688 np
= ThermPoly ((PCBTypePtr
) (d
->pcb
), pin
, i
);
694 np
= PinPoly (pin
, pin
->Thickness
, pin
->Clearance
);
698 return Subtract (np
, p
, TRUE
);
702 SubtractLine (LineType
* line
, PolygonType
* p
)
706 if (!TEST_FLAG (CLEARLINEFLAG
, line
))
708 if (!(np
= LinePoly (line
, line
->Thickness
+ line
->Clearance
)))
710 return Subtract (np
, p
, True
);
714 SubtractArc (ArcType
* arc
, PolygonType
* p
)
718 if (!TEST_FLAG (CLEARLINEFLAG
, arc
))
720 if (!(np
= ArcPoly (arc
, arc
->Thickness
+ arc
->Clearance
)))
722 return Subtract (np
, p
, True
);
726 SubtractText (TextType
* text
, PolygonType
* p
)
729 const BoxType
*b
= &text
->BoundingBox
;
731 if (!TEST_FLAG (CLEARLINEFLAG
, text
))
733 if (!(np
= RoundRect (b
->X1
+ PCB
->Bloat
, b
->X2
- PCB
->Bloat
,
734 b
->Y1
+ PCB
->Bloat
, b
->Y2
- PCB
->Bloat
, PCB
->Bloat
)))
736 return Subtract (np
, p
, True
);
740 SubtractPad (PadType
* pad
, PolygonType
* p
)
744 if (TEST_FLAG (SQUAREFLAG
, pad
))
747 (np
= SquarePadPoly (pad
, pad
->Thickness
+ pad
->Clearance
)))
753 (np
= LinePoly ((LineType
*) pad
, pad
->Thickness
+ pad
->Clearance
)))
756 return Subtract (np
, p
, True
);
761 const BoxType
*other
;
764 PolygonType
*polygon
;
770 pin_sub_callback (const BoxType
* b
, void *cl
)
772 PinTypePtr pin
= (PinTypePtr
) b
;
773 struct cpInfo
*info
= (struct cpInfo
*) cl
;
774 PolygonTypePtr polygon
;
776 /* don't subtract the object that was put back! */
777 if (b
== info
->other
)
779 polygon
= info
->polygon
;
780 if (SubtractPin (info
->data
, pin
, info
->layer
, polygon
) < 0)
781 longjmp (info
->env
, 1);
786 arc_sub_callback (const BoxType
* b
, void *cl
)
788 ArcTypePtr arc
= (ArcTypePtr
) b
;
789 struct cpInfo
*info
= (struct cpInfo
*) cl
;
790 PolygonTypePtr polygon
;
792 /* don't subtract the object that was put back! */
793 if (b
== info
->other
)
795 if (!TEST_FLAG (CLEARLINEFLAG
, arc
))
797 polygon
= info
->polygon
;
798 if (SubtractArc (arc
, polygon
) < 0)
799 longjmp (info
->env
, 1);
804 pad_sub_callback (const BoxType
* b
, void *cl
)
806 PadTypePtr pad
= (PadTypePtr
) b
;
807 struct cpInfo
*info
= (struct cpInfo
*) cl
;
808 PolygonTypePtr polygon
;
810 /* don't subtract the object that was put back! */
811 if (b
== info
->other
)
813 polygon
= info
->polygon
;
814 if (XOR (TEST_FLAG (ONSOLDERFLAG
, pad
), !info
->solder
))
816 if (SubtractPad (pad
, polygon
) < 0)
817 longjmp (info
->env
, 1);
824 line_sub_callback (const BoxType
* b
, void *cl
)
826 LineTypePtr line
= (LineTypePtr
) b
;
827 struct cpInfo
*info
= (struct cpInfo
*) cl
;
828 PolygonTypePtr polygon
;
830 /* don't subtract the object that was put back! */
831 if (b
== info
->other
)
833 if (!TEST_FLAG (CLEARLINEFLAG
, line
))
835 polygon
= info
->polygon
;
836 if (SubtractLine (line
, polygon
) < 0)
837 longjmp (info
->env
, 1);
842 text_sub_callback (const BoxType
* b
, void *cl
)
844 TextTypePtr text
= (TextTypePtr
) b
;
845 struct cpInfo
*info
= (struct cpInfo
*) cl
;
846 PolygonTypePtr polygon
;
848 /* don't subtract the object that was put back! */
849 if (b
== info
->other
)
851 if (!TEST_FLAG (CLEARLINEFLAG
, text
))
853 polygon
= info
->polygon
;
854 if (SubtractText (text
, polygon
) < 0)
855 longjmp (info
->env
, 1);
860 Group (DataTypePtr Data
, Cardinal layer
)
863 for (i
= 0; i
< max_layer
; i
++)
864 for (j
= 0; j
< ((PCBType
*) (Data
->pcb
))->LayerGroups
.Number
[i
]; j
++)
865 if (layer
== ((PCBType
*) (Data
->pcb
))->LayerGroups
.Entries
[i
][j
])
871 clearPoly (DataTypePtr Data
, LayerTypePtr Layer
, PolygonType
* polygon
,
872 const BoxType
* here
, BDimension expand
)
879 if (!TEST_FLAG (CLEARPOLYFLAG
, polygon
)
880 || GetLayerNumber (Data
, Layer
) >= max_layer
)
882 group
= Group (Data
, GetLayerNumber (Data
, Layer
));
883 info
.solder
= (group
== Group (Data
, max_layer
+ SOLDER_LAYER
));
887 info
.polygon
= polygon
;
889 region
= clip_box (here
, &polygon
->BoundingBox
);
891 region
= polygon
->BoundingBox
;
892 region
= bloat_box (®ion
, expand
);
894 if (setjmp (info
.env
) == 0)
896 r
= r_search (Data
->via_tree
, ®ion
, NULL
, pin_sub_callback
, &info
);
897 r
+= r_search (Data
->pin_tree
, ®ion
, NULL
, pin_sub_callback
, &info
);
898 GROUP_LOOP (Data
, group
);
901 r_search (layer
->line_tree
, ®ion
, NULL
, line_sub_callback
,
904 r_search (layer
->arc_tree
, ®ion
, NULL
, arc_sub_callback
, &info
);
906 r_search (layer
->text_tree
, ®ion
, NULL
, text_sub_callback
, &info
);
909 if (info
.solder
|| group
== Group (Data
, max_layer
+ COMPONENT_LAYER
))
910 r
+= r_search (Data
->pad_tree
, ®ion
, NULL
, pad_sub_callback
, &info
);
916 Unsubtract (POLYAREA
* np1
, PolygonType
* p
)
918 POLYAREA
*merged
= NULL
, *np
= np1
;
921 assert (p
&& p
->Clipped
);
922 x
= poly_Boolean_free (p
->Clipped
, np
, &merged
, PBO_UNITE
);
925 fprintf (stderr
, "Error while clipping PBO_UNITE: %d\n", x
);
930 p
->Clipped
= biggest (merged
);
931 assert (!p
->Clipped
|| poly_Valid (p
->Clipped
));
932 return ClipOriginal (p
);
936 UnsubtractPin (PinType
* pin
, LayerType
* l
, PolygonType
* p
)
940 /* overlap a bit to prevent gaps from rounding errors */
941 np
= BoxPolyBloated (&pin
->BoundingBox
, UNSUBTRACT_BLOAT
);
945 if (!Unsubtract (np
, p
))
947 clearPoly (PCB
->Data
, l
, p
, (const BoxType
*) pin
, 2 * UNSUBTRACT_BLOAT
);
952 UnsubtractArc (ArcType
* arc
, LayerType
* l
, PolygonType
* p
)
956 if (!TEST_FLAG (CLEARLINEFLAG
, arc
))
959 /* overlap a bit to prevent gaps from rounding errors */
960 np
= BoxPolyBloated (&arc
->BoundingBox
, UNSUBTRACT_BLOAT
);
964 if (!Unsubtract (np
, p
))
966 clearPoly (PCB
->Data
, l
, p
, (const BoxType
*) arc
, 2 * UNSUBTRACT_BLOAT
);
971 UnsubtractLine (LineType
* line
, LayerType
* l
, PolygonType
* p
)
975 if (!TEST_FLAG (CLEARLINEFLAG
, line
))
978 /* overlap a bit to prevent notches from rounding errors */
979 np
= BoxPolyBloated (&line
->BoundingBox
, UNSUBTRACT_BLOAT
);
983 if (!Unsubtract (np
, p
))
985 clearPoly (PCB
->Data
, l
, p
, (const BoxType
*) line
, 2 * UNSUBTRACT_BLOAT
);
990 UnsubtractText (TextType
* text
, LayerType
* l
, PolygonType
* p
)
994 if (!TEST_FLAG (CLEARLINEFLAG
, text
))
997 /* overlap a bit to prevent notches from rounding errors */
998 np
= BoxPolyBloated (&text
->BoundingBox
, UNSUBTRACT_BLOAT
);
1002 if (!Unsubtract (np
, p
))
1004 clearPoly (PCB
->Data
, l
, p
, (const BoxType
*) text
, 2 * UNSUBTRACT_BLOAT
);
1009 UnsubtractPad (PadType
* pad
, LayerType
* l
, PolygonType
* p
)
1013 /* overlap a bit to prevent notches from rounding errors */
1014 np
= BoxPolyBloated (&pad
->BoundingBox
, UNSUBTRACT_BLOAT
);
1018 if (!Unsubtract (np
, p
))
1020 clearPoly (PCB
->Data
, l
, p
, (const BoxType
*) pad
, 2 * UNSUBTRACT_BLOAT
);
1024 static Boolean inhibit
= False
;
1027 InitClip (DataTypePtr Data
, LayerTypePtr layer
, PolygonType
* p
)
1032 poly_Free (&p
->Clipped
);
1033 p
->Clipped
= original_poly (p
);
1036 assert (poly_Valid (p
->Clipped
));
1037 if (TEST_FLAG (CLEARPOLYFLAG
, p
))
1038 clearPoly (Data
, layer
, p
, NULL
, 0);
1042 /* --------------------------------------------------------------------------
1043 * remove redundant polygon points. Any point that lies on the straight
1044 * line between the points on either side of it is redundant.
1045 * returns true if any points are removed
1048 RemoveExcessPolygonPoints (LayerTypePtr Layer
, PolygonTypePtr Polygon
)
1050 PointTypePtr pt1
, pt2
, pt3
;
1053 Boolean changed
= False
;
1057 /* there are always at least three points in a polygon */
1058 pt1
= &Polygon
->Points
[Polygon
->PointN
- 1];
1059 pt2
= &Polygon
->Points
[0];
1060 pt3
= &Polygon
->Points
[1];
1061 for (n
= 0; n
< Polygon
->PointN
; n
++, pt1
++, pt2
++, pt3
++)
1063 /* wrap around polygon */
1065 pt1
= &Polygon
->Points
[0];
1066 if (n
== Polygon
->PointN
- 1)
1067 pt3
= &Polygon
->Points
[0];
1071 if (IsPointOnLine ((float) pt2
->X
, (float) pt2
->Y
, 0.0, &line
))
1073 RemoveObject (POLYGONPOINT_TYPE
, (void *) Layer
, (void *) Polygon
,
1081 /* ---------------------------------------------------------------------------
1082 * returns the index of the polygon point which is the end
1083 * point of the segment with the lowest distance to the passed
1087 GetLowestDistancePolygonPoint (PolygonTypePtr Polygon
, LocationType X
,
1090 double mindistance
= (double) MAX_COORD
* MAX_COORD
;
1091 PointTypePtr ptr1
= &Polygon
->Points
[Polygon
->PointN
- 1],
1092 ptr2
= &Polygon
->Points
[0];
1093 Cardinal n
, result
= 0;
1095 /* we calculate the distance to each segment and choose the
1096 * shortest distance. If the closest approach between the
1097 * given point and the projected line (i.e. the segment extended)
1098 * is not on the segment, then the distance is the distance
1099 * to the segment end point.
1102 for (n
= 0; n
< Polygon
->PointN
; n
++, ptr2
++)
1104 register double u
, dx
, dy
;
1105 dx
= ptr2
->X
- ptr1
->X
;
1106 dy
= ptr2
->Y
- ptr1
->Y
;
1107 if (dx
!= 0.0 || dy
!= 0.0)
1109 /* projected intersection is at P1 + u(P2 - P1) */
1110 u
= ((X
- ptr1
->X
) * dx
+ (Y
- ptr1
->Y
) * dy
) / (dx
* dx
+ dy
* dy
);
1113 { /* ptr1 is closest point */
1114 u
= SQUARE (X
- ptr1
->X
) + SQUARE (Y
- ptr1
->Y
);
1117 { /* ptr2 is closest point */
1118 u
= SQUARE (X
- ptr2
->X
) + SQUARE (Y
- ptr2
->Y
);
1121 { /* projected intersection is closest point */
1122 u
= SQUARE (X
- ptr1
->X
* (1.0 - u
) - u
* ptr2
->X
) +
1123 SQUARE (Y
- ptr1
->Y
* (1.0 - u
) - u
* ptr2
->Y
);
1125 if (u
< mindistance
)
1136 /* ---------------------------------------------------------------------------
1137 * go back to the previous point of the polygon
1140 GoToPreviousPoint (void)
1142 switch (Crosshair
.AttachedPolygon
.PointN
)
1144 /* do nothing if mode has just been entered */
1148 /* reset number of points and 'LINE_MODE' state */
1150 Crosshair
.AttachedPolygon
.PointN
= 0;
1151 Crosshair
.AttachedLine
.State
= STATE_FIRST
;
1155 /* back-up one point */
1158 PointTypePtr points
= Crosshair
.AttachedPolygon
.Points
;
1159 Cardinal n
= Crosshair
.AttachedPolygon
.PointN
- 2;
1161 Crosshair
.AttachedPolygon
.PointN
--;
1162 Crosshair
.AttachedLine
.Point1
.X
= points
[n
].X
;
1163 Crosshair
.AttachedLine
.Point1
.Y
= points
[n
].Y
;
1169 /* ---------------------------------------------------------------------------
1170 * close polygon if possible
1175 Cardinal n
= Crosshair
.AttachedPolygon
.PointN
;
1177 /* check number of points */
1180 /* if 45 degree lines are what we want do a quick check
1181 * if closing the polygon makes sense
1183 if (!TEST_FLAG (ALLDIRECTIONFLAG
, PCB
))
1187 dx
= abs (Crosshair
.AttachedPolygon
.Points
[n
- 1].X
-
1188 Crosshair
.AttachedPolygon
.Points
[0].X
);
1189 dy
= abs (Crosshair
.AttachedPolygon
.Points
[n
- 1].Y
-
1190 Crosshair
.AttachedPolygon
.Points
[0].Y
);
1191 if (!(dx
== 0 || dy
== 0 || dx
== dy
))
1195 ("Cannot close polygon because 45 degree lines are requested.\n"));
1199 CopyAttachedPolygonToLayer ();
1203 Message (_("A polygon has to have at least 3 points\n"));
1206 /* ---------------------------------------------------------------------------
1207 * moves the data of the attached (new) polygon to the current layer
1210 CopyAttachedPolygonToLayer (void)
1212 PolygonTypePtr polygon
;
1215 /* move data to layer and clear attached struct */
1216 polygon
= CreateNewPolygon (CURRENT
, NoFlags ());
1217 saveID
= polygon
->ID
;
1218 *polygon
= Crosshair
.AttachedPolygon
;
1219 polygon
->ID
= saveID
;
1220 SET_FLAG (CLEARPOLYFLAG
, polygon
);
1221 if (TEST_FLAG (NEWFULLPOLYFLAG
, PCB
))
1222 SET_FLAG (FULLPOLYFLAG
, polygon
);
1223 memset (&Crosshair
.AttachedPolygon
, 0, sizeof (PolygonType
));
1224 SetPolygonBoundingBox (polygon
);
1225 if (!CURRENT
->polygon_tree
)
1226 CURRENT
->polygon_tree
= r_create_tree (NULL
, 0, 0);
1227 r_insert_entry (CURRENT
->polygon_tree
, (BoxType
*) polygon
, 0);
1228 InitClip (PCB
->Data
, CURRENT
, polygon
);
1229 DrawPolygon (CURRENT
, polygon
, 0);
1230 SetChangedFlag (True
);
1232 /* reset state of attached line */
1233 Crosshair
.AttachedLine
.State
= STATE_FIRST
;
1236 /* add to undo list */
1237 AddObjectToCreateUndoList (POLYGON_TYPE
, CURRENT
, polygon
, polygon
);
1238 IncrementUndoSerialNumber ();
1241 /* find polygon holes in range, then call the callback function for
1242 * each hole. If the callback returns non-zero, stop
1246 PolygonHoles (PolygonType
*polygon
, const BoxType
*range
,
1247 int (*callback
) (PLINE
*contour
, void *user_data
),
1250 POLYAREA
*pa
= polygon
->Clipped
;
1252 /* If this hole is so big the polygon doesn't exist, then it's not
1257 for (pl
= pa
->contours
->next
; pl
; pl
= pl
->next
)
1259 if (pl
->xmin
> range
->X2
|| pl
->xmax
< range
->X1
||
1260 pl
->ymin
> range
->Y2
|| pl
->ymax
< range
->Y1
)
1262 if (callback (pl
, user_data
))
1276 int (*callback
) (DataTypePtr
, LayerTypePtr
, PolygonTypePtr
, int, void *,
1281 subtract_plow (DataTypePtr Data
, LayerTypePtr Layer
, PolygonTypePtr Polygon
,
1282 int type
, void *ptr1
, void *ptr2
)
1284 if (!Polygon
->Clipped
)
1290 SubtractPin (Data
, (PinTypePtr
) ptr2
, Layer
, Polygon
);
1293 SubtractLine ((LineTypePtr
) ptr2
, Polygon
);
1296 SubtractArc ((ArcTypePtr
) ptr2
, Polygon
);
1299 SubtractPad ((PadTypePtr
) ptr2
, Polygon
);
1302 SubtractText ((TextTypePtr
) ptr2
, Polygon
);
1309 add_plow (DataTypePtr Data
, LayerTypePtr Layer
, PolygonTypePtr Polygon
,
1310 int type
, void *ptr1
, void *ptr2
)
1316 UnsubtractPin ((PinTypePtr
) ptr2
, Layer
, Polygon
);
1319 UnsubtractLine ((LineTypePtr
) ptr2
, Layer
, Polygon
);
1322 UnsubtractArc ((ArcTypePtr
) ptr2
, Layer
, Polygon
);
1325 UnsubtractPad ((PadTypePtr
) ptr2
, Layer
, Polygon
);
1328 UnsubtractText ((TextTypePtr
) ptr2
, Layer
, Polygon
);
1335 plow_callback (const BoxType
* b
, void *cl
)
1337 struct plow_info
*plow
= (struct plow_info
*) cl
;
1338 PolygonTypePtr polygon
= (PolygonTypePtr
) b
;
1340 if (TEST_FLAG (CLEARPOLYFLAG
, polygon
))
1341 return plow
->callback (plow
->data
, plow
->layer
, polygon
, plow
->type
,
1342 plow
->ptr1
, plow
->ptr2
);
1347 PlowsPolygon (DataType
* Data
, int type
, void *ptr1
, void *ptr2
,
1348 int (*call_back
) (DataTypePtr data
, LayerTypePtr lay
,
1349 PolygonTypePtr poly
, int type
, void *ptr1
,
1352 BoxType sb
= ((PinTypePtr
) ptr2
)->BoundingBox
;
1354 struct plow_info info
;
1360 info
.callback
= call_back
;
1365 if (type
== PIN_TYPE
|| ptr1
== ptr2
|| ptr1
== NULL
)
1367 LAYER_LOOP (Data
, max_layer
);
1371 r_search (layer
->polygon_tree
, &sb
, NULL
, plow_callback
, &info
);
1377 GROUP_LOOP (Data
, GetLayerGroupNumberByNumber (GetLayerNumber (Data
,
1378 ((LayerTypePtr
) ptr1
))));
1382 r_search (layer
->polygon_tree
, &sb
, NULL
, plow_callback
, &info
);
1390 /* the cast works equally well for lines and arcs */
1391 if (!TEST_FLAG (CLEARLINEFLAG
, (LineTypePtr
) ptr2
))
1393 /* silk doesn't plow */
1394 if (GetLayerNumber (Data
, ptr1
) >= max_layer
)
1396 GROUP_LOOP (Data
, GetLayerGroupNumberByNumber (GetLayerNumber (Data
,
1397 ((LayerTypePtr
) ptr1
))));
1400 r
+= r_search (layer
->polygon_tree
, &sb
, NULL
, plow_callback
, &info
);
1406 Cardinal group
= TEST_FLAG (ONSOLDERFLAG
,
1407 (PadType
*) ptr2
) ? SOLDER_LAYER
:
1409 group
= GetLayerGroupNumberByNumber (max_layer
+ group
);
1410 GROUP_LOOP (Data
, group
);
1414 r_search (layer
->polygon_tree
, &sb
, NULL
, plow_callback
, &info
);
1422 PIN_LOOP ((ElementType
*) ptr1
);
1424 PlowsPolygon (Data
, PIN_TYPE
, ptr1
, pin
, call_back
);
1427 PAD_LOOP ((ElementType
*) ptr1
);
1429 PlowsPolygon (Data
, PAD_TYPE
, ptr1
, pad
, call_back
);
1439 RestoreToPolygon (DataType
* Data
, int type
, void *ptr1
, void *ptr2
)
1441 if (type
== POLYGON_TYPE
)
1442 InitClip (PCB
->Data
, (LayerTypePtr
) ptr1
, (PolygonTypePtr
) ptr2
);
1444 PlowsPolygon (Data
, type
, ptr1
, ptr2
, add_plow
);
1448 ClearFromPolygon (DataType
* Data
, int type
, void *ptr1
, void *ptr2
)
1450 if (type
== POLYGON_TYPE
)
1451 InitClip (PCB
->Data
, (LayerTypePtr
) ptr1
, (PolygonTypePtr
) ptr2
);
1453 PlowsPolygon (Data
, type
, ptr1
, ptr2
, subtract_plow
);
1457 isects (POLYAREA
* a
, PolygonTypePtr p
, Boolean fr
)
1461 ans
= Touching (a
, p
->Clipped
);
1462 /* argument may be register, so we must copy it */
1471 IsPointInPolygon (LocationType X
, LocationType Y
, BDimension r
,
1478 if (poly_CheckInside (p
->Clipped
, v
))
1482 if (!(c
= CirclePoly (X
, Y
, r
)))
1484 return isects (c
, p
, True
);
1489 IsPointInPolygonIgnoreHoles (LocationType X
, LocationType Y
, PolygonTypePtr p
)
1494 return poly_InsideContour (p
->Clipped
->contours
, v
);
1498 IsRectangleInPolygon (LocationType X1
, LocationType Y1
, LocationType X2
,
1499 LocationType Y2
, PolygonTypePtr p
)
1503 (s
= RectPoly (min (X1
, X2
), max (X1
, X2
), min (Y1
, Y2
), max (Y1
, Y2
))))
1505 return isects (s
, p
, True
);
1509 r_NoHolesPolygonDicer (PLINE
* p
,
1510 void (*emit
) (PLINE
*, void *), void *user_data
)
1514 pa
= (POLYAREA
*) malloc (sizeof (*pa
));
1517 if (!p
->next
) /* no holes */
1519 emit (p
, user_data
);
1525 POLYAREA
*poly2
, *left
, *right
;
1527 /* make a rectangle of the left region slicing through the middle of the first hole */
1529 RectPoly (p
->xmin
, (p
->next
->xmin
+ p
->next
->xmax
) / 2, p
->ymin
,
1531 poly_AndSubtract_free (pa
, poly2
, &left
, &right
);
1538 PLINE
*pl
= x
->contours
;
1539 r_NoHolesPolygonDicer (pl
, emit
, user_data
);
1541 /* the pline was already freed by its use int he recursive dicer */
1544 while ((x
= y
) != left
);
1552 PLINE
*pl
= x
->contours
;
1553 r_NoHolesPolygonDicer (pl
, emit
, user_data
);
1557 while ((x
= y
) != right
);
1563 NoHolesPolygonDicer (PolygonTypePtr p
, const BoxType
* clip
,
1564 void (*emit
) (PLINE
*, void *), void *user_data
)
1566 POLYAREA
*save
, *ans
;
1568 ans
= save
= poly_Create ();
1569 /* copy the main poly only */
1570 poly_Copy1 (save
, p
->Clipped
);
1571 /* clip to the bounding box */
1574 POLYAREA
*cbox
= RectPoly (clip
->X1
, clip
->X2
, clip
->Y1
, clip
->Y2
);
1577 int r
= poly_Boolean_free (save
, cbox
, &ans
, PBO_ISECT
);
1585 /* now dice it up */
1589 r_NoHolesPolygonDicer (save
->contours
, emit
, user_data
);
1590 /* go to next poly (could be one because of clip) */
1593 /* free the previouse POLYAREA. Note the contour was consumed in the dicer */
1596 while (save
!= ans
);
1599 /* make a polygon split into multiple parts into multiple polygons */
1601 MorphPolygon (LayerTypePtr layer
, PolygonTypePtr poly
)
1603 POLYAREA
*p
, *start
;
1604 Boolean many
= False
;
1607 if (!poly
->Clipped
|| TEST_FLAG (LOCKFLAG
, poly
))
1609 if (poly
->Clipped
->f
== poly
->Clipped
)
1611 ErasePolygon (poly
);
1612 start
= p
= poly
->Clipped
;
1613 /* This is ugly. The creation of the new polygons can cause
1614 * all of the polygon pointers (including the one we're called
1615 * with to change if there is a realloc in GetPolygonMemory().
1616 * That will invalidate our original "poly" argument, potentially
1617 * inside the loop. We need to steal the Clipped pointer and
1618 * hide it from the Remove call so that it still exists while
1619 * we do this dirty work.
1621 poly
->Clipped
= NULL
;
1622 flags
= poly
->Flags
;
1623 RemovePolygon (layer
, poly
);
1630 if (p
->contours
->area
> PCB
->IsleArea
)
1632 new = CreateNewPolygon (layer
, flags
);
1636 v
= &p
->contours
->head
;
1637 CreateNewPointInPolygon (new, v
->point
[0], v
->point
[1]);
1638 for (v
= v
->next
; v
!= &p
->contours
->head
; v
= v
->next
)
1639 CreateNewPointInPolygon (new, v
->point
[0], v
->point
[1]);
1640 new->BoundingBox
.X1
= p
->contours
->xmin
;
1641 new->BoundingBox
.X2
= p
->contours
->xmax
+ 1;
1642 new->BoundingBox
.Y1
= p
->contours
->ymin
;
1643 new->BoundingBox
.Y2
= p
->contours
->ymax
+ 1;
1644 AddObjectToCreateUndoList (POLYGON_TYPE
, layer
, new, new);
1646 p
= p
->f
; /* go to next pline */
1647 new->Clipped
->b
= new->Clipped
->f
= new->Clipped
; /* unlink from others */
1648 r_insert_entry (layer
->polygon_tree
, (BoxType
*) new, 0);
1649 DrawPolygon (layer
, new, 0);
1656 poly_DelContour (&t
->contours
);
1662 IncrementUndoSerialNumber ();
1666 void debug_pline (PLINE
*pl
)
1669 fprintf (stderr
, "\txmin %d xmax %d ymin %d ymax %d\n",
1670 pl
->xmin
, pl
->xmax
, pl
->ymin
, pl
->ymax
);
1674 fprintf(stderr
, "\t\tvnode: %d,%d\n", v
->point
[0], v
->point
[1]);
1682 debug_polyarea (POLYAREA
*p
)
1686 fprintf (stderr
, "POLYAREA %p\n", p
);
1687 for (pl
=p
->contours
; pl
; pl
=pl
->next
)
1692 debug_polygon (PolygonType
*p
)
1696 fprintf (stderr
, "POLYGON %p %d pts\n", p
, p
->PointN
);
1697 for (i
=0; i
<p
->PointN
; i
++)
1698 fprintf(stderr
, "\t%d: %d, %d\n", i
, p
->Points
[i
].X
, p
->Points
[i
].Y
);
1702 debug_polyarea (pa
);
1704 if (pa
== p
->Clipped
)