ratsnest_data.cpp 28.3 KB
Newer Older
Maciej Suminski's avatar
Maciej Suminski committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
/*
 * This program source code file is part of KICAD, a free EDA CAD application.
 *
 * Copyright (C) 2013 CERN
 * @author Maciej Suminski <maciej.suminski@cern.ch>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, you may find one here:
 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
 * or you may search the http://www.gnu.org website for the version 2 license,
 * or you may write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 */

/**
 * @file ratsnest_data.cpp
 * @brief Class that computes missing connections on a PCB.
 */

30 31 32 33
#ifdef USE_OPENMP
#include <omp.h>
#endif /* USE_OPENMP */

Maciej Suminski's avatar
Maciej Suminski committed
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
#include <ratsnest_data.h>

#include <class_board.h>
#include <class_module.h>
#include <class_pad.h>
#include <class_track.h>
#include <class_zone.h>

#include <boost/range/adaptor/map.hpp>
#include <boost/scoped_ptr.hpp>
#include <boost/make_shared.hpp>
#include <boost/bind.hpp>

#include <cassert>
#include <algorithm>
#include <limits>

uint64_t getDistance( const RN_NODE_PTR& aNode1, const RN_NODE_PTR& aNode2 )
{
    // Drop the least significant bits to avoid overflow
    int64_t x = ( aNode1->GetX() - aNode2->GetX() ) >> 16;
    int64_t y = ( aNode1->GetY() - aNode2->GetY() ) >> 16;

    // We do not need sqrt() here, as the distance is computed only for comparison
    return ( x * x + y * y );
}


bool sortDistance( const RN_NODE_PTR& aOrigin, const RN_NODE_PTR& aNode1,
                   const RN_NODE_PTR& aNode2 )
{
    return getDistance( aOrigin, aNode1 ) < getDistance( aOrigin, aNode2 );
}


bool sortWeight( const RN_EDGE_PTR& aEdge1, const RN_EDGE_PTR& aEdge2 )
{
71
    return aEdge1->GetWeight() < aEdge2->GetWeight();
Maciej Suminski's avatar
Maciej Suminski committed
72 73 74 75 76 77 78 79 80
}


bool sortArea( const RN_POLY& aP1, const RN_POLY& aP2 )
{
    return aP1.m_bbox.GetArea() < aP2.m_bbox.GetArea();
}


81 82 83 84 85 86 87 88 89 90 91 92
bool operator==( const RN_NODE_PTR& aFirst, const RN_NODE_PTR& aSecond )
{
    return aFirst->GetX() == aSecond->GetX() && aFirst->GetY() == aSecond->GetY();
}


bool operator!=( const RN_NODE_PTR& aFirst, const RN_NODE_PTR& aSecond )
{
    return aFirst->GetX() != aSecond->GetX() || aFirst->GetY() != aSecond->GetY();
}


Maciej Suminski's avatar
Maciej Suminski committed
93 94
bool isEdgeConnectingNode( const RN_EDGE_PTR& aEdge, const RN_NODE_PTR& aNode )
{
95
    return aEdge->GetSourceNode() == aNode || aEdge->GetTargetNode() == aNode;
Maciej Suminski's avatar
Maciej Suminski committed
96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
}


std::vector<RN_EDGE_PTR>* kruskalMST( RN_LINKS::RN_EDGE_LIST& aEdges,
                                      const std::vector<RN_NODE_PTR>& aNodes )
{
    unsigned int nodeNumber = aNodes.size();
    unsigned int mstExpectedSize = nodeNumber - 1;
    unsigned int mstSize = 0;

    // The output
    std::vector<RN_EDGE_PTR>* mst = new std::vector<RN_EDGE_PTR>;
    mst->reserve( mstExpectedSize );

    // Set tags for marking cycles
    boost::unordered_map<RN_NODE_PTR, int> tags;
    unsigned int tag = 0;
    BOOST_FOREACH( const RN_NODE_PTR& node, aNodes )
        tags[node] = tag++;

    // Lists of nodes connected together (subtrees) to detect cycles in the graph
    std::vector<std::list<int> > cycles( nodeNumber );
    for( unsigned int i = 0; i < nodeNumber; ++i )
        cycles[i].push_back( i );

    // Kruskal algorithm requires edges to be sorted by their weight
    aEdges.sort( sortWeight );

    while( mstSize < mstExpectedSize && !aEdges.empty() )
    {
        RN_EDGE_PTR& dt = *aEdges.begin();

128 129
        int srcTag = tags[dt->GetSourceNode()];
        int trgTag = tags[dt->GetTargetNode()];
Maciej Suminski's avatar
Maciej Suminski committed
130 131 132 133 134 135 136 137 138 139 140 141

        // Check if by adding this edge we are going to join two different forests
        if( srcTag != trgTag )
        {
            // Update tags
            std::list<int>::iterator it, itEnd;
            for( it = cycles[trgTag].begin(), itEnd = cycles[trgTag].end(); it != itEnd; ++it )
                tags[aNodes[*it]] = srcTag;

            // Move nodes that were marked with old tag to the list marked with the new tag
            cycles[srcTag].splice( cycles[srcTag].end(), cycles[trgTag] );

142
            if( dt->GetWeight() == 0 )      // Skip already existing connections (weight == 0)
Maciej Suminski's avatar
Maciej Suminski committed
143
            {
Maciej Suminski's avatar
Maciej Suminski committed
144
                mstExpectedSize--;
Maciej Suminski's avatar
Maciej Suminski committed
145
            }
Maciej Suminski's avatar
Maciej Suminski committed
146 147
            else
            {
Maciej Suminski's avatar
Maciej Suminski committed
148 149 150
                // Do a copy of edge, but make it RN_EDGE_MST. In contrary to RN_EDGE,
                // RN_EDGE_MST saves both source and target node and does not require any other
                // edges to exist for getting source/target nodes
151 152 153
                RN_EDGE_MST_PTR newEdge = boost::make_shared<RN_EDGE_MST>( dt->GetSourceNode(),
                                                                           dt->GetTargetNode(),
                                                                           dt->GetWeight() );
Maciej Suminski's avatar
Maciej Suminski committed
154
                mst->push_back( newEdge );
Maciej Suminski's avatar
Maciej Suminski committed
155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171
                ++mstSize;
            }
        }

        // Remove the edge that was just processed
        aEdges.erase( aEdges.begin() );
    }

    // Probably we have discarded some of edges, so reduce the size
    mst->resize( mstSize );

    return mst;
}


void RN_NET::validateEdge( RN_EDGE_PTR& aEdge )
{
172 173
    RN_NODE_PTR source = aEdge->GetSourceNode();
    RN_NODE_PTR target = aEdge->GetTargetNode();
Maciej Suminski's avatar
Maciej Suminski committed
174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225
    bool valid = true;

    // If any of nodes belonging to the edge has the flag set,
    // change it to the closest node that has flag cleared
    if( source->GetFlag() )
    {
        valid = false;

        std::list<RN_NODE_PTR> closest = GetClosestNodes( source, WITHOUT_FLAG() );
        BOOST_FOREACH( RN_NODE_PTR& node, closest )
        {
            if( node && node != target )
            {
                source = node;
                break;
            }
        }
    }

    if( target->GetFlag() )
    {
        valid = false;

        std::list<RN_NODE_PTR> closest = GetClosestNodes( target, WITHOUT_FLAG() );
        BOOST_FOREACH( RN_NODE_PTR& node, closest )
        {
            if( node && node != source )
            {
                target = node;
                break;
            }
        }
    }

    // Replace an invalid edge with new, valid one
    if( !valid )
        aEdge.reset( new RN_EDGE_MST( source, target ) );
}


const RN_NODE_PTR& RN_LINKS::AddNode( int aX, int aY )
{
    RN_NODE_SET::iterator node;
    bool wasNewElement;

    boost::tie( node, wasNewElement ) = m_nodes.emplace( boost::make_shared<RN_NODE>( aX, aY ) );
    (*node)->IncRefCount(); // TODO use the shared_ptr use_count

    return *node;
}


226
bool RN_LINKS::RemoveNode( const RN_NODE_PTR& aNode )
Maciej Suminski's avatar
Maciej Suminski committed
227 228 229 230
{
    aNode->DecRefCount(); // TODO use the shared_ptr use_count

    if( aNode->GetRefCount() == 0 )
231
    {
Maciej Suminski's avatar
Maciej Suminski committed
232
        m_nodes.erase( aNode );
233 234 235 236 237

        return true;
    }

    return false;
Maciej Suminski's avatar
Maciej Suminski committed
238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270
}


const RN_EDGE_PTR& RN_LINKS::AddConnection( const RN_NODE_PTR& aNode1, const RN_NODE_PTR& aNode2,
                                            unsigned int aDistance )
{
    m_edges.push_back( boost::make_shared<RN_EDGE_MST>( aNode1, aNode2, aDistance ) );

    return m_edges.back();
}


void RN_NET::compute()
{
    const RN_LINKS::RN_NODE_SET& boardNodes = m_links.GetNodes();
    const RN_LINKS::RN_EDGE_LIST& boardEdges = m_links.GetConnections();

    // Special case that does need so complicated algorithm
    if( boardNodes.size() == 2 )
    {
        m_rnEdges.reset( new std::vector<RN_EDGE_PTR>( 0 ) );

        // Check if the only possible connection exists
        if( boardEdges.size() == 0 )
        {
            RN_LINKS::RN_NODE_SET::iterator last = ++boardNodes.begin();

            // There can be only one possible connection, but it is missing
            m_rnEdges->push_back( boost::make_shared<RN_EDGE_MST>( *boardNodes.begin(), *last ) );
        }

        return;
    }
271
    else if( boardNodes.size() <= 1 )   // This case is even simpler
Maciej Suminski's avatar
Maciej Suminski committed
272 273 274 275 276 277 278 279 280 281 282
    {
        m_rnEdges.reset( new std::vector<RN_EDGE_PTR>( 0 ) );

        return;
    }

    // Move and sort (sorting speeds up) all nodes to a vector for the Delaunay triangulation
    std::vector<RN_NODE_PTR> nodes( boardNodes.size() );
    std::partial_sort_copy( boardNodes.begin(), boardNodes.end(), nodes.begin(), nodes.end() );

    TRIANGULATOR triangulator;
283 284
    triangulator.CreateDelaunay( nodes.begin(), nodes.end() );
    boost::scoped_ptr<RN_LINKS::RN_EDGE_LIST> triangEdges( triangulator.GetEdges() );
Maciej Suminski's avatar
Maciej Suminski committed
285 286 287 288

    // Compute weight/distance for edges resulting from triangulation
    RN_LINKS::RN_EDGE_LIST::iterator eit, eitEnd;
    for( eit = (*triangEdges).begin(), eitEnd = (*triangEdges).end(); eit != eitEnd; ++eit )
289
        (*eit)->SetWeight( getDistance( (*eit)->GetSourceNode(), (*eit)->GetTargetNode() ) );
Maciej Suminski's avatar
Maciej Suminski committed
290 291 292 293 294 295 296 297 298 299 300

    // Add the currently existing connections list to the results of triangulation
    std::copy( boardEdges.begin(), boardEdges.end(), std::front_inserter( *triangEdges ) );

    // Get the minimal spanning tree
    m_rnEdges.reset( kruskalMST( *triangEdges, nodes ) );
}


void RN_NET::clearNode( const RN_NODE_PTR& aNode )
{
301 302 303
    if( !m_rnEdges )
        return;

Maciej Suminski's avatar
Maciej Suminski committed
304 305 306 307
    std::vector<RN_EDGE_PTR>::iterator newEnd;

    // Remove all ratsnest edges for associated with the node
    newEnd = std::remove_if( m_rnEdges->begin(), m_rnEdges->end(),
308
                             boost::bind( isEdgeConnectingNode, _1, boost::ref( aNode ) ) );
Maciej Suminski's avatar
Maciej Suminski committed
309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358

    m_rnEdges->resize( std::distance( m_rnEdges->begin(), newEnd ) );
}


RN_POLY::RN_POLY( const CPolyPt* aBegin, const CPolyPt* aEnd, const ZONE_CONTAINER* aParent,
            RN_LINKS& aConnections, const BOX2I& aBBox ) :
    m_parent( aParent), m_begin( aBegin ), m_end( aEnd ), m_bbox( aBBox )
{
    m_node = aConnections.AddNode( m_begin->x, m_begin->y );

    // Mark it as not feasible as a destination of ratsnest edges
    // (edges coming out from a polygon vertex look weird)
    m_node->SetFlag( true );
}


bool RN_POLY::HitTest( const RN_NODE_PTR& aNode ) const
{
    long xt = aNode->GetX();
    long yt = aNode->GetY();

    // If the point lies outside the bounding box, there is no point to check it further
    if( !m_bbox.Contains( xt, yt ) )
        return false;

    long xNew, yNew, xOld, yOld, x1, y1, x2, y2;
    bool inside = false;

    // For the first loop we have to use the last point as the previous point
    xOld = m_end->x;
    yOld = m_end->y;

    for( const CPolyPt* point = m_begin; point <= m_end; ++point )
    {
        xNew = point->x;
        yNew = point->y;

        // Swap points if needed, so always x2 >= x1
        if( xNew > xOld )
        {
            x1 = xOld; y1 = yOld;
            x2 = xNew; y2 = yNew;
        }
        else
        {
            x1 = xNew; y1 = yNew;
            x2 = xOld; y2 = yOld;
        }

359
        if( ( xNew < xt ) == ( xt <= xOld ) && /* edge "open" at left end */
360
          (double)( yt - y1 ) * (double)( x2 - x1 ) < (double)( y2 - y1 ) * (double)( xt - x1 ) )
Maciej Suminski's avatar
Maciej Suminski committed
361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395
        {
            inside = !inside;
        }

        xOld = xNew;
        yOld = yNew;
    }

    return inside;
}


void RN_NET::Update()
{
    // Add edges resulting from nodes being connected by zones
    processZones();

    compute();

    BOOST_FOREACH( RN_EDGE_PTR& edge, *m_rnEdges )
        validateEdge( edge );

    m_dirty = false;
}


void RN_NET::AddItem( const D_PAD* aPad )
{
    RN_NODE_PTR nodePtr = m_links.AddNode( aPad->GetPosition().x, aPad->GetPosition().y );
    m_pads[aPad] = nodePtr;

    m_dirty = true;
}


396
void RN_NET::AddItem( const VIA* aVia )
Maciej Suminski's avatar
Maciej Suminski committed
397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424
{
    m_vias[aVia] = m_links.AddNode( aVia->GetPosition().x, aVia->GetPosition().y );

    m_dirty = true;
}


void RN_NET::AddItem( const TRACK* aTrack )
{
    RN_NODE_PTR start = m_links.AddNode( aTrack->GetStart().x, aTrack->GetStart().y );
    RN_NODE_PTR end = m_links.AddNode( aTrack->GetEnd().x, aTrack->GetEnd().y );

    m_tracks[aTrack] = m_links.AddConnection( start, end );

    m_dirty = true;
}


void RN_NET::AddItem( const ZONE_CONTAINER* aZone )
{
    // Prepare a list of polygons (every zone can contain one or more polygons)
    const std::vector<CPolyPt>& polyPoints = aZone->GetFilledPolysList().GetList();
    if( polyPoints.size() == 0 )
        return;

    // Origin and end of bounding box for a polygon
    VECTOR2I origin( polyPoints[0].x, polyPoints[0].y );
    VECTOR2I end( polyPoints[0].x, polyPoints[0].y );
Maciej Suminski's avatar
Maciej Suminski committed
425
    unsigned int idxStart = 0;
Maciej Suminski's avatar
Maciej Suminski committed
426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450

    // Extract polygons from zones
    for( unsigned int i = 0; i < polyPoints.size(); ++i )
    {
        const CPolyPt& point = polyPoints[i];

        // Determine bounding box
        if( point.x < origin.x )
            origin.x = point.x;
        else if( point.x > end.x )
            end.x = point.x;

        if( point.y < origin.y )
            origin.y = point.y;
        else if( point.y > end.y )
            end.y = point.y;

        if( point.end_contour )
        {
            // The last vertex is enclosing the polygon (it repeats at the beginning and
            // at the end), so we skip it
            m_zonePolygons[aZone].push_back( RN_POLY( &polyPoints[idxStart], &point, aZone,
                                             m_links, BOX2I( origin, end - origin ) ) );

            idxStart = i + 1;
Maciej Suminski's avatar
Maciej Suminski committed
451 452 453 454 455 456 457 458

            if( idxStart < polyPoints.size() )
            {
                origin.x = polyPoints[idxStart].x;
                origin.y = polyPoints[idxStart].y;
                end.x = polyPoints[idxStart].x;
                end.y = polyPoints[idxStart].y;
            }
Maciej Suminski's avatar
Maciej Suminski committed
459 460 461 462 463 464 465 466 467
        }
    }

    m_dirty = true;
}


void RN_NET::RemoveItem( const D_PAD* aPad )
{
468 469 470
    try
    {
        RN_NODE_PTR node = m_pads.at( aPad );
Maciej Suminski's avatar
Maciej Suminski committed
471

472 473
        if( m_links.RemoveNode( node ) )
            clearNode( node );
Maciej Suminski's avatar
Maciej Suminski committed
474

475
        m_pads.erase( aPad );
Maciej Suminski's avatar
Maciej Suminski committed
476

477 478 479 480 481
        m_dirty = true;
    }
    catch( ... )
    {
    }
Maciej Suminski's avatar
Maciej Suminski committed
482 483 484
}


485
void RN_NET::RemoveItem( const VIA* aVia )
Maciej Suminski's avatar
Maciej Suminski committed
486
{
487 488 489
    try
    {
        RN_NODE_PTR node = m_vias.at( aVia );
Maciej Suminski's avatar
Maciej Suminski committed
490

491 492
        if( m_links.RemoveNode( node ) )
            clearNode( node );
Maciej Suminski's avatar
Maciej Suminski committed
493

494
        m_vias.erase( aVia );
Maciej Suminski's avatar
Maciej Suminski committed
495

496 497 498 499 500
        m_dirty = true;
    }
    catch( ... )
    {
    }
Maciej Suminski's avatar
Maciej Suminski committed
501 502 503 504 505
}


void RN_NET::RemoveItem( const TRACK* aTrack )
{
506 507 508
    try
    {
        RN_EDGE_PTR& edge = m_tracks.at( aTrack );
Maciej Suminski's avatar
Maciej Suminski committed
509

510
        // Save nodes, so they can be cleared later
511 512
        RN_NODE_PTR aBegin = edge->GetSourceNode();
        RN_NODE_PTR aEnd = edge->GetTargetNode();
513
        m_links.RemoveConnection( edge );
Maciej Suminski's avatar
Maciej Suminski committed
514

515 516 517 518
        // Remove nodes associated with the edge. It is done in a safe way, there is a check
        // if nodes are not used by other edges.
        if( m_links.RemoveNode( aBegin ) )
            clearNode( aBegin );
Maciej Suminski's avatar
Maciej Suminski committed
519

520 521
        if( m_links.RemoveNode( aEnd ) )
            clearNode( aEnd );
Maciej Suminski's avatar
Maciej Suminski committed
522

523 524 525 526 527 528 529
        m_tracks.erase( aTrack );

        m_dirty = true;
    }
    catch( ... )
    {
    }
Maciej Suminski's avatar
Maciej Suminski committed
530 531 532 533 534
}


void RN_NET::RemoveItem( const ZONE_CONTAINER* aZone )
{
535 536 537 538 539
    try
    {
        // Remove all subpolygons that make the zone
        std::deque<RN_POLY>& polygons = m_zonePolygons.at( aZone );
        BOOST_FOREACH( RN_POLY& polygon, polygons )
540 541 542 543 544 545
        {
            const RN_NODE_PTR node = polygon.GetNode();

            if( m_links.RemoveNode( node ) )
                clearNode( node );
        }
546 547 548 549 550 551 552
        polygons.clear();

        // Remove all connections added by the zone
        std::deque<RN_EDGE_PTR>& edges = m_zoneConnections.at( aZone );
        BOOST_FOREACH( RN_EDGE_PTR& edge, edges )
            m_links.RemoveConnection( edge );
        edges.clear();
Maciej Suminski's avatar
Maciej Suminski committed
553

554 555 556 557 558
        m_dirty = true;
    }
    catch( ... )
    {
    }
Maciej Suminski's avatar
Maciej Suminski committed
559 560 561 562 563 564 565 566 567 568 569 570 571
}


const RN_NODE_PTR RN_NET::GetClosestNode( const RN_NODE_PTR& aNode ) const
{
    const RN_LINKS::RN_NODE_SET& nodes = m_links.GetNodes();
    RN_LINKS::RN_NODE_SET::const_iterator it, itEnd;

    unsigned int minDistance = std::numeric_limits<unsigned int>::max();
    RN_NODE_PTR closest;

    for( it = nodes.begin(), itEnd = nodes.end(); it != itEnd; ++it )
    {
572 573
        RN_NODE_PTR node = *it;

Maciej Suminski's avatar
Maciej Suminski committed
574 575
        // Obviously the distance between node and itself is the shortest,
        // that's why we have to skip it
576
        if( node != aNode )
Maciej Suminski's avatar
Maciej Suminski committed
577
        {
578
            unsigned int distance = getDistance( node, aNode );
Maciej Suminski's avatar
Maciej Suminski committed
579 580 581
            if( distance < minDistance )
            {
                minDistance = distance;
582
                closest = node;
Maciej Suminski's avatar
Maciej Suminski committed
583 584 585 586 587 588 589 590
            }
        }
    }

    return closest;
}


591 592
const RN_NODE_PTR RN_NET::GetClosestNode( const RN_NODE_PTR& aNode,
                                          const RN_NODE_FILTER& aFilter ) const
Maciej Suminski's avatar
Maciej Suminski committed
593 594 595 596 597 598 599 600 601
{
    const RN_LINKS::RN_NODE_SET& nodes = m_links.GetNodes();
    RN_LINKS::RN_NODE_SET::const_iterator it, itEnd;

    unsigned int minDistance = std::numeric_limits<unsigned int>::max();
    RN_NODE_PTR closest;

    for( it = nodes.begin(), itEnd = nodes.end(); it != itEnd; ++it )
    {
602
        RN_NODE_PTR node = *it;
Maciej Suminski's avatar
Maciej Suminski committed
603 604 605

        // Obviously the distance between node and itself is the shortest,
        // that's why we have to skip it
606
        if( node != aNode && aFilter( node ) )
Maciej Suminski's avatar
Maciej Suminski committed
607
        {
608 609
            unsigned int distance = getDistance( node, aNode );

Maciej Suminski's avatar
Maciej Suminski committed
610 611 612
            if( distance < minDistance )
            {
                minDistance = distance;
613
                closest = node;
Maciej Suminski's avatar
Maciej Suminski committed
614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631
            }
        }
    }

    return closest;
}


std::list<RN_NODE_PTR> RN_NET::GetClosestNodes( const RN_NODE_PTR& aNode, int aNumber ) const
{
    std::list<RN_NODE_PTR> closest;
    const RN_LINKS::RN_NODE_SET& nodes = m_links.GetNodes();

    // Copy nodes
    BOOST_FOREACH( const RN_NODE_PTR& node, nodes )
        closest.push_back( node );

    // Sort by the distance from aNode
632
    closest.sort( boost::bind( sortDistance, boost::ref( aNode ), _1, _2 ) );
Maciej Suminski's avatar
Maciej Suminski committed
633 634 635 636 637 638 639 640 641 642 643 644 645

    // Remove the first node (==aNode), as it is surely located within the smallest distance
    closest.pop_front();

    // Trim the result to the asked size
    if( aNumber > 0 )
        closest.resize( std::min( (size_t)aNumber, nodes.size() ) );

    return closest;
}


std::list<RN_NODE_PTR> RN_NET::GetClosestNodes( const RN_NODE_PTR& aNode,
646
                                                const RN_NODE_FILTER& aFilter, int aNumber ) const
Maciej Suminski's avatar
Maciej Suminski committed
647 648 649 650 651 652 653 654 655
{
    std::list<RN_NODE_PTR> closest;
    const RN_LINKS::RN_NODE_SET& nodes = m_links.GetNodes();

    // Copy nodes
    BOOST_FOREACH( const RN_NODE_PTR& node, nodes )
        closest.push_back( node );

    // Sort by the distance from aNode
656
    closest.sort( boost::bind( sortDistance, boost::ref( aNode ), _1, _2 ) );
Maciej Suminski's avatar
Maciej Suminski committed
657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675

    // Remove the first node (==aNode), as it is surely located within the smallest distance
    closest.pop_front();

    // Filter out by condition
    std::remove_if( closest.begin(), closest.end(), aFilter );

    // Trim the result to the asked size
    if( aNumber > 0 )
        closest.resize( std::min( static_cast<size_t>( aNumber ), nodes.size() ) );

    return closest;
}


std::list<RN_NODE_PTR> RN_NET::GetNodes( const BOARD_CONNECTED_ITEM* aItem ) const
{
    std::list<RN_NODE_PTR> nodes;

676
    try
Maciej Suminski's avatar
Maciej Suminski committed
677
    {
678 679 680 681 682 683 684 685
        switch( aItem->Type() )
        {
        case PCB_PAD_T:
        {
            const D_PAD* pad = static_cast<const D_PAD*>( aItem );
            nodes.push_back( m_pads.at( pad ) );
        }
        break;
Maciej Suminski's avatar
Maciej Suminski committed
686

687 688
        case PCB_VIA_T:
        {
689
            const VIA* via = static_cast<const VIA*>( aItem );
690 691 692
            nodes.push_back( m_vias.at( via ) );
        }
        break;
Maciej Suminski's avatar
Maciej Suminski committed
693

694 695 696 697
        case PCB_TRACE_T:
        {
            const TRACK* track = static_cast<const TRACK*>( aItem );
            RN_EDGE_PTR edge = m_tracks.at( track );
Maciej Suminski's avatar
Maciej Suminski committed
698

699 700
            nodes.push_back( edge->GetSourceNode() );
            nodes.push_back( edge->GetTargetNode() );
701
        }
Maciej Suminski's avatar
Maciej Suminski committed
702
        break;
703 704 705 706 707 708 709 710

        default:
            break;
        }
    }
    catch ( ... )
    {
        return nodes;
Maciej Suminski's avatar
Maciej Suminski committed
711 712 713 714 715 716
    }

    return nodes;
}


717
void RN_DATA::AddSimple( const BOARD_ITEM* aItem )
Maciej Suminski's avatar
Maciej Suminski committed
718
{
719
    int net;
Maciej Suminski's avatar
Maciej Suminski committed
720

721 722 723
    if( aItem->IsConnected() )
    {
        const BOARD_CONNECTED_ITEM* item = static_cast<const BOARD_CONNECTED_ITEM*>( aItem );
724
        net = item->GetNetCode();
Maciej Suminski's avatar
Maciej Suminski committed
725

726 727
        if( net < 1 )           // do not process unconnected items
            return;
Maciej Suminski's avatar
Maciej Suminski committed
728

729 730 731
        // Add all nodes belonging to the item
        BOOST_FOREACH( RN_NODE_PTR node, m_nets[net].GetNodes( item ) )
            m_nets[net].AddSimpleNode( node );
732 733 734 735
    }
    else if( aItem->Type() == PCB_MODULE_T )
    {
        const MODULE* module = static_cast<const MODULE*>( aItem );
Maciej Suminski's avatar
Maciej Suminski committed
736

737 738 739 740 741 742 743
        for( const D_PAD* pad = module->Pads().GetFirst(); pad; pad = pad->Next() )
            AddSimple( pad );

        return;
    }
    else
        return;
Maciej Suminski's avatar
Maciej Suminski committed
744 745 746
}


747 748 749 750 751 752 753
void RN_DATA::AddBlocked( const BOARD_ITEM* aItem )
{
    int net;

    if( aItem->IsConnected() )
    {
        const BOARD_CONNECTED_ITEM* item = static_cast<const BOARD_CONNECTED_ITEM*>( aItem );
754
        net = item->GetNetCode();
755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786

        if( net < 1 )           // do not process unconnected items
            return;

        // Block all nodes belonging to the item
        BOOST_FOREACH( RN_NODE_PTR node, m_nets[net].GetNodes( item ) )
            m_nets[net].AddBlockedNode( node );
    }
    else if( aItem->Type() == PCB_MODULE_T )
    {
        const MODULE* module = static_cast<const MODULE*>( aItem );

        for( const D_PAD* pad = module->Pads().GetFirst(); pad; pad = pad->Next() )
            AddBlocked( pad );

        return;
    }
    else
        return;
}


void RN_DATA::AddSimple( const VECTOR2I& aPosition, int aNetCode )
{
    assert( aNetCode > 0 );

    RN_NODE_PTR newNode = boost::make_shared<RN_NODE>( aPosition.x, aPosition.y );

    m_nets[aNetCode].AddSimpleNode( newNode );
}


Maciej Suminski's avatar
Maciej Suminski committed
787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833
void RN_NET::processZones()
{
    BOOST_FOREACH( std::deque<RN_EDGE_PTR>& edges, m_zoneConnections | boost::adaptors::map_values )
    {
        BOOST_FOREACH( RN_EDGE_PTR& edge, edges )
            m_links.RemoveConnection( edge );

        edges.clear();
    }

    RN_LINKS::RN_NODE_SET candidates = m_links.GetNodes();

    BOOST_FOREACH( std::deque<RN_POLY>& polygons, m_zonePolygons | boost::adaptors::map_values )
    {
        RN_LINKS::RN_NODE_SET::iterator point, pointEnd;
        std::deque<RN_POLY>::iterator poly, polyEnd;

        // Sorting by area should speed up the processing, as smaller polygons are computed
        // faster and may reduce the number of points for further checks
        std::sort( polygons.begin(), polygons.end(), sortArea );

        for( poly = polygons.begin(), polyEnd = polygons.end(); poly != polyEnd; ++poly )
        {
            point = candidates.begin();
            pointEnd = candidates.end();

            while( point != pointEnd )
            {
                if( poly->HitTest( *point ) )
                {
                    const RN_EDGE_PTR& connection = m_links.AddConnection( poly->GetNode(), *point );
                    m_zoneConnections[poly->GetParent()].push_back( connection );

                    // This point already belongs to a polygon, we do not need to check it anymore
                    point = candidates.erase( point );
                    pointEnd = candidates.end();
                }
                else
                {
                    ++point;
                }
            }
        }
    }
}


834
void RN_DATA::Add( const BOARD_ITEM* aItem )
Maciej Suminski's avatar
Maciej Suminski committed
835
{
836 837 838 839
    int net;

    if( aItem->IsConnected() )
    {
840
        net = static_cast<const BOARD_CONNECTED_ITEM*>( aItem )->GetNetCode();
841 842
        if( net < 1 )           // do not process unconnected items
            return;
843

844
        if( net >= (int) m_nets.size() )            // Autoresize
845
            m_nets.resize( net + 1 );
846 847 848 849 850 851
    }
    else if( aItem->Type() == PCB_MODULE_T )
    {
        const MODULE* module = static_cast<const MODULE*>( aItem );
        for( const D_PAD* pad = module->Pads().GetFirst(); pad; pad = pad->Next() )
        {
852
            net = pad->GetNetCode();
853

854 855 856
            if( net < 1 )       // do not process unconnected items
                continue;

857
            if( net >= (int) m_nets.size() )        // Autoresize
858 859
                m_nets.resize( net + 1 );

860 861 862 863 864 865
            m_nets[net].AddItem( pad );
        }

        return;
    }
    else
Maciej Suminski's avatar
Maciej Suminski committed
866 867 868 869 870
        return;

    switch( aItem->Type() )
    {
    case PCB_PAD_T:
871 872
        m_nets[net].AddItem( static_cast<const D_PAD*>( aItem ) );
        break;
Maciej Suminski's avatar
Maciej Suminski committed
873 874

    case PCB_TRACE_T:
875 876
        m_nets[net].AddItem( static_cast<const TRACK*>( aItem ) );
        break;
Maciej Suminski's avatar
Maciej Suminski committed
877 878

    case PCB_VIA_T:
879
        m_nets[net].AddItem( static_cast<const VIA*>( aItem ) );
880
        break;
Maciej Suminski's avatar
Maciej Suminski committed
881 882

    case PCB_ZONE_AREA_T:
883 884
        m_nets[net].AddItem( static_cast<const ZONE_CONTAINER*>( aItem ) );
        break;
Maciej Suminski's avatar
Maciej Suminski committed
885 886 887 888 889 890 891

    default:
        break;
    }
}


892
void RN_DATA::Remove( const BOARD_ITEM* aItem )
Maciej Suminski's avatar
Maciej Suminski committed
893
{
894
    int net;
Maciej Suminski's avatar
Maciej Suminski committed
895

896 897
    if( aItem->IsConnected() )
    {
898
        net = static_cast<const BOARD_CONNECTED_ITEM*>( aItem )->GetNetCode();
899

900 901
        if( net < 1 )           // do not process unconnected items
            return;
902 903 904 905 906 907 908 909 910 911

#ifdef NDEBUG
        if( net >= (int) m_nets.size() )        // Autoresize
        {
            m_nets.resize( net + 1 );

            return;     // if it was resized, then surely the item had not been added before
        }
#endif
        assert( net < (int) m_nets.size() );
912 913 914 915 916
    }
    else if( aItem->Type() == PCB_MODULE_T )
    {
        const MODULE* module = static_cast<const MODULE*>( aItem );
        for( const D_PAD* pad = module->Pads().GetFirst(); pad; pad = pad->Next() )
Maciej Suminski's avatar
Maciej Suminski committed
917
        {
918
            net = pad->GetNetCode();
919

920 921 922
            if( net < 1 )       // do not process unconnected items
                continue;

923 924 925 926 927 928 929 930 931 932
#ifdef NDEBUG
            if( net >= (int) m_nets.size() )    // Autoresize
            {
                m_nets.resize( net + 1 );

                return;     // if it was resized, then surely the item had not been added before
            }
#endif
            assert( net < (int) m_nets.size() );

Maciej Suminski's avatar
Maciej Suminski committed
933 934
            m_nets[net].RemoveItem( pad );
        }
935 936

        return;
Maciej Suminski's avatar
Maciej Suminski committed
937
    }
938 939 940 941 942 943 944 945 946 947 948 949 950 951
    else
        return;

    switch( aItem->Type() )
    {
    case PCB_PAD_T:
        m_nets[net].RemoveItem( static_cast<const D_PAD*>( aItem ) );
        break;

    case PCB_TRACE_T:
        m_nets[net].RemoveItem( static_cast<const TRACK*>( aItem ) );
        break;

    case PCB_VIA_T:
952
        m_nets[net].RemoveItem( static_cast<const VIA*>( aItem ) );
953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968
        break;

    case PCB_ZONE_AREA_T:
        m_nets[net].RemoveItem( static_cast<const ZONE_CONTAINER*>( aItem ) );
        break;

    default:
        break;
    }
}


void RN_DATA::Update( const BOARD_ITEM* aItem )
{
    Remove( aItem );
    Add( aItem );
Maciej Suminski's avatar
Maciej Suminski committed
969 970 971 972 973 974 975
}


void RN_DATA::ProcessBoard()
{
    m_nets.clear();
    m_nets.resize( m_board->GetNetCount() );
976
    int netCode;
Maciej Suminski's avatar
Maciej Suminski committed
977 978 979 980 981

    // Iterate over all items that may need to be connected
    for( MODULE* module = m_board->m_Modules; module; module = module->Next() )
    {
        for( D_PAD* pad = module->Pads().GetFirst(); pad; pad = pad->Next() )
982
        {
Maciej Suminski's avatar
Maciej Suminski committed
983
            netCode = pad->GetNetCode();
984 985 986 987

            if( netCode > 0 )
                m_nets[netCode].AddItem( pad );
        }
Maciej Suminski's avatar
Maciej Suminski committed
988 989 990 991
    }

    for( TRACK* track = m_board->m_Track; track; track = track->Next() )
    {
Maciej Suminski's avatar
Maciej Suminski committed
992
        netCode = track->GetNetCode();
993 994 995 996

        if( netCode > 0 )
        {
            if( track->Type() == PCB_VIA_T )
997
                m_nets[netCode].AddItem( static_cast<VIA*>( track ) );
998 999 1000
            else if( track->Type() == PCB_TRACE_T )
                m_nets[netCode].AddItem( track );
        }
Maciej Suminski's avatar
Maciej Suminski committed
1001 1002 1003 1004 1005
    }

    for( int i = 0; i < m_board->GetAreaCount(); ++i )
    {
        ZONE_CONTAINER* zone = m_board->GetArea( i );
1006

Maciej Suminski's avatar
Maciej Suminski committed
1007
        netCode = zone->GetNetCode();
1008 1009 1010

        if( netCode > 0 )
            m_nets[netCode].AddItem( zone );
Maciej Suminski's avatar
Maciej Suminski committed
1011
    }
1012 1013

    Recalculate();
Maciej Suminski's avatar
Maciej Suminski committed
1014 1015 1016 1017 1018
}


void RN_DATA::Recalculate( int aNet )
{
1019 1020 1021 1022
    unsigned int netCount = m_board->GetNetCount();

    if( netCount > m_nets.size() )
        m_nets.resize( netCount );
1023

Maciej Suminski's avatar
Maciej Suminski committed
1024 1025
    if( aNet < 0 )              // Recompute everything
    {
1026
        unsigned int i;
1027
#ifdef USE_OPENMP
Maciej Suminski's avatar
Maciej Suminski committed
1028
        #pragma omp parallel shared(netCount) private(i)
Maciej Suminski's avatar
Maciej Suminski committed
1029
        {
Maciej Suminski's avatar
Maciej Suminski committed
1030
            #pragma omp for schedule(guided, 1)
1031 1032 1033
#else /* USE_OPENMP */
        {
#endif
Maciej Suminski's avatar
Maciej Suminski committed
1034
            // Start with net number 1, as 0 stands for not connected
1035 1036 1037 1038 1039
            for( i = 1; i < netCount; ++i )
            {
                if( m_nets[i].IsDirty() )
                    updateNet( i );
            }
Maciej Suminski's avatar
Maciej Suminski committed
1040
        }  /* end of parallel section */
Maciej Suminski's avatar
Maciej Suminski committed
1041
    }
1042
    else if( aNet > 0 )         // Recompute only specific net
Maciej Suminski's avatar
Maciej Suminski committed
1043 1044 1045 1046
    {
        updateNet( aNet );
    }
}
1047 1048 1049 1050 1051


void RN_DATA::updateNet( int aNetCode )
{
    assert( aNetCode < (int) m_nets.size() );
1052

1053
    if( aNetCode < 1 || aNetCode > (int) m_nets.size() )
1054 1055 1056 1057 1058
        return;

    m_nets[aNetCode].ClearSimple();
    m_nets[aNetCode].Update();
}