求两点间用横平竖直线端连接的算法,不能和两点间的物体(线形)相交
如题,已知平面空间两点,同时散布一些不确定位置的线形.先需要在两点间用横平竖直的线端连接,且不能和空间内线形相交.算法大致是什么思路.或有什么现成的算法思路?
谢谢!
问题点数：0、回复次数：4Top
1 楼BlueSky2008（懒惰是程序员的美德）回复于 2003-12-04 20:30:27 得分 0
网格化，被线形占据的方格作为禁止的方格，其它方格都是能走的。然后就变成A*寻路的问题了。寻出来的路肯定是横平竖直的，因为都是从一个方格走到另一个方格。Top
2 楼Tooler（小杨）回复于 2003-12-15 23:47:10 得分 0
那你去这看看吧！
http://www.wonyen.net/bbs/nboard.asp?ntypeid=33Top
3 楼zzwu（未名）回复于 2003-12-17 13:26:52 得分 0
最简单的，是使用Lee氏算法。这是PCB和LSI布线中最基本的一种布线算法，其特点是，只要存在可行路径，就一定能找出横线-竖线路径（曼哈顿路径），并且能最短。
可以找本《LSI设计方法》一类的书来看看，就行了。Top
4 楼amdcwf（谈，我爱你）回复于 2003-12-17 14:56:31 得分 0
网格化，被线形占据的方格作为禁止的方格，其它方格都是能走的。然后就变成A*寻路的问题了。寻出来的路肯定是横平竖直的，因为都是从一个方格走到另一个方格。Top
