<p>I am analyzing a large amount of <a href="https://en.wikipedia.org/wiki/OSI_model" rel="nofollow noreferrer">Layers 0-4</a> Network Data. I am trying to render diagrams dynamically showing the Network Devices involved in the data (Desktop, Switch, Router, Server, etc.) and how they speak to each other (lines connecting them indicating a data flow). I have a pretty good heuristics from that data on where to place the devices in the diagrams (ARP, Gateways, etc.). My main issue is getting the lines that connect them to stop looking like spaghetti. PCB CAD programs seem to have and solve this issue, but also have to deal with other issues (length/impedance matching, N-layers, etc.).</p>
<p>I was wondering if there was an algorithm that just did the initial part of PCB Trace layout, specifically:</p>
<p>Given</p>
<ul>
<li>a 2D space</li>
<li>the graphical location of nodes</li>
<li>requests to connect some of the nodes together with lines</li>
</ul>
<p>Generate line paths that</p>
<ul>
<li>limit the number of <a href="https://en.wikipedia.org/wiki/Circuit_diagram" rel="nofollow noreferrer">crossovers</a></li>
<li>Minimize the length of a crossover when they occur</li>
<li>(not critical) Allow for 90 degree turns to be replaced with two 45 turns (the PCB trace look)</li>
</ul>

CC BY-SA 4.0
2023-08-21T16:35:52.583Z
I wonder whether this question is really related to computer graphics. Wouldn't it be better to ask this question [here](https://electronics.stackexchange.com/)?
Enigmatisms
CC BY-SA 4.0
2023-08-21T17:06:22.387Z
@Enigmatisms ,from experience, the EE guys use CAD but they don't program it. I thought about the Comp Sci stack exchange but they don't touch graphical subjects often.
Liam Kelly
CC BY-SA 4.0
2023-08-21T19:14:14.160Z
I think the kind of problem you're thinking of would be more generally called [graph layout, or graph drawing](https://en.wikipedia.org/wiki/Graph_drawing) and you'll likely find more information if you explore from there than if you pursue PCB layout specifically (which is largely proprietary software). (I'm not sure whether this should be an answer, but I'm going with a comment because I'm not pointing at a specific “how to” for your problem.)
Kevin Reid
<computational-geometry><algorithm>
What algorithms are typically used for finding 'PCB Trace'-like paths?
Liam Kelly
# What algorithms are typically used for finding 'PCB Trace'-like paths?

(Asked by: username_0 on 2023-08-21)

I am analyzing a large amount of [Layers 0-4](https://en.wikipedia.org/wiki/OSI_model) Network Data. I am trying to render diagrams dynamically showing the Network Devices involved in the data (Desktop, Switch, Router, Server, etc.) and how they speak to each other (lines connecting them indicating a data flow). I have a pretty good heuristics from that data on where to place the devices in the diagrams (ARP, Gateways, etc.). My main issue is getting the lines that connect them to stop looking like spaghetti. PCB CAD programs seem to have and solve this issue, but also have to deal with other issues (length/impedance matching, N-layers, etc.).

I was wondering if there was an algorithm that just did the initial part of PCB Trace layout, specifically:

Given

* a 2D space
* the graphical location of nodes
* requests to connect some of the nodes together with lines

Generate line paths that

* limit the number of [crossovers](https://en.wikipedia.org/wiki/Circuit_diagram)
* Minimize the length of a crossover when they occur
* (not critical) Allow for 90 degree turns to be replaced with two 45 turns (the PCB trace look)

**Tags:** computational-geometry, algorithm

> **Comments:**
> **username_1**: I wonder whether this question is really related to computer graphics. Wouldn't it be better to ask this question [here](https://electronics.stackexchange.com/)?  
> **username_0**: @username_1 ,from experience, the EE guys use CAD but they don't program it. I thought about the Comp Sci stack exchange but they don't touch graphical subjects often.  
> **username_2**: I think the kind of problem you're thinking of would be more generally called [graph layout, or graph drawing](https://en.wikipedia.org/wiki/Graph_drawing) and you'll likely find more information if you explore from there than if you pursue PCB layout specifically (which is largely proprietary software). (I'm not sure whether this should be an answer, but I'm going with a comment because I'm not pointing at a specific “how to” for your problem.)  

---

## 0 answers

