求流程图、电路图中“智能连线”的算法

kb1024

如图：

http://john.itwind.net/temp/flow.gif

这种所谓“智能连线”经常可以在流程图、电路图等看到，确定线的起点和终点，自动产生最佳的连线（折线）。

哪位大哥能指教一下，程序应该怎么写？

kb1024

我现在的程序已经做好了“布局”的工作，现在正为“布线”的工作而苦恼：D

我的每一根线有一些基本属性，记录它起始于哪个框/器件，终止于哪个框/器件，以前起始/终止于框的哪个部位（框的上边线、下、左右、左上角、右下角等，每个框的四周共有十六个“锚点”可以作线的起点或终点）

根据线的属性（起始于哪个框的哪个锚点，终止于框哪个框的哪个锚点）以前框/器件的坐标，很容易算出线起点/终点的绝对座标，如果是直接连线，很容易就可以实现了！

问题是这种自动并且合理拐角的线该怎么做：D

zh1110

图上看，无遮挡情况拐角取的是中间位置 [em17]

kb1024

图中显示的是比较简单的情况下，如果从左框的左侧一点连到右框的右侧一点，要多拐几道弯：D

kb1024

暂不考虑连线过程中遇到其他框需要绕行的问题

zh1110 兄提及的中心点似乎很重要，不管怎么拐弯，线总是要经过中心点

zh1110

也许可以这样：先画出节点网各——用寻径方法找出所有最短线路——筛选结果中不与其他线路重叠的线路——转折最少的线路——起使和末尾尽可能有转折的线路

nusnurt

电路图都是分层的阿，不会有相交。

以前去过一个公司。主要研究电路图布线。

用的是  A* 和 遗传算法。呵呵，不知道你们了