1 /*!
2 * \file src/polygon.c
3 *
4 * \brief Special polygon editing routines.
5 *
6 * Here's a brief tour of the data and life of a polygon, courtesy of
7 * Ben Jackson:
8 *
9 * A PCB PolygonType contains an array of points outlining the polygon.
10 * This is what is manipulated by the UI and stored in the saved PCB.
11 *
12 * A PolygonType also contains a POLYAREA called 'Clipped' which is
13 * computed dynamically by InitClip every time a board is loaded.
14 * The point array is coverted to a POLYAREA by original_poly and then
15 * holes are cut in it by clearPoly.
16 * After that it is maintained dynamically as parts are added, moved or
17 * removed (this is why sometimes bugs can be fixed by just re-loading
18 * the board).
19 *
20 * A POLYAREA consists of a linked list of PLINE structures.
21 * The head of that list is POLYAREA.contours.
22 * The first contour is an outline of a filled region.
23 * All of the subsequent PLINEs are holes cut out of that first contour.
24 * POLYAREAs are in a doubly-linked list and each member of the list is
25 * an independent (non-overlapping) area with its own outline and holes.
26 * The function biggest() finds the largest POLYAREA so that
27 * PolygonType.Clipped points to that shape.
28 * The rest of the polygon still exists, it's just ignored when turning
29 * the polygon into copper.
30 *
31 * The first POLYAREA in PolygonType.Clipped is what is used for the
32 * vast majority of Polygon related tests.
33 * The basic logic for an intersection is "is the target shape inside
34 * POLYAREA.contours and NOT fully enclosed in any of
35 * POLYAREA.contours.next... (the holes)".
36 *
37 * The polygon dicer (NoHolesPolygonDicer and r_NoHolesPolygonDicer)
38 * emits a series of "simple" PLINE shapes.
39 * That is, the PLINE isn't linked to any other "holes" oulines.
40 * That's the meaning of the first test in r_NoHolesPolygonDicer.
41 * It is testing to see if the PLINE contour (the first, making it a
42 * solid outline) has a valid next pointer (which would point to one or
43 * more holes).
44 * The dicer works by recursively chopping the polygon in half through
45 * the first hole it sees (which is guaranteed to eliminate at least
46 * that one hole).
47 * The dicer output is used for HIDs which cannot render things with
48 * holes (which would require erasure).
49 *
50 * <hr>
51 *
52 * <h1><b>Copyright.</b></h1>\n
53 *
54 * PCB, interactive printed circuit board design
55 *
56 * Copyright (C) 1994,1995,1996,2010 Thomas Nau
57 *
58 * This program is free software; you can redistribute it and/or modify
59 * it under the terms of the GNU General Public License as published by
60 * the Free Software Foundation; either version 2 of the License, or
61 * (at your option) any later version.
62 *
63 * This program is distributed in the hope that it will be useful,
64 * but WITHOUT ANY WARRANTY; without even the implied warranty of
65 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
66 * GNU General Public License for more details.
67 *
68 * You should have received a copy of the GNU General Public License along
69 * with this program; if not, write to the Free Software Foundation, Inc.,
70 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
71 *
72 * Contact addresses for paper mail and Email:
73 *
74 * Thomas Nau, Schlehenweg 15, 88471 Baustetten, Germany
75 *
76 * Thomas.Nau@rz.uni-ulm.de
77 */
78
79 #ifdef HAVE_CONFIG_H
80 #include "config.h"
81 #endif
82
83 #include <assert.h>
84 #include <math.h>
85 #include <memory.h>
86 #include <setjmp.h>
87
88 #include "global.h"
89 #include "box.h"
90 #include "create.h"
91 #include "crosshair.h"
92 #include "data.h"
93 #include "draw.h"
94 #include "error.h"
95 #include "find.h"
96 #include "misc.h"
97 #include "move.h"
98 #include "pcb-printf.h"
99 #include "polygon.h"
100 #include "remove.h"
101 #include "rtree.h"
102 #include "search.h"
103 #include "set.h"
104 #include "thermal.h"
105 #include "undo.h"
106
107 #ifdef HAVE_LIBDMALLOC
108 #include <dmalloc.h>
109 #endif
110
111 #define ROUND(x) ((long)(((x) >= 0 ? (x) + 0.5 : (x) - 0.5)))
112
113 #define UNSUBTRACT_BLOAT 10
114 #define SUBTRACT_PIN_VIA_BATCH_SIZE 100
115 #define SUBTRACT_LINE_BATCH_SIZE 20
116
117 static double rotate_circle_seg[4];
118
119 void
polygon_init(void)120 polygon_init (void)
121 {
122 double cos_ang = cos (2.0 * M_PI / POLY_CIRC_SEGS_F);
123 double sin_ang = sin (2.0 * M_PI / POLY_CIRC_SEGS_F);
124
125 rotate_circle_seg[0] = cos_ang; rotate_circle_seg[1] = -sin_ang;
126 rotate_circle_seg[2] = sin_ang; rotate_circle_seg[3] = cos_ang;
127 }
128
129 Cardinal
polygon_point_idx(PolygonType * polygon,PointType * point)130 polygon_point_idx (PolygonType *polygon, PointType *point)
131 {
132 assert (point >= polygon->Points);
133 assert (point <= polygon->Points + polygon->PointN);
134 return ((char *)point - (char *)polygon->Points) / sizeof (PointType);
135 }
136
137 /*!
138 * \brief Find contour number.
139 *
140 * 0 for outer,
141 *
142 * 1 for first hole etc..
143 */
144 Cardinal
polygon_point_contour(PolygonType * polygon,Cardinal point)145 polygon_point_contour (PolygonType *polygon, Cardinal point)
146 {
147 Cardinal i;
148 Cardinal contour = 0;
149
150 for (i = 0; i < polygon->HoleIndexN; i++)
151 if (point >= polygon->HoleIndex[i])
152 contour = i + 1;
153 return contour;
154 }
155
156 Cardinal
next_contour_point(PolygonType * polygon,Cardinal point)157 next_contour_point (PolygonType *polygon, Cardinal point)
158 {
159 Cardinal contour;
160 Cardinal this_contour_start;
161 Cardinal next_contour_start;
162
163 contour = polygon_point_contour (polygon, point);
164
165 this_contour_start = (contour == 0) ? 0 :
166 polygon->HoleIndex[contour - 1];
167 next_contour_start =
168 (contour == polygon->HoleIndexN) ? polygon->PointN :
169 polygon->HoleIndex[contour];
170
171 /* Wrap back to the start of the contour we're in if we pass the end */
172 if (++point == next_contour_start)
173 point = this_contour_start;
174
175 return point;
176 }
177
178 Cardinal
prev_contour_point(PolygonType * polygon,Cardinal point)179 prev_contour_point (PolygonType *polygon, Cardinal point)
180 {
181 Cardinal contour;
182 Cardinal prev_contour_end;
183 Cardinal this_contour_end;
184
185 contour = polygon_point_contour (polygon, point);
186
187 prev_contour_end = (contour == 0) ? 0 :
188 polygon->HoleIndex[contour - 1];
189 this_contour_end =
190 (contour == polygon->HoleIndexN) ? polygon->PointN - 1:
191 polygon->HoleIndex[contour] - 1;
192
193 /* Wrap back to the start of the contour we're in if we pass the end */
194 if (point == prev_contour_end)
195 point = this_contour_end;
196 else
197 point--;
198
199 return point;
200 }
201
202 static void
add_noholes_polyarea(PLINE * pline,void * user_data)203 add_noholes_polyarea (PLINE *pline, void *user_data)
204 {
205 PolygonType *poly = (PolygonType *)user_data;
206
207 /* Prepend the pline into the NoHoles linked list */
208 pline->next = poly->NoHoles;
209 poly->NoHoles = pline;
210 }
211
212 void
ComputeNoHoles(PolygonType * poly)213 ComputeNoHoles (PolygonType *poly)
214 {
215 poly_FreeContours (&poly->NoHoles);
216 if (poly->Clipped)
217 NoHolesPolygonDicer (poly, NULL, add_noholes_polyarea, poly);
218 else
219 printf ("Compute_noholes caught poly->Clipped = NULL\n");
220 poly->NoHolesValid = 1;
221 }
222
223 static POLYAREA *
biggest(POLYAREA * p)224 biggest (POLYAREA * p)
225 {
226 POLYAREA *n, *top = NULL;
227 PLINE *pl;
228 rtree_t *tree;
229 double big = -1;
230 if (!p)
231 return NULL;
232 n = p;
233 do
234 {
235 #if 0
236 if (n->contours->area < PCB->IsleArea)
237 {
238 n->b->f = n->f;
239 n->f->b = n->b;
240 poly_DelContour (&n->contours);
241 if (n == p)
242 p = n->f;
243 n = n->f;
244 if (!n->contours)
245 {
246 free (n);
247 return NULL;
248 }
249 }
250 #endif
251 if (n->contours->area > big)
252 {
253 top = n;
254 big = n->contours->area;
255 }
256 }
257 while ((n = n->f) != p);
258 assert (top);
259 if (top == p)
260 return p;
261 pl = top->contours;
262 tree = top->contour_tree;
263 top->contours = p->contours;
264 top->contour_tree = p->contour_tree;
265 p->contours = pl;
266 p->contour_tree = tree;
267 assert (pl);
268 assert (p->f);
269 assert (p->b);
270 return p;
271 }
272
273 POLYAREA *
ContourToPoly(PLINE * contour)274 ContourToPoly (PLINE * contour)
275 {
276 POLYAREA *p;
277 poly_PreContour (contour, TRUE);
278 assert (contour->Flags.orient == PLF_DIR);
279 if (!(p = poly_Create ()))
280 return NULL;
281 poly_InclContour (p, contour);
282 assert (poly_Valid (p));
283 return p;
284 }
285
286 /*!
287 * \brief Generate the basic polygon shape.
288 *
289 * This includes the perimeter of the polygon with any holes removed, but no
290 * areas cleared by objects.
291 * */
292 POLYAREA *
original_poly(PolygonType * p)293 original_poly (PolygonType * p)
294 {
295 PLINE *contour = NULL;
296 POLYAREA *np = NULL;
297 Cardinal n;
298 Vector v;
299 int hole = 0;
300
301 /* If we can't create the structures, we can't do anything. */
302 if ((np = poly_Create ()) == NULL)
303 return NULL;
304
305 /* Iterate over every point in the array. Note that this includes both the
306 * perimeter points and the points that define holes contours in the
307 * polygon. The indices at which the points of each hole start are
308 * recorded in the HoleIndex array. */
309 for (n = 0; n < p->PointN; n++)
310 {
311 /* No current contour? Make a new one starting at point */
312 /* (or) Add point to existing contour */
313
314 v[0] = p->Points[n].X;
315 v[1] = p->Points[n].Y;
316 if (contour == NULL)
317 {
318 /* This is the first VNODE in the contour, we need to initialize
319 * the contour.
320 * */
321 if ((contour = poly_NewContour (v)) == NULL)
322 return NULL; /* Couldn't allocate memory*/
323 }
324 else
325 {
326 /* Create a new VNODE at v, and insert it after head.prev */
327 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
328 }
329
330 /* Is current point last in contour (perimeter or hole)?
331 * If so process it.
332 * */
333 if (n == p->PointN - 1 /* last perimeter point */
334 /* or, last point of a hole contour.*/
335 || (hole < p->HoleIndexN && n == p->HoleIndex[hole] - 1))
336 {
337 /* Process the contour */
338 poly_PreContour (contour, TRUE);
339
340 /* make sure it is a positive contour (outer) or negative (hole) */
341 if (contour->Flags.orient != (hole ? PLF_INV : PLF_DIR))
342 poly_InvContour (contour);
343 assert (contour->Flags.orient == (hole ? PLF_INV : PLF_DIR));
344
345 /* Insert the contour in the POLYAREA PLINE chain */
346 poly_InclContour (np, contour);
347 assert (poly_Valid (np));
348
349 /* advance to the next hole contour and start over */
350 hole++;
351 contour = NULL;
352 }
353 }
354 return biggest (np);
355 }
356
357 POLYAREA *
PolygonToPoly(PolygonType * p)358 PolygonToPoly (PolygonType *p)
359 {
360 return original_poly (p);
361 }
362
363 POLYAREA *
RectPoly(Coord x1,Coord x2,Coord y1,Coord y2)364 RectPoly (Coord x1, Coord x2, Coord y1, Coord y2)
365 {
366 PLINE *contour = NULL;
367 Vector v;
368
369 /* Return NULL for zero or negatively sized rectangles */
370 if (x2 <= x1 || y2 <= y1)
371 return NULL;
372
373 v[0] = x1;
374 v[1] = y1;
375 if ((contour = poly_NewContour (v)) == NULL)
376 return NULL;
377 v[0] = x2;
378 v[1] = y1;
379 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
380 v[0] = x2;
381 v[1] = y2;
382 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
383 v[0] = x1;
384 v[1] = y2;
385 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
386 return ContourToPoly (contour);
387 }
388
389 POLYAREA *
OctagonPoly(Coord x,Coord y,Coord radius)390 OctagonPoly (Coord x, Coord y, Coord radius)
391 {
392 PLINE *contour = NULL;
393 Vector v;
394
395 v[0] = x + ROUND (radius * 0.5);
396 v[1] = y + ROUND (radius * TAN_22_5_DEGREE_2);
397 if ((contour = poly_NewContour (v)) == NULL)
398 return NULL;
399 v[0] = x + ROUND (radius * TAN_22_5_DEGREE_2);
400 v[1] = y + ROUND (radius * 0.5);
401 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
402 v[0] = x - (v[0] - x);
403 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
404 v[0] = x - ROUND (radius * 0.5);
405 v[1] = y + ROUND (radius * TAN_22_5_DEGREE_2);
406 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
407 v[1] = y - (v[1] - y);
408 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
409 v[0] = x - ROUND (radius * TAN_22_5_DEGREE_2);
410 v[1] = y - ROUND (radius * 0.5);
411 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
412 v[0] = x - (v[0] - x);
413 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
414 v[0] = x + ROUND (radius * 0.5);
415 v[1] = y - ROUND (radius * TAN_22_5_DEGREE_2);
416 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
417 return ContourToPoly (contour);
418 }
419
420 /*!
421 * \brief Add vertices in a fractional-circle starting from v
422 * centered at X, Y and going counter-clockwise.
423 *
424 * Does not include the first point.
425 * last argument is 1 for a full circle.
426 * 2 for a half circle.
427 * or 4 for a quarter circle.
428 */
429 void
frac_circle(PLINE * c,Coord X,Coord Y,Vector v,int fraction)430 frac_circle (PLINE * c, Coord X, Coord Y, Vector v, int fraction)
431 {
432 double e1, e2, t1;
433 int i, range;
434
435 poly_InclVertex (c->head.prev, poly_CreateNode (v));
436 /* move vector to origin */
437 e1 = (v[0] - X) * POLY_CIRC_RADIUS_ADJ;
438 e2 = (v[1] - Y) * POLY_CIRC_RADIUS_ADJ;
439
440 /* NB: the caller adds the last vertex, hence the -1 */
441 range = POLY_CIRC_SEGS / fraction - 1;
442 for (i = 0; i < range; i++)
443 {
444 /* rotate the vector */
445 t1 = rotate_circle_seg[0] * e1 + rotate_circle_seg[1] * e2;
446 e2 = rotate_circle_seg[2] * e1 + rotate_circle_seg[3] * e2;
447 e1 = t1;
448 v[0] = X + ROUND (e1);
449 v[1] = Y + ROUND (e2);
450 poly_InclVertex (c->head.prev, poly_CreateNode (v));
451 }
452 }
453
454 /*!
455 * \brief Create a circle approximation from lines.
456 */
457 POLYAREA *
CirclePoly(Coord x,Coord y,Coord radius)458 CirclePoly (Coord x, Coord y, Coord radius)
459 {
460 PLINE *contour;
461 Vector v;
462
463 if (radius <= 0)
464 return NULL;
465 v[0] = x + radius;
466 v[1] = y;
467 if ((contour = poly_NewContour (v)) == NULL)
468 return NULL;
469 frac_circle (contour, x, y, v, 1);
470 contour->is_round = TRUE;
471 contour->cx = x;
472 contour->cy = y;
473 contour->radius = radius;
474 return ContourToPoly (contour);
475 }
476
477 /*!
478 * \brief Make a rounded-corner rectangle with radius t beyond
479 * x1,x2,y1,y2 rectangle.
480 */
481 POLYAREA *
RoundRect(Coord x1,Coord x2,Coord y1,Coord y2,Coord t)482 RoundRect (Coord x1, Coord x2, Coord y1, Coord y2, Coord t)
483 {
484 PLINE *contour = NULL;
485 Vector v;
486
487 assert (x2 > x1);
488 assert (y2 > y1);
489 v[0] = x1 - t;
490 v[1] = y1;
491 if ((contour = poly_NewContour (v)) == NULL)
492 return NULL;
493 frac_circle (contour, x1, y1, v, 4);
494 v[0] = x2;
495 v[1] = y1 - t;
496 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
497 frac_circle (contour, x2, y1, v, 4);
498 v[0] = x2 + t;
499 v[1] = y2;
500 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
501 frac_circle (contour, x2, y2, v, 4);
502 v[0] = x1;
503 v[1] = y2 + t;
504 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
505 frac_circle (contour, x1, y2, v, 4);
506 return ContourToPoly (contour);
507 }
508
509 #define ARC_ANGLE 5
510 static POLYAREA *
ArcPolyNoIntersect(ArcType * a,Coord thick)511 ArcPolyNoIntersect (ArcType * a, Coord thick)
512 {
513 PLINE *contour = NULL;
514 POLYAREA *np = NULL;
515 Vector v;
516 BoxType *ends;
517 int i, segs;
518 double ang, da, rx, ry;
519 long half;
520 double radius_adj;
521
522 if (thick <= 0)
523 return NULL;
524 if (a->Delta < 0)
525 {
526 a->StartAngle += a->Delta;
527 a->Delta = -a->Delta;
528 }
529 half = (thick + 1) / 2;
530 ends = GetArcEnds (a);
531 /* start with inner radius */
532 rx = MAX (a->Width - half, 0);
533 ry = MAX (a->Height - half, 0);
534 segs = 1;
535 if(thick > 0)
536 segs = MAX (segs, a->Delta * M_PI / 360 *
537 sqrt (hypot (rx, ry) /
538 POLY_ARC_MAX_DEVIATION / 2 / thick));
539 segs = MAX(segs, a->Delta / ARC_ANGLE);
540
541 ang = a->StartAngle;
542 da = (1.0 * a->Delta) / segs;
543 radius_adj = (M_PI*da/360)*(M_PI*da/360)/2;
544 v[0] = a->X - rx * cos (ang * M180);
545 v[1] = a->Y + ry * sin (ang * M180);
546 if ((contour = poly_NewContour (v)) == NULL)
547 return 0;
548 for (i = 0; i < segs - 1; i++)
549 {
550 ang += da;
551 v[0] = a->X - rx * cos (ang * M180);
552 v[1] = a->Y + ry * sin (ang * M180);
553 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
554 }
555 /* find last point */
556 ang = a->StartAngle + a->Delta;
557 v[0] = a->X - rx * cos (ang * M180) * (1 - radius_adj);
558 v[1] = a->Y + ry * sin (ang * M180) * (1 - radius_adj);
559 /* add the round cap at the end */
560 frac_circle (contour, ends->X2, ends->Y2, v, 2);
561 /* and now do the outer arc (going backwards) */
562 rx = (a->Width + half) * (1+radius_adj);
563 ry = (a->Width + half) * (1+radius_adj);
564 da = -da;
565 for (i = 0; i < segs; i++)
566 {
567 v[0] = a->X - rx * cos (ang * M180);
568 v[1] = a->Y + ry * sin (ang * M180);
569 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
570 ang += da;
571 }
572 /* now add other round cap */
573 ang = a->StartAngle;
574 v[0] = a->X - rx * cos (ang * M180) * (1 - radius_adj);
575 v[1] = a->Y + ry * sin (ang * M180) * (1 - radius_adj);
576 frac_circle (contour, ends->X1, ends->Y1, v, 2);
577 /* now we have the whole contour */
578 if (!(np = ContourToPoly (contour)))
579 return NULL;
580 return np;
581 }
582
583 #define MIN_CLEARANCE_BEFORE_BISECT 10.
584 POLYAREA *
ArcPoly(ArcType * a,Coord thick)585 ArcPoly (ArcType * a, Coord thick)
586 {
587 double delta;
588 ArcType seg1, seg2;
589 POLYAREA *tmp1, *tmp2, *res;
590
591 delta = (a->Delta < 0) ? -a->Delta : a->Delta;
592
593 /* If the arc segment would self-intersect, we need to construct it as the union of
594 two non-intersecting segments */
595
596 if (2 * M_PI * a->Width * (1. - (double)delta / 360.) - thick < MIN_CLEARANCE_BEFORE_BISECT)
597 {
598 int half_delta = a->Delta / 2;
599
600 seg1 = seg2 = *a;
601 seg1.Delta = half_delta;
602 seg2.Delta -= half_delta;
603 seg2.StartAngle += half_delta;
604
605 tmp1 = ArcPolyNoIntersect (&seg1, thick);
606 tmp2 = ArcPolyNoIntersect (&seg2, thick);
607 poly_Boolean_free (tmp1, tmp2, &res, PBO_UNITE);
608 return res;
609 }
610
611 return ArcPolyNoIntersect (a, thick);
612 }
613
614 POLYAREA *
LinePoly(LineType * L,Coord thick)615 LinePoly (LineType * L, Coord thick)
616 {
617 PLINE *contour = NULL;
618 POLYAREA *np = NULL;
619 Vector v;
620 double d, dx, dy;
621 long half;LineType _l=*L,*l=&_l;
622
623 if (thick <= 0)
624 return NULL;
625 half = (thick + 1) / 2;
626 d = hypot (l->Point1.X - l->Point2.X, l->Point1.Y - l->Point2.Y);
627 if (!TEST_FLAG (SQUAREFLAG,l))
628 if (d == 0) /* line is a point */
629 return CirclePoly (l->Point1.X, l->Point1.Y, half);
630 if (d != 0)
631 {
632 d = half / d;
633 dx = (l->Point1.Y - l->Point2.Y) * d;
634 dy = (l->Point2.X - l->Point1.X) * d;
635 }
636 else
637 {
638 dx = half;
639 dy = 0;
640 }
641 if (TEST_FLAG (SQUAREFLAG,l))/* take into account the ends */
642 {
643 l->Point1.X -= dy;
644 l->Point1.Y += dx;
645 l->Point2.X += dy;
646 l->Point2.Y -= dx;
647 }
648 v[0] = l->Point1.X - dx;
649 v[1] = l->Point1.Y - dy;
650 if ((contour = poly_NewContour (v)) == NULL)
651 return 0;
652 v[0] = l->Point2.X - dx;
653 v[1] = l->Point2.Y - dy;
654 if (TEST_FLAG (SQUAREFLAG,l))
655 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
656 else
657 frac_circle (contour, l->Point2.X, l->Point2.Y, v, 2);
658 v[0] = l->Point2.X + dx;
659 v[1] = l->Point2.Y + dy;
660 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
661 v[0] = l->Point1.X + dx;
662 v[1] = l->Point1.Y + dy;
663 if (TEST_FLAG (SQUAREFLAG,l))
664 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
665 else
666 frac_circle (contour, l->Point1.X, l->Point1.Y, v, 2);
667 /* now we have the line contour */
668 if (!(np = ContourToPoly (contour)))
669 return NULL;
670 return np;
671 }
672
673 /*!
674 * \brief Make a rounded-corner rectangle.
675 */
676 POLYAREA *
SquarePadPoly(PadType * pad,Coord clear)677 SquarePadPoly (PadType * pad, Coord clear)
678 {
679 PLINE *contour = NULL;
680 POLYAREA *np = NULL;
681 Vector v;
682 double d;
683 double tx, ty;
684 double cx, cy;
685 PadType _t=*pad,*t=&_t;
686 PadType _c=*pad,*c=&_c;
687 int halfthick = (pad->Thickness + 1) / 2;
688 int halfclear = (clear + 1) / 2;
689
690 d = hypot (pad->Point1.X - pad->Point2.X, pad->Point1.Y - pad->Point2.Y);
691 if (d != 0)
692 {
693 double a = halfthick / d;
694 tx = (t->Point1.Y - t->Point2.Y) * a;
695 ty = (t->Point2.X - t->Point1.X) * a;
696 a = halfclear / d;
697 cx = (c->Point1.Y - c->Point2.Y) * a;
698 cy = (c->Point2.X - c->Point1.X) * a;
699
700 t->Point1.X -= ty;
701 t->Point1.Y += tx;
702 t->Point2.X += ty;
703 t->Point2.Y -= tx;
704 c->Point1.X -= cy;
705 c->Point1.Y += cx;
706 c->Point2.X += cy;
707 c->Point2.Y -= cx;
708 }
709 else
710 {
711 tx = halfthick;
712 ty = 0;
713 cx = halfclear;
714 cy = 0;
715
716 t->Point1.Y += tx;
717 t->Point2.Y -= tx;
718 c->Point1.Y += cx;
719 c->Point2.Y -= cx;
720 }
721
722 v[0] = c->Point1.X - tx;
723 v[1] = c->Point1.Y - ty;
724 if ((contour = poly_NewContour (v)) == NULL)
725 return 0;
726 frac_circle (contour, (t->Point1.X - tx), (t->Point1.Y - ty), v, 4);
727
728 v[0] = t->Point2.X - cx;
729 v[1] = t->Point2.Y - cy;
730 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
731 frac_circle (contour, (t->Point2.X - tx), (t->Point2.Y - ty), v, 4);
732
733 v[0] = c->Point2.X + tx;
734 v[1] = c->Point2.Y + ty;
735 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
736 frac_circle (contour, (t->Point2.X + tx), (t->Point2.Y + ty), v, 4);
737
738 v[0] = t->Point1.X + cx;
739 v[1] = t->Point1.Y + cy;
740 poly_InclVertex (contour->head.prev, poly_CreateNode (v));
741 frac_circle (contour, (t->Point1.X + tx), (t->Point1.Y + ty), v, 4);
742
743 /* now we have the line contour */
744 if (!(np = ContourToPoly (contour)))
745 return NULL;
746 return np;
747 }
748
749 /*!
750 * \brief Clear np1 from the polygon.
751 */
752 static int
Subtract(POLYAREA * np1,PolygonType * p,bool fnp)753 Subtract (POLYAREA * np1, PolygonType * p, bool fnp)
754 {
755 POLYAREA *merged = NULL, *np = np1;
756 int x;
757 assert (np);
758 assert (p);
759
760 if (!p->Clipped)
761 /* polygon has no poly area, nothing to subtract from */
762 {
763 if (fnp)
764 poly_Free (&np);
765 return 1;
766 }
767
768 assert (poly_Valid (p->Clipped));
769 assert (poly_Valid (np));
770
771 /* subtract the polyarea, using a boolean subtraction operation */
772 if (fnp)
773 x = poly_Boolean_free (p->Clipped, np, &merged, PBO_SUB);
774 else
775 {
776 x = poly_Boolean (p->Clipped, np, &merged, PBO_SUB);
777 poly_Free (&p->Clipped);
778 }
779
780 assert (!merged || poly_Valid (merged));
781 if (x != err_ok)
782 {
783 fprintf (stderr, "Error while clipping PBO_SUB: %d\n", x);
784 poly_Free (&merged);
785 p->Clipped = NULL;
786 if (p->NoHoles) printf ("Just leaked in Subtract\n");
787 p->NoHoles = NULL;
788 return -1;
789 }
790 p->Clipped = biggest (merged);
791 assert (!p->Clipped || poly_Valid (p->Clipped));
792 if (!p->Clipped)
793 Message ("Polygon cleared out of existence near (%d, %d)\n",
794 (p->BoundingBox.X1 + p->BoundingBox.X2) / 2,
795 (p->BoundingBox.Y1 + p->BoundingBox.Y2) / 2);
796 return 1;
797 }
798
799 /*!
800 * \brief Create a polygon of the pin clearance.
801 */
802 POLYAREA *
PinPoly(PinType * pin,Coord thick,Coord clear)803 PinPoly (PinType * pin, Coord thick, Coord clear)
804 {
805 int size;
806
807 if (TEST_FLAG (SQUAREFLAG, pin))
808 {
809 size = (thick + 1) / 2;
810 return RoundRect (pin->X - size, pin->X + size, pin->Y - size,
811 pin->Y + size, (clear + 1) / 2);
812 }
813 else
814 {
815 size = (thick + clear + 1) / 2;
816 if (TEST_FLAG (OCTAGONFLAG, pin))
817 {
818 return OctagonPoly (pin->X, pin->Y, size + size);
819 }
820 }
821 return CirclePoly (pin->X, pin->Y, size);
822 }
823
824 POLYAREA *
BoxPolyBloated(BoxType * box,Coord bloat)825 BoxPolyBloated (BoxType *box, Coord bloat)
826 {
827 return RectPoly (box->X1 - bloat, box->X2 + bloat,
828 box->Y1 - bloat, box->Y2 + bloat);
829 }
830
831 /*!
832 * \brief Remove the pin clearance from the polygon.
833 */
834 static int
SubtractPin(DataType * d,PinType * pin,LayerType * l,PolygonType * p)835 SubtractPin (DataType * d, PinType * pin, LayerType * l, PolygonType * p)
836 {
837 POLYAREA *np;
838 Cardinal i;
839
840 if (pin->Clearance == 0)
841 return 0;
842 i = GetLayerNumber (d, l);
843 if (TEST_THERM (i, pin))
844 {
845 np = ThermPoly ((PCBType *) (d->pcb), pin, i);
846 if (!np)
847 return 0;
848 }
849 else
850 {
851 np = PinPoly (pin, PIN_SIZE (pin), pin->Clearance);
852 if (!np)
853 return -1;
854 }
855 return Subtract (np, p, TRUE);
856 }
857
858 static int
SubtractLine(LineType * line,PolygonType * p)859 SubtractLine (LineType * line, PolygonType * p)
860 {
861 POLYAREA *np;
862
863 if (!TEST_FLAG (CLEARLINEFLAG, line))
864 return 0;
865 if (!(np = LinePoly (line, line->Thickness + line->Clearance)))
866 return -1;
867 return Subtract (np, p, true);
868 }
869
870 static int
SubtractArc(ArcType * arc,PolygonType * p)871 SubtractArc (ArcType * arc, PolygonType * p)
872 {
873 POLYAREA *np;
874
875 if (!TEST_FLAG (CLEARLINEFLAG, arc))
876 return 0;
877 if (!(np = ArcPoly (arc, arc->Thickness + arc->Clearance)))
878 return -1;
879 return Subtract (np, p, true);
880 }
881
882 static int
SubtractText(TextType * text,PolygonType * p)883 SubtractText (TextType * text, PolygonType * p)
884 {
885 POLYAREA *np;
886 const BoxType *b = &text->BoundingBox;
887
888 if (!TEST_FLAG (CLEARLINEFLAG, text))
889 return 0;
890 if (!(np = RoundRect (b->X1 + PCB->Bloat, b->X2 - PCB->Bloat,
891 b->Y1 + PCB->Bloat, b->Y2 - PCB->Bloat, PCB->Bloat)))
892 return -1;
893 return Subtract (np, p, true);
894 }
895
896 static int
SubtractPad(PadType * pad,PolygonType * p)897 SubtractPad (PadType * pad, PolygonType * p)
898 {
899 POLYAREA *np = NULL;
900
901 if (pad->Clearance == 0)
902 return 0;
903 if (TEST_FLAG (SQUAREFLAG, pad))
904 {
905 if (!
906 (np = SquarePadPoly (pad, pad->Thickness + pad->Clearance)))
907 return -1;
908 }
909 else
910 {
911 if (!
912 (np = LinePoly ((LineType *) pad, pad->Thickness + pad->Clearance)))
913 return -1;
914 }
915 return Subtract (np, p, true);
916 }
917
918 struct cpInfo
919 {
920 const BoxType *other;
921 DataType *data;
922 LayerType *layer;
923 PolygonType *polygon;
924 bool bottom;
925 POLYAREA *accumulate;
926 int batch_size;
927 jmp_buf env;
928 };
929
930 static void
subtract_accumulated(struct cpInfo * info,PolygonType * polygon)931 subtract_accumulated (struct cpInfo *info, PolygonType *polygon)
932 {
933 if (info->accumulate == NULL)
934 return;
935 Subtract (info->accumulate, polygon, true);
936 info->accumulate = NULL;
937 info->batch_size = 0;
938 }
939
940 static int
pin_sub_callback(const BoxType * b,void * cl)941 pin_sub_callback (const BoxType * b, void *cl)
942 {
943 PinType *pin = (PinType *) b;
944 struct cpInfo *info = (struct cpInfo *) cl;
945 PolygonType *polygon;
946 POLYAREA *np;
947 POLYAREA *merged;
948 Cardinal i;
949
950 /* don't subtract the object that was put back! */
951 if (b == info->other)
952 return 0;
953 polygon = info->polygon;
954
955 i = GetLayerNumber (info->data, info->layer);
956
957 if (VIA_IS_BURIED (pin) && (!VIA_ON_LAYER (pin, i)))
958 return 0;
959
960 if (pin->Clearance == 0)
961 return 0;
962 if (TEST_THERM (i, pin))
963 {
964 np = ThermPoly ((PCBType *) (info->data->pcb), pin, i);
965 if (!np)
966 return 1;
967 }
968 else
969 {
970 np = PinPoly (pin, PIN_SIZE (pin), pin->Clearance);
971 if (!np)
972 longjmp (info->env, 1);
973 }
974
975 poly_Boolean_free (info->accumulate, np, &merged, PBO_UNITE);
976 info->accumulate = merged;
977
978 info->batch_size ++;
979
980 if (info->batch_size == SUBTRACT_PIN_VIA_BATCH_SIZE)
981 subtract_accumulated (info, polygon);
982
983 return 1;
984 }
985
986 static int
arc_sub_callback(const BoxType * b,void * cl)987 arc_sub_callback (const BoxType * b, void *cl)
988 {
989 ArcType *arc = (ArcType *) b;
990 struct cpInfo *info = (struct cpInfo *) cl;
991 PolygonType *polygon;
992
993 /* don't subtract the object that was put back! */
994 if (b == info->other)
995 return 0;
996 if (!TEST_FLAG (CLEARLINEFLAG, arc))
997 return 0;
998 polygon = info->polygon;
999 if (SubtractArc (arc, polygon) < 0)
1000 longjmp (info->env, 1);
1001 return 1;
1002 }
1003
1004 static int
pad_sub_callback(const BoxType * b,void * cl)1005 pad_sub_callback (const BoxType * b, void *cl)
1006 {
1007 PadType *pad = (PadType *) b;
1008 struct cpInfo *info = (struct cpInfo *) cl;
1009 PolygonType *polygon;
1010
1011 /* don't subtract the object that was put back! */
1012 if (b == info->other)
1013 return 0;
1014 if (pad->Clearance == 0)
1015 return 0;
1016 polygon = info->polygon;
1017 if (XOR (TEST_FLAG (ONSOLDERFLAG, pad), !info->bottom))
1018 {
1019 if (SubtractPad (pad, polygon) < 0)
1020 longjmp (info->env, 1);
1021 return 1;
1022 }
1023 return 0;
1024 }
1025
1026 static int
line_sub_callback(const BoxType * b,void * cl)1027 line_sub_callback (const BoxType * b, void *cl)
1028 {
1029 LineType *line = (LineType *) b;
1030 struct cpInfo *info = (struct cpInfo *) cl;
1031 PolygonType *polygon;
1032 POLYAREA *np;
1033 POLYAREA *merged;
1034
1035 /* don't subtract the object that was put back! */
1036 if (b == info->other)
1037 return 0;
1038 if (!TEST_FLAG (CLEARLINEFLAG, line))
1039 return 0;
1040 polygon = info->polygon;
1041
1042 if (!(np = LinePoly (line, line->Thickness + line->Clearance)))
1043 longjmp (info->env, 1);
1044
1045 poly_Boolean_free (info->accumulate, np, &merged, PBO_UNITE);
1046 info->accumulate = merged;
1047 info->batch_size ++;
1048
1049 if (info->batch_size == SUBTRACT_LINE_BATCH_SIZE)
1050 subtract_accumulated (info, polygon);
1051
1052 return 1;
1053 }
1054
1055 static int
text_sub_callback(const BoxType * b,void * cl)1056 text_sub_callback (const BoxType * b, void *cl)
1057 {
1058 TextType *text = (TextType *) b;
1059 struct cpInfo *info = (struct cpInfo *) cl;
1060 PolygonType *polygon;
1061
1062 /* don't subtract the object that was put back! */
1063 if (b == info->other)
1064 return 0;
1065 if (!TEST_FLAG (CLEARLINEFLAG, text))
1066 return 0;
1067 polygon = info->polygon;
1068 if (SubtractText (text, polygon) < 0)
1069 longjmp (info->env, 1);
1070 return 1;
1071 }
1072
1073 static int
Group(DataType * Data,Cardinal layer)1074 Group (DataType *Data, Cardinal layer)
1075 {
1076 Cardinal i, j;
1077 for (i = 0; i < max_group; i++)
1078 for (j = 0; j < ((PCBType *) (Data->pcb))->LayerGroups.Number[i]; j++)
1079 if (layer == ((PCBType *) (Data->pcb))->LayerGroups.Entries[i][j])
1080 return i;
1081 return i;
1082 }
1083
1084 static int
clearPoly(DataType * Data,LayerType * Layer,PolygonType * polygon,const BoxType * here,Coord expand)1085 clearPoly (DataType *Data, LayerType *Layer, PolygonType * polygon,
1086 const BoxType * here, Coord expand)
1087 {
1088 int r = 0;
1089 BoxType region;
1090 struct cpInfo info;
1091 Cardinal group;
1092
1093 if (!TEST_FLAG (CLEARPOLYFLAG, polygon)
1094 || GetLayerNumber (Data, Layer) >= max_copper_layer)
1095 return 0;
1096 group = Group (Data, GetLayerNumber (Data, Layer));
1097 info.bottom = (group == Group (Data, bottom_silk_layer));
1098 info.data = Data;
1099 info.other = here;
1100 info.layer = Layer;
1101 info.polygon = polygon;
1102 if (here)
1103 region = clip_box (here, &polygon->BoundingBox);
1104 else
1105 region = polygon->BoundingBox;
1106 region = bloat_box (®ion, expand);
1107
1108 if (setjmp (info.env) == 0)
1109 {
1110 r = 0;
1111 info.accumulate = NULL;
1112 info.batch_size = 0;
1113 if (info.bottom || group == Group (Data, top_silk_layer))
1114 r += r_search (Data->pad_tree, ®ion, NULL, pad_sub_callback, &info);
1115 GROUP_LOOP (Data, group);
1116 {
1117 r +=
1118 r_search (layer->line_tree, ®ion, NULL, line_sub_callback,
1119 &info);
1120 subtract_accumulated (&info, polygon);
1121 r +=
1122 r_search (layer->arc_tree, ®ion, NULL, arc_sub_callback, &info);
1123 r +=
1124 r_search (layer->text_tree, ®ion, NULL, text_sub_callback, &info);
1125 }
1126 END_LOOP;
1127 r += r_search (Data->via_tree, ®ion, NULL, pin_sub_callback, &info);
1128 r += r_search (Data->pin_tree, ®ion, NULL, pin_sub_callback, &info);
1129 subtract_accumulated (&info, polygon);
1130 }
1131 polygon->NoHolesValid = 0;
1132 return r;
1133 }
1134
1135 static int
Unsubtract(POLYAREA * np1,PolygonType * p)1136 Unsubtract (POLYAREA * np1, PolygonType * p)
1137 {
1138 POLYAREA *merged = NULL, *np = np1;
1139 POLYAREA *orig_poly, *clipped_np;
1140 int x;
1141 assert (np);
1142 assert (p && p->Clipped);
1143
1144 orig_poly = original_poly (p);
1145
1146 x = poly_Boolean_free (np, orig_poly, &clipped_np, PBO_ISECT);
1147 if (x != err_ok)
1148 {
1149 fprintf (stderr, "Error while clipping PBO_ISECT: %d\n", x);
1150 poly_Free (&clipped_np);
1151 goto fail;
1152 }
1153
1154 x = poly_Boolean_free (p->Clipped, clipped_np, &merged, PBO_UNITE);
1155 if (x != err_ok)
1156 {
1157 fprintf (stderr, "Error while clipping PBO_UNITE: %d\n", x);
1158 poly_Free (&merged);
1159 goto fail;
1160 }
1161 p->Clipped = biggest (merged);
1162 assert (!p->Clipped || poly_Valid (p->Clipped));
1163 return 1;
1164
1165 fail:
1166 p->Clipped = NULL;
1167 if (p->NoHoles) printf ("Just leaked in Unsubtract\n");
1168 p->NoHoles = NULL;
1169 return 0;
1170 }
1171
1172 static int
UnsubtractPin(PinType * pin,LayerType * l,PolygonType * p)1173 UnsubtractPin (PinType * pin, LayerType * l, PolygonType * p)
1174 {
1175 POLYAREA *np;
1176
1177 /* overlap a bit to prevent gaps from rounding errors */
1178 np = BoxPolyBloated (&pin->BoundingBox, UNSUBTRACT_BLOAT);
1179
1180 if (!np)
1181 return 0;
1182 if (!Unsubtract (np, p))
1183 return 0;
1184 clearPoly (PCB->Data, l, p, (const BoxType *) pin, 2 * UNSUBTRACT_BLOAT);
1185 return 1;
1186 }
1187
1188 static int
UnsubtractArc(ArcType * arc,LayerType * l,PolygonType * p)1189 UnsubtractArc (ArcType * arc, LayerType * l, PolygonType * p)
1190 {
1191 POLYAREA *np;
1192
1193 if (!TEST_FLAG (CLEARLINEFLAG, arc))
1194 return 0;
1195
1196 /* overlap a bit to prevent gaps from rounding errors */
1197 np = BoxPolyBloated (&arc->BoundingBox, UNSUBTRACT_BLOAT);
1198
1199 if (!np)
1200 return 0;
1201 if (!Unsubtract (np, p))
1202 return 0;
1203 clearPoly (PCB->Data, l, p, (const BoxType *) arc, 2 * UNSUBTRACT_BLOAT);
1204 return 1;
1205 }
1206
1207 static int
UnsubtractLine(LineType * line,LayerType * l,PolygonType * p)1208 UnsubtractLine (LineType * line, LayerType * l, PolygonType * p)
1209 {
1210 POLYAREA *np;
1211
1212 if (!TEST_FLAG (CLEARLINEFLAG, line))
1213 return 0;
1214
1215 /* overlap a bit to prevent notches from rounding errors */
1216 np = BoxPolyBloated (&line->BoundingBox, UNSUBTRACT_BLOAT);
1217
1218 if (!np)
1219 return 0;
1220 if (!Unsubtract (np, p))
1221 return 0;
1222 clearPoly (PCB->Data, l, p, (const BoxType *) line, 2 * UNSUBTRACT_BLOAT);
1223 return 1;
1224 }
1225
1226 static int
UnsubtractText(TextType * text,LayerType * l,PolygonType * p)1227 UnsubtractText (TextType * text, LayerType * l, PolygonType * p)
1228 {
1229 POLYAREA *np;
1230
1231 if (!TEST_FLAG (CLEARLINEFLAG, text))
1232 return 0;
1233
1234 /* overlap a bit to prevent notches from rounding errors */
1235 np = BoxPolyBloated (&text->BoundingBox, UNSUBTRACT_BLOAT);
1236
1237 if (!np)
1238 return -1;
1239 if (!Unsubtract (np, p))
1240 return 0;
1241 clearPoly (PCB->Data, l, p, (const BoxType *) text, 2 * UNSUBTRACT_BLOAT);
1242 return 1;
1243 }
1244
1245 static int
UnsubtractPad(PadType * pad,LayerType * l,PolygonType * p)1246 UnsubtractPad (PadType * pad, LayerType * l, PolygonType * p)
1247 {
1248 POLYAREA *np;
1249
1250 /* overlap a bit to prevent notches from rounding errors */
1251 np = BoxPolyBloated (&pad->BoundingBox, UNSUBTRACT_BLOAT);
1252
1253 if (!np)
1254 return 0;
1255 if (!Unsubtract (np, p))
1256 return 0;
1257 clearPoly (PCB->Data, l, p, (const BoxType *) pad, 2 * UNSUBTRACT_BLOAT);
1258 return 1;
1259 }
1260
1261 static bool inhibit = false;
1262
1263 /*!
1264 * \brief Initialize low level polygon data structures.
1265 * */
1266 int
InitClip(DataType * Data,LayerType * layer,PolygonType * p)1267 InitClip (DataType *Data, LayerType *layer, PolygonType * p)
1268 {
1269 if (inhibit)
1270 return 0;
1271
1272 /* Clear any existing data. */
1273 if (p->Clipped)
1274 poly_Free (&p->Clipped);
1275
1276 /* Compute the perimeter of the polygon */
1277 p->Clipped = original_poly (p);
1278
1279 /* NoHoles is a version of the polygon broken into pieces so that it is
1280 * hole free. If we have one, we need to clear it. */
1281 poly_FreeContours (&p->NoHoles);
1282 if (!p->Clipped)
1283 return 0;
1284 assert (poly_Valid (p->Clipped));
1285
1286 /* If the polygon is clearing, we need to add all of the object cutouts. */
1287 if (TEST_FLAG (CLEARPOLYFLAG, p))
1288 clearPoly (Data, layer, p, NULL, 0);
1289 else
1290 p->NoHolesValid = 0;
1291 return 1;
1292 }
1293
1294 /*!
1295 * \brief Remove redundant polygon points.
1296 *
1297 * Any point that lies on the straight line between the points on either
1298 * side of it is redundant.
1299 *
1300 * \return True if any points are removed.
1301 */
1302 bool
RemoveExcessPolygonPoints(LayerType * Layer,PolygonType * Polygon)1303 RemoveExcessPolygonPoints (LayerType *Layer, PolygonType *Polygon)
1304 {
1305 PointType *p;
1306 Cardinal n, prev, next;
1307 LineType line;
1308 bool changed = false;
1309
1310 if (Undoing ())
1311 return (false);
1312
1313 for (n = 0; n < Polygon->PointN; n++)
1314 {
1315 prev = prev_contour_point (Polygon, n);
1316 next = next_contour_point (Polygon, n);
1317 p = &Polygon->Points[n];
1318
1319 line.Point1 = Polygon->Points[prev];
1320 line.Point2 = Polygon->Points[next];
1321 line.Thickness = 0;
1322 if (IsPointOnLine (p->X, p->Y, 0.0, &line))
1323 {
1324 RemoveObject (POLYGONPOINT_TYPE, Layer, Polygon, p);
1325 changed = true;
1326 }
1327 }
1328 return (changed);
1329 }
1330
1331 /*!
1332 * \brief .
1333 *
1334 * \return The index of the polygon point which is the end point of the
1335 * segment with the lowest distance to the passed coordinates.
1336 */
1337 Cardinal
GetLowestDistancePolygonPoint(PolygonType * Polygon,Coord X,Coord Y)1338 GetLowestDistancePolygonPoint (PolygonType *Polygon, Coord X, Coord Y)
1339 {
1340 double mindistance = (double) MAX_COORD * MAX_COORD;
1341 PointType *ptr1, *ptr2;
1342 Cardinal n, result = 0;
1343
1344 /* we calculate the distance to each segment and choose the
1345 * shortest distance. If the closest approach between the
1346 * given point and the projected line (i.e. the segment extended)
1347 * is not on the segment, then the distance is the distance
1348 * to the segment end point.
1349 */
1350
1351 for (n = 0; n < Polygon->PointN; n++)
1352 {
1353 double u, dx, dy;
1354 ptr1 = &Polygon->Points[prev_contour_point (Polygon, n)];
1355 ptr2 = &Polygon->Points[n];
1356
1357 dx = ptr2->X - ptr1->X;
1358 dy = ptr2->Y - ptr1->Y;
1359 if (dx != 0.0 || dy != 0.0)
1360 {
1361 /* projected intersection is at P1 + u(P2 - P1) */
1362 u = ((X - ptr1->X) * dx + (Y - ptr1->Y) * dy) / (dx * dx + dy * dy);
1363
1364 if (u < 0.0)
1365 { /* ptr1 is closest point */
1366 u = SQUARE (X - ptr1->X) + SQUARE (Y - ptr1->Y);
1367 }
1368 else if (u > 1.0)
1369 { /* ptr2 is closest point */
1370 u = SQUARE (X - ptr2->X) + SQUARE (Y - ptr2->Y);
1371 }
1372 else
1373 { /* projected intersection is closest point */
1374 u = SQUARE (X - ptr1->X * (1.0 - u) - u * ptr2->X) +
1375 SQUARE (Y - ptr1->Y * (1.0 - u) - u * ptr2->Y);
1376 }
1377 if (u < mindistance)
1378 {
1379 mindistance = u;
1380 result = n;
1381 }
1382 }
1383 }
1384 return (result);
1385 }
1386
1387 /*!
1388 * \brief Go back to the previous point of the polygon.
1389 */
1390 void
GoToPreviousPoint(void)1391 GoToPreviousPoint (void)
1392 {
1393 switch (Crosshair.AttachedPolygon.PointN)
1394 {
1395 /* do nothing if mode has just been entered */
1396 case 0:
1397 break;
1398
1399 /* reset number of points and 'LINE_MODE' state */
1400 case 1:
1401 Crosshair.AttachedPolygon.PointN = 0;
1402 Crosshair.AttachedLine.State = STATE_FIRST;
1403 addedLines = 0;
1404 break;
1405
1406 /* back-up one point */
1407 default:
1408 {
1409 PointType *points = Crosshair.AttachedPolygon.Points;
1410 Cardinal n = Crosshair.AttachedPolygon.PointN - 2;
1411
1412 Crosshair.AttachedPolygon.PointN--;
1413 Crosshair.AttachedLine.Point1.X = points[n].X;
1414 Crosshair.AttachedLine.Point1.Y = points[n].Y;
1415 break;
1416 }
1417 }
1418 }
1419
1420 /*!
1421 * \brief Close polygon if possible.
1422 */
1423 void
ClosePolygon(void)1424 ClosePolygon (void)
1425 {
1426 Cardinal n = Crosshair.AttachedPolygon.PointN;
1427
1428 /* check number of points */
1429 if (n >= 3)
1430 {
1431 /* if 45 degree lines are what we want do a quick check
1432 * if closing the polygon makes sense
1433 */
1434 if (!TEST_FLAG (ALLDIRECTIONFLAG, PCB))
1435 {
1436 Coord dx, dy;
1437
1438 dx = abs (Crosshair.AttachedPolygon.Points[n - 1].X -
1439 Crosshair.AttachedPolygon.Points[0].X);
1440 dy = abs (Crosshair.AttachedPolygon.Points[n - 1].Y -
1441 Crosshair.AttachedPolygon.Points[0].Y);
1442 if (!(dx == 0 || dy == 0 || dx == dy))
1443 {
1444 Message
1445 (_
1446 ("Cannot close polygon because 45 degree lines are requested.\n"));
1447 return;
1448 }
1449 }
1450 CopyAttachedPolygonToLayer ();
1451 Draw ();
1452 }
1453 else
1454 Message (_("A polygon has to have at least 3 points\n"));
1455 }
1456
1457 /*!
1458 * \brief Moves the data of the attached (new) polygon to the current
1459 * layer.
1460 */
1461 void
CopyAttachedPolygonToLayer(void)1462 CopyAttachedPolygonToLayer (void)
1463 {
1464 PolygonType *polygon;
1465 int saveID;
1466
1467 /* move data to layer and clear attached struct */
1468 polygon = CreateNewPolygon (CURRENT, NoFlags ());
1469 saveID = polygon->ID;
1470 *polygon = Crosshair.AttachedPolygon;
1471 polygon->ID = saveID;
1472 SET_FLAG (CLEARPOLYFLAG, polygon);
1473 if (TEST_FLAG (NEWFULLPOLYFLAG, PCB))
1474 SET_FLAG (FULLPOLYFLAG, polygon);
1475 memset (&Crosshair.AttachedPolygon, 0, sizeof (PolygonType));
1476 SetPolygonBoundingBox (polygon);
1477 if (!CURRENT->polygon_tree)
1478 CURRENT->polygon_tree = r_create_tree (NULL, 0, 0);
1479 r_insert_entry (CURRENT->polygon_tree, (BoxType *) polygon, 0);
1480 InitClip (PCB->Data, CURRENT, polygon);
1481 DrawPolygon (CURRENT, polygon);
1482 SetChangedFlag (true);
1483
1484 /* reset state of attached line */
1485 Crosshair.AttachedLine.State = STATE_FIRST;
1486 addedLines = 0;
1487
1488 /* add to undo list */
1489 AddObjectToCreateUndoList (POLYGON_TYPE, CURRENT, polygon, polygon);
1490 IncrementUndoSerialNumber ();
1491 }
1492
1493 /*!
1494 * \brief Find polygon holes in range, then call the callback function
1495 * for each hole.
1496 *
1497 * If the callback returns non-zero, stop the search.
1498 */
1499 int
PolygonHoles(PolygonType * polygon,const BoxType * range,int (* callback)(PLINE * contour,void * user_data),void * user_data)1500 PolygonHoles (PolygonType *polygon, const BoxType *range,
1501 int (*callback) (PLINE *contour, void *user_data),
1502 void *user_data)
1503 {
1504 POLYAREA *pa = polygon->Clipped;
1505 PLINE *pl;
1506 /* If this hole is so big the polygon doesn't exist, then it's not
1507 * really a hole.
1508 */
1509 if (!pa)
1510 return 0;
1511 for (pl = pa->contours->next; pl; pl = pl->next)
1512 {
1513 if (range != NULL &&
1514 (pl->xmin > range->X2 || pl->xmax < range->X1 ||
1515 pl->ymin > range->Y2 || pl->ymax < range->Y1))
1516 continue;
1517 if (callback (pl, user_data))
1518 {
1519 return 1;
1520 }
1521 }
1522 return 0;
1523 }
1524
1525 struct plow_info
1526 {
1527 int type;
1528 void *ptr1, *ptr2;
1529 LayerType *layer;
1530 DataType *data;
1531 int (*callback) (DataType *, LayerType *, PolygonType *, int, void *,
1532 void *, void *);
1533 void *userdata;
1534 };
1535
1536 static int
subtract_plow(DataType * Data,LayerType * Layer,PolygonType * Polygon,int type,void * ptr1,void * ptr2,void * userdata)1537 subtract_plow (DataType *Data, LayerType *Layer, PolygonType *Polygon,
1538 int type, void *ptr1, void *ptr2, void *userdata)
1539 {
1540 PinType *via;
1541 int layer_n = GetLayerNumber (Data, Layer);
1542
1543 if (!Polygon->Clipped)
1544 return 0;
1545 switch (type)
1546 {
1547 case PIN_TYPE:
1548 SubtractPin (Data, (PinType *) ptr2, Layer, Polygon);
1549 Polygon->NoHolesValid = 0;
1550 return 1;
1551 case VIA_TYPE:
1552 via = (PinType *) ptr2;
1553 if (!VIA_IS_BURIED (via) || VIA_ON_LAYER (via, layer_n))
1554 {
1555 SubtractPin (Data, via, Layer, Polygon);
1556 Polygon->NoHolesValid = 0;
1557 return 1;
1558 }
1559 break;
1560 case LINE_TYPE:
1561 SubtractLine ((LineType *) ptr2, Polygon);
1562 Polygon->NoHolesValid = 0;
1563 return 1;
1564 case ARC_TYPE:
1565 SubtractArc ((ArcType *) ptr2, Polygon);
1566 Polygon->NoHolesValid = 0;
1567 return 1;
1568 case PAD_TYPE:
1569 SubtractPad ((PadType *) ptr2, Polygon);
1570 Polygon->NoHolesValid = 0;
1571 return 1;
1572 case TEXT_TYPE:
1573 SubtractText ((TextType *) ptr2, Polygon);
1574 Polygon->NoHolesValid = 0;
1575 return 1;
1576 }
1577 return 0;
1578 }
1579
1580 static int
add_plow(DataType * Data,LayerType * Layer,PolygonType * Polygon,int type,void * ptr1,void * ptr2,void * userdata)1581 add_plow (DataType *Data, LayerType *Layer, PolygonType *Polygon,
1582 int type, void *ptr1, void *ptr2, void *userdata)
1583 {
1584 PinType *via;
1585 int layer_n = GetLayerNumber (Data, Layer);
1586
1587 switch (type)
1588 {
1589 case PIN_TYPE:
1590 UnsubtractPin ((PinType *) ptr2, Layer, Polygon);
1591 return 1;
1592 case VIA_TYPE:
1593 via = (PinType *) ptr2;
1594 if (!VIA_IS_BURIED (via) || VIA_ON_LAYER (via, layer_n))
1595 {
1596 UnsubtractPin ((PinType *) ptr2, Layer, Polygon);
1597 return 1;
1598 }
1599 break;
1600 case LINE_TYPE:
1601 UnsubtractLine ((LineType *) ptr2, Layer, Polygon);
1602 return 1;
1603 case ARC_TYPE:
1604 UnsubtractArc ((ArcType *) ptr2, Layer, Polygon);
1605 return 1;
1606 case PAD_TYPE:
1607 UnsubtractPad ((PadType *) ptr2, Layer, Polygon);
1608 return 1;
1609 case TEXT_TYPE:
1610 UnsubtractText ((TextType *) ptr2, Layer, Polygon);
1611 return 1;
1612 }
1613 return 0;
1614 }
1615
1616 static int
plow_callback(const BoxType * b,void * cl)1617 plow_callback (const BoxType * b, void *cl)
1618 {
1619 struct plow_info *plow = (struct plow_info *) cl;
1620 PolygonType *polygon = (PolygonType *) b;
1621
1622 if (TEST_FLAG (CLEARPOLYFLAG, polygon))
1623 return plow->callback (plow->data, plow->layer, polygon, plow->type,
1624 plow->ptr1, plow->ptr2, plow->userdata);
1625 return 0;
1626 }
1627
1628 int
PlowsPolygon(DataType * Data,int type,void * ptr1,void * ptr2,int (* call_back)(DataType * data,LayerType * lay,PolygonType * poly,int type,void * ptr1,void * ptr2,void * userdata),void * userdata)1629 PlowsPolygon (DataType * Data, int type, void *ptr1, void *ptr2,
1630 int (*call_back) (DataType *data, LayerType *lay,
1631 PolygonType *poly, int type, void *ptr1,
1632 void *ptr2, void *userdata),
1633 void *userdata)
1634 {
1635 BoxType sb = ((PinType *) ptr2)->BoundingBox;
1636 int r = 0;
1637 struct plow_info info;
1638
1639 info.type = type;
1640 info.ptr1 = ptr1;
1641 info.ptr2 = ptr2;
1642 info.data = Data;
1643 info.callback = call_back;
1644 info.userdata = userdata;
1645 switch (type)
1646 {
1647 case PIN_TYPE:
1648 case VIA_TYPE:
1649 if (type == PIN_TYPE || ptr1 == ptr2 || ptr1 == NULL)
1650 {
1651 LAYER_LOOP (Data, max_copper_layer);
1652 {
1653 info.layer = layer;
1654 r +=
1655 r_search (layer->polygon_tree, &sb, NULL, plow_callback, &info);
1656 }
1657 END_LOOP;
1658 }
1659 else
1660 {
1661 GROUP_LOOP (Data, GetLayerGroupNumberByNumber (GetLayerNumber (Data,
1662 ((LayerType *) ptr1))));
1663 {
1664 info.layer = layer;
1665 r +=
1666 r_search (layer->polygon_tree, &sb, NULL, plow_callback, &info);
1667 }
1668 END_LOOP;
1669 }
1670 break;
1671 case LINE_TYPE:
1672 case ARC_TYPE:
1673 case TEXT_TYPE:
1674 /* Don't test clearlineflag here because the DRC still needs to check
1675 * such objects. */
1676 /* silk doesn't plow */
1677 if (GetLayerNumber (Data, (LayerType *)ptr1) >= max_copper_layer)
1678 return 0;
1679 GROUP_LOOP (Data, GetLayerGroupNumberByNumber (GetLayerNumber (Data,
1680 ((LayerType *) ptr1))));
1681 {
1682 info.layer = layer;
1683 r += r_search (layer->polygon_tree, &sb, NULL, plow_callback, &info);
1684 }
1685 END_LOOP;
1686 break;
1687 case PAD_TYPE:
1688 {
1689 Cardinal group = GetLayerGroupNumberByNumber (
1690 TEST_FLAG (ONSOLDERFLAG, (PadType *) ptr2) ?
1691 bottom_silk_layer : top_silk_layer);
1692 GROUP_LOOP (Data, group);
1693 {
1694 info.layer = layer;
1695 r +=
1696 r_search (layer->polygon_tree, &sb, NULL, plow_callback, &info);
1697 }
1698 END_LOOP;
1699 }
1700 break;
1701
1702 case ELEMENT_TYPE:
1703 {
1704 PIN_LOOP ((ElementType *) ptr1);
1705 {
1706 PlowsPolygon (Data, PIN_TYPE, ptr1, pin, call_back, userdata);
1707 }
1708 END_LOOP;
1709 PAD_LOOP ((ElementType *) ptr1);
1710 {
1711 PlowsPolygon (Data, PAD_TYPE, ptr1, pad, call_back, userdata);
1712 }
1713 END_LOOP;
1714 }
1715 break;
1716 }
1717 return r;
1718 }
1719
1720 void
RestoreToPolygon(DataType * Data,int type,void * ptr1,void * ptr2)1721 RestoreToPolygon (DataType * Data, int type, void *ptr1, void *ptr2)
1722 {
1723 if (!Data->polyClip)
1724 return;
1725
1726 if (type == POLYGON_TYPE)
1727 InitClip (PCB->Data, (LayerType *) ptr1, (PolygonType *) ptr2);
1728 else
1729 PlowsPolygon (Data, type, ptr1, ptr2, add_plow, NULL);
1730 }
1731
1732 void
ClearFromPolygon(DataType * Data,int type,void * ptr1,void * ptr2)1733 ClearFromPolygon (DataType * Data, int type, void *ptr1, void *ptr2)
1734 {
1735 if (!Data->polyClip)
1736 return;
1737
1738 if (type == POLYGON_TYPE)
1739 InitClip (PCB->Data, (LayerType *) ptr1, (PolygonType *) ptr2);
1740 else
1741 PlowsPolygon (Data, type, ptr1, ptr2, subtract_plow, NULL);
1742 }
1743
1744 /*!
1745 * \brief Determine if a POLYAREA touches a polygon.
1746 *
1747 * if the third argument is true, this function will free the POLYAREA when
1748 * finished.
1749 * */
1750 bool
isects(POLYAREA * a,PolygonType * p,bool fr)1751 isects (POLYAREA * a, PolygonType *p, bool fr)
1752 {
1753 POLYAREA *x;
1754 bool ans;
1755 ans = Touching (a, p->Clipped);
1756 /* argument may be register, so we must copy it */
1757 x = a;
1758 if (fr)
1759 poly_Free (&x);
1760 return ans;
1761 }
1762
1763 /*!
1764 * \brief Determine if a point of radius r is inside a polygon.
1765 * */
1766 bool
IsPointInPolygon(Coord X,Coord Y,Coord r,PolygonType * p)1767 IsPointInPolygon (Coord X, Coord Y, Coord r, PolygonType *p)
1768 {
1769 POLYAREA *c;
1770 Vector v;
1771 v[0] = X;
1772 v[1] = Y;
1773 /* If the center point is inside, then some part of the point must be too. */
1774 if (poly_CheckInside (p->Clipped, v))
1775 return true;
1776
1777 /* if the center isn't inside, then the point has to have a non-zero
1778 * radius.
1779 * */
1780 if (r < 1)
1781 return false;
1782
1783 /* Create a circular POLYAREA of radius r, and see if it intersects. */
1784 if (!(c = CirclePoly (X, Y, r)))
1785 return false; /* failed to create POLYAREA */
1786
1787 return isects (c, p, true);
1788 }
1789
1790
1791 bool
IsPointInPolygonIgnoreHoles(Coord X,Coord Y,PolygonType * p)1792 IsPointInPolygonIgnoreHoles (Coord X, Coord Y, PolygonType *p)
1793 {
1794 Vector v;
1795 v[0] = X;
1796 v[1] = Y;
1797 return poly_InsideContour (p->Clipped->contours, v);
1798 }
1799
1800 bool
IsRectangleInPolygon(Coord X1,Coord Y1,Coord X2,Coord Y2,PolygonType * p)1801 IsRectangleInPolygon (Coord X1, Coord Y1, Coord X2, Coord Y2, PolygonType *p)
1802 {
1803 POLYAREA *s;
1804 if (!
1805 (s = RectPoly (min (X1, X2), max (X1, X2), min (Y1, Y2), max (Y1, Y2))))
1806 return false;
1807 return isects (s, p, true);
1808 }
1809
1810 /*!
1811 * \brief .
1812 *
1813 * \note This function will free the passed POLYAREA.
1814 * It must only be passed a single POLYAREA (pa->f == pa->b == pa).
1815 */
1816 static void
r_NoHolesPolygonDicer(POLYAREA * pa,void (* emit)(PLINE *,void *),void * user_data)1817 r_NoHolesPolygonDicer (POLYAREA * pa,
1818 void (*emit) (PLINE *, void *), void *user_data)
1819 {
1820 PLINE *p = pa->contours;
1821
1822 if (!pa->contours->next) /* no holes */
1823 {
1824 pa->contours = NULL; /* The callback now owns the contour */
1825 /* Don't bother removing it from the POLYAREA's rtree
1826 since we're going to free the POLYAREA below anyway */
1827 emit (p, user_data);
1828 poly_Free (&pa);
1829 return;
1830 }
1831 else
1832 {
1833 POLYAREA *poly2, *left, *right;
1834
1835 /* make a rectangle of the left region slicing through the middle of the first hole */
1836 poly2 = RectPoly (p->xmin, (p->next->xmin + p->next->xmax) / 2,
1837 p->ymin, p->ymax);
1838 poly_AndSubtract_free (pa, poly2, &left, &right);
1839 if (left)
1840 {
1841 POLYAREA *cur, *next;
1842 cur = left;
1843 do
1844 {
1845 next = cur->f;
1846 cur->f = cur->b = cur; /* Detach this polygon piece */
1847 r_NoHolesPolygonDicer (cur, emit, user_data);
1848 /* NB: The POLYAREA was freed by its use in the recursive dicer */
1849 }
1850 while ((cur = next) != left);
1851 }
1852 if (right)
1853 {
1854 POLYAREA *cur, *next;
1855 cur = right;
1856 do
1857 {
1858 next = cur->f;
1859 cur->f = cur->b = cur; /* Detach this polygon piece */
1860 r_NoHolesPolygonDicer (cur, emit, user_data);
1861 /* NB: The POLYAREA was freed by its use in the recursive dicer */
1862 }
1863 while ((cur = next) != right);
1864 }
1865 }
1866 }
1867
1868 void
NoHolesPolygonDicer(PolygonType * p,const BoxType * clip,void (* emit)(PLINE *,void *),void * user_data)1869 NoHolesPolygonDicer (PolygonType *p, const BoxType * clip,
1870 void (*emit) (PLINE *, void *), void *user_data)
1871 {
1872 POLYAREA *main_contour, *cur, *next;
1873
1874 main_contour = poly_Create ();
1875 /* copy the main poly only */
1876 poly_Copy1 (main_contour, p->Clipped);
1877 /* clip to the bounding box */
1878 if (clip)
1879 {
1880 POLYAREA *cbox = RectPoly (clip->X1, clip->X2, clip->Y1, clip->Y2);
1881 poly_Boolean_free (main_contour, cbox, &main_contour, PBO_ISECT);
1882 }
1883 if (main_contour == NULL)
1884 return;
1885 /* Now dice it up.
1886 * NB: Could be more than one piece (because of the clip above)
1887 */
1888 cur = main_contour;
1889 do
1890 {
1891 next = cur->f;
1892 cur->f = cur->b = cur; /* Detach this polygon piece */
1893 r_NoHolesPolygonDicer (cur, emit, user_data);
1894 /* NB: The POLYAREA was freed by its use in the recursive dicer */
1895 }
1896 while ((cur = next) != main_contour);
1897 }
1898
1899 /*!
1900 * \brief Make a polygon split into multiple parts into multiple
1901 * polygons.
1902 */
1903 bool
MorphPolygon(LayerType * layer,PolygonType * poly)1904 MorphPolygon (LayerType *layer, PolygonType *poly)
1905 {
1906 POLYAREA *p, *start;
1907 bool many = false;
1908 FlagType flags;
1909
1910 if (!poly->Clipped || TEST_FLAG (LOCKFLAG, poly))
1911 return false;
1912 if (poly->Clipped->f == poly->Clipped)
1913 return false;
1914 ErasePolygon (poly);
1915 start = p = poly->Clipped;
1916 /* This is ugly. The creation of the new polygons can cause
1917 * all of the polygon pointers (including the one we're called
1918 * with to change if there is a realloc in GetPolygonMemory().
1919 * That will invalidate our original "poly" argument, potentially
1920 * inside the loop. We need to steal the Clipped pointer and
1921 * hide it from the Remove call so that it still exists while
1922 * we do this dirty work.
1923 */
1924 poly->Clipped = NULL;
1925 if (poly->NoHoles) printf ("Just leaked in MorpyPolygon\n");
1926 poly->NoHoles = NULL;
1927 flags = poly->Flags;
1928 RemovePolygon (layer, poly);
1929 inhibit = true;
1930 do
1931 {
1932 VNODE *v;
1933 PolygonType *newone;
1934
1935 if (p->contours->area > PCB->IsleArea)
1936 {
1937 newone = CreateNewPolygon (layer, flags);
1938 if (!newone)
1939 return false;
1940 many = true;
1941 v = &p->contours->head;
1942 CreateNewPointInPolygon (newone, v->point[0], v->point[1]);
1943 for (v = v->next; v != &p->contours->head; v = v->next)
1944 CreateNewPointInPolygon (newone, v->point[0], v->point[1]);
1945 newone->BoundingBox.X1 = p->contours->xmin;
1946 newone->BoundingBox.X2 = p->contours->xmax + 1;
1947 newone->BoundingBox.Y1 = p->contours->ymin;
1948 newone->BoundingBox.Y2 = p->contours->ymax + 1;
1949 AddObjectToCreateUndoList (POLYGON_TYPE, layer, newone, newone);
1950 newone->Clipped = p;
1951 p = p->f; /* go to next pline */
1952 newone->Clipped->b = newone->Clipped->f = newone->Clipped; /* unlink from others */
1953 r_insert_entry (layer->polygon_tree, (BoxType *) newone, 0);
1954 DrawPolygon (layer, newone);
1955 }
1956 else
1957 {
1958 POLYAREA *t = p;
1959
1960 p = p->f;
1961 poly_DelContour (&t->contours);
1962 free (t);
1963 }
1964 }
1965 while (p != start);
1966 inhibit = false;
1967 IncrementUndoSerialNumber ();
1968 return many;
1969 }
1970
debug_pline(PLINE * pl)1971 void debug_pline (PLINE *pl)
1972 {
1973 VNODE *v;
1974 pcb_fprintf (stderr, "\txmin %#mS xmax %#mS ymin %#mS ymax %#mS\n",
1975 pl->xmin, pl->xmax, pl->ymin, pl->ymax);
1976 v = &pl->head;
1977 while (v)
1978 {
1979 pcb_fprintf(stderr, "\t\tvnode: %#mD\n", v->point[0], v->point[1]);
1980 v = v->next;
1981 if (v == &pl->head)
1982 break;
1983 }
1984 }
1985
1986 void
debug_polyarea(POLYAREA * p)1987 debug_polyarea (POLYAREA *p)
1988 {
1989 PLINE *pl;
1990
1991 fprintf (stderr, "POLYAREA %p\n", p);
1992 for (pl=p->contours; pl; pl=pl->next)
1993 debug_pline (pl);
1994 }
1995
1996 void
debug_polygon(PolygonType * p)1997 debug_polygon (PolygonType *p)
1998 {
1999 Cardinal i;
2000 POLYAREA *pa;
2001 fprintf (stderr, "POLYGON %p %d pts\n", p, p->PointN);
2002 for (i=0; i<p->PointN; i++)
2003 pcb_fprintf(stderr, "\t%d: %#mD\n", i, p->Points[i].X, p->Points[i].Y);
2004 if (p->HoleIndexN)
2005 {
2006 fprintf (stderr, "%d holes, starting at indices\n", p->HoleIndexN);
2007 for (i=0; i<p->HoleIndexN; i++)
2008 fprintf(stderr, "\t%d: %d\n", i, p->HoleIndex[i]);
2009 }
2010 else
2011 fprintf (stderr, "it has no holes\n");
2012 pa = p->Clipped;
2013 while (pa)
2014 {
2015 debug_polyarea (pa);
2016 pa = pa->f;
2017 if (pa == p->Clipped)
2018 break;
2019 }
2020 }
2021
2022 /*!
2023 * \brief Convert a POLYAREA (and all linked POLYAREA) to raw PCB
2024 * polygons on the given layer.
2025 */
2026 void
PolyToPolygonsOnLayer(DataType * Destination,LayerType * Layer,POLYAREA * Input,FlagType Flags)2027 PolyToPolygonsOnLayer (DataType *Destination, LayerType *Layer,
2028 POLYAREA *Input, FlagType Flags)
2029 {
2030 PolygonType *Polygon;
2031 POLYAREA *pa;
2032 PLINE *pline;
2033 VNODE *node;
2034 bool outer;
2035
2036 if (Input == NULL)
2037 return;
2038
2039 pa = Input;
2040 do
2041 {
2042 Polygon = CreateNewPolygon (Layer, Flags);
2043
2044 pline = pa->contours;
2045 outer = true;
2046
2047 do
2048 {
2049 if (!outer)
2050 CreateNewHoleInPolygon (Polygon);
2051 outer = false;
2052
2053 node = &pline->head;
2054 do
2055 {
2056 CreateNewPointInPolygon (Polygon, node->point[0],
2057 node->point[1]);
2058 }
2059 while ((node = node->next) != &pline->head);
2060
2061 }
2062 while ((pline = pline->next) != NULL);
2063
2064 InitClip (Destination, Layer, Polygon);
2065 SetPolygonBoundingBox (Polygon);
2066 if (!Layer->polygon_tree)
2067 Layer->polygon_tree = r_create_tree (NULL, 0, 0);
2068 r_insert_entry (Layer->polygon_tree, (BoxType *) Polygon, 0);
2069
2070 DrawPolygon (Layer, Polygon);
2071 /* add to undo list */
2072 AddObjectToCreateUndoList (POLYGON_TYPE, Layer, Polygon, Polygon);
2073 }
2074 while ((pa = pa->f) != Input);
2075
2076 SetChangedFlag (true);
2077 }
2078