基于CGAL的电路板路由算法

Question

CGAL的文档似乎没完没了，我觉得我可以进入一个兔子洞试图找到我正在寻找的东西，因为它有这么多的特性。然而，根据我到目前为止在这个库中看到的算法，创建一个高效的电子电路自动路由算法的最佳包/引擎/内核是什么？也就是说，如果一个二维平面上有一个多边形域(部件垫、孔等)，再加上一个需要连接到其他多边形的网络列表，我们就需要解决创建一个迷宫(或者解决一个迷宫)的问题。用平面内的路径连接这些多边形。

如果允许路由器在两个(或更多) 2D平面上创建vias (通过板孔)，那么问题就会变得更加复杂。

注意，这只是一种路由算法；将多边形(电路组件)本身放置将留给用户。

Answer 1

人们一直在使用用"Arrangement_2“特征实例化的"Arr_circle_segment_traits_2”模板来表示电子电路；参见CGAL手册。看一看图书CGAL安排及其应用 8.4节“应用:通用多边形上的多路操作”。

你需要正式陈述你的问题才能得到更好的答案。