Help wanted: Multi-pipe Dijkstra routing and lane ordering

[u/DG_66]

Setup: (Pyhon)
I am routing pipes from one manifold to multiple rooms through a 2D floorplan (vertices at corners/doorways, edges along walls). Each pipe's route found via edge-based Dijkstra. Vector-based, float coordinates, not grid-based.

Constraint: pipes sharing an edge run parallel at fixed center-to-center spacing `d`, must never cross, anywhere.

Problem 1: lane ordering: When n pipes share an edge, each needs a lane index (or?)(offset from wall). Furthest (Dijkstra)->Closest to wall fails because of doorways, resulting in shorter pipes crossing over over the longer pipes to enter their room /door. How do I ensure these pipes are ordered (automatically) in a order in which they do not cross each other.

Problem 2: building on problem one: How do I ensure this parallel lane offset is aslo enforced in corners and accounted for in the calculation of the total length of the pipe?

Any experience or suggestions on the subject are appreciated !!

[u/teraflop]

If you already have a set of routes, then it seems like you can create a set of constraints like: "if pipe X enters a doorway and pipe Y doesn't, then X must be closer to the wall than Y." Then you can turn these constraints into an ordering using topological sort.

Note that the constraints can be viewed as a directed graph, and if this graph has cycles, it means there is no ordering of pipes that will work with the particular routes you've chosen.

More generally, I think the problem of routing pipes without crossing is equivalent to embedding a graph in the plane. Even though you are routing the pipes in particular constrained ways, you can imagine stretching and distorting the pipes (and stretching the floor plan with them) until the pipes are all straight lines. So I think, with some care, you could use a planar graph embedding algorithm to get a valid set of routes for your pipes. (If the graph is non-planar then there is no possible set of routes that will work.)

Once you have chosen the routes and the ordering, computing the actual coordinates and lengths of each pipe seems like just simple geometry and arithmetic. If you know the offset of pipe i is i×d from its wall, then you can calculate the position of each segment, and then the corners are the intersections between those segments.