KiCad PCB EDA Suite
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 <alejandro.garciamontoro@gmail.com>
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 <profile.h>
36 
37 #include <atomic>
38 #include <thread>
39 #include <unordered_set>
40 #include <utility>
41 
42 
44 {
45  assert( aPoly->size() == 1 );
46 
47  struct EDGE
48  {
49  int m_index = 0;
50  SHAPE_LINE_CHAIN* m_poly = nullptr;
51  bool m_duplicate = false;
52 
53  EDGE( SHAPE_LINE_CHAIN *aPolygon, int aIndex ) :
54  m_index(aIndex),
55  m_poly(aPolygon)
56  {}
57 
58  bool compareSegs( const SEG& s1, const SEG& s2) const
59  {
60  return (s1.A == s2.A && s1.B == s2.B) || (s1.A == s2.B && s1.B == s2.A);
61  }
62 
63  bool operator==( const EDGE& aOther ) const
64  {
65  return compareSegs(
66  m_poly->Segment( m_index ), aOther.m_poly->Segment( aOther.m_index ) );
67  }
68 
69  bool operator!=( const EDGE& aOther ) const
70  {
71  return !compareSegs(
72  m_poly->Segment( m_index ), aOther.m_poly->Segment( aOther.m_index ) );
73  }
74 
75  struct HASH
76  {
77  std::size_t operator()( const EDGE& aEdge ) const
78  {
79  const auto& a = aEdge.m_poly->Segment( aEdge.m_index );
80  return (std::size_t) ( a.A.x + a.B.x + a.A.y + a.B.y );
81  }
82  };
83 
84  };
85 
86  struct EDGE_LIST_ENTRY
87  {
88  int index;
89  EDGE_LIST_ENTRY *next;
90  };
91 
92  std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
93 
94  auto lc = (*aPoly)[0];
95  lc.Simplify();
96 
97  auto edgeList = std::make_unique<EDGE_LIST_ENTRY []>( lc.SegmentCount() );
98 
99  for(int i = 0; i < lc.SegmentCount(); i++)
100  {
101  edgeList[i].index = i;
102  edgeList[i].next = &edgeList[ (i != lc.SegmentCount() - 1) ? i + 1 : 0 ];
103  }
104 
105  std::unordered_set<EDGE_LIST_ENTRY*> queue;
106 
107  for(int i = 0; i < lc.SegmentCount(); i++)
108  {
109  EDGE e ( &lc, i );
110  uniqueEdges.insert( e );
111  }
112 
113  for(int i = 0; i < lc.SegmentCount(); i++)
114  {
115  EDGE e ( &lc, i );
116  auto it = uniqueEdges.find(e);
117  if (it != uniqueEdges.end() && it->m_index != i )
118  {
119  int e1 = it->m_index;
120  int e2 = i;
121  if( e1 > e2 )
122  std::swap(e1, e2);
123 
124  int e1_prev = e1 - 1;
125  if (e1_prev < 0)
126  e1_prev = lc.SegmentCount() - 1;
127 
128  int e2_prev = e2 - 1;
129  if (e2_prev < 0)
130  e2_prev = lc.SegmentCount() - 1;
131 
132  int e1_next = e1 + 1;
133  if (e1_next == lc.SegmentCount() )
134  e1_next = 0;
135 
136  int e2_next = e2 + 1;
137  if (e2_next == lc.SegmentCount() )
138  e2_next = 0;
139 
140  edgeList[e1_prev].next = &edgeList[ e2_next ];
141  edgeList[e2_prev].next = &edgeList[ e1_next ];
142  edgeList[i].next = nullptr;
143  edgeList[it->m_index].next = nullptr;
144  }
145  }
146 
147  for(int i = 0; i < lc.SegmentCount(); i++)
148  {
149  if ( edgeList[i].next )
150  queue.insert ( &edgeList[i] );
151  }
152 
153  auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.SegmentCount() );
154 
155  int n = 0;
156  int outline = -1;
157 aResult->clear();
158  while (queue.size())
159  {
160  auto e_first = (*queue.begin());
161  auto e = e_first;
162  int cnt=0;
163 
164  do
165  {
166  edgeBuf[cnt++] = e;
167  e = e->next;
168  } while( e != e_first );
169 
170  SHAPE_LINE_CHAIN outl;
171 
172  for(int i = 0; i < cnt ;i++)
173  {
174  auto p = lc.CPoint(edgeBuf[i]->index);
175  outl.Append( p );
176  queue.erase( edgeBuf[i] );
177  }
178 
179  // auto p_last = lc.Point( edgeBuf[cnt-1]->index + 1 );
180  // outl.Append( p_last );
181 
182  outl.SetClosed(true);
183 
184  bool cw = outl.Area() > 0.0;
185 
186  if(cw)
187  outline = n;
188 
189  aResult->push_back(outl);
190  n++;
191  }
192 
193  assert(outline >= 0);
194 
195  if(outline !=0 )
196  std::swap( (*aResult) [0], (*aResult)[outline] );
197 }
198 
199 
201 {
203 };
204 
205 
206 int polygon_triangulation_main( int argc, char *argv[] )
207 {
208  std::string filename;
209 
210  if( argc > 1 )
211  filename = argv[1];
212 
213  auto brd = KI_TEST::ReadBoardFromFileOrStream( filename );
214 
215  if( !brd )
217 
218 
219  PROF_COUNTER cnt( "allBoard" );
220 
221 
222  std::atomic<size_t> zonesToTriangulate( 0 );
223  std::atomic<size_t> threadsFinished( 0 );
224 
225  size_t parallelThreadCount = std::max<size_t>( std::thread::hardware_concurrency(), 2 );
226  for( size_t ii = 0; ii < parallelThreadCount; ++ii )
227  {
228  std::thread t = std::thread( [&brd, &zonesToTriangulate, &threadsFinished]() {
229  for( size_t areaId = zonesToTriangulate.fetch_add( 1 );
230  areaId < static_cast<size_t>( brd->GetAreaCount() );
231  areaId = zonesToTriangulate.fetch_add( 1 ) )
232  {
233  auto zone = brd->GetArea( areaId );
234 
235  // NOTE: this could be refactored to do multiple layers from the same zone in
236  // parallel, but since the test case doesn't have any of these, I'm not bothering
237  // to do that right now.
238  for( PCB_LAYER_ID layer : zone->GetLayerSet().Seq() )
239  {
240  SHAPE_POLY_SET poly = zone->GetFilledPolysList( layer );
241 
242  poly.CacheTriangulation();
243 
244  (void) poly;
245 #if 0
246  PROF_COUNTER unfrac("unfrac");
248  unfrac.Show();
249 
250  PROF_COUNTER triangulate("triangulate");
251 
252  for(int i =0; i< poly.OutlineCount(); i++)
253  {
254  poly.triangulatePoly( &poly.Polygon(i) );
255  }
256  triangulate.Show();
257 #endif
258  }
259  }
260 
261  threadsFinished++;
262  } );
263 
264  t.detach();
265  }
266 
267  while( threadsFinished < parallelThreadCount )
268  std::this_thread::sleep_for( std::chrono::milliseconds( 10 ) );
269 
270  cnt.Show();
271 
272  return KI_TEST::RET_CODES::OK;
273 }
274 
275 
277  "polygon_triangulation",
278  "Process polygon triangulation on a PCB",
280 } );
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
CITER next(CITER it)
Definition: ptree.cpp:126
Tools can define their own statuses from here onwards.
int OutlineCount() const
Return the number of vertices in a given outline/hole.
#define OK
bool operator==(const PART_LIB &aLibrary, const wxString &aName)
Case insensitive library name comparison.
int polygon_triangulation_main(int argc, char *argv[])
A small class to help profiling.
Definition: profile.h:45
static bool registered
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
void SetClosed(bool aClosed)
Function SetClosed()
PCB_LAYER_ID
A quick note on layer IDs:
static bool Register(const KI_TEST::UTILITY_PROGRAM &aProgInfo)
Register a utility program factory function against an ID string.
Represent a set of closed polygons.
Definition: seg.h:41
SEG Segment(int aIndex)
Function Segment()
SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:49
void CacheTriangulation(bool aPartition=true)
void unfracture(SHAPE_POLY_SET::POLYGON *aPoly, SHAPE_POLY_SET::POLYGON *aResult)
void Show(std::ostream &aStream=std::cerr)
Print the elapsed time (in a suitable unit) to a stream.
Definition: profile.h:102
General utilities for PCB file IO for QA programs.
std::unique_ptr< BOARD > ReadBoardFromFileOrStream(const std::string &aFilename, std::istream &aFallback)
Read a board from a file, or another stream, as appropriate.
POLYGON & Polygon(int aIndex)
bool operator!=(const PART_LIB &aLibrary, const wxString &aName)
VECTOR2I B
Definition: seg.h:50
void Unfracture(POLYGON_MODE aFastMode)
Return true if the polygon set has any holes.