Back in April I started to work on cuboid surface shortest path problem, and found an example where shortest path between two points needs to visit 4 faces:

https://twitter.com/HermannSW/status/15 ... 5390921729
The screenshot was created with planar_graph_playground example using htmlsvg.js, online here:

https://hermann-sw.github.io/planar_gra ... rtest_path
In the last days I got the idea how to solve that problem, for cuboid with different size lengths, and with OpenSCAD output.

New "scad.header3()" (only 37 lines) provides what is needed to embed a graph onto cuboid surface (instead of sphere):

https://github.com/Hermann-SW/planar_gr ... 54da49a154
Nearly no geometry is needed, I just discretize the 12 edges of the cuboid by introducing variable numer of vertices.

After creating the required graph, just calling "floyd_warshall[_path](G, w)" all pairs shortest path problem does the job.

Until today these functions worked on unit edge length, I added optional passing wheight edge mapping "w" today:

https://github.com/Hermann-SW/planar_gr ... f934041d22
I used this command for generating below explanation screenshots (modifying code to display the edges of interest only).

Start point is (0.4, 0.2, 0), target points are 2*2 points on top (z=1) because of dividing into 3 parts (last arg).

Cube edges are divided into 4 parts.

X direction length is always 1, lengths for Y and Z are passed after start point:

Code: Select all

`./rjs node.cuboid_surface_shortest_path.js 0.4 0.2 1 1 4 3`

Left shows start point, it is connected to each vertex of bottom face.

Middle shows top target points, each is connected to all top corner and cube edge vertices.

Both get done by "mk_complete_bipartite()":

https://github.com/Hermann-SW/planar_gr ... js#L87-L93
*cube.shortest_path.png* - cube.shortest_path.png (116.61 KiB) Viewed 268 times

Right shows the dges for a side face, just complete graph of all vertices, done with "mk_complete()":

https://github.com/Hermann-SW/planar_gr ... js#L78-L85
All edges get 3D distance between its source and target vertex coordinates as weight:

https://github.com/Hermann-SW/planar_gr ... #L114-L122
Code: Select all

```
function dist3D(p, q) {
var d = [p[0] - q[0], p[1] - q[1], p[2] - q[2]];
return Math.sqrt(d[0]*d[0] + d[1]*d[1] + d[2]*d[2]);
}
var w = filled_array(n_edges(G), 1, -1);
forall_edges(G, function(e) {
w[e] = dist3D(coords[source(G, e)], coords[target(G, e)]);
});
```

Running for cube (X=Y=Z=1) with this command, start point at (0.4, 0.2, 0).

Cube edges get divided into 100 pieces, resulting in 99 vertices.

Top face gets divided into 20 poices, resulting in 19*19 top face target vertices in topc:

Code: Select all

`./rjs node.cuboid_surface_shortest_path.js 0.4 0.2 1 1 100 20`

This is bottom view of start point:

*cube.shortest_path.bottom_big.png* - cube.shortest_path.bottom_big.png (39.51 KiB) Viewed 268 times

Determining number of edges on shortest path is done with "nedges()":

https://github.com/Hermann-SW/planar_gr ... #L147-L155
Following shortest path from each target point (vertex) is done by iterationg "topc" and following shortest path (with "next" array) to start point s, and draring all edges with the determined color:

https://github.com/Hermann-SW/planar_gr ... #L157-L167
Code: Select all

```
topc.forEach(function (v) {
var cnt = nedges(v, s);
assert.assert( (cnt > 2) && (cnt < 5) );
var col = (cnt === 4) ? [0,0,1] : [1,0.666666,0];
while (v !== s) {
var e = next[v][s];
scad.wlog("color(",col,") edge(",source(G, e),",",target(G, e),",",0.005,");");
v = opposite(G, v, e);
}
});
```

And here is top view animation, blue shortest paths have 4 edges, orange shortest paths have 3 edges.

Wonderful example showing that there can be 3 distint regions on top face with 4 edges shortest paths (blue)!

Demonstration that algorithm works for X=1, Y=0.8, Z=1.2 cuboid as well:

Code: Select all

`./rjs node.cuboid_surface_shortest_path.js 0.65 0.1 0.8 1.2 100 20`

*cuboid.shortest_path.png* - cuboid.shortest_path.png (70.63 KiB) Viewed 268 times

P.S:

I forgot to mention, that execution for N=100 and n=20 takes less than 1 minute runtime:

Code: Select all

```
pi@pi400-64:~/planar_graph_playground $ time ./rjs node.cuboid_surface_shortest_path.js 0.4 0.2 1 1 100 20
real 0m47.210s
user 0m49.777s
sys 0m1.548s
pi@pi400-64:~/planar_graph_playground $
```

I appended this line, and learned that the generated graph consists of n=1558 vertices and m=464000(!) edges:

Code: Select all

`console.log(n_vertices(G), n_edges(G));`

The inner loop of "floyd_warshall_path()" for updating shortest path distances is executed n³ = 3,781,833,112 times:

https://github.com/Hermann-SW/planar_gr ... #L547-L556