【高分求算法】JS图形，找两点之间的最短路径以及自动避开障碍，帮顶有分

现有效果图如下；

http://www.i-love-mm.com/images/WRTW/1.jpg
http://www.i-love-mm.com/images/WRTW/2.jpg

如果你用过VISO或者SQL Server里面的“关系图”就知道我想做什么

图中的几个表格ID已经知道，每个字段所在单元格的ID也知道

假设有几个表，在网页中他们的ID分别是t_1,t_2,t_3,t_4.....
这几个表的间距最少是40象素
t_1中几个单元格的ID依次是 c_1_1,c_1_2,c_1_3......
t_2中几个单元格ID依次是 c_2_1,c_2_2,c_2_3...........

现在已经知道有一个关联是从 t_1的c_1_1到 t_4的c_4_8

如何找出他们之间的最短路径（连线的起点和终点都在单元格的边框上）
这个路径是一条折线，不是现在的直接连接，并且尽量避免与现有的连线和表格图形重叠

算法的入口是两个ID
输出一个数组，从起点到终点所有转折点的坐标

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
这个ID的分全部在这里了，我另外一个ID还有2000多分
全部压在这个问题上了

21 个解决方案

#1

帮顶

#2

帮你顶，关注

#3

#4

http://www.51js.com/viewthread.php?fpage=1&tid=18944
看看星际的路径算法部分吧，呵呵干吗要折线啊

#5

看到这么复杂的问题
我就晕
昨晚上喝多了
帮楼主顶一下！！！

#6

回复人： ttyp(愿赌服输) ( ) 信誉：105  2004-12-30 09:55:00  得分: 0

   http://www.51js.com/viewthread.php?fpage=1&tid=18944
看看星际的路径算法部分吧，呵呵干吗要折线啊

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
他这个太复杂了，看不明白
我这个只要注意避开两样东西就可以了
一个是表格，一个是现有的线条

#7

那可以用一个最简单的方法~~
我不清楚你现在如何绘制图象，所以我说的方法里关于绘制都需要你自己想办法了~

首先找到直线的最短路径，然后让点延这个直线行走，同时绘制，当遇到另一条直线时（就是碰撞检测），绘制一个曲线，VISIO用过就知道什么意思。当遇到是图形时，就判断这个图形的边缘，而这个绘制的点就向最进的那个边缘移动，同时绘制，一直绘制到这个点可以再次不与图形碰撞，可向目标点运动为止，则继续直接向目标点运动。

这个是最简单的路径查找方法，在你这里是可以用的，如果用在游戏里，可能就会出现《血狮》那个游戏里出现的卡死到某个地方出不来的情况。

当然，用星际的A*算法是最好的，这样绘制出来的线条是最短而且最好看的~~~

#8

我做过，这把发财了。

几个问题先问清楚：
生成各表的方式，我是指，比如各表外面套了一个大table
各表是否可移动

我用这个来画办公自动化的流程图，倒跟你这个类似

#9

to 椅子：

我这些表都是套在一个SPAN里面的，这些SPAN放在一个DIV里面，让他们*排列
表不可以移动，都是固定的

to 懒猫：
我用的是VML画线，VML里面有一个PATH，可以直接指定线的路径，就是我要得到的几个转折点坐标
现在没多少时间去研究什么A*算法
而且在网页里面还得考虑效率问题，搞不好网页就死在那里了
如果用点来追溯，这样在有几十个表，上百个关系的时候，速度可能会很慢

#10

A(x1,y1) ,B(x2,y2),常量k1=k2=1（使线路美观）
1 根据两点坐标求出三角形两边
  有两种可能，随便哪种都可以
  C(x3,y3)
  x3=x2-k1 ,y3=y1
  相应可求出D(x4,y4)点
  x4=x3,y4=y2

2 在AC、BC中判断是否有障碍
  无障碍情况可根据C、D得出线路
  有障碍情况：
  计算障碍高度，根据障碍点居上还是居下来决定是爬升还是降落。
  设爬升点是A1(x5,y5)
  x5=障碍左边缘-k1,y5=x3+障碍上边缘+k1
计算A1到B的。。。，重复1

我下午有课，得赶紧走了，我写了一个演示，但没写完，原理是利用table在网页中构造一个25*25的网格，利用合并单元格的操作生成出表（字段），线条用改变网格的bordercolor（上下左右）来实现。
这样的好处在于我判断障碍和得出障碍的四个边缘非常容易。

#11

是AC,BD中判断是否有障碍

#12

我说的点是虚拟的点，比如你将你的页面分成16X16的区，然后每个图形都会占有一个或几个区，但是因为是你自己划分的区，则区的边界位置已经知道。然后在绘制线条的时候通过判断来绕过这些区域，就是当碰到要通过区域的情况时，就在区域边界放置一个折线顶点。并延着不可通过的区域的边界绘制。直到可以直接向目标点（区域）绘制为止。

当然这个区你划分越大，速度越快，但是越不精确~~~
不知道你理解我的意思没有~~~这里的点是一个抽象的点，并不是像素的点~~~如何绘制，采用任何方法都是一样的~~~和用VML还是组件无关~~

#13

谢谢椅子

我先试试

#14

up起来

#15

#16

#17

顶

#18

可以采用连续变形法来求最短路径：
  已知：初始点A和结束点B的坐标
  步骤：
   1  在A、B两点之间拉直线段AB
   2  求出跟所有障碍物边界的所有的交点，共有n个 (M1 ,M2,.....Mn)
   3  循环交点直到交点数目为0
      a）把第i个交点调整到两个障碍物之间，
      b) 计算新产生的交点，调整交点数组
   4  重复步骤3，直到交点数目为0

#19

继续UP

#20

学习

#21

这个强呀

#1

帮顶

#2

帮你顶，关注

#3

#4

http://www.51js.com/viewthread.php?fpage=1&tid=18944
看看星际的路径算法部分吧，呵呵干吗要折线啊

#5

看到这么复杂的问题
我就晕
昨晚上喝多了
帮楼主顶一下！！！

【高分求算法】JS图形，找两点之间的最短路径以及自动避开障碍，帮顶有分

21 个解决方案

#1

#2

#3

#4

#5

#6

#7

#8

#9

#10

#11

#12

#13

#14

#15

#16

#17

#18

#19

#20

#21

#1

#2

#3

#4

#5

#6

#7

#8

#9

#10

#11

#12

#13

#14

#15

#16

#17

#18

#19

#20

#21

相关文章