1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
<h2> different faces of a polygon </H2>
<p>
In pcb-rnd polygons have three possible appearance:
<ul>
<li> points: the as-drawn version
<li> clipped: the as-shown version, with holes
<li> no-holes: the as-shown version, without holes
</ul>
<H3> The as-drawn version </H3>
<p>
The as-drawn version is a list of points (corners), as drawn
by the user. The points are stored in an array of x;y coordinates.
There is a single, continous, dynamically allocated array for all points,
including the outer contour and the holes.
<p>
The points are stored in the <i>Points[]</i> field. The HoleIndex[]
field lists the starting index of each hole. For example a
rectangular polygon with 2 triangle holes is stored as:
<p>
<table border=1 cellspacing=0>
<tr><th> index <th> 0. <th> 1. <th> 2. <th> 3. <th> 4. <th> 5. <th> 6. <th> 7. <th> 8. <th> 9.
<tr><th> Points[] value <td> c1 <td> c2 <td> c3 <td> c4 <td> h1.1 <td> h1.2 <td> h1.3 <td> h2.1 <td> h2.2 <td> h2.3
<tr><th> part of <td colspan=4> outer contour <td colspan=3> hole 1 <td colspan=3> hole 2
</table>
<p>
The array length of Points[] is 10, the length of the correspoding HoleIndex[] is 2.
The values of HoleIndex[] is {4, 7}, indicating that the corners of first hole
starts at 4 while the corners of the second hole starts at 7.
<p>
If HoldeIndex[] is NULL, there are no holes and all points are part of the
outer contour. The Outer contour must contain at least 3 points.
<p>
The as-drawn version always contains the contour of a single island
and 0 or more holes - none of them can intersect or touch any contour or
hole of the same polygon. This also means a contour or hole can not be
self-intersecting.
<p>
The as-drawn version is stored to make editing possible. It is
not affected by other objects (e.g. clearances) or flags of the polygon.
The as-drawn points exist and are stored even if they are not visible
(clipped). The UI maniulates the as-drawn version.
<H3> The clipped version </H3>
<p>
The polygon is clipped by an object if both the polygon and the object have
the correspoding 'clear' flag set. A clipped polygon typically has a much
more complex shape than the as-drawn polygon, due to the clearance cutouts
(not to be confused with user drawn holes). The clipped polygon is the actual
"in-copper" shape of the polygon.
<p>
In some cases the clearance cutouts slice the polygon in multiple components
or in other word <i>islands</i>. If the polygon is <i>full</i> (set by
a polygon flag), all islands are kept, else only the largest island is kept.
(Note: the find code handles all islands of a full polygon as one polygon: it
indicates connection between them even if there is no connection, which makes
full polygons dangerous on copper layers.)
<p>
The clipped polygon is stored in the polyarea field Clipped. It is a doubly
linked circular list (link fields are .f for forward and .b for backward). Each
item on the list is an island of the polygon. If Clipped is NULL, the
polygon clipping is not yet compiled for the given polygon; call pcb_poly_init_clip().
<p>
Each island is a polyarea, which consists of an outer contour and 0 or more
holes - all correspoding to the actual cutouts created by user-drawn polygon
holes and/or clearance cutouts. These contours are stored in a singly linked
list of plines. The first element of the list is the pline for the outer
contour and always exists. The next 0 or more plines, using the .next field
of the pline, are the contours of the cutouts (holes).
<p>
A pline consists of a circular, doubly linked list of points; traversing using
the .next field, the points are ordered in counter-clockwise.
<p>
The clipped polygon shall be updated by any code that changes:
<ul>
<li> the as-drawn points of the polygon
<li> geomerty of any object that may overlap with the polygon (so that clearance changes are applied)
</ul>
<p>
When some code forgets to update clippig, the clipped polygon doesn't match
the clearances dictated by other objects; a reload of the board "fixes" the
problem by forcing the clip. (Native save files contain the as-drawn poly only,
not the (outdated) clipped poly).
<H3> The no-holes version </H3>
<p>
Some export plugins (and/or export formats) don't support holes in polygons.
The no-hole version of the polygon is stored in the .NoHoles filed and is
a list of islands, each specified with an outer countour that are crafted
to include the holes. This is done by slicing an island at each hole.
TODO: check how it looks, include image
<H3> Further comments by Ben Jackson </H3>
As extracted from the original code comments:
<pre>
The first pcb_polyarea_t in pcb_polygon_t.Clipped is what is used for the vast
majority of Polygon related tests. The basic logic for an
intersection is "is the target shape inside pcb_polyarea_t.contours and NOT
fully enclosed in any of pcb_polyarea_t.contours.next... (the holes)".
The polygon dicer (NoHolesPolygonDicer and r_NoHolesPolygonDicer)
emits a series of "simple" pcb_pline_t shapes. That is, the pcb_pline_t isn't
linked to any other "holes" outlines). That's the meaning of the first
test in r_NoHolesPolygonDicer. It is testing to see if the pcb_pline_t
contour (the first, making it a solid outline) has a valid next
pointer (which would point to one or more holes). The dicer works by
recursively chopping the polygon in half through the first hole it
sees (which is guaranteed to eliminate at least that one hole). The
dicer output is used for HIDs which cannot render things with holes
(which would require erasure).
</pre>
<h2> How to code with polygons </h2>
<h3> Iterators: looping on clipped polygon geometry </H3>
The following code prints all contours and holes of a polygon, using loops
iterators. The same iterator holds all states, so that it points to:
<ul>
<li> one polygon
<li> one of the islands of that polygon
<li> either the outer contour or one of the holes in that polygon (cntr)
<li> one of the points in cntr
</ul>
<pre>
void print_poly(pcb_polygon_t *polygon)
{
pcb_poly_it_t it;
rnd_polyarea_t *pa;
/* first, iterate over all islands of a polygon */
for(pa = pcb_poly_island_first(polygon, &it); pa != NULL; pa = pcb_poly_island_next(&it)) {
rnd_coord_t x, y;
rnd_pline_t *pl;
int go;
printf(" island\n");
/* check if we have a contour for the given island */
pl = pcb_poly_contour(&it);
if (pl != NULL) {
printf(" contour:\n");
/* iterate over the vectors of the contour */
for(go = pcb_poly_vect_first(&it, &x, &y); go; go = pcb_poly_vect_next(&it, &x, &y)) {
pcb_printf(" %mm %mm\n", x, y);
}
/* iterate over all holes within this island */
for(pl = pcb_poly_hole_first(&it); pl != NULL; pl = pcb_poly_hole_next(&it)) {
printf(" hole:\n");
/* iterate over the vectors of the given hole */
for(go = pcb_poly_vect_first(&it, &x, &y); go; go = pcb_poly_vect_next(&it, &x, &y)) {
rnd_printf(" %mm %mm\n", x, y);
}
}
}
}
}
</pre>
|
