23
2021
06

曼哈顿路由在电路连线中的应用

问题描述

已知导线的两个端点以及两个端点处的方向,并且导线只能沿水平或者竖直方向,自动计算导线的路径。

解决过程

最早接触这个问题是2015年,当时要做一个流程图编辑工具,其中,连线部分是最难的。微软的viso中的算法是很强大的,但是我没有找到相关资料。搜索过程中,了解到,这种连线算法被称为路由算法,比较著名的一个算法叫曼哈顿路由算法(ManhattanConnectionRouter)。

当时,国内比较著名的在线流程图工具processon已经上线了,连线功能做的很棒,本来想参考一下,但是当我看到他家的连线算法写了1200多行if...else...时,就果断放弃了。

后来找到了这篇文章:连线自动路由算法:在GEF中实现连线的自动直角路由,智能避障并绕开模型,选择最佳路径进行布线,仿Visio效果。文章中讲的很详细,可以学习原理。

我还找到一个java的库:draw2d,非常强大。如果做流程图软件,可以拿来用或者参考。

如果你现在搜索draw2d,可能会发现draw2d.org。这是一个js实现的draw2d库。

至此,我们只需要了解曼哈顿路由的原理,以及如何应用,再封装一下draw2d中的方法就可以了。

应用场景

最早当然是应用在流程图工具中。不只是曼哈顿路由,还有好多其它路由算法,或者基于曼哈顿路由的扩展,比如半哈密顿路由、绕过障碍、导线交叉处加桥等等。

后来在做电路图工具的时候,又用到了曼哈顿路由算法。draw2d.org的官方example中也有相应的应用,可以参考。

最近在做家庭电路,又用到曼哈顿路由算法。

曼哈顿路由的实现代码

export class ManhattanRouter<T extends IPoint> extends DirectRouter<T> {
  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 = RouterDirection.Left;
    const RIGHT: RouterDirection = RouterDirection.Right;
    const UP: RouterDirection = RouterDirection.Up;
    const DOWN: RouterDirection = 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<T extends IPoint> {

  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
}

我们还定义了一个直线路由:直接连接起点和终点。

效果

总结

很强大的算法。而且很容易扩展。以后遇到其它问题可能还会用到。

想一下,如何实现一个路由算法,功能是按照用户鼠标移动的轨迹画线。然后再在这个路由算法的基础上加上滤波效果。


« 上一篇下一篇 »

相关文章:

并查集在电路计算中的应用  (2021-6-23 13:40:24)

流程图连线算法  (2015-9-10 17:2:27)

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。