KiCad PCB EDA Suite
RN_NET::TRIANGULATOR_STATE Class Reference

Public Member Functions

void Clear ()
 
void AddNode (CN_ANCHOR_PTR aNode)
 
void Triangulate (std::vector< CN_EDGE > &mstEdges)
 

Private Member Functions

bool areNodesColinear (const std::vector< CN_ANCHOR_PTR > &aNodes) const
 

Private Attributes

std::multiset< CN_ANCHOR_PTR, CN_PTR_CMPm_allNodes
 

Detailed Description

Definition at line 135 of file ratsnest_data.cpp.

Member Function Documentation

◆ AddNode()

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

Definition at line 169 of file ratsnest_data.cpp.

170  {
171  m_allNodes.insert( aNode );
172  }
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_allNodes

◆ areNodesColinear()

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

Definition at line 143 of file ratsnest_data.cpp.

144  {
145  if ( aNodes.size() <= 2 )
146  return true;
147 
148  const VECTOR2I p0( aNodes[0]->Pos() );
149  const VECTOR2I v0( aNodes[1]->Pos() - p0 );
150 
151  for( unsigned i = 2; i < aNodes.size(); i++ )
152  {
153  const VECTOR2I v1 = aNodes[i]->Pos() - p0;
154 
155  if( v0.Cross( v1 ) != 0 )
156  return false;
157  }
158 
159  return true;
160  }

References VECTOR2< T >::Cross().

◆ Clear()

void RN_NET::TRIANGULATOR_STATE::Clear ( )
inline

Definition at line 164 of file ratsnest_data.cpp.

165  {
166  m_allNodes.clear();
167  }
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_allNodes

◆ Triangulate()

void RN_NET::TRIANGULATOR_STATE::Triangulate ( std::vector< CN_EDGE > &  mstEdges)
inline

Definition at line 174 of file ratsnest_data.cpp.

175  {
176  std::vector<double> node_pts;
177  std::vector<CN_ANCHOR_PTR> anchors;
178  std::vector< std::vector<CN_ANCHOR_PTR> > anchorChains( m_allNodes.size() );
179 
180  node_pts.reserve( 2 * m_allNodes.size() );
181  anchors.reserve( m_allNodes.size() );
182 
183  CN_ANCHOR_PTR prev = nullptr;
184 
185  for( const CN_ANCHOR_PTR& n : m_allNodes )
186  {
187  if( !prev || prev->Pos() != n->Pos() )
188  {
189  node_pts.push_back( n->Pos().x );
190  node_pts.push_back( n->Pos().y );
191  anchors.push_back( n );
192  prev = n;
193  }
194 
195  anchorChains[anchors.size() - 1].push_back( n );
196  }
197 
198  if( anchors.size() < 2 )
199  {
200  return;
201  }
202  else if( areNodesColinear( anchors ) )
203  {
204  // special case: all nodes are on the same line - there's no
205  // triangulation for such set. In this case, we sort along any coordinate
206  // and chain the nodes together.
207  for( size_t i = 0; i < anchors.size() - 1; i++ )
208  {
209  const CN_ANCHOR_PTR& src = anchors[i];
210  const CN_ANCHOR_PTR& dst = anchors[i + 1];
211  mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
212  }
213  }
214  else
215  {
216  delaunator::Delaunator delaunator( node_pts );
217  auto& triangles = delaunator.triangles;
218 
219  for( size_t i = 0; i < triangles.size(); i += 3 )
220  {
221  CN_ANCHOR_PTR src = anchors[triangles[i]];
222  CN_ANCHOR_PTR dst = anchors[triangles[i + 1]];
223  mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
224 
225  src = anchors[triangles[i + 1]];
226  dst = anchors[triangles[i + 2]];
227  mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
228 
229  src = anchors[triangles[i + 2]];
230  dst = anchors[triangles[i]];
231  mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
232  }
233 
234  for( size_t i = 0; i < delaunator.halfedges.size(); i++ )
235  {
236  if( delaunator.halfedges[i] == delaunator::INVALID_INDEX )
237  continue;
238 
239  const CN_ANCHOR_PTR& src = anchors[triangles[i]];
240  const CN_ANCHOR_PTR& dst = anchors[triangles[delaunator.halfedges[i]]];
241  mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
242  }
243  }
244 
245  for( size_t i = 0; i < anchorChains.size(); i++ )
246  {
247  std::vector<CN_ANCHOR_PTR>& chain = anchorChains[i];
248 
249  if( chain.size() < 2 )
250  continue;
251 
252  std::sort( chain.begin(), chain.end(),
253  [] ( const CN_ANCHOR_PTR& a, const CN_ANCHOR_PTR& b )
254  {
255  return a->GetCluster().get() < b->GetCluster().get();
256  } );
257 
258  for( unsigned int j = 1; j < chain.size(); j++ )
259  {
260  const CN_ANCHOR_PTR& prevNode = chain[j - 1];
261  const CN_ANCHOR_PTR& curNode = chain[j];
262  int weight = prevNode->GetCluster() != curNode->GetCluster() ? 1 : 0;
263  mstEdges.emplace_back( prevNode, curNode, weight );
264  }
265  }
266  }
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_allNodes
bool areNodesColinear(const std::vector< CN_ANCHOR_PTR > &aNodes) const
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR

Member Data Documentation

◆ m_allNodes

std::multiset<CN_ANCHOR_PTR, CN_PTR_CMP> RN_NET::TRIANGULATOR_STATE::m_allNodes
private

Definition at line 138 of file ratsnest_data.cpp.


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