KiCad PCB EDA Suite
RN_NET::TRIANGULATOR_STATE Class Reference

Public Member Functions

void Clear ()
 
void AddNode (CN_ANCHOR_PTR aNode)
 
const std::list< CN_EDGETriangulate ()
 

Private Member Functions

std::list< hed::EDGE_PTRhedTriangulation (std::vector< hed::NODE_PTR > &aNodes)
 
bool areNodesColinear (const std::vector< hed::NODE_PTR > &aNodes) const
 

Private Attributes

std::vector< CN_ANCHOR_PTRm_allNodes
 

Detailed Description

Definition at line 153 of file ratsnest_data.cpp.

Member Function Documentation

void RN_NET::TRIANGULATOR_STATE::AddNode ( CN_ANCHOR_PTR  aNode)
inline

Definition at line 199 of file ratsnest_data.cpp.

200  {
201  m_allNodes.push_back( aNode );
202  }
std::vector< CN_ANCHOR_PTR > m_allNodes
bool RN_NET::TRIANGULATOR_STATE::areNodesColinear ( const std::vector< hed::NODE_PTR > &  aNodes) const
inlineprivate

Definition at line 171 of file ratsnest_data.cpp.

References i.

172  {
173  if ( aNodes.size() <= 2 )
174  return true;
175 
176  const auto p0 = aNodes[0]->Pos();
177  const auto v0 = aNodes[1]->Pos() - p0;
178 
179  for( unsigned i = 2; i < aNodes.size(); i++ )
180  {
181  const auto v1 = aNodes[i]->Pos() - p0;
182 
183  if( v0.Cross( v1 ) != 0 )
184  {
185  return false;
186  }
187  }
188 
189  return true;
190  }
size_t i
Definition: json11.cpp:597
void RN_NET::TRIANGULATOR_STATE::Clear ( )
inline

Definition at line 194 of file ratsnest_data.cpp.

195  {
196  m_allNodes.clear();
197  }
std::vector< CN_ANCHOR_PTR > m_allNodes
std::list<hed::EDGE_PTR> RN_NET::TRIANGULATOR_STATE::hedTriangulation ( std::vector< hed::NODE_PTR > &  aNodes)
inlineprivate

Definition at line 158 of file ratsnest_data.cpp.

References hed::TRIANGULATION::CreateDelaunay(), and hed::TRIANGULATION::GetEdges().

159  {
160  hed::TRIANGULATION triangulator;
161  triangulator.CreateDelaunay( aNodes.begin(), aNodes.end() );
162  std::list<hed::EDGE_PTR> edges;
163  triangulator.GetEdges( edges );
164 
165  return edges;
166  }
void GetEdges(std::list< EDGE_PTR > &aEdges, bool aSkipBoundaryEdges=false) const
Returns a list of half-edges (one half-edge for each arc)
Definition: hetriang.cpp:397
void CreateDelaunay(NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast)
Creates a Delaunay triangulation from a set of points.
Definition: hetriang.cpp:187
Triangulation class for the half-edge data structure with adaption to TTL.
Definition: hetriang.h:281
const std::list<CN_EDGE> RN_NET::TRIANGULATOR_STATE::Triangulate ( )
inline

Definition at line 204 of file ratsnest_data.cpp.

References hed::TRIANGULATION::CreateDelaunay(), getDistance(), hed::TRIANGULATION::GetEdges(), and i.

205  {
206  std::list<CN_EDGE> mstEdges;
207  std::list<hed::EDGE_PTR> triangEdges;
208  std::vector<hed::NODE_PTR> triNodes;
209 
210  using ANCHOR_LIST = std::vector<CN_ANCHOR_PTR>;
211  std::vector<ANCHOR_LIST> anchorChains;
212 
213  triNodes.reserve( m_allNodes.size() );
214  anchorChains.reserve( m_allNodes.size() );
215 
216  std::sort( m_allNodes.begin(), m_allNodes.end(),
217  [] ( const CN_ANCHOR_PTR& aNode1, const CN_ANCHOR_PTR& aNode2 )
218  {
219  if( aNode1->Pos().y < aNode2->Pos().y )
220  return true;
221  else if( aNode1->Pos().y == aNode2->Pos().y )
222  {
223  return aNode1->Pos().x < aNode2->Pos().x;
224  }
225 
226  return false;
227  }
228  );
229 
230  CN_ANCHOR_PTR prev, last;
231  int id = 0;
232 
233  for( auto n : m_allNodes )
234  {
235  anchorChains.push_back( ANCHOR_LIST() );
236  }
237 
238  for( auto n : m_allNodes )
239  {
240  if( !prev || prev->Pos() != n->Pos() )
241  {
242  auto tn = std::make_shared<hed::NODE> ( n->Pos().x, n->Pos().y );
243 
244  tn->SetId( id );
245  triNodes.push_back( tn );
246  }
247 
248  id++;
249  prev = n;
250  }
251 
252  int prevId = 0;
253 
254  for( auto n : triNodes )
255  {
256  for( int i = prevId; i < n->Id(); i++ )
257  anchorChains[prevId].push_back( m_allNodes[ i ] );
258 
259  prevId = n->Id();
260  }
261 
262  for( int i = prevId; i < id; i++ )
263  anchorChains[prevId].push_back( m_allNodes[ i ] );
264 
265  if( triNodes.size() == 1 )
266  {
267  return mstEdges;
268  }
269  else if( areNodesColinear( triNodes ) )
270  {
271  // special case: all nodes are on the same line - there's no
272  // triangulation for such set. In this case, we sort along any coordinate
273  // and chain the nodes together.
274  for(int i = 0; i < (int)triNodes.size() - 1; i++ )
275  {
276  auto src = m_allNodes[ triNodes[i]->Id() ];
277  auto dst = m_allNodes[ triNodes[i + 1]->Id() ];
278  mstEdges.emplace_back( src, dst, getDistance( src, dst ) );
279  }
280  }
281  else
282  {
283  hed::TRIANGULATION triangulator;
284  triangulator.CreateDelaunay( triNodes.begin(), triNodes.end() );
285  triangulator.GetEdges( triangEdges );
286 
287  for( auto e : triangEdges )
288  {
289  auto src = m_allNodes[ e->GetSourceNode()->Id() ];
290  auto dst = m_allNodes[ e->GetTargetNode()->Id() ];
291 
292  mstEdges.emplace_back( src, dst, getDistance( src, dst ) );
293  }
294  }
295 
296  for( unsigned int i = 0; i < anchorChains.size(); i++ )
297  {
298  auto& chain = anchorChains[i];
299 
300  if( chain.size() < 2 )
301  continue;
302 
303  std::sort( chain.begin(), chain.end(),
304  [] ( const CN_ANCHOR_PTR& a, const CN_ANCHOR_PTR& b ) {
305  return a->GetCluster().get() < b->GetCluster().get();
306  } );
307 
308  for( unsigned int j = 1; j < chain.size(); j++ )
309  {
310  const auto& prevNode = chain[j - 1];
311  const auto& curNode = chain[j];
312  int weight = prevNode->GetCluster() != curNode->GetCluster() ? 1 : 0;
313  mstEdges.push_back( CN_EDGE ( prevNode, curNode, weight ) );
314  }
315  }
316 
317  return mstEdges;
318  }
std::vector< CN_ANCHOR_PTR > m_allNodes
void GetEdges(std::list< EDGE_PTR > &aEdges, bool aSkipBoundaryEdges=false) const
Returns a list of half-edges (one half-edge for each arc)
Definition: hetriang.cpp:397
void CreateDelaunay(NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast)
Creates a Delaunay triangulation from a set of points.
Definition: hetriang.cpp:187
size_t i
Definition: json11.cpp:597
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
static uint64_t getDistance(const CN_ANCHOR_PTR &aNode1, const CN_ANCHOR_PTR &aNode2)
Triangulation class for the half-edge data structure with adaption to TTL.
Definition: hetriang.h:281
bool areNodesColinear(const std::vector< hed::NODE_PTR > &aNodes) const

Member Data Documentation

std::vector<CN_ANCHOR_PTR> RN_NET::TRIANGULATOR_STATE::m_allNodes
private

Definition at line 156 of file ratsnest_data.cpp.


The documentation for this class was generated from the following file: