Describe ratsnest for a single net. More...

#include <ratsnest_data.h>

Classes
class	TRIANGULATOR_STATE

Public Member Functions
	RN_NET ()

bool	IsDirty () const
	Return state of the 'dirty' flag, indicating that ratsnest for a given net is invalid and requires an update. More...

void	UpdateNet ()
	Recompute ratsnest for a net. More...

void	Clear ()

void	AddCluster (std::shared_ptr< CN_CLUSTER > aCluster)

unsigned int	GetNodeCount () const

const std::vector< CN_EDGE > &	GetEdges () const

std::vector< CN_EDGE > &	GetEdges ()

bool	NearestBicoloredPair (RN_NET *aOtherNet, VECTOR2I &aPos1, VECTOR2I &aPos2) const

Protected Member Functions
void	compute ()
	< Recompute ratsnest from scratch. More...

void	kruskalMST (const std::vector< CN_EDGE > &aEdges)
	Find optimal ends of RNEdges. More...

void	optimizeRNEdges ()

Protected Attributes
std::multiset< std::shared_ptr< CN_ANCHOR >, CN_PTR_CMP >	m_nodes
	< Vector of nodes More...

std::vector< CN_EDGE >	m_boardEdges
	Vector of edges that makes ratsnest for a given net. More...

std::vector< CN_EDGE >	m_rnEdges
	Flag indicating necessity of recalculation of ratsnest for a net. More...

bool	m_dirty

std::shared_ptr< TRIANGULATOR_STATE >	m_triangulator

Detailed Description

Describe ratsnest for a single net.

Definition at line 62 of file ratsnest_data.h.

Constructor & Destructor Documentation

◆ RN_NET()

RN_NET::RN_NET ( )

Definition at line 262 of file ratsnest_data.cpp.

 : m_dirty( true )
{
 m_triangulator.reset( new TRIANGULATOR_STATE );
}

References m_triangulator.

Member Function Documentation

◆ AddCluster()

void RN_NET::AddCluster ( std::shared_ptr< CN_CLUSTER > aCluster )

Definition at line 473 of file ratsnest_data.cpp.

{
 std::shared_ptr<CN_ANCHOR> firstAnchor;
 
 for( CN_ITEM* item : *aCluster )
 {
 std::vector<std::shared_ptr<CN_ANCHOR>>& anchors = item->Anchors();
 unsigned int nAnchors = dynamic_cast<CN_ZONE_LAYER*>( item ) ? 1 : anchors.size();
 
 if( nAnchors > anchors.size() )
 nAnchors = anchors.size();
 
 for( unsigned int i = 0; i < nAnchors; i++ )
 {
 anchors[i]->SetCluster( aCluster );
 m_nodes.insert( anchors[i] );
 
 if( firstAnchor )
 {
 if( firstAnchor != anchors[i] )
 m_boardEdges.emplace_back( firstAnchor, anchors[i], 0 );
 }
 else
 {
 firstAnchor = anchors[i];
 }
 }
 }
}

References m_boardEdges, and m_nodes.

Referenced by CONNECTIVITY_DATA::addRatsnestCluster().

◆ Clear()

void RN_NET::Clear ( )

Definition at line 463 of file ratsnest_data.cpp.

{
 m_rnEdges.clear();
 m_boardEdges.clear();
 m_nodes.clear();
 
 m_dirty = true;
}

References m_boardEdges, m_dirty, m_nodes, and m_rnEdges.

◆ compute()

void RN_NET::compute ( )

protected

< Recompute ratsnest from scratch.

Compute the minimum spanning tree using Kruskal's algorithm

Definition at line 268 of file ratsnest_data.cpp.

{
 // Special cases do not need complicated algorithms (actually, it does not work well with
 // the Delaunay triangulator)
 if( m_nodes.size() <= 2 )
 {
 m_rnEdges.clear();
 
 // Check if the only possible connection exists
 if( m_boardEdges.size() == 0 && m_nodes.size() == 2 )
 {
 // There can be only one possible connection, but it is missing
 auto it = m_nodes.begin();
 const std::shared_ptr<CN_ANCHOR>& source = *it++;
 const std::shared_ptr<CN_ANCHOR>& target = *it;
 
 source->SetTag( 0 );
 target->SetTag( 1 );
 m_rnEdges.emplace_back( source, target );
 }
 else
 {
 // Set tags to m_nodes as connected
 for( const std::shared_ptr<CN_ANCHOR>& node : m_nodes )
 node->SetTag( 0 );
 }
 
 return;
 }
 
 
 m_triangulator->Clear();
 
 for( const std::shared_ptr<CN_ANCHOR>& n : m_nodes )
 m_triangulator->AddNode( n );
 
 std::vector<CN_EDGE> triangEdges;
 triangEdges.reserve( m_nodes.size() + m_boardEdges.size() );
 
#ifdef PROFILE
 PROF_TIMER cnt( "triangulate" );
#endif
 m_triangulator->Triangulate( triangEdges );
#ifdef PROFILE
 cnt.Show();
#endif
 
 for( const CN_EDGE& e : m_boardEdges )
 triangEdges.emplace_back( e );
 
 std::sort( triangEdges.begin(), triangEdges.end() );
 
// Get the minimal spanning tree
#ifdef PROFILE
 PROF_TIMER cnt2( "mst" );
#endif
 kruskalMST( triangEdges );
#ifdef PROFILE
 cnt2.Show();
#endif
}

References kruskalMST(), m_boardEdges, m_nodes, m_rnEdges, m_triangulator, and PROF_TIMER::Show().

Referenced by UpdateNet().

◆ GetEdges() [1/2]

std::vector< CN_EDGE > & RN_NET::GetEdges ( )

inline

Definition at line 86 of file ratsnest_data.h.

86{ return m_rnEdges; }

References m_rnEdges.

◆ GetEdges() [2/2]

const std::vector< CN_EDGE > & RN_NET::GetEdges ( ) const

inline

Definition at line 85 of file ratsnest_data.h.

85{ return m_rnEdges; }

References m_rnEdges.

Referenced by CONNECTIVITY_DATA::GetRatsnestForComponent(), CONNECTIVITY_DATA::GetRatsnestForItems(), CONNECTIVITY_DATA::GetRatsnestForPad(), ROUTER_TOOL::Init(), ROUTER_TOOL::RouteSelected(), and RATSNEST_VIEW_ITEM::ViewDraw().

◆ GetNodeCount()

unsigned int RN_NET::GetNodeCount ( ) const

inline

Definition at line 83 of file ratsnest_data.h.

83{ return m_nodes.size(); }

References m_nodes.

Referenced by CONNECTIVITY_DATA::ComputeLocalRatsnest().

◆ IsDirty()

bool RN_NET::IsDirty ( ) const

inline

Return state of the 'dirty' flag, indicating that ratsnest for a given net is invalid and requires an update.

Returns: True if ratsnest requires recomputation, false otherwise.

Definition at line 73 of file ratsnest_data.h.

73{ return m_dirty; }

References m_dirty.

◆ kruskalMST()

void RN_NET::kruskalMST ( const std::vector< CN_EDGE > & aEdges )

protected

Find optimal ends of RNEdges.

The MST will have found the closest anchors, but when zones are involved we might have points closer than the anchors.

Definition at line 110 of file ratsnest_data.cpp.

{
 disjoint_set dset( m_nodes.size() );
 
 m_rnEdges.clear();
 
 int i = 0;
 
 for( const std::shared_ptr<CN_ANCHOR>& node : m_nodes )
 node->SetTag( i++ );
 
 for( const CN_EDGE& tmp : aEdges )
 {
 const std::shared_ptr<const CN_ANCHOR>& source = tmp.GetSourceNode();
 const std::shared_ptr<const CN_ANCHOR>& target = tmp.GetTargetNode();
 
 if( dset.unite( source->GetTag(), target->GetTag() ) )
 {
 if( tmp.GetWeight() > 0 )
 m_rnEdges.push_back( tmp );
 }
 }
}

References m_nodes, m_rnEdges, and disjoint_set::unite().

Referenced by compute().

◆ NearestBicoloredPair()

bool RN_NET::NearestBicoloredPair	(	RN_NET *	aOtherNet,
		VECTOR2I &	aPos1,
		VECTOR2I &	aPos2
	)		const

Sweep-line algorithm to cut the number of comparisons to find the closest point

Step 1: The outer loop needs to be the subset (selected nodes) as it is a linear search

Step 2: O( log n ) search to identify a close element ordered by x The fwd_it iterator will move forward through the elements while the rev_it iterator will move backward through the same set

As soon as the x distance (primary sort) is larger than the smallest distance, stop checking further elements

Step 3: using the same starting point, check points backwards for closer points

Definition at line 504 of file ratsnest_data.cpp.

{
 bool rv = false;
 
 SEG::ecoord distMax_sq = VECTOR2I::ECOORD_MAX;
 
 auto verify =
 [&]( const std::shared_ptr<CN_ANCHOR>& aTestNode1,
 const std::shared_ptr<CN_ANCHOR>& aTestNode2 )
 {
 VECTOR2I diff = aTestNode1->Pos() - aTestNode2->Pos();
 SEG::ecoord dist_sq = diff.SquaredEuclideanNorm();
 
 if( dist_sq < distMax_sq )
 {
 rv = true;
 distMax_sq = dist_sq;
 aPos1 = aTestNode1->Pos();
 aPos2 = aTestNode2->Pos();
 }
 };
 
 std::multiset<std::shared_ptr<CN_ANCHOR>, CN_PTR_CMP> nodes_b;
 
 std::copy_if( m_nodes.begin(), m_nodes.end(), std::inserter( nodes_b, nodes_b.end() ),
 []( const std::shared_ptr<CN_ANCHOR> &aVal )
 { return !aVal->GetNoLine(); } );
 
 for( const std::shared_ptr<CN_ANCHOR>& nodeA : aOtherNet->m_nodes )
 {
 
 if( nodeA->GetNoLine() )
 continue;
 
 auto fwd_it = nodes_b.lower_bound( nodeA );
 auto rev_it = std::make_reverse_iterator( fwd_it );
 
 for( ; fwd_it != nodes_b.end(); ++fwd_it )
 {
 const std::shared_ptr<CN_ANCHOR>& nodeB = *fwd_it;
 
 SEG::ecoord distX_sq = SEG::Square( nodeA->Pos().x - nodeB->Pos().x );
 
 if( distX_sq > distMax_sq )
 break;
 
 verify( nodeA, nodeB );
 }
 
 for( ; rev_it != nodes_b.rend(); ++rev_it )
 {
 const std::shared_ptr<CN_ANCHOR>& nodeB = *rev_it;
 
 SEG::ecoord distX_sq = SEG::Square( nodeA->Pos().x - nodeB->Pos().x );
 
 if( distX_sq > distMax_sq )
 break;
 
 verify( nodeA, nodeB );
 }
 }
 
 return rv;
}

References VECTOR2< int >::ECOORD_MAX, m_nodes, SEG::Square(), and VECTOR2< T >::SquaredEuclideanNorm().

Referenced by CONNECTIVITY_DATA::ComputeLocalRatsnest().

◆ optimizeRNEdges()

void RN_NET::optimizeRNEdges ( )

protected

Definition at line 331 of file ratsnest_data.cpp.

{
 auto optimizeZoneAnchor =
 [&]( const VECTOR2I& aPos, const LSET& aLayerSet,
 const std::shared_ptr<const CN_ANCHOR>& aAnchor,
  std::function<void( std::shared_ptr<const CN_ANCHOR> )> setOptimizedTo )
 {
 SEG::ecoord closest_dist_sq = ( aAnchor->Pos() - aPos ).SquaredEuclideanNorm();
 VECTOR2I closest_pt;
 CN_ITEM* closest_item = nullptr;
 
 for( CN_ITEM* item : aAnchor->Item()->ConnectedItems() )
 {
 CN_ZONE_LAYER* zoneLayer = dynamic_cast<CN_ZONE_LAYER*>( item );
 
 if( zoneLayer && aLayerSet.test( zoneLayer->Layer() ) )
 {
 const std::vector<VECTOR2I>& pts = zoneLayer->GetOutline().CPoints();
 
 for( VECTOR2I pt : pts )
 {
 SEG::ecoord dist_sq = ( pt - aPos ).SquaredEuclideanNorm();
 
 if( dist_sq < closest_dist_sq )
 {
 closest_pt = pt;
 closest_item = zoneLayer;
 closest_dist_sq = dist_sq;
 }
 }
 }
 }
 
 if( closest_item )
  setOptimizedTo( std::make_shared<CN_ANCHOR>( closest_pt, closest_item ) );
 };
 
 auto optimizeZoneToZoneAnchors =
 [&]( const std::shared_ptr<const CN_ANCHOR>& a,
 const std::shared_ptr<const CN_ANCHOR>& b,
 std::function<void(const std::shared_ptr<const CN_ANCHOR>&)> setOptimizedATo,
 std::function<void(const std::shared_ptr<const CN_ANCHOR>&)> setOptimizedBTo )
 {
 for( CN_ITEM* itemA : a->Item()->ConnectedItems() )
 {
 CN_ZONE_LAYER* zoneLayerA = dynamic_cast<CN_ZONE_LAYER*>( itemA );
 
 if( !zoneLayerA )
 continue;
 
 for( CN_ITEM* itemB : b->Item()->ConnectedItems() )
 {
 CN_ZONE_LAYER* zoneLayerB = dynamic_cast<CN_ZONE_LAYER*>( itemB );
 
 if( zoneLayerB && zoneLayerB->Layer() == zoneLayerA->Layer() )
 {
 // Process the first matching layer. We don't really care if it's
 // the "best" layer or not, as anything will be better than the
 // original anchors (which are connected to the zone and so certainly
  // don't look like they should have ratsnest lines coming off them).
 
 VECTOR2I startA = zoneLayerA->GetOutline().GetPoint( 0 );
 VECTOR2I startB = zoneLayerB->GetOutline().GetPoint( 0 );
 const SHAPE* shapeA = &zoneLayerA->GetOutline();
 const SHAPE* shapeB = &zoneLayerB->GetOutline();
 int startDist = ( startA - startB ).EuclideanNorm();
 
 VECTOR2I ptA;
 shapeA->Collide( shapeB, startDist + 10, nullptr, &ptA );
 setOptimizedATo( std::make_shared<CN_ANCHOR>( ptA, zoneLayerA ) );
 
 VECTOR2I ptB;
 shapeB->Collide( shapeA, startDist + 10, nullptr, &ptB );
 setOptimizedBTo( std::make_shared<CN_ANCHOR>( ptB, zoneLayerB ) );
 }
 }
 }
 };
 
 for( CN_EDGE& edge : m_rnEdges )
 {
 const std::shared_ptr<const CN_ANCHOR>& source = edge.GetSourceNode();
 const std::shared_ptr<const CN_ANCHOR>& target = edge.GetTargetNode();
 
 if( source->ConnectedItemsCount() == 0 )
 {
 optimizeZoneAnchor( source->Pos(), source->Parent()->GetLayerSet(), target,
 [&]( std::shared_ptr<const CN_ANCHOR> optimized )
 {
 edge.SetTargetNode( optimized );
 } );
 }
 else if( target->ConnectedItemsCount() == 0 )
 {
 optimizeZoneAnchor( target->Pos(), target->Parent()->GetLayerSet(), source,
 [&]( std::shared_ptr<const CN_ANCHOR> optimized )
 {
 edge.SetSourceNode( optimized );
 } );
 }
 else
 {
 optimizeZoneToZoneAnchors( source, target,
 [&]( std::shared_ptr<const CN_ANCHOR> optimized )
 {
 edge.SetSourceNode( optimized );
 },
 [&]( std::shared_ptr<const CN_ANCHOR> optimized )
 {
 edge.SetTargetNode( optimized );
 } );
 }
 }
}

References SHAPE::Collide(), CN_ITEM::ConnectedItems(), SHAPE_LINE_CHAIN::CPoints(), EuclideanNorm(), CN_ZONE_LAYER::GetOutline(), SHAPE_LINE_CHAIN::GetPoint(), CN_ITEM::Layer(), and m_rnEdges.

Referenced by UpdateNet().

◆ UpdateNet()

void RN_NET::UpdateNet ( )

Recompute ratsnest for a net.

Definition at line 447 of file ratsnest_data.cpp.

{
 compute();
 
#ifdef PROFILE
 PROF_TIMER cnt( "optimize" );
#endif
 optimizeRNEdges();
#ifdef PROFILE
 cnt.Show();
#endif
 
 m_dirty = false;
}

References compute(), m_dirty, optimizeRNEdges(), and PROF_TIMER::Show().

Member Data Documentation

◆ m_boardEdges

std::vector<CN_EDGE> RN_NET::m_boardEdges

protected

Vector of edges that makes ratsnest for a given net.

Definition at line 106 of file ratsnest_data.h.

Referenced by AddCluster(), Clear(), and compute().

◆ m_dirty

bool RN_NET::m_dirty

protected

Definition at line 112 of file ratsnest_data.h.

Referenced by Clear(), IsDirty(), and UpdateNet().

◆ m_nodes

std::multiset<std::shared_ptr<CN_ANCHOR>, CN_PTR_CMP> RN_NET::m_nodes

protected

< Vector of nodes

Vector of edges that make pre-defined connections

Definition at line 103 of file ratsnest_data.h.

Referenced by AddCluster(), Clear(), compute(), GetNodeCount(), kruskalMST(), and NearestBicoloredPair().

◆ m_rnEdges

std::vector<CN_EDGE> RN_NET::m_rnEdges

protected

Flag indicating necessity of recalculation of ratsnest for a net.

Definition at line 109 of file ratsnest_data.h.

Referenced by Clear(), compute(), GetEdges(), kruskalMST(), and optimizeRNEdges().

◆ m_triangulator

std::shared_ptr<TRIANGULATOR_STATE> RN_NET::m_triangulator

protected

Definition at line 116 of file ratsnest_data.h.

Referenced by compute(), and RN_NET().

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

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ RN_NET()

Member Function Documentation

◆ AddCluster()

◆ Clear()

◆ compute()

◆ GetEdges() [1/2]

◆ GetEdges() [2/2]

◆ GetNodeCount()

◆ IsDirty()

◆ kruskalMST()

◆ NearestBicoloredPair()

◆ optimizeRNEdges()

◆ UpdateNet()

Member Data Documentation

◆ m_boardEdges

◆ m_dirty

◆ m_nodes

◆ m_rnEdges

◆ m_triangulator