基于CGAL的电路板布线算法

Question

CGAL 的文档似乎无穷无尽，我觉得我可以进入一个兔子洞试图找到我正在寻找的东西，因为它有这么多的功能。但是，根据我目前在该库中看到的算法，什么是为电子电路创建高效自动布线算法的最佳 package/engine/kernel？也就是说，给定一个带有多边形区域（元件焊盘、孔等）的二维平面，以及需要将多边形连接到其他多边形的网表，我们需要解决创建迷宫（或解决迷宫？）通过使用平面内路径连接这些多边形。

如果允许布线器创建过孔（穿板孔）并因此在两个（或更多）2D 平面中运行，问题会变得更加复杂。

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

Answer 1

人们一直在使用用“Arr_circle_segment_traits_2”特征实例化的“Arrangement_2”模板来表示电子电路；参见 CGAL manual. Take a look at the Book CGAL Arrangements and Their Applications 第 8.4 节“应用：一般多边形的多路操作”。

您需要正式陈述您的问题以获得更好的答案。