KiCad PCB EDA Suite
Loading...
Searching...
No Matches
polygon_triangulation.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright (C) 2017 CERN
5 * Copyright (C) 2020 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * @author Alejandro GarcĂ­a Montoro <[email protected]>
8 *
9 * This program is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU General Public License
11 * as published by the Free Software Foundation; either version 2
12 * of the License, or (at your option) any later version.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, you may find one here:
21 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
22 * or you may search the http://www.gnu.org website for the version 2 license,
23 * or you may write to the Free Software Foundation, Inc.,
24 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
25 */
26
29
31
33
34#include <board.h>
35#include <core/ignore.h>
36#include <zone.h>
37#include <core/profile.h>
38
39#include <atomic>
40#include <thread>
41#include <unordered_set>
42#include <utility>
43
44
46{
47 assert( aPoly->size() == 1 );
48
49 struct EDGE
50 {
51 int m_index = 0;
52 SHAPE_LINE_CHAIN* m_poly = nullptr;
53 bool m_duplicate = false;
54
55 EDGE( SHAPE_LINE_CHAIN *aPolygon, int aIndex ) :
56 m_index(aIndex),
57 m_poly(aPolygon)
58 {}
59
60 bool compareSegs( const SEG& s1, const SEG& s2) const
61 {
62 return (s1.A == s2.A && s1.B == s2.B) || (s1.A == s2.B && s1.B == s2.A);
63 }
64
65 bool operator==( const EDGE& aOther ) const
66 {
67 return compareSegs(
68 m_poly->Segment( m_index ), aOther.m_poly->Segment( aOther.m_index ) );
69 }
70
71 bool operator!=( const EDGE& aOther ) const
72 {
73 return !compareSegs(
74 m_poly->Segment( m_index ), aOther.m_poly->Segment( aOther.m_index ) );
75 }
76
77 struct HASH
78 {
79 std::size_t operator()( const EDGE& aEdge ) const
80 {
81 const auto& a = aEdge.m_poly->Segment( aEdge.m_index );
82 return (std::size_t) ( a.A.x + a.B.x + a.A.y + a.B.y );
83 }
84 };
85
86 };
87
88 struct EDGE_LIST_ENTRY
89 {
90 int index;
91 EDGE_LIST_ENTRY *next;
92 };
93
94 std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
95
96 auto lc = (*aPoly)[0];
97 lc.Simplify();
98
99 auto edgeList = std::make_unique<EDGE_LIST_ENTRY []>( lc.SegmentCount() );
100
101 for(int i = 0; i < lc.SegmentCount(); i++)
102 {
103 edgeList[i].index = i;
104 edgeList[i].next = &edgeList[ (i != lc.SegmentCount() - 1) ? i + 1 : 0 ];
105 }
106
107 std::unordered_set<EDGE_LIST_ENTRY*> queue;
108
109 for(int i = 0; i < lc.SegmentCount(); i++)
110 {
111 EDGE e ( &lc, i );
112 uniqueEdges.insert( e );
113 }
114
115 for(int i = 0; i < lc.SegmentCount(); i++)
116 {
117 EDGE e ( &lc, i );
118 auto it = uniqueEdges.find(e);
119 if (it != uniqueEdges.end() && it->m_index != i )
120 {
121 int e1 = it->m_index;
122 int e2 = i;
123 if( e1 > e2 )
124 std::swap(e1, e2);
125
126 int e1_prev = e1 - 1;
127 if (e1_prev < 0)
128 e1_prev = lc.SegmentCount() - 1;
129
130 int e2_prev = e2 - 1;
131 if (e2_prev < 0)
132 e2_prev = lc.SegmentCount() - 1;
133
134 int e1_next = e1 + 1;
135 if (e1_next == lc.SegmentCount() )
136 e1_next = 0;
137
138 int e2_next = e2 + 1;
139 if (e2_next == lc.SegmentCount() )
140 e2_next = 0;
141
142 edgeList[e1_prev].next = &edgeList[ e2_next ];
143 edgeList[e2_prev].next = &edgeList[ e1_next ];
144 edgeList[i].next = nullptr;
145 edgeList[it->m_index].next = nullptr;
146 }
147 }
148
149 for(int i = 0; i < lc.SegmentCount(); i++)
150 {
151 if ( edgeList[i].next )
152 queue.insert ( &edgeList[i] );
153 }
154
155 auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.SegmentCount() );
156
157 int n = 0;
158 int outline = -1;
159aResult->clear();
160 while (queue.size())
161 {
162 auto e_first = (*queue.begin());
163 auto e = e_first;
164 int cnt=0;
165
166 do
167 {
168 edgeBuf[cnt++] = e;
169 e = e->next;
170 } while( e != e_first );
171
172 SHAPE_LINE_CHAIN outl;
173
174 for(int i = 0; i < cnt ;i++)
175 {
176 auto p = lc.CPoint(edgeBuf[i]->index);
177 outl.Append( p );
178 queue.erase( edgeBuf[i] );
179 }
180
181 // auto p_last = lc.Point( edgeBuf[cnt-1]->index + 1 );
182 // outl.Append( p_last );
183
184 outl.SetClosed(true);
185
186 bool cw = outl.Area() > 0.0;
187
188 if(cw)
189 outline = n;
190
191 aResult->push_back(outl);
192 n++;
193 }
194
195 assert(outline >= 0);
196
197 if(outline !=0 )
198 std::swap( (*aResult) [0], (*aResult)[outline] );
199}
200
201
203{
205};
206
207
208int polygon_triangulation_main( int argc, char *argv[] )
209{
210 std::string filename;
211
212 if( argc > 1 )
213 filename = argv[1];
214
215 auto brd = KI_TEST::ReadBoardFromFileOrStream( filename );
216
217 if( !brd )
219
220
221 PROF_TIMER cnt( "allBoard" );
222
223
224 std::atomic<size_t> zonesToTriangulate( 0 );
225 std::atomic<size_t> threadsFinished( 0 );
226
227 size_t parallelThreadCount = std::max<size_t>( std::thread::hardware_concurrency(), 2 );
228 for( size_t ii = 0; ii < parallelThreadCount; ++ii )
229 {
230 std::thread t = std::thread( [&brd, &zonesToTriangulate, &threadsFinished]() {
231 for( size_t areaId = zonesToTriangulate.fetch_add( 1 );
232 areaId < static_cast<size_t>( brd->GetAreaCount() );
233 areaId = zonesToTriangulate.fetch_add( 1 ) )
234 {
235 auto zone = brd->GetArea( areaId );
236
237 // NOTE: this could be refactored to do multiple layers from the same zone in
238 // parallel, but since the test case doesn't have any of these, I'm not bothering
239 // to do that right now.
240 for( PCB_LAYER_ID layer : zone->GetLayerSet().Seq() )
241 {
242 SHAPE_POLY_SET poly = *zone->GetFilledPolysList( layer );
243
244 poly.CacheTriangulation();
245
246 ignore_unused( poly );
247#if 0
248 PROF_TIMER unfrac("unfrac");
249 poly.Unfracture( SHAPE_POLY_SET::PM_FAST );
250 unfrac.Show();
251
252 PROF_TIMER triangulate("triangulate");
253
254 for(int i =0; i< poly.OutlineCount(); i++)
255 {
256 poly.triangulatePoly( &poly.Polygon(i) );
257 }
258 triangulate.Show();
259#endif
260 }
261 }
262
263 threadsFinished++;
264 } );
265
266 t.detach();
267 }
268
269 while( threadsFinished < parallelThreadCount )
270 std::this_thread::sleep_for( std::chrono::milliseconds( 10 ) );
271
272 cnt.Show();
273
275}
276
277
279 "polygon_triangulation",
280 "Process polygon triangulation on a PCB",
282} );
bool operator==(const wxAuiPaneInfo &aLhs, const wxAuiPaneInfo &aRhs)
General utilities for PCB file IO for QA programs.
bool operator!=(const BOM_FIELD &lhs, const BOM_FIELD &rhs)
A small class to help profiling.
Definition: profile.h:48
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
SEG Segment(int aIndex) const
Return a copy of the aIndex-th segment in the line chain.
double Area(bool aAbsolute=true) const
Return the area of this chain.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
static bool Register(const KI_TEST::UTILITY_PROGRAM &aProgInfo)
Register a utility program factory function against an ID string.
std::unique_ptr< BOARD > ReadBoardFromFileOrStream(const std::string &aFilename, std::istream &aFallback)
Read a board from a file, or another stream, as appropriate.
@ OK
Tool exited OK.
@ TOOL_SPECIFIC
Tools can define their own statuses from here onwards.
static bool registered
int polygon_triangulation_main(int argc, char *argv[])
void unfracture(SHAPE_POLY_SET::POLYGON *aPoly, SHAPE_POLY_SET::POLYGON *aResult)
CITER next(CITER it)
Definition: ptree.cpp:126