Manhattan Routing Algorithm Implementation for Diagram Connections

Problem Description: Given two endpoints and their directions, with connections constrained to horizontal or vertical segments, automatically compute the routing path for the wire.

Solution Process: The author first encountered this problem in 2015 while building a flowchart editor, noting that Visio’s algorithm was powerful but undocumented. Research revealed the term "routing algorithm" and the well‑known Manhattan Connection Router. Existing tools like ProcessOn used extensive if‑else logic, prompting the search for a cleaner solution. An informative article on automatic routing in GEF and the Java library draw2d (also available as a JavaScript implementation at draw2d.org) were identified as valuable resources.

Application Scenarios: Initially applied in flowchart tools, the algorithm also fits circuit diagram editors and home‑circuit design, with extensions such as semi‑Hamiltonian routing, obstacle avoidance, and bridge creation at wire crossings.

Manhattan Routing Implementation Code:

export class ManhattanRouter
extends DirectRouter
{
  public TOL: number = 0.1;
  public TOGGLE_DIST: number = 5;
  public MINDIST: number = 30;

  public route(Point: { new(x: number, y: number) }: T, conn: T[], fromPt: T, fromDir: RouterDirection, toPt: T, toDir: RouterDirection): void {
    const TOL: number = this.TOL;
    const TOLxTOL: number = TOL * TOL;
    const MINDIST: number = this.MINDIST;
    const LEFT = RouterDirection.Left;
    const RIGHT = RouterDirection.Right;
    const UP = RouterDirection.Up;
    const DOWN = RouterDirection.Down;

    const xDiff: number = fromPt.x - toPt.x;
    const yDiff: number = fromPt.y - toPt.y;
    let point: T;
    let pos: number;
    let dir: RouterDirection;
    if ((xDiff * xDiff < TOLxTOL) && (yDiff * yDiff < TOLxTOL)) {
      conn.push(new Point(toPt.x, toPt.y));
      return;
    }
    if (fromDir == LEFT) {
      if (xDiff > 0 && yDiff * yDiff < TOL && toDir == RIGHT) {
        point = toPt;
        dir = toDir;
      } else {
        if (xDiff < 0) {
          point = new Point(fromPt.x - MINDIST, fromPt.y);
        } else if ((yDiff > 0 && toDir == DOWN) || (yDiff < 0 && toDir == UP)) {
          point = new Point(toPt.x, fromPt.y);
        } else if (fromDir == toDir) {
          pos = Math.min(fromPt.x, toPt.x) - MINDIST;
          point = new Point(pos, fromPt.y);
        } else {
          point = new Point(fromPt.x - (xDiff / 2), fromPt.y);
        }
        if (yDiff > 0) {
          dir = UP;
        } else {
          dir = DOWN;
        }
      }
    } else if (fromDir == RIGHT) {
      if (xDiff < 0 && yDiff * yDiff < TOL && toDir == LEFT) {
        point = toPt;
        dir = toDir;
      } else {
        if (xDiff > 0) {
          point = new Point(fromPt.x + MINDIST, fromPt.y);
        } else if ((yDiff > 0 && toDir == DOWN) || (yDiff < 0 && toDir == UP)) {
          point = new Point(toPt.x, fromPt.y);
        } else if (fromDir == toDir) {
          pos = Math.max(fromPt.x, toPt.x) + MINDIST;
          point = new Point(pos, fromPt.y);
        } else {
          point = new Point(fromPt.x - (xDiff / 2), fromPt.y);
        }
        if (yDiff > 0) {
          dir = UP;
        } else {
          dir = DOWN;
        }
      }
    } else if (fromDir == DOWN) {
      if (xDiff * xDiff < TOL && yDiff < 0 && toDir == UP) {
        point = toPt;
        dir = toDir;
      } else {
        if (yDiff > 0) {
          point = new Point(fromPt.x, fromPt.y + MINDIST);
        } else if ((xDiff > 0 && toDir == RIGHT) || (xDiff < 0 && toDir == LEFT)) {
          point = new Point(fromPt.x, toPt.y);
        } else if (fromDir == toDir) {
          pos = Math.max(fromPt.y, toPt.y) + MINDIST;
          point = new Point(fromPt.x, pos);
        } else {
          point = new Point(fromPt.x, fromPt.y - yDiff / 2);
        }
        if (xDiff > 0) {
          dir = LEFT;
        } else {
          dir = RIGHT;
        }
      }
    } else if (fromDir == UP) {
      if (xDiff * xDiff < TOL && yDiff > 0 && toDir == DOWN) {
        point = toPt;
        dir = toDir;
      } else {
        if (yDiff < 0) {
          point = new Point(fromPt.x, fromPt.y - MINDIST);
        } else if ((xDiff > 0 && toDir == RIGHT) || (xDiff < 0 && toDir == LEFT)) {
          point = new Point(fromPt.x, toPt.y);
        } else if (fromDir == toDir) {
          pos = Math.min(fromPt.y, toPt.y) - MINDIST;
          point = new Point(fromPt.x, pos);
        } else {
          point = new Point(fromPt.x, fromPt.y - yDiff / 2);
        }
        if (xDiff > 0) {
          dir = LEFT;
        } else {
          dir = RIGHT;
        }
      }
    }
    this.route(Point, conn, point, dir, toPt, toDir);
    conn.push(fromPt);
  }
}

export class DirectRouter
{
  constructor() {}
  public route(Point: { new(x: number, y: number) }: T, conn: T[], fromPt: T, fromDir: RouterDirection, toPt: T, toDir: RouterDirection): void {
    conn.push(fromPt, toPt);
  }
}

export const enum RouterDirection {
  Left = 0,
  Up,
  Down,
  Right
}

Effect: The algorithm produces clean orthogonal connections similar to Visio, as demonstrated by the accompanying GIF illustration.

Conclusion: The Manhattan routing algorithm is powerful, easy to extend, and applicable to various diagramming and circuit design problems, with potential for further enhancements such as mouse‑trajectory routing and filtering effects.