4 * PCB, interactive printed circuit board design
5 * Copyright (C) 1994,1995,1996,2010 Thomas Nau
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
21 * Contact addresses for paper mail and Email:
22 * Thomas Nau, Schlehenweg 15, 88471 Baustetten, Germany
23 * Thomas.Nau@rz.uni-ulm.de
30 Here's a brief tour of the data and life of a polygon, courtesy of Ben
33 A PCB PolygonType contains an array of points outlining the polygon.
34 This is what is manipulated by the UI and stored in the saved PCB.
36 A PolygonType also contains a POLYAREA called 'Clipped' which is
37 computed dynamically by InitClip every time a board is loaded. The
38 point array is coverted to a POLYAREA by original_poly and then holes
39 are cut in it by clearPoly. After that it is maintained dynamically
40 as parts are added, moved or removed (this is why sometimes bugs can
41 be fixed by just re-loading the board).
43 A POLYAREA consists of a linked list of PLINE structures. The head of
44 that list is POLYAREA.contours. The first contour is an outline of a
45 filled region. All of the subsequent PLINEs are holes cut out of that
46 first contour. POLYAREAs are in a doubly-linked list and each member
47 of the list is an independent (non-overlapping) area with its own
48 outline and holes. The function biggest() finds the largest POLYAREA
49 so that PolygonType.Clipped points to that shape. The rest of the
50 polygon still exists, it's just ignored when turning the polygon into
53 The first POLYAREA in PolygonType.Clipped is what is used for the vast
54 majority of Polygon related tests. The basic logic for an
55 intersection is "is the target shape inside POLYAREA.contours and NOT
56 fully enclosed in any of POLYAREA.contours.next... (the holes)".
58 The polygon dicer (NoHolesPolygonDicer and r_NoHolesPolygonDicer)
59 emits a series of "simple" PLINE shapes. That is, the PLINE isn't
60 linked to any other "holes" oulines). That's the meaning of the first
61 test in r_NoHolesPolygonDicer. It is testing to see if the PLINE
62 contour (the first, making it a solid outline) has a valid next
63 pointer (which would point to one or more holes). The dicer works by
64 recursively chopping the polygon in half through the first hole it
65 sees (which is guaranteed to eliminate at least that one hole). The
66 dicer output is used for HIDs which cannot render things with holes
67 (which would require erasure).
71 /* special polygon editing routines
86 #include "crosshair.h"
93 #include "pcb-printf.h"
102 #ifdef HAVE_LIBDMALLOC
106 #define ROUND(x) ((long)(((x) >= 0 ? (x) + 0.5 : (x) - 0.5)))
108 #define UNSUBTRACT_BLOAT 10
109 #define SUBTRACT_PIN_VIA_BATCH_SIZE 100
110 #define SUBTRACT_LINE_BATCH_SIZE 20
112 static double rotate_circle_seg
[4];
117 double cos_ang
= cos (2.0 * M_PI
/ POLY_CIRC_SEGS_F
);
118 double sin_ang
= sin (2.0 * M_PI
/ POLY_CIRC_SEGS_F
);
120 rotate_circle_seg
[0] = cos_ang
; rotate_circle_seg
[1] = -sin_ang
;
121 rotate_circle_seg
[2] = sin_ang
; rotate_circle_seg
[3] = cos_ang
;
125 polygon_point_idx (PolygonTypePtr polygon
, PointTypePtr point
)
127 assert (point
>= polygon
->Points
);
128 assert (point
<= polygon
->Points
+ polygon
->PointN
);
129 return ((char *)point
- (char *)polygon
->Points
) / sizeof (PointType
);
132 /* Find contour number: 0 for outer, 1 for first hole etc.. */
134 polygon_point_contour (PolygonTypePtr polygon
, Cardinal point
)
137 Cardinal contour
= 0;
139 for (i
= 0; i
< polygon
->HoleIndexN
; i
++)
140 if (point
>= polygon
->HoleIndex
[i
])
146 next_contour_point (PolygonTypePtr polygon
, Cardinal point
)
149 Cardinal this_contour_start
;
150 Cardinal next_contour_start
;
152 contour
= polygon_point_contour (polygon
, point
);
154 this_contour_start
= (contour
== 0) ? 0 :
155 polygon
->HoleIndex
[contour
- 1];
157 (contour
== polygon
->HoleIndexN
) ? polygon
->PointN
:
158 polygon
->HoleIndex
[contour
];
160 /* Wrap back to the start of the contour we're in if we pass the end */
161 if (++point
== next_contour_start
)
162 point
= this_contour_start
;
168 prev_contour_point (PolygonTypePtr polygon
, Cardinal point
)
171 Cardinal prev_contour_end
;
172 Cardinal this_contour_end
;
174 contour
= polygon_point_contour (polygon
, point
);
176 prev_contour_end
= (contour
== 0) ? 0 :
177 polygon
->HoleIndex
[contour
- 1];
179 (contour
== polygon
->HoleIndexN
) ? polygon
->PointN
- 1:
180 polygon
->HoleIndex
[contour
] - 1;
182 /* Wrap back to the start of the contour we're in if we pass the end */
183 if (point
== prev_contour_end
)
184 point
= this_contour_end
;
192 add_noholes_polyarea (PLINE
*pline
, void *user_data
)
194 PolygonType
*poly
= (PolygonType
*)user_data
;
196 /* Prepend the pline into the NoHoles linked list */
197 pline
->next
= poly
->NoHoles
;
198 poly
->NoHoles
= pline
;
202 ComputeNoHoles (PolygonType
*poly
)
204 poly_FreeContours (&poly
->NoHoles
);
206 NoHolesPolygonDicer (poly
, NULL
, add_noholes_polyarea
, poly
);
208 printf ("Compute_noholes caught poly->Clipped = NULL\n");
209 poly
->NoHolesValid
= 1;
213 biggest (POLYAREA
* p
)
215 POLYAREA
*n
, *top
= NULL
;
225 if (n
->contours
->area
< PCB
->IsleArea
)
229 poly_DelContour (&n
->contours
);
240 if (n
->contours
->area
> big
)
243 big
= n
->contours
->area
;
246 while ((n
= n
->f
) != p
);
251 tree
= top
->contour_tree
;
252 top
->contours
= p
->contours
;
253 top
->contour_tree
= p
->contour_tree
;
255 p
->contour_tree
= tree
;
263 ContourToPoly (PLINE
* contour
)
266 poly_PreContour (contour
, TRUE
);
267 assert (contour
->Flags
.orient
== PLF_DIR
);
268 if (!(p
= poly_Create ()))
270 poly_InclContour (p
, contour
);
271 assert (poly_Valid (p
));
276 original_poly (PolygonType
* p
)
278 PLINE
*contour
= NULL
;
284 if ((np
= poly_Create ()) == NULL
)
287 /* first make initial polygon contour */
288 for (n
= 0; n
< p
->PointN
; n
++)
290 /* No current contour? Make a new one starting at point */
291 /* (or) Add point to existing contour */
293 v
[0] = p
->Points
[n
].X
;
294 v
[1] = p
->Points
[n
].Y
;
297 if ((contour
= poly_NewContour (v
)) == NULL
)
302 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
305 /* Is current point last in contour? If so process it. */
306 if (n
== p
->PointN
- 1 ||
307 (hole
< p
->HoleIndexN
&& n
== p
->HoleIndex
[hole
] - 1))
309 poly_PreContour (contour
, TRUE
);
311 /* make sure it is a positive contour (outer) or negative (hole) */
312 if (contour
->Flags
.orient
!= (hole
? PLF_INV
: PLF_DIR
))
313 poly_InvContour (contour
);
314 assert (contour
->Flags
.orient
== (hole
? PLF_INV
: PLF_DIR
));
316 poly_InclContour (np
, contour
);
318 assert (poly_Valid (np
));
327 PolygonToPoly (PolygonType
*p
)
329 return original_poly (p
);
333 RectPoly (Coord x1
, Coord x2
, Coord y1
, Coord y2
)
335 PLINE
*contour
= NULL
;
338 /* Return NULL for zero or negatively sized rectangles */
339 if (x2
<= x1
|| y2
<= y1
)
344 if ((contour
= poly_NewContour (v
)) == NULL
)
348 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
351 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
354 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
355 return ContourToPoly (contour
);
359 OctagonPoly (Coord x
, Coord y
, Coord radius
)
361 PLINE
*contour
= NULL
;
364 v
[0] = x
+ ROUND (radius
* 0.5);
365 v
[1] = y
+ ROUND (radius
* TAN_22_5_DEGREE_2
);
366 if ((contour
= poly_NewContour (v
)) == NULL
)
368 v
[0] = x
+ ROUND (radius
* TAN_22_5_DEGREE_2
);
369 v
[1] = y
+ ROUND (radius
* 0.5);
370 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
371 v
[0] = x
- (v
[0] - x
);
372 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
373 v
[0] = x
- ROUND (radius
* 0.5);
374 v
[1] = y
+ ROUND (radius
* TAN_22_5_DEGREE_2
);
375 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
376 v
[1] = y
- (v
[1] - y
);
377 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
378 v
[0] = x
- ROUND (radius
* TAN_22_5_DEGREE_2
);
379 v
[1] = y
- ROUND (radius
* 0.5);
380 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
381 v
[0] = x
- (v
[0] - x
);
382 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
383 v
[0] = x
+ ROUND (radius
* 0.5);
384 v
[1] = y
- ROUND (radius
* TAN_22_5_DEGREE_2
);
385 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
386 return ContourToPoly (contour
);
389 /* add verticies in a fractional-circle starting from v
390 * centered at X, Y and going counter-clockwise
391 * does not include the first point
392 * last argument is 1 for a full circle
393 * 2 for a half circle
394 * or 4 for a quarter circle
397 frac_circle (PLINE
* c
, Coord X
, Coord Y
, Vector v
, int range
)
402 poly_InclVertex (c
->head
.prev
, poly_CreateNode (v
));
403 /* move vector to origin */
404 e1
= (v
[0] - X
) * POLY_CIRC_RADIUS_ADJ
;
405 e2
= (v
[1] - Y
) * POLY_CIRC_RADIUS_ADJ
;
407 /* NB: the caller adds the last vertex, hence the -1 */
408 range
= POLY_CIRC_SEGS
/ range
- 1;
409 for (i
= 0; i
< range
; i
++)
411 /* rotate the vector */
412 t1
= rotate_circle_seg
[0] * e1
+ rotate_circle_seg
[1] * e2
;
413 e2
= rotate_circle_seg
[2] * e1
+ rotate_circle_seg
[3] * e2
;
415 v
[0] = X
+ ROUND (e1
);
416 v
[1] = Y
+ ROUND (e2
);
417 poly_InclVertex (c
->head
.prev
, poly_CreateNode (v
));
421 /* create a circle approximation from lines */
423 CirclePoly (Coord x
, Coord y
, Coord radius
)
432 if ((contour
= poly_NewContour (v
)) == NULL
)
434 frac_circle (contour
, x
, y
, v
, 1);
435 contour
->is_round
= TRUE
;
438 contour
->radius
= radius
;
439 return ContourToPoly (contour
);
442 /* make a rounded-corner rectangle with radius t beyond x1,x2,y1,y2 rectangle */
444 RoundRect (Coord x1
, Coord x2
, Coord y1
, Coord y2
, Coord t
)
446 PLINE
*contour
= NULL
;
453 if ((contour
= poly_NewContour (v
)) == NULL
)
455 frac_circle (contour
, x1
, y1
, v
, 4);
458 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
459 frac_circle (contour
, x2
, y1
, v
, 4);
462 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
463 frac_circle (contour
, x2
, y2
, v
, 4);
466 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
467 frac_circle (contour
, x1
, y2
, v
, 4);
468 return ContourToPoly (contour
);
473 ArcPolyNoIntersect (ArcType
* a
, Coord thick
)
475 PLINE
*contour
= NULL
;
480 double ang
, da
, rx
, ry
;
488 a
->StartAngle
+= a
->Delta
;
489 a
->Delta
= -a
->Delta
;
491 half
= (thick
+ 1) / 2;
492 ends
= GetArcEnds (a
);
493 /* start with inner radius */
494 rx
= MAX (a
->Width
- half
, 0);
495 ry
= MAX (a
->Height
- half
, 0);
498 segs
= MAX (segs
, a
->Delta
* M_PI
/ 360 *
499 sqrt (sqrt ((double)rx
* rx
+ (double)ry
* ry
) /
500 POLY_ARC_MAX_DEVIATION
/ 2 / thick
));
501 segs
= MAX(segs
, a
->Delta
/ ARC_ANGLE
);
504 da
= (1.0 * a
->Delta
) / segs
;
505 radius_adj
= (M_PI
*da
/360)*(M_PI
*da
/360)/2;
506 v
[0] = a
->X
- rx
* cos (ang
* M180
);
507 v
[1] = a
->Y
+ ry
* sin (ang
* M180
);
508 if ((contour
= poly_NewContour (v
)) == NULL
)
510 for (i
= 0; i
< segs
- 1; i
++)
513 v
[0] = a
->X
- rx
* cos (ang
* M180
);
514 v
[1] = a
->Y
+ ry
* sin (ang
* M180
);
515 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
517 /* find last point */
518 ang
= a
->StartAngle
+ a
->Delta
;
519 v
[0] = a
->X
- rx
* cos (ang
* M180
) * (1 - radius_adj
);
520 v
[1] = a
->Y
+ ry
* sin (ang
* M180
) * (1 - radius_adj
);
521 /* add the round cap at the end */
522 frac_circle (contour
, ends
->X2
, ends
->Y2
, v
, 2);
523 /* and now do the outer arc (going backwards) */
524 rx
= (a
->Width
+ half
) * (1+radius_adj
);
525 ry
= (a
->Width
+ half
) * (1+radius_adj
);
527 for (i
= 0; i
< segs
; i
++)
529 v
[0] = a
->X
- rx
* cos (ang
* M180
);
530 v
[1] = a
->Y
+ ry
* sin (ang
* M180
);
531 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
534 /* now add other round cap */
536 v
[0] = a
->X
- rx
* cos (ang
* M180
) * (1 - radius_adj
);
537 v
[1] = a
->Y
+ ry
* sin (ang
* M180
) * (1 - radius_adj
);
538 frac_circle (contour
, ends
->X1
, ends
->Y1
, v
, 2);
539 /* now we have the whole contour */
540 if (!(np
= ContourToPoly (contour
)))
545 #define MIN_CLEARANCE_BEFORE_BISECT 10.
547 ArcPoly (ArcType
* a
, Coord thick
)
551 POLYAREA
*tmp1
, *tmp2
, *res
;
553 delta
= (a
->Delta
< 0) ? -a
->Delta
: a
->Delta
;
555 /* If the arc segment would self-intersect, we need to construct it as the union of
556 two non-intersecting segments */
558 if (2 * M_PI
* a
->Width
* (1. - (double)delta
/ 360.) - thick
< MIN_CLEARANCE_BEFORE_BISECT
)
560 int half_delta
= a
->Delta
/ 2;
563 seg1
.Delta
= half_delta
;
564 seg2
.Delta
-= half_delta
;
565 seg2
.StartAngle
+= half_delta
;
567 tmp1
= ArcPolyNoIntersect (&seg1
, thick
);
568 tmp2
= ArcPolyNoIntersect (&seg2
, thick
);
569 poly_Boolean_free (tmp1
, tmp2
, &res
, PBO_UNITE
);
573 return ArcPolyNoIntersect (a
, thick
);
577 LinePoly (LineType
* L
, Coord thick
)
579 PLINE
*contour
= NULL
;
583 long half
;LineType _l
=*L
,*l
=&_l
;
587 half
= (thick
+ 1) / 2;
589 sqrt (SQUARE (l
->Point1
.X
- l
->Point2
.X
) +
590 SQUARE (l
->Point1
.Y
- l
->Point2
.Y
));
591 if (!TEST_FLAG (SQUAREFLAG
,l
))
592 if (d
== 0) /* line is a point */
593 return CirclePoly (l
->Point1
.X
, l
->Point1
.Y
, half
);
597 dx
= (l
->Point1
.Y
- l
->Point2
.Y
) * d
;
598 dy
= (l
->Point2
.X
- l
->Point1
.X
) * d
;
605 if (TEST_FLAG (SQUAREFLAG
,l
))/* take into account the ends */
612 v
[0] = l
->Point1
.X
- dx
;
613 v
[1] = l
->Point1
.Y
- dy
;
614 if ((contour
= poly_NewContour (v
)) == NULL
)
616 v
[0] = l
->Point2
.X
- dx
;
617 v
[1] = l
->Point2
.Y
- dy
;
618 if (TEST_FLAG (SQUAREFLAG
,l
))
619 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
621 frac_circle (contour
, l
->Point2
.X
, l
->Point2
.Y
, v
, 2);
622 v
[0] = l
->Point2
.X
+ dx
;
623 v
[1] = l
->Point2
.Y
+ dy
;
624 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
625 v
[0] = l
->Point1
.X
+ dx
;
626 v
[1] = l
->Point1
.Y
+ dy
;
627 if (TEST_FLAG (SQUAREFLAG
,l
))
628 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
630 frac_circle (contour
, l
->Point1
.X
, l
->Point1
.Y
, v
, 2);
631 /* now we have the line contour */
632 if (!(np
= ContourToPoly (contour
)))
637 /* make a rounded-corner rectangle */
639 SquarePadPoly (PadType
* pad
, Coord clear
)
641 PLINE
*contour
= NULL
;
647 PadType _t
=*pad
,*t
=&_t
;
648 PadType _c
=*pad
,*c
=&_c
;
649 int halfthick
= (pad
->Thickness
+ 1) / 2;
650 int halfclear
= (clear
+ 1) / 2;
653 sqrt (SQUARE (pad
->Point1
.X
- pad
->Point2
.X
) +
654 SQUARE (pad
->Point1
.Y
- pad
->Point2
.Y
));
657 double a
= halfthick
/ d
;
658 tx
= (t
->Point1
.Y
- t
->Point2
.Y
) * a
;
659 ty
= (t
->Point2
.X
- t
->Point1
.X
) * a
;
661 cx
= (c
->Point1
.Y
- c
->Point2
.Y
) * a
;
662 cy
= (c
->Point2
.X
- c
->Point1
.X
) * a
;
686 v
[0] = c
->Point1
.X
- tx
;
687 v
[1] = c
->Point1
.Y
- ty
;
688 if ((contour
= poly_NewContour (v
)) == NULL
)
690 frac_circle (contour
, (t
->Point1
.X
- tx
), (t
->Point1
.Y
- ty
), v
, 4);
692 v
[0] = t
->Point2
.X
- cx
;
693 v
[1] = t
->Point2
.Y
- cy
;
694 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
695 frac_circle (contour
, (t
->Point2
.X
- tx
), (t
->Point2
.Y
- ty
), v
, 4);
697 v
[0] = c
->Point2
.X
+ tx
;
698 v
[1] = c
->Point2
.Y
+ ty
;
699 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
700 frac_circle (contour
, (t
->Point2
.X
+ tx
), (t
->Point2
.Y
+ ty
), v
, 4);
702 v
[0] = t
->Point1
.X
+ cx
;
703 v
[1] = t
->Point1
.Y
+ cy
;
704 poly_InclVertex (contour
->head
.prev
, poly_CreateNode (v
));
705 frac_circle (contour
, (t
->Point1
.X
+ tx
), (t
->Point1
.Y
+ ty
), v
, 4);
707 /* now we have the line contour */
708 if (!(np
= ContourToPoly (contour
)))
713 /* clear np1 from the polygon */
715 Subtract (POLYAREA
* np1
, PolygonType
* p
, bool fnp
)
717 POLYAREA
*merged
= NULL
, *np
= np1
;
727 assert (poly_Valid (p
->Clipped
));
728 assert (poly_Valid (np
));
730 x
= poly_Boolean_free (p
->Clipped
, np
, &merged
, PBO_SUB
);
733 x
= poly_Boolean (p
->Clipped
, np
, &merged
, PBO_SUB
);
734 poly_Free (&p
->Clipped
);
736 assert (!merged
|| poly_Valid (merged
));
739 fprintf (stderr
, "Error while clipping PBO_SUB: %d\n", x
);
742 if (p
->NoHoles
) printf ("Just leaked in Subtract\n");
746 p
->Clipped
= biggest (merged
);
747 assert (!p
->Clipped
|| poly_Valid (p
->Clipped
));
749 Message ("Polygon cleared out of existence near (%d, %d)\n",
750 (p
->BoundingBox
.X1
+ p
->BoundingBox
.X2
) / 2,
751 (p
->BoundingBox
.Y1
+ p
->BoundingBox
.Y2
) / 2);
755 /* create a polygon of the pin clearance */
757 PinPoly (PinType
* pin
, Coord thick
, Coord clear
)
761 if (TEST_FLAG (SQUAREFLAG
, pin
))
763 size
= (thick
+ 1) / 2;
764 return RoundRect (pin
->X
- size
, pin
->X
+ size
, pin
->Y
- size
,
765 pin
->Y
+ size
, (clear
+ 1) / 2);
769 size
= (thick
+ clear
+ 1) / 2;
770 if (TEST_FLAG (OCTAGONFLAG
, pin
))
772 return OctagonPoly (pin
->X
, pin
->Y
, size
+ size
);
775 return CirclePoly (pin
->X
, pin
->Y
, size
);
779 BoxPolyBloated (BoxType
*box
, Coord bloat
)
781 return RectPoly (box
->X1
- bloat
, box
->X2
+ bloat
,
782 box
->Y1
- bloat
, box
->Y2
+ bloat
);
785 /* remove the pin clearance from the polygon */
787 SubtractPin (DataType
* d
, PinType
* pin
, LayerType
* l
, PolygonType
* p
)
792 if (pin
->Clearance
== 0)
794 i
= GetLayerNumber (d
, l
);
795 if (TEST_THERM (i
, pin
))
797 np
= ThermPoly ((PCBTypePtr
) (d
->pcb
), pin
, i
);
803 np
= PinPoly (pin
, PIN_SIZE (pin
), pin
->Clearance
);
807 return Subtract (np
, p
, TRUE
);
811 SubtractLine (LineType
* line
, PolygonType
* p
)
815 if (!TEST_FLAG (CLEARLINEFLAG
, line
))
817 if (!(np
= LinePoly (line
, line
->Thickness
+ line
->Clearance
)))
819 return Subtract (np
, p
, true);
823 SubtractArc (ArcType
* arc
, PolygonType
* p
)
827 if (!TEST_FLAG (CLEARLINEFLAG
, arc
))
829 if (!(np
= ArcPoly (arc
, arc
->Thickness
+ arc
->Clearance
)))
831 return Subtract (np
, p
, true);
835 SubtractText (TextType
* text
, PolygonType
* p
)
838 const BoxType
*b
= &text
->BoundingBox
;
840 if (!TEST_FLAG (CLEARLINEFLAG
, text
))
842 if (!(np
= RoundRect (b
->X1
+ PCB
->Bloat
, b
->X2
- PCB
->Bloat
,
843 b
->Y1
+ PCB
->Bloat
, b
->Y2
- PCB
->Bloat
, PCB
->Bloat
)))
845 return Subtract (np
, p
, true);
849 SubtractPad (PadType
* pad
, PolygonType
* p
)
853 if (pad
->Clearance
== 0)
855 if (TEST_FLAG (SQUAREFLAG
, pad
))
858 (np
= SquarePadPoly (pad
, pad
->Thickness
+ pad
->Clearance
)))
864 (np
= LinePoly ((LineType
*) pad
, pad
->Thickness
+ pad
->Clearance
)))
867 return Subtract (np
, p
, true);
872 const BoxType
*other
;
875 PolygonType
*polygon
;
877 POLYAREA
*accumulate
;
883 subtract_accumulated (struct cpInfo
*info
, PolygonTypePtr polygon
)
885 if (info
->accumulate
== NULL
)
887 Subtract (info
->accumulate
, polygon
, true);
888 info
->accumulate
= NULL
;
889 info
->batch_size
= 0;
893 pin_sub_callback (const BoxType
* b
, void *cl
)
895 PinTypePtr pin
= (PinTypePtr
) b
;
896 struct cpInfo
*info
= (struct cpInfo
*) cl
;
897 PolygonTypePtr polygon
;
902 /* don't subtract the object that was put back! */
903 if (b
== info
->other
)
905 polygon
= info
->polygon
;
907 if (pin
->Clearance
== 0)
909 i
= GetLayerNumber (info
->data
, info
->layer
);
910 if (TEST_THERM (i
, pin
))
912 np
= ThermPoly ((PCBTypePtr
) (info
->data
->pcb
), pin
, i
);
918 np
= PinPoly (pin
, PIN_SIZE (pin
), pin
->Clearance
);
920 longjmp (info
->env
, 1);
923 poly_Boolean_free (info
->accumulate
, np
, &merged
, PBO_UNITE
);
924 info
->accumulate
= merged
;
928 if (info
->batch_size
== SUBTRACT_PIN_VIA_BATCH_SIZE
)
929 subtract_accumulated (info
, polygon
);
935 arc_sub_callback (const BoxType
* b
, void *cl
)
937 ArcTypePtr arc
= (ArcTypePtr
) b
;
938 struct cpInfo
*info
= (struct cpInfo
*) cl
;
939 PolygonTypePtr polygon
;
941 /* don't subtract the object that was put back! */
942 if (b
== info
->other
)
944 if (!TEST_FLAG (CLEARLINEFLAG
, arc
))
946 polygon
= info
->polygon
;
947 if (SubtractArc (arc
, polygon
) < 0)
948 longjmp (info
->env
, 1);
953 pad_sub_callback (const BoxType
* b
, void *cl
)
955 PadTypePtr pad
= (PadTypePtr
) b
;
956 struct cpInfo
*info
= (struct cpInfo
*) cl
;
957 PolygonTypePtr polygon
;
959 /* don't subtract the object that was put back! */
960 if (b
== info
->other
)
962 if (pad
->Clearance
== 0)
964 polygon
= info
->polygon
;
965 if (XOR (TEST_FLAG (ONSOLDERFLAG
, pad
), !info
->solder
))
967 if (SubtractPad (pad
, polygon
) < 0)
968 longjmp (info
->env
, 1);
975 line_sub_callback (const BoxType
* b
, void *cl
)
977 LineTypePtr line
= (LineTypePtr
) b
;
978 struct cpInfo
*info
= (struct cpInfo
*) cl
;
979 PolygonTypePtr polygon
;
983 /* don't subtract the object that was put back! */
984 if (b
== info
->other
)
986 if (!TEST_FLAG (CLEARLINEFLAG
, line
))
988 polygon
= info
->polygon
;
990 if (!(np
= LinePoly (line
, line
->Thickness
+ line
->Clearance
)))
991 longjmp (info
->env
, 1);
993 poly_Boolean_free (info
->accumulate
, np
, &merged
, PBO_UNITE
);
994 info
->accumulate
= merged
;
997 if (info
->batch_size
== SUBTRACT_LINE_BATCH_SIZE
)
998 subtract_accumulated (info
, polygon
);
1004 text_sub_callback (const BoxType
* b
, void *cl
)
1006 TextTypePtr text
= (TextTypePtr
) b
;
1007 struct cpInfo
*info
= (struct cpInfo
*) cl
;
1008 PolygonTypePtr polygon
;
1010 /* don't subtract the object that was put back! */
1011 if (b
== info
->other
)
1013 if (!TEST_FLAG (CLEARLINEFLAG
, text
))
1015 polygon
= info
->polygon
;
1016 if (SubtractText (text
, polygon
) < 0)
1017 longjmp (info
->env
, 1);
1022 Group (DataTypePtr Data
, Cardinal layer
)
1025 for (i
= 0; i
< max_group
; i
++)
1026 for (j
= 0; j
< ((PCBType
*) (Data
->pcb
))->LayerGroups
.Number
[i
]; j
++)
1027 if (layer
== ((PCBType
*) (Data
->pcb
))->LayerGroups
.Entries
[i
][j
])
1033 clearPoly (DataTypePtr Data
, LayerTypePtr Layer
, PolygonType
* polygon
,
1034 const BoxType
* here
, Coord expand
)
1041 if (!TEST_FLAG (CLEARPOLYFLAG
, polygon
)
1042 || GetLayerNumber (Data
, Layer
) >= max_copper_layer
)
1044 group
= Group (Data
, GetLayerNumber (Data
, Layer
));
1045 info
.solder
= (group
== Group (Data
, solder_silk_layer
));
1049 info
.polygon
= polygon
;
1051 region
= clip_box (here
, &polygon
->BoundingBox
);
1053 region
= polygon
->BoundingBox
;
1054 region
= bloat_box (®ion
, expand
);
1056 if (setjmp (info
.env
) == 0)
1059 info
.accumulate
= NULL
;
1060 info
.batch_size
= 0;
1061 if (info
.solder
|| group
== Group (Data
, component_silk_layer
))
1062 r
+= r_search (Data
->pad_tree
, ®ion
, NULL
, pad_sub_callback
, &info
);
1063 GROUP_LOOP (Data
, group
);
1066 r_search (layer
->line_tree
, ®ion
, NULL
, line_sub_callback
,
1068 subtract_accumulated (&info
, polygon
);
1070 r_search (layer
->arc_tree
, ®ion
, NULL
, arc_sub_callback
, &info
);
1072 r_search (layer
->text_tree
, ®ion
, NULL
, text_sub_callback
, &info
);
1075 r
+= r_search (Data
->via_tree
, ®ion
, NULL
, pin_sub_callback
, &info
);
1076 r
+= r_search (Data
->pin_tree
, ®ion
, NULL
, pin_sub_callback
, &info
);
1077 subtract_accumulated (&info
, polygon
);
1079 polygon
->NoHolesValid
= 0;
1084 Unsubtract (POLYAREA
* np1
, PolygonType
* p
)
1086 POLYAREA
*merged
= NULL
, *np
= np1
;
1087 POLYAREA
*orig_poly
, *clipped_np
;
1090 assert (p
&& p
->Clipped
);
1092 orig_poly
= original_poly (p
);
1094 x
= poly_Boolean_free (np
, orig_poly
, &clipped_np
, PBO_ISECT
);
1097 fprintf (stderr
, "Error while clipping PBO_ISECT: %d\n", x
);
1098 poly_Free (&clipped_np
);
1102 x
= poly_Boolean_free (p
->Clipped
, clipped_np
, &merged
, PBO_UNITE
);
1105 fprintf (stderr
, "Error while clipping PBO_UNITE: %d\n", x
);
1106 poly_Free (&merged
);
1109 p
->Clipped
= biggest (merged
);
1110 assert (!p
->Clipped
|| poly_Valid (p
->Clipped
));
1115 if (p
->NoHoles
) printf ("Just leaked in Unsubtract\n");
1121 UnsubtractPin (PinType
* pin
, LayerType
* l
, PolygonType
* p
)
1125 /* overlap a bit to prevent gaps from rounding errors */
1126 np
= BoxPolyBloated (&pin
->BoundingBox
, UNSUBTRACT_BLOAT
);
1130 if (!Unsubtract (np
, p
))
1132 clearPoly (PCB
->Data
, l
, p
, (const BoxType
*) pin
, 2 * UNSUBTRACT_BLOAT
);
1137 UnsubtractArc (ArcType
* arc
, LayerType
* l
, PolygonType
* p
)
1141 if (!TEST_FLAG (CLEARLINEFLAG
, arc
))
1144 /* overlap a bit to prevent gaps from rounding errors */
1145 np
= BoxPolyBloated (&arc
->BoundingBox
, UNSUBTRACT_BLOAT
);
1149 if (!Unsubtract (np
, p
))
1151 clearPoly (PCB
->Data
, l
, p
, (const BoxType
*) arc
, 2 * UNSUBTRACT_BLOAT
);
1156 UnsubtractLine (LineType
* line
, LayerType
* l
, PolygonType
* p
)
1160 if (!TEST_FLAG (CLEARLINEFLAG
, line
))
1163 /* overlap a bit to prevent notches from rounding errors */
1164 np
= BoxPolyBloated (&line
->BoundingBox
, UNSUBTRACT_BLOAT
);
1168 if (!Unsubtract (np
, p
))
1170 clearPoly (PCB
->Data
, l
, p
, (const BoxType
*) line
, 2 * UNSUBTRACT_BLOAT
);
1175 UnsubtractText (TextType
* text
, LayerType
* l
, PolygonType
* p
)
1179 if (!TEST_FLAG (CLEARLINEFLAG
, text
))
1182 /* overlap a bit to prevent notches from rounding errors */
1183 np
= BoxPolyBloated (&text
->BoundingBox
, UNSUBTRACT_BLOAT
);
1187 if (!Unsubtract (np
, p
))
1189 clearPoly (PCB
->Data
, l
, p
, (const BoxType
*) text
, 2 * UNSUBTRACT_BLOAT
);
1194 UnsubtractPad (PadType
* pad
, LayerType
* l
, PolygonType
* p
)
1198 /* overlap a bit to prevent notches from rounding errors */
1199 np
= BoxPolyBloated (&pad
->BoundingBox
, UNSUBTRACT_BLOAT
);
1203 if (!Unsubtract (np
, p
))
1205 clearPoly (PCB
->Data
, l
, p
, (const BoxType
*) pad
, 2 * UNSUBTRACT_BLOAT
);
1209 static bool inhibit
= false;
1212 InitClip (DataTypePtr Data
, LayerTypePtr layer
, PolygonType
* p
)
1217 poly_Free (&p
->Clipped
);
1218 p
->Clipped
= original_poly (p
);
1219 poly_FreeContours (&p
->NoHoles
);
1222 assert (poly_Valid (p
->Clipped
));
1223 if (TEST_FLAG (CLEARPOLYFLAG
, p
))
1224 clearPoly (Data
, layer
, p
, NULL
, 0);
1226 p
->NoHolesValid
= 0;
1230 /* --------------------------------------------------------------------------
1231 * remove redundant polygon points. Any point that lies on the straight
1232 * line between the points on either side of it is redundant.
1233 * returns true if any points are removed
1236 RemoveExcessPolygonPoints (LayerTypePtr Layer
, PolygonTypePtr Polygon
)
1239 Cardinal n
, prev
, next
;
1241 bool changed
= false;
1246 for (n
= 0; n
< Polygon
->PointN
; n
++)
1248 prev
= prev_contour_point (Polygon
, n
);
1249 next
= next_contour_point (Polygon
, n
);
1250 p
= &Polygon
->Points
[n
];
1252 line
.Point1
= Polygon
->Points
[prev
];
1253 line
.Point2
= Polygon
->Points
[next
];
1255 if (IsPointOnLine (p
->X
, p
->Y
, 0.0, &line
))
1257 RemoveObject (POLYGONPOINT_TYPE
, Layer
, Polygon
, p
);
1264 /* ---------------------------------------------------------------------------
1265 * returns the index of the polygon point which is the end
1266 * point of the segment with the lowest distance to the passed
1270 GetLowestDistancePolygonPoint (PolygonTypePtr Polygon
, Coord X
, Coord Y
)
1272 double mindistance
= (double) MAX_COORD
* MAX_COORD
;
1273 PointTypePtr ptr1
, ptr2
;
1274 Cardinal n
, result
= 0;
1276 /* we calculate the distance to each segment and choose the
1277 * shortest distance. If the closest approach between the
1278 * given point and the projected line (i.e. the segment extended)
1279 * is not on the segment, then the distance is the distance
1280 * to the segment end point.
1283 for (n
= 0; n
< Polygon
->PointN
; n
++)
1286 ptr1
= &Polygon
->Points
[prev_contour_point (Polygon
, n
)];
1287 ptr2
= &Polygon
->Points
[n
];
1289 dx
= ptr2
->X
- ptr1
->X
;
1290 dy
= ptr2
->Y
- ptr1
->Y
;
1291 if (dx
!= 0.0 || dy
!= 0.0)
1293 /* projected intersection is at P1 + u(P2 - P1) */
1294 u
= ((X
- ptr1
->X
) * dx
+ (Y
- ptr1
->Y
) * dy
) / (dx
* dx
+ dy
* dy
);
1297 { /* ptr1 is closest point */
1298 u
= SQUARE (X
- ptr1
->X
) + SQUARE (Y
- ptr1
->Y
);
1301 { /* ptr2 is closest point */
1302 u
= SQUARE (X
- ptr2
->X
) + SQUARE (Y
- ptr2
->Y
);
1305 { /* projected intersection is closest point */
1306 u
= SQUARE (X
- ptr1
->X
* (1.0 - u
) - u
* ptr2
->X
) +
1307 SQUARE (Y
- ptr1
->Y
* (1.0 - u
) - u
* ptr2
->Y
);
1309 if (u
< mindistance
)
1319 /* ---------------------------------------------------------------------------
1320 * go back to the previous point of the polygon
1323 GoToPreviousPoint (void)
1325 switch (Crosshair
.AttachedPolygon
.PointN
)
1327 /* do nothing if mode has just been entered */
1331 /* reset number of points and 'LINE_MODE' state */
1333 Crosshair
.AttachedPolygon
.PointN
= 0;
1334 Crosshair
.AttachedLine
.State
= STATE_FIRST
;
1338 /* back-up one point */
1341 PointTypePtr points
= Crosshair
.AttachedPolygon
.Points
;
1342 Cardinal n
= Crosshair
.AttachedPolygon
.PointN
- 2;
1344 Crosshair
.AttachedPolygon
.PointN
--;
1345 Crosshair
.AttachedLine
.Point1
.X
= points
[n
].X
;
1346 Crosshair
.AttachedLine
.Point1
.Y
= points
[n
].Y
;
1352 /* ---------------------------------------------------------------------------
1353 * close polygon if possible
1358 Cardinal n
= Crosshair
.AttachedPolygon
.PointN
;
1360 /* check number of points */
1363 /* if 45 degree lines are what we want do a quick check
1364 * if closing the polygon makes sense
1366 if (!TEST_FLAG (ALLDIRECTIONFLAG
, PCB
))
1370 dx
= abs (Crosshair
.AttachedPolygon
.Points
[n
- 1].X
-
1371 Crosshair
.AttachedPolygon
.Points
[0].X
);
1372 dy
= abs (Crosshair
.AttachedPolygon
.Points
[n
- 1].Y
-
1373 Crosshair
.AttachedPolygon
.Points
[0].Y
);
1374 if (!(dx
== 0 || dy
== 0 || dx
== dy
))
1378 ("Cannot close polygon because 45 degree lines are requested.\n"));
1382 CopyAttachedPolygonToLayer ();
1386 Message (_("A polygon has to have at least 3 points\n"));
1389 /* ---------------------------------------------------------------------------
1390 * moves the data of the attached (new) polygon to the current layer
1393 CopyAttachedPolygonToLayer (void)
1395 PolygonTypePtr polygon
;
1398 /* move data to layer and clear attached struct */
1399 polygon
= CreateNewPolygon (CURRENT
, NoFlags ());
1400 saveID
= polygon
->ID
;
1401 *polygon
= Crosshair
.AttachedPolygon
;
1402 polygon
->ID
= saveID
;
1403 SET_FLAG (CLEARPOLYFLAG
, polygon
);
1404 if (TEST_FLAG (NEWFULLPOLYFLAG
, PCB
))
1405 SET_FLAG (FULLPOLYFLAG
, polygon
);
1406 memset (&Crosshair
.AttachedPolygon
, 0, sizeof (PolygonType
));
1407 SetPolygonBoundingBox (polygon
);
1408 if (!CURRENT
->polygon_tree
)
1409 CURRENT
->polygon_tree
= r_create_tree (NULL
, 0, 0);
1410 r_insert_entry (CURRENT
->polygon_tree
, (BoxType
*) polygon
, 0);
1411 InitClip (PCB
->Data
, CURRENT
, polygon
);
1412 DrawPolygon (CURRENT
, polygon
);
1413 SetChangedFlag (true);
1415 /* reset state of attached line */
1416 Crosshair
.AttachedLine
.State
= STATE_FIRST
;
1419 /* add to undo list */
1420 AddObjectToCreateUndoList (POLYGON_TYPE
, CURRENT
, polygon
, polygon
);
1421 IncrementUndoSerialNumber ();
1424 /* find polygon holes in range, then call the callback function for
1425 * each hole. If the callback returns non-zero, stop
1429 PolygonHoles (PolygonType
*polygon
, const BoxType
*range
,
1430 int (*callback
) (PLINE
*contour
, void *user_data
),
1433 POLYAREA
*pa
= polygon
->Clipped
;
1435 /* If this hole is so big the polygon doesn't exist, then it's not
1440 for (pl
= pa
->contours
->next
; pl
; pl
= pl
->next
)
1442 if (range
!= NULL
&&
1443 (pl
->xmin
> range
->X2
|| pl
->xmax
< range
->X1
||
1444 pl
->ymin
> range
->Y2
|| pl
->ymax
< range
->Y1
))
1446 if (callback (pl
, user_data
))
1460 int (*callback
) (DataTypePtr
, LayerTypePtr
, PolygonTypePtr
, int, void *,
1465 subtract_plow (DataTypePtr Data
, LayerTypePtr Layer
, PolygonTypePtr Polygon
,
1466 int type
, void *ptr1
, void *ptr2
)
1468 if (!Polygon
->Clipped
)
1474 SubtractPin (Data
, (PinTypePtr
) ptr2
, Layer
, Polygon
);
1475 Polygon
->NoHolesValid
= 0;
1478 SubtractLine ((LineTypePtr
) ptr2
, Polygon
);
1479 Polygon
->NoHolesValid
= 0;
1482 SubtractArc ((ArcTypePtr
) ptr2
, Polygon
);
1483 Polygon
->NoHolesValid
= 0;
1486 SubtractPad ((PadTypePtr
) ptr2
, Polygon
);
1487 Polygon
->NoHolesValid
= 0;
1490 SubtractText ((TextTypePtr
) ptr2
, Polygon
);
1491 Polygon
->NoHolesValid
= 0;
1498 add_plow (DataTypePtr Data
, LayerTypePtr Layer
, PolygonTypePtr Polygon
,
1499 int type
, void *ptr1
, void *ptr2
)
1505 UnsubtractPin ((PinTypePtr
) ptr2
, Layer
, Polygon
);
1508 UnsubtractLine ((LineTypePtr
) ptr2
, Layer
, Polygon
);
1511 UnsubtractArc ((ArcTypePtr
) ptr2
, Layer
, Polygon
);
1514 UnsubtractPad ((PadTypePtr
) ptr2
, Layer
, Polygon
);
1517 UnsubtractText ((TextTypePtr
) ptr2
, Layer
, Polygon
);
1524 plow_callback (const BoxType
* b
, void *cl
)
1526 struct plow_info
*plow
= (struct plow_info
*) cl
;
1527 PolygonTypePtr polygon
= (PolygonTypePtr
) b
;
1529 if (TEST_FLAG (CLEARPOLYFLAG
, polygon
))
1530 return plow
->callback (plow
->data
, plow
->layer
, polygon
, plow
->type
,
1531 plow
->ptr1
, plow
->ptr2
);
1536 PlowsPolygon (DataType
* Data
, int type
, void *ptr1
, void *ptr2
,
1537 int (*call_back
) (DataTypePtr data
, LayerTypePtr lay
,
1538 PolygonTypePtr poly
, int type
, void *ptr1
,
1541 BoxType sb
= ((PinTypePtr
) ptr2
)->BoundingBox
;
1543 struct plow_info info
;
1549 info
.callback
= call_back
;
1554 if (type
== PIN_TYPE
|| ptr1
== ptr2
|| ptr1
== NULL
)
1556 LAYER_LOOP (Data
, max_copper_layer
);
1560 r_search (layer
->polygon_tree
, &sb
, NULL
, plow_callback
, &info
);
1566 GROUP_LOOP (Data
, GetLayerGroupNumberByNumber (GetLayerNumber (Data
,
1567 ((LayerTypePtr
) ptr1
))));
1571 r_search (layer
->polygon_tree
, &sb
, NULL
, plow_callback
, &info
);
1579 /* the cast works equally well for lines and arcs */
1580 if (!TEST_FLAG (CLEARLINEFLAG
, (LineTypePtr
) ptr2
))
1582 /* silk doesn't plow */
1583 if (GetLayerNumber (Data
, (LayerTypePtr
)ptr1
) >= max_copper_layer
)
1585 GROUP_LOOP (Data
, GetLayerGroupNumberByNumber (GetLayerNumber (Data
,
1586 ((LayerTypePtr
) ptr1
))));
1589 r
+= r_search (layer
->polygon_tree
, &sb
, NULL
, plow_callback
, &info
);
1595 Cardinal group
= GetLayerGroupNumberByNumber (
1596 TEST_FLAG (ONSOLDERFLAG
, (PadType
*) ptr2
) ?
1597 solder_silk_layer
: component_silk_layer
);
1598 GROUP_LOOP (Data
, group
);
1602 r_search (layer
->polygon_tree
, &sb
, NULL
, plow_callback
, &info
);
1610 PIN_LOOP ((ElementType
*) ptr1
);
1612 PlowsPolygon (Data
, PIN_TYPE
, ptr1
, pin
, call_back
);
1615 PAD_LOOP ((ElementType
*) ptr1
);
1617 PlowsPolygon (Data
, PAD_TYPE
, ptr1
, pad
, call_back
);
1627 RestoreToPolygon (DataType
* Data
, int type
, void *ptr1
, void *ptr2
)
1629 if (type
== POLYGON_TYPE
)
1630 InitClip (PCB
->Data
, (LayerTypePtr
) ptr1
, (PolygonTypePtr
) ptr2
);
1632 PlowsPolygon (Data
, type
, ptr1
, ptr2
, add_plow
);
1636 ClearFromPolygon (DataType
* Data
, int type
, void *ptr1
, void *ptr2
)
1638 if (type
== POLYGON_TYPE
)
1639 InitClip (PCB
->Data
, (LayerTypePtr
) ptr1
, (PolygonTypePtr
) ptr2
);
1641 PlowsPolygon (Data
, type
, ptr1
, ptr2
, subtract_plow
);
1645 isects (POLYAREA
* a
, PolygonTypePtr p
, bool fr
)
1649 ans
= Touching (a
, p
->Clipped
);
1650 /* argument may be register, so we must copy it */
1659 IsPointInPolygon (Coord X
, Coord Y
, Coord r
, PolygonTypePtr p
)
1665 if (poly_CheckInside (p
->Clipped
, v
))
1669 if (!(c
= CirclePoly (X
, Y
, r
)))
1671 return isects (c
, p
, true);
1676 IsPointInPolygonIgnoreHoles (Coord X
, Coord Y
, PolygonTypePtr p
)
1681 return poly_InsideContour (p
->Clipped
->contours
, v
);
1685 IsRectangleInPolygon (Coord X1
, Coord Y1
, Coord X2
, Coord Y2
, PolygonTypePtr p
)
1689 (s
= RectPoly (min (X1
, X2
), max (X1
, X2
), min (Y1
, Y2
), max (Y1
, Y2
))))
1691 return isects (s
, p
, true);
1694 /* NB: This function will free the passed POLYAREA.
1695 * It must only be passed a single POLYAREA (pa->f == pa->b == pa)
1698 r_NoHolesPolygonDicer (POLYAREA
* pa
,
1699 void (*emit
) (PLINE
*, void *), void *user_data
)
1701 PLINE
*p
= pa
->contours
;
1703 if (!pa
->contours
->next
) /* no holes */
1705 pa
->contours
= NULL
; /* The callback now owns the contour */
1706 /* Don't bother removing it from the POLYAREA's rtree
1707 since we're going to free the POLYAREA below anyway */
1708 emit (p
, user_data
);
1714 POLYAREA
*poly2
, *left
, *right
;
1716 /* make a rectangle of the left region slicing through the middle of the first hole */
1717 poly2
= RectPoly (p
->xmin
, (p
->next
->xmin
+ p
->next
->xmax
) / 2,
1719 poly_AndSubtract_free (pa
, poly2
, &left
, &right
);
1722 POLYAREA
*cur
, *next
;
1727 cur
->f
= cur
->b
= cur
; /* Detach this polygon piece */
1728 r_NoHolesPolygonDicer (cur
, emit
, user_data
);
1729 /* NB: The POLYAREA was freed by its use in the recursive dicer */
1731 while ((cur
= next
) != left
);
1735 POLYAREA
*cur
, *next
;
1740 cur
->f
= cur
->b
= cur
; /* Detach this polygon piece */
1741 r_NoHolesPolygonDicer (cur
, emit
, user_data
);
1742 /* NB: The POLYAREA was freed by its use in the recursive dicer */
1744 while ((cur
= next
) != right
);
1750 NoHolesPolygonDicer (PolygonTypePtr p
, const BoxType
* clip
,
1751 void (*emit
) (PLINE
*, void *), void *user_data
)
1753 POLYAREA
*main_contour
, *cur
, *next
;
1755 main_contour
= poly_Create ();
1756 /* copy the main poly only */
1757 poly_Copy1 (main_contour
, p
->Clipped
);
1758 /* clip to the bounding box */
1761 POLYAREA
*cbox
= RectPoly (clip
->X1
, clip
->X2
, clip
->Y1
, clip
->Y2
);
1762 poly_Boolean_free (main_contour
, cbox
, &main_contour
, PBO_ISECT
);
1764 if (main_contour
== NULL
)
1767 * NB: Could be more than one piece (because of the clip above)
1773 cur
->f
= cur
->b
= cur
; /* Detach this polygon piece */
1774 r_NoHolesPolygonDicer (cur
, emit
, user_data
);
1775 /* NB: The POLYAREA was freed by its use in the recursive dicer */
1777 while ((cur
= next
) != main_contour
);
1780 /* make a polygon split into multiple parts into multiple polygons */
1782 MorphPolygon (LayerTypePtr layer
, PolygonTypePtr poly
)
1784 POLYAREA
*p
, *start
;
1788 if (!poly
->Clipped
|| TEST_FLAG (LOCKFLAG
, poly
))
1790 if (poly
->Clipped
->f
== poly
->Clipped
)
1792 ErasePolygon (poly
);
1793 start
= p
= poly
->Clipped
;
1794 /* This is ugly. The creation of the new polygons can cause
1795 * all of the polygon pointers (including the one we're called
1796 * with to change if there is a realloc in GetPolygonMemory().
1797 * That will invalidate our original "poly" argument, potentially
1798 * inside the loop. We need to steal the Clipped pointer and
1799 * hide it from the Remove call so that it still exists while
1800 * we do this dirty work.
1802 poly
->Clipped
= NULL
;
1803 if (poly
->NoHoles
) printf ("Just leaked in MorpyPolygon\n");
1804 poly
->NoHoles
= NULL
;
1805 flags
= poly
->Flags
;
1806 RemovePolygon (layer
, poly
);
1811 PolygonTypePtr newone
;
1813 if (p
->contours
->area
> PCB
->IsleArea
)
1815 newone
= CreateNewPolygon (layer
, flags
);
1819 v
= &p
->contours
->head
;
1820 CreateNewPointInPolygon (newone
, v
->point
[0], v
->point
[1]);
1821 for (v
= v
->next
; v
!= &p
->contours
->head
; v
= v
->next
)
1822 CreateNewPointInPolygon (newone
, v
->point
[0], v
->point
[1]);
1823 newone
->BoundingBox
.X1
= p
->contours
->xmin
;
1824 newone
->BoundingBox
.X2
= p
->contours
->xmax
+ 1;
1825 newone
->BoundingBox
.Y1
= p
->contours
->ymin
;
1826 newone
->BoundingBox
.Y2
= p
->contours
->ymax
+ 1;
1827 AddObjectToCreateUndoList (POLYGON_TYPE
, layer
, newone
, newone
);
1828 newone
->Clipped
= p
;
1829 p
= p
->f
; /* go to next pline */
1830 newone
->Clipped
->b
= newone
->Clipped
->f
= newone
->Clipped
; /* unlink from others */
1831 r_insert_entry (layer
->polygon_tree
, (BoxType
*) newone
, 0);
1832 DrawPolygon (layer
, newone
);
1839 poly_DelContour (&t
->contours
);
1845 IncrementUndoSerialNumber ();
1849 void debug_pline (PLINE
*pl
)
1852 pcb_fprintf (stderr
, "\txmin %#mS xmax %#mS ymin %#mS ymax %#mS\n",
1853 pl
->xmin
, pl
->xmax
, pl
->ymin
, pl
->ymax
);
1857 pcb_fprintf(stderr
, "\t\tvnode: %#mD\n", v
->point
[0], v
->point
[1]);
1865 debug_polyarea (POLYAREA
*p
)
1869 fprintf (stderr
, "POLYAREA %p\n", p
);
1870 for (pl
=p
->contours
; pl
; pl
=pl
->next
)
1875 debug_polygon (PolygonType
*p
)
1879 fprintf (stderr
, "POLYGON %p %d pts\n", p
, p
->PointN
);
1880 for (i
=0; i
<p
->PointN
; i
++)
1881 pcb_fprintf(stderr
, "\t%d: %#mD\n", i
, p
->Points
[i
].X
, p
->Points
[i
].Y
);
1884 fprintf (stderr
, "%d holes, starting at indices\n", p
->HoleIndexN
);
1885 for (i
=0; i
<p
->HoleIndexN
; i
++)
1886 fprintf(stderr
, "\t%d: %d\n", i
, p
->HoleIndex
[i
]);
1889 fprintf (stderr
, "it has no holes\n");
1893 debug_polyarea (pa
);
1895 if (pa
== p
->Clipped
)
1900 /* Convert a POLYAREA (and all linked POLYAREA) to
1901 * raw PCB polygons on the given layer.
1904 PolyToPolygonsOnLayer (DataType
*Destination
, LayerType
*Layer
,
1905 POLYAREA
*Input
, FlagType Flags
)
1907 PolygonType
*Polygon
;
1919 Polygon
= CreateNewPolygon (Layer
, Flags
);
1921 pline
= pa
->contours
;
1927 CreateNewHoleInPolygon (Polygon
);
1930 node
= &pline
->head
;
1933 CreateNewPointInPolygon (Polygon
, node
->point
[0],
1936 while ((node
= node
->next
) != &pline
->head
);
1939 while ((pline
= pline
->next
) != NULL
);
1941 InitClip (Destination
, Layer
, Polygon
);
1942 SetPolygonBoundingBox (Polygon
);
1943 if (!Layer
->polygon_tree
)
1944 Layer
->polygon_tree
= r_create_tree (NULL
, 0, 0);
1945 r_insert_entry (Layer
->polygon_tree
, (BoxType
*) Polygon
, 0);
1947 DrawPolygon (Layer
, Polygon
);
1948 /* add to undo list */
1949 AddObjectToCreateUndoList (POLYGON_TYPE
, Layer
, Polygon
, Polygon
);
1951 while ((pa
= pa
->f
) != Input
);
1953 SetChangedFlag (true);