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_PTR > hedTriangulation (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

◆ AddNode()

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

◆ areNodesColinear()

bool RN_NET::TRIANGULATOR_STATE::areNodesColinear ( const std::vector< hed::NODE_PTR > &  aNodes) const
inlineprivate

Definition at line 171 of file ratsnest_data.cpp.

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  }

◆ Clear()

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

◆ hedTriangulation()

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.

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  }

◆ Triangulate()

const std::list<CN_EDGE> RN_NET::TRIANGULATOR_STATE::Triangulate ( )
inline

Definition at line 204 of file ratsnest_data.cpp.

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.resize( 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( const auto& n : m_allNodes )
234  {
235  if( !prev || prev->Pos() != n->Pos() )
236  {
237  auto tn = std::make_shared<hed::NODE> ( n->Pos().x, n->Pos().y );
238 
239  tn->SetId( id );
240  triNodes.push_back( tn );
241  }
242 
243  id++;
244  prev = n;
245  }
246 
247  int prevId = 0;
248 
249  for( const auto& n : triNodes )
250  {
251  for( int i = prevId; i < n->Id(); i++ )
252  anchorChains[prevId].push_back( m_allNodes[ i ] );
253 
254  prevId = n->Id();
255  }
256 
257  for( int i = prevId; i < id; i++ )
258  anchorChains[prevId].push_back( m_allNodes[ i ] );
259 
260  if( triNodes.size() == 1 )
261  {
262  return mstEdges;
263  }
264  else if( areNodesColinear( triNodes ) )
265  {
266  // special case: all nodes are on the same line - there's no
267  // triangulation for such set. In this case, we sort along any coordinate
268  // and chain the nodes together.
269  for(int i = 0; i < (int)triNodes.size() - 1; i++ )
270  {
271  auto src = m_allNodes[ triNodes[i]->Id() ];
272  auto dst = m_allNodes[ triNodes[i + 1]->Id() ];
273  mstEdges.emplace_back( src, dst, getDistance( src, dst ) );
274  }
275  }
276  else
277  {
278  hed::TRIANGULATION triangulator;
279  triangulator.CreateDelaunay( triNodes.begin(), triNodes.end() );
280  triangulator.GetEdges( triangEdges );
281 
282  for( const auto& e : triangEdges )
283  {
284  auto src = m_allNodes[ e->GetSourceNode()->Id() ];
285  auto dst = m_allNodes[ e->GetTargetNode()->Id() ];
286 
287  mstEdges.emplace_back( src, dst, getDistance( src, dst ) );
288  }
289  }
290 
291  for( unsigned int i = 0; i < anchorChains.size(); i++ )
292  {
293  auto& chain = anchorChains[i];
294 
295  if( chain.size() < 2 )
296  continue;
297 
298  std::sort( chain.begin(), chain.end(),
299  [] ( const CN_ANCHOR_PTR& a, const CN_ANCHOR_PTR& b ) {
300  return a->GetCluster().get() < b->GetCluster().get();
301  } );
302 
303  for( unsigned int j = 1; j < chain.size(); j++ )
304  {
305  const auto& prevNode = chain[j - 1];
306  const auto& curNode = chain[j];
307  int weight = prevNode->GetCluster() != curNode->GetCluster() ? 1 : 0;
308  mstEdges.emplace_back( prevNode, curNode, weight );
309  }
310  }
311 
312  return mstEdges;
313  }
std::vector< CN_ANCHOR_PTR > m_allNodes
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
static uint64_t getDistance(const CN_ANCHOR_PTR &aNode1, const CN_ANCHOR_PTR &aNode2)
bool areNodesColinear(const std::vector< hed::NODE_PTR > &aNodes) const

References getDistance().

Member Data Documentation

◆ m_allNodes

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: