有一算法问题请大伙帮忙

WWWDONG · 发表于 2003-12-8 21:33:00

问题：
假设平面中有若干点，有何办法创建一多义线，使其首尾相连，且不交叉？

efan2000 · 发表于 2003-12-8 21:52:00

这个算法就大了，将所有点存入一个数组，假设为N点。任意取出一点为起点，接下来第一段的终点就有N-1种，而第二段的终点就有N-2种，……，总共有N（N-1）（N-2）……1，从第三段开始还要与前面的各段进行比较，判断有没有交叉。
呵呵，这个解决了，那呼吸的世界中那一道关于连线的问题也解决了。

lockmyeye · 发表于 2003-12-8 23:48:00

比“呼吸的世界中那一道关于连线的问题”易多了，在这里，任意加入一点，一定可以找到一个合适的插入位置。“呼吸的世界中那一道关于连线的问题”，每一个节点，最多只有四个方向啊：(

今晚打老虎 · 发表于 2003-12-9 08:06:00

哦~~~有意思~~~

bluemoon · 发表于 2003-12-10 10:10:00

我觉得这样也行啊：将所有点存入一个数组，然后以X（或Y）为基准，给定一个增量，然后在Y（或X）方向检索数组，按其大小依次排列数组。最后绘出来的类似于M行

zeng29 · 发表于 2003-12-12 08:26:00

如果点阵的总数不多时,采用穷举的方法还可以勉强接受,但如果数量太多时,这种方法就难以忍受.因为在经过N次尝试连接成功,前面的N-1次尝试都是失败的,而每次尝试一般都要经过庞大的计算量.
可以用这种算法:类似于雷达扫描的方法即旋转扫描的方法.
1 在点阵的外围找到一个初始点.
2 给定一个初始角
3 沿初始角按一个确定的方法(顺时针/逆时针)旋转
4 扫描到的第一个点就是下一个基点,并连接这两个点,以此类推.
5 如果扫描到的后续点是初始点,那么就改变扫描的方法,以此类推.
6 如果已经没有未扫描的点,就连接初始点.
这种方法的优点是:可以确保每一次连接都是正确的,而没有N-1次的失败.

有一算法问题请大伙帮忙

发表回复

精选推荐