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 <[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 <ignore.h>
36 #include <zone.h>
37 #include <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;
159 aResult->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 
208 int 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_COUNTER 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_COUNTER unfrac("unfrac");
250  unfrac.Show();
251 
252  PROF_COUNTER 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 
274  return KI_TEST::RET_CODES::OK;
275 }
276 
277 
279  "polygon_triangulation",
280  "Process polygon triangulation on a PCB",
282 } );
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 SYMBOL_LIB &aLibrary, const wxString &aName)
double Area(bool aAbsolute=true) const
Return the area of this chain.
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)
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.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
static bool Register(const KI_TEST::UTILITY_PROGRAM &aProgInfo)
Register a utility program factory function against an ID string.
bool operator==(const SYMBOL_LIB &aLibrary, const wxString &aName)
Case insensitive library name comparison.
Represent a set of closed polygons.
Definition: seg.h:40
SEG Segment(int aIndex)
Return a copy of the aIndex-th segment in the line chain.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:65
VECTOR2I A
Definition: seg.h:48
void ignore_unused(const T &)
Definition: ignore.h:24
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)
VECTOR2I B
Definition: seg.h:49
void Unfracture(POLYGON_MODE aFastMode)
Return true if the polygon set has any holes.