kicad-developers team mailing list archive

[Tomasz Wlostowski <tomasz.wlostowski@xxxxxxx>]

On 25.04.2014 23:44, Lorenzo Marcantonio wrote:
> On Fri, Apr 25, 2014 at 03:18:51PM -0500, inkblotter wrote:
> > algorithms; imagine a graph of all the nets and pads; sort of a live
> > netlist, with built in search and visiting algorithms. If I wasn't already
>
> The 'live' thing could be a big problem; the current pcbnew works well
> because there is almost no redundancy in the data structures. Keeping
> a connection graph would be somewhat tricky, especially considering that
> the undo architecture is copy based, not transactional (command based).

Hi Lorenzo,

Look at the classes PNS_NODE and PNS_INDEX.

> AFAIK currently 'index' data structure are built from scratch just
> before something big like the track cleanup. Maybe there is some support
> structure for the ratnests too (updated with the rebuild, probably...
> when the nest goes crazy a rebuild fixes it). I actually never worked on
> these innards.
>
> However just only something like an rtree could really help some
> operations (the CERN people were working on something like that).
>
> Luckily modern PCs are sufficiently fast to work with the simple linear
> search used everywhere (until the board is, maybe, 5000 pad big, more or
> less). And, of course, even if DRC is slow, who cares :D
Nope, they are not. That's why we have R-trees and hashes in the router.


Cheers,
Tom