Search code examples
cgal

CGAL-based circuit board routing algorithm


The documentation for CGAL seems endless, and I feel as though I can get into a rabbit hole trying to find what I'm looking for since it has so many features. However, based on what I'm seeing so far with the algorithms in that library, what would be the best package/engine/kernel for creating a highly-efficient autorouting algorithm for electronic circuits? That is, given a 2D plane with a field of polygons (component pads, holes, etc.), along with a netlist of which polygons need to be connected to other polygons, we would need to solve the problem of creating a maze (or solving a maze?) by connecting those polygons using in-plane paths.

The problem grows much more complicated if you allow the router to create vias (through-the-board holes) and therefore operate in two (or more) 2D planes.

Note this would be just a routing algorithm; placing the polygons (circuit components) themselves would be left to the user.


Solution

  • People have been using the "Arrangement_2" template instantiated with the "Arr_circle_segment_traits_2" traits to represent electronic circuits; see CGAL manual. Take a look at the Book CGAL Arrangements and Their Applications Section 8.4 "Application: Multiway Operations on General Polygons".

    You need to formally state your problem to get better answers.