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  * @author Alejandro GarcĂ­a Montoro <alejandro.garciamontoro@gmail.com>
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
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.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 
27 
29 
31 
32 #include <class_board.h>
33 #include <class_zone.h>
34 #include <profile.h>
35 
36 #include <atomic>
37 #include <thread>
38 #include <unordered_set>
39 #include <utility>
40 
41 
43 {
44  assert( aPoly->size() == 1 );
45 
46  struct EDGE
47  {
48  int m_index = 0;
49  SHAPE_LINE_CHAIN* m_poly = nullptr;
50  bool m_duplicate = false;
51 
52  EDGE( SHAPE_LINE_CHAIN *aPolygon, int aIndex ) :
53  m_index(aIndex),
54  m_poly(aPolygon)
55  {}
56 
57  bool compareSegs( const SEG& s1, const SEG& s2) const
58  {
59  return (s1.A == s2.A && s1.B == s2.B) || (s1.A == s2.B && s1.B == s2.A);
60  }
61 
62  bool operator==( const EDGE& aOther ) const
63  {
64  return compareSegs(
65  m_poly->Segment( m_index ), aOther.m_poly->Segment( aOther.m_index ) );
66  }
67 
68  bool operator!=( const EDGE& aOther ) const
69  {
70  return !compareSegs(
71  m_poly->Segment( m_index ), aOther.m_poly->Segment( aOther.m_index ) );
72  }
73 
74  struct HASH
75  {
76  std::size_t operator()( const EDGE& aEdge ) const
77  {
78  const auto& a = aEdge.m_poly->Segment( aEdge.m_index );
79  return (std::size_t) ( a.A.x + a.B.x + a.A.y + a.B.y );
80  }
81  };
82 
83  };
84 
85  struct EDGE_LIST_ENTRY
86  {
87  int index;
88  EDGE_LIST_ENTRY *next;
89  };
90 
91  std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
92 
93  auto lc = (*aPoly)[0];
94  lc.Simplify();
95 
96  auto edgeList = std::make_unique<EDGE_LIST_ENTRY []>( lc.SegmentCount() );
97 
98  for(int i = 0; i < lc.SegmentCount(); i++)
99  {
100  edgeList[i].index = i;
101  edgeList[i].next = &edgeList[ (i != lc.SegmentCount() - 1) ? i + 1 : 0 ];
102  //printf("n %p\n", edgeList[i].next);
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  // printf("e1 %d e2 %d\n", 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  //else
154  //printf("Skip %d\n", i);
155  }
156 
157  auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.SegmentCount() );
158 
159  int n = 0;
160  int outline = -1;
161 aResult->clear();
162  while (queue.size())
163  {
164  auto e_first = (*queue.begin());
165  auto e = e_first;
166  int cnt=0;
167  do {
168  // printf("e %p cnt %d IDX %d\n", e, cnt, e->index);
169  edgeBuf[cnt++] = e;
170  e = e->next;
171  } while( e != e_first );
172 
173  SHAPE_LINE_CHAIN outl;
174 
175  for(int i = 0; i < cnt ;i++)
176  {
177  auto p = lc.CPoint(edgeBuf[i]->index);
178 // printf("append %d %d\n", p.x, p.y);
179  outl.Append( p );
180  queue.erase( edgeBuf[i] );
181  }
182 
183  // auto p_last = lc.Point( edgeBuf[cnt-1]->index + 1 );
184  //printf("appendl %d %d\n", p_last.x, p_last.y);
185  // outl.Append( p_last );
186 
187  outl.SetClosed(true);
188 
189  bool cw = outl.Area() > 0.0;
190 
191  if(cw)
192  outline = n;
193 
194  aResult->push_back(outl);
195  n++;
196  }
197 
198  assert(outline >= 0);
199 
200  if(outline !=0 )
201  std::swap( (*aResult) [0], (*aResult)[outline] );
202 }
203 
204 
206 {
208 };
209 
210 
211 int polygon_triangulation_main( int argc, char *argv[] )
212 {
213  std::string filename;
214 
215  if( argc > 1 )
216  filename = argv[1];
217 
218  auto brd = KI_TEST::ReadBoardFromFileOrStream( filename );
219 
220  if( !brd )
222 
223 
224  PROF_COUNTER cnt( "allBoard" );
225 
226 
227  std::atomic<size_t> zonesToTriangulate( 0 );
228  std::atomic<size_t> threadsFinished( 0 );
229 
230  size_t parallelThreadCount = std::max<size_t>( std::thread::hardware_concurrency(), 2 );
231  for( size_t ii = 0; ii < parallelThreadCount; ++ii )
232  {
233  std::thread t = std::thread( [&brd, &zonesToTriangulate, &threadsFinished]() {
234  for( size_t areaId = zonesToTriangulate.fetch_add( 1 );
235  areaId < static_cast<size_t>( brd->GetAreaCount() );
236  areaId = zonesToTriangulate.fetch_add( 1 ) )
237  {
238  auto zone = brd->GetArea( areaId );
239 
240  // NOTE: this could be refactored to do multiple layers from the same zone in
241  // parallel, but since the test case doesn't have any of these, I'm not bothering
242  // to do that right now.
243  for( PCB_LAYER_ID layer : zone->GetLayerSet().Seq() )
244  {
245  SHAPE_POLY_SET poly = zone->GetFilledPolysList( layer );
246 
247  poly.CacheTriangulation();
248 
249  (void) poly;
250  printf( "zone %zu/%d\n", ( areaId + 1 ), brd->GetAreaCount() );
251 #if 0
252  PROF_COUNTER unfrac("unfrac");
254  unfrac.Show();
255 
256  PROF_COUNTER triangulate("triangulate");
257 
258  for(int i =0; i< poly.OutlineCount(); i++)
259  {
260  poly.triangulatePoly( &poly.Polygon(i) );
261  }
262  triangulate.Show();
263 #endif
264  }
265  }
266 
267  threadsFinished++;
268  } );
269 
270  t.detach();
271  }
272 
273  while( threadsFinished < parallelThreadCount )
274  std::this_thread::sleep_for( std::chrono::milliseconds( 10 ) );
275 
276  cnt.Show();
277 
278  return KI_TEST::RET_CODES::OK;
279 }
280 
281 
283  "polygon_triangulation",
284  "Process polygon triangulation on a PCB",
286 } );
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
CITER next(CITER it)
Definition: ptree.cpp:130
Tools can define their own statuses from here onwards.
int OutlineCount() const
Returns the number of outlines in the set
#define OK
bool operator==(const PART_LIB &aLibrary, const wxString &aName)
Case insensitive library name comparison.
int polygon_triangulation_main(int argc, char *argv[])
The class PROF_COUNTER is a small class to help profiling.
Definition: profile.h:44
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.
SHAPE_POLY_SET.
Definition: seg.h:39
SEG Segment(int aIndex)
Function Segment()
SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:47
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:99
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)
Returns the aIndex-th subpolygon in the set
bool operator!=(const PART_LIB &aLibrary, const wxString &aName)
VECTOR2I B
Definition: seg.h:48
void Unfracture(POLYGON_MODE aFastMode)
Converts a single outline slitted ("fractured") polygon into a set ouf outlines with holes.