Mail Archives: geda-user/2013/10/30/19:44:02
On Wed, 2013-10-30 at 15:39 -0500, John Griessen wrote:
> On 10/30/2013 03:09 PM, Stefan Salewski wrote:
> > http://ssalewski.de/tmp/routerfun-tut1.png
> >
> > Unfortunately many shortcuts in the center of the picture, so there is
> > still some work to do.
>
> That looks like some rapid progress.
Yes, sometimes progress is fast, but I had two cases where I searched 30
hours for a bug -- one was the "Dijkstra shortest path search" (a non
trivial variant) and one was ordering of the attached nets. And maybe
one more the convex hull of a set of disc in 2d -- I wrote 3 variants
and finally replaced it with CGAL's Apollonius graph, which works really
great. Debugging is of course the greatest problem for such kind of
software.
> How steep is the learning curve to help with it?
Currently it is not a good point for help -- as I already said, I have
to clean up the code now. That is not much fun, but I am the best man to
do it, because I created all that garbage...
> Ruby, and what else is needed?
Generally I tried hard to make the code easy and it is easy. So when I
have done the cleanup, it should be possible for other people to
continue the work. Ruby is a fine easy language, very similar but
currently not so popular (in western countries) as Python.
> Does your code use the CGAL library like openSCAD does?
From CGAL I use only the initial constrained Delaunay triangulation and
the Apollonius Graph for the convex Hull of a set of disks in 2d. In
this way I follow the thesis of Tal Dayan, while Anthony B. used the GTS
library very much in his code. So I think his strategy is different.
One topic for the far future is using steiner trees -- I have not
investigated this yet. The first step for the layer assignment process
is splitting all the multi-terminal nets into single two terminal nets.
Currently I am using a minimum spanning tree based on the euclidean
distance of the terminals. This is very easy, but can be a bad idea for
dense populated boards: There can exists rows of pins on the board,
which block paths on all layers. So we should not use the euclidean
geometrical distance as a measure, but maybe employ a Dijkstra router to
determine all the point to point distances, and maybe we should combine
this with the possibility to insert steiner points. This task has not
high priority for me now, but it is necessary to get a really good
router. For Steiner Trees there exist not many supporting libraries, I
just asked at CGAL mailing list, with no result. There exist
Geo-Steiner, an exact solver, which is a large collection of tools
written in C. And there exists many theoretical papers -- some 30 pages
long and really complicated. My current favorite is
"L. Kou, G. Markowsky, and L. Berman, A fast algorithm for Steiner
trees, Acta Informatica 15 (1981), 141–145."
which is a not too long and complicated description for a heuristic.
But that is no stuff for the next months.
> I'm wanting to understand CGAL so I can add some features to OpenSCAD...
> and then I might be able to help you find bugs...
If someone is interested in this topic, then it may be a good start to
read Tal Dayan's thesis to get a feeling for the problems, maybe
skipping the theoretical proves. You can find that thesis if you do a
google search for "tal dayan ferguson".
Best regards
Stefan Salewski
- Raw text -