Ben Jackson wrote: > On Wed, Jul 09, 2008 at 07:02:12PM +1200, Anthony Blake wrote: >> If anyone is interested in the topological autorouter I'm working on, > > Looks neat! Nice presentation of the progress. > > I'm curious: What do your internal data structures look like, and how > applicable would they be as a replacement for PCB's own clunky internals? >
The data structures are still pretty sketchy, but I think there are parts which could be put back into PCB. In particular, using the delaunay triangulation code we can do EMST in O(nlogn) time rather than the O(n^2) with the current code. When moving only a few points, we would only end up doing the computation for those points, and then generating the MST in linear time. This should improve the rats-nest code. TBH, I'm not really familiar with a lot of PCB's internals, so it's hard for me to say whether or not it would be useful to replace parts. _______________________________________________ geda-dev mailing list [email protected] http://www.seul.org/cgi-bin/mailman/listinfo/geda-dev
