RN_NET Class Reference

Describe ratsnest for a single net. More...

#include <ratsnest_data.h>

Classes
class	TRIANGULATOR_STATE

Public Member Functions
	RN_NET ()
void	SetVisible (bool aEnabled)
	Set state of the visibility flag. More...
void	MarkDirty ()
	Mark ratsnest for given net as 'dirty', i.e. More...
bool	IsDirty () const
	Return state of the 'dirty' flag, indicating that ratsnest for a given net is invalid and requires an update. More...
const std::vector< CN_EDGE >	GetUnconnected () const
	Return pointer to a vector of edges that makes ratsnest for a given net. More...
void	Update ()
	Recompute ratsnest for a net. More...
void	Clear ()
void	AddCluster (std::shared_ptr< CN_CLUSTER > aCluster)
unsigned int	GetNodeCount () const
std::list< CN_ANCHOR_PTR >	GetNodes (const BOARD_CONNECTED_ITEM *aItem) const
	Return list of nodes that are associated with a given item. More...
const std::vector< CN_EDGE > &	GetEdges () const
void	GetAllItems (std::list< BOARD_CONNECTED_ITEM * > &aOutput, const KICAD_T aTypes[]) const
	Add all stored items to a list. More...
const CN_ANCHOR_PTR	GetClosestNode (const CN_ANCHOR_PTR &aNode) const
	Return a single node that lies in the shortest distance from a specific node. More...
bool	NearestBicoloredPair (const RN_NET &aOtherNet, CN_ANCHOR_PTR &aNode1, CN_ANCHOR_PTR &aNode2) const

Protected Member Functions
void	compute ()
	< Recompute ratsnest from scratch. More...
void	kruskalMST (const std::vector< CN_EDGE > &aEdges)
	Vector of nodes. More...

Protected Attributes
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP >	m_nodes
	Vector of edges that make pre-defined connections. 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 61 of file ratsnest_data.h.

Constructor & Destructor Documentation

RN_NET()

RN_NET::RN_NET

(

)

Definition at line 271 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 361 of file ratsnest_data.cpp.

{
    CN_ANCHOR_PTR firstAnchor;

    for( auto item : *aCluster )
    {
        bool isZone = dynamic_cast<CN_ZONE_LAYER*>(item) != nullptr;
        auto& anchors = item->Anchors();
        unsigned int nAnchors = isZone ? 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.

Clear()

void RN_NET::Clear

(

)

Definition at line 351 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 277 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 )
        {
            auto last = ++m_nodes.begin();

            // There can be only one possible connection, but it is missing
            CN_EDGE edge ( *m_nodes.begin(), *last );
            edge.GetSourceNode()->SetTag( 0 );
            edge.GetTargetNode()->SetTag( 1 );

            m_rnEdges.push_back( edge );
        }
        else
        {
            // Set tags to m_nodes as connected
            for( const auto& node : m_nodes )
                node->SetTag( 0 );
        }

        return;
    }


    m_triangulator->Clear();

    for( const auto& n : m_nodes )
    {
        m_triangulator->AddNode( n );
    }

    std::vector<CN_EDGE> triangEdges;
    triangEdges.reserve( m_nodes.size() + m_boardEdges.size() );

    #ifdef PROFILE
    PROF_COUNTER cnt("triangulate");
    #endif
    m_triangulator->Triangulate( triangEdges );
    #ifdef PROFILE
    cnt.Show();
    #endif

    for( const auto& e : m_boardEdges )
        triangEdges.emplace_back( e );

    std::sort( triangEdges.begin(), triangEdges.end() );

// Get the minimal spanning tree
#ifdef PROFILE
    PROF_COUNTER cnt2("mst");
#endif
    kruskalMST( triangEdges );
#ifdef PROFILE
    cnt2.Show();
#endif
}

References CN_EDGE::GetSourceNode(), kruskalMST(), m_boardEdges, m_nodes, m_rnEdges, m_triangulator, and PROF_COUNTER::Show().

Referenced by Update().

GetAllItems()

void RN_NET::GetAllItems	(	std::list< BOARD_CONNECTED_ITEM * > &	aOutput,
		const KICAD_T	aTypes[]
	)		const

Add all stored items to a list.

Parameters

aOutput	is the list that will have items added.
aTypes	determines the type of added items.

GetClosestNode()

const CN_ANCHOR_PTR RN_NET::GetClosestNode

(

const CN_ANCHOR_PTR &

aNode

)

const

Return a single node that lies in the shortest distance from a specific node.

Parameters

aNode

is the node for which the closest node is searched.

GetEdges()

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

inline

Definition at line 124 of file ratsnest_data.h.

    {
        return m_rnEdges;
    }

References m_rnEdges.

GetNodeCount()

unsigned int RN_NET::GetNodeCount ( ) const

inline

Definition at line 111 of file ratsnest_data.h.

    {
        return m_nodes.size();
    }

References m_nodes.

GetNodes()

std::list<CN_ANCHOR_PTR> RN_NET::GetNodes

(

const BOARD_CONNECTED_ITEM *

aItem

)

const

Return list of nodes that are associated with a given item.

Parameters

aItem

is an item for which the list is generated.

Returns

List of associated nodes.

GetUnconnected()

const std::vector<CN_EDGE> RN_NET::GetUnconnected ( ) const

inline

Return pointer to a vector of edges that makes ratsnest for a given net.

Returns

Pointer to a vector of edges that makes ratsnest for a given net.

Definition at line 98 of file ratsnest_data.h.

    {
        return m_rnEdges;
    }

References m_rnEdges.

Referenced by RATSNEST_VIEW_ITEM::ViewDraw().

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 88 of file ratsnest_data.h.

    {
        return m_dirty;
    }

References m_dirty.

kruskalMST()

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

protected

Vector of nodes.

Definition at line 109 of file ratsnest_data.cpp.

{
    disjoint_set dset( m_nodes.size() );

    m_rnEdges.clear();

    int i = 0;

    for( auto& node : m_nodes )
        node->SetTag( i++ );

    for( auto& tmp : aEdges )
    {
        int u = tmp.GetSourceNode()->GetTag();
        int v = tmp.GetTargetNode()->GetTag();

        if( dset.unite( u, v ) )
        {
            if( tmp.GetWeight() > 0 )
                m_rnEdges.push_back( tmp );
        }
    }
}

Referenced by compute().

MarkDirty()

void RN_NET::MarkDirty ( )

inline

Mark ratsnest for given net as 'dirty', i.e.

requiring recomputation.

Definition at line 77 of file ratsnest_data.h.

    {
        m_dirty = true;
    }

References m_dirty.

NearestBicoloredPair()

bool RN_NET::NearestBicoloredPair	(	const RN_NET &	aOtherNet,
		CN_ANCHOR_PTR &	aNode1,
		CN_ANCHOR_PTR &	aNode2
	)		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 395 of file ratsnest_data.cpp.

{
    bool rv = false;

    VECTOR2I::extended_type distMax = VECTOR2I::ECOORD_MAX;

    auto verify = [&]( auto& aTestNode1, auto& aTestNode2 )
        {
            auto squaredDist = ( aTestNode1->Pos() - aTestNode2->Pos() ).SquaredEuclideanNorm();

            if( squaredDist < distMax )
            {
                rv      = true;
                distMax = squaredDist;
                aNode1  = aTestNode1;
                aNode2  = aTestNode2;
            }
        };

    for( const auto& nodeA : aOtherNet.m_nodes )
    {
        if( nodeA->GetNoLine() )
            continue;

        auto fwd_it = m_nodes.lower_bound( nodeA );
        auto rev_it = std::make_reverse_iterator( fwd_it );

        for( ; fwd_it != m_nodes.end(); ++fwd_it )
        {
            const std::shared_ptr<CN_ANCHOR>& nodeB = *fwd_it;

            if( nodeB->GetNoLine() )
                continue;

            VECTOR2I::extended_type distX = nodeA->Pos().x - nodeB->Pos().x;

            if( distX * distX > distMax )
                break;

            verify( nodeA, nodeB );
        }

        for( ; rev_it != m_nodes.rend(); ++rev_it )
        {
            const std::shared_ptr<CN_ANCHOR>& nodeB = *rev_it;

            if( nodeB->GetNoLine() )
                continue;

            VECTOR2I::extended_type distX = nodeA->Pos().x - nodeB->Pos().x;

            if( distX * distX > distMax )
                break;

            verify( nodeA, nodeB );
        }
    }

    return rv;
}

References VECTOR2< T >::ECOORD_MAX, and m_nodes.

SetVisible()

void RN_NET::SetVisible

(

bool

aEnabled

)

Set state of the visibility flag.

Parameters

aEnabled

is new state. True if ratsnest for a given net is meant to be displayed, false otherwise.

Definition at line 467 of file ratsnest_data.cpp.

{
    for( auto& edge : m_rnEdges )
        edge.SetVisible( aEnabled );
}

References m_rnEdges.

Update()

void RN_NET::Update

(

)

Recompute ratsnest for a net.

Definition at line 343 of file ratsnest_data.cpp.

{
    compute();

    m_dirty = false;
}

References compute(), and m_dirty.

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 158 of file ratsnest_data.h.

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

m_dirty

bool RN_NET::m_dirty

protected

Definition at line 164 of file ratsnest_data.h.

Referenced by Clear(), IsDirty(), MarkDirty(), and Update().

m_nodes

std::multiset<CN_ANCHOR_PTR, CN_PTR_CMP> RN_NET::m_nodes

protected

Vector of edges that make pre-defined connections.

Definition at line 155 of file ratsnest_data.h.

Referenced by AddCluster(), Clear(), compute(), GetNodeCount(), 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 161 of file ratsnest_data.h.

Referenced by Clear(), compute(), GetEdges(), GetUnconnected(), and SetVisible().

m_triangulator

std::shared_ptr<TRIANGULATOR_STATE> RN_NET::m_triangulator

protected

Definition at line 166 of file ratsnest_data.h.

Referenced by compute(), and RN_NET().

---

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

• ratsnest_data.h
• ratsnest_data.cpp