山寨机中的战斗机！	程序优化工程师到底对IT界有没有贡献

VC下面绘制不相交的连续线段的问题.

楼主idau7（(小i不怕)我爱Eva）2005-01-11 04:01:28 在 VC/MFC / 图形处理/算法提问

目的实现就是用鼠标点击一系列的点,将各个点连成直线,但是不允许与已经存在的线相交.

大概要怎么做呢?有什么参考的东东啊?

求救啊~~急啊~~

分不是问题!~解决了再给100分都无问题~

问题点数：100、回复次数：18Top

1 楼jiangsheng（蒋晟.Net[MVP]）回复于 2005-01-11 07:01:11 得分 35

1 找任意一个和典籍中任何两点都不在一个直线上的点
2 以此点为极点，任一方向为极轴建立极坐标系。
3 将点集按极坐标的角度排序
4 按照此顺序连接点集中的点
这是高中数学题？Top

2 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-01-11 11:58:22 得分 34

找凸包
剩余的点再次找凸包
循环直到所有的点都进入了凸包当中

显然这些凸包是相互包含的
一个套一个

然后再打开这个系列凸包就是了
所谓的打开,就是从凸包上的任意一点,找到下一个凸包上的一个点,使得他们之间的连线和内部凸包无交点即可
这样的结果是一个类似螺旋形状的折线

为了说明问题,把处理方案规划成为找多个凸包
实际上在具体操作当中,找凸包的同时就可以生成这个解的
Top

3 楼xuzheng318（忧郁王子）回复于 2005-01-11 12:02:59 得分 1

关注，帮顶，学习！Top

4 楼idau7（(小i不怕)我爱Eva）回复于 2005-01-11 13:06:32 得分 0

还是不是很清楚....
偶笨笨的说...

哪儿有相关资料啊?Top

5 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-01-11 13:28:51 得分 0

一堆点如何找凸包?
先找出一个极值点,比如y分量最小的点当中x分量最小的点,它肯定是凸包上的一个点
然后从这里开始找一个点,使得其他的点都在这个点和和起点的连线的同一侧
记录这个线段,然后再把找到的点作为新的起点,找下一个线段,一直到完成一个封闭的多边形为止
Top

6 楼I_Love_CPP（Never stop!）回复于 2005-01-11 17:56:52 得分 30

这个问题我在回答“画不相交的折线”时已经解决：
//////////////////////////////////////////////////////////////
这需要一点矢量方面的知识，考验你数学基础了：
对一条折线而言，每转折一次相当于做了一次旋转.
因此,你需要计算一条折线的一共的旋转角，如果〉=360，则一定相交了。

如果不清楚请EMALI联系：I.Love.Cpp@126.com

见帖子
http://community.csdn.net/Expert/topic/3695/3695712.xml?temp=.8586847
////////////////////////////////////////////////////////////////

其实这与 jiangsheng(蒋晟.MSMVP2004Jan) 的方法相似。
无须用更复杂的方法。Top

7 楼idau7（(小i不怕)我爱Eva）回复于 2005-01-11 19:40:59 得分 0

其实..说出来不怕丢人..

偶听的是迷迷糊糊的...Top

8 楼idau7（(小i不怕)我爱Eva）回复于 2005-01-11 20:06:08 得分 0

看了半天,有点儿明白了.

jiangsheng(蒋晟.MSMVP2004Jan)说的用极坐标的方法
happy__888([顾问团]寻开心)说的用凸点的方法.

我的理解如果没有错的话,都是需要对已经存在的点进行某种方式的排序,然后以这种排的序列依次连接.
这是一种不会使得直线相交的连接点的方法,却不是唯一的连接方法.
即:
所说的两种方法是连接的点不相交的充分条件,却不一定也是必要条件

偶脑袋比较苯的说...
劳烦大虾说清楚点儿~不胜感谢..^^

btw:哇,mvp哦,而且还是5*,oh......第一次见...

Top

9 楼I_Love_CPP（Never stop!）回复于 2005-01-11 21:11:34 得分 0

上面的方法没有叙述清楚，
改进了一下：

判断一系列（首尾相连的）折线是否相交：
原理：利用矢量：将从一点到另一点的线段当作矢量。
如果连续N个矢量（V1，V2，...，Vn）的和矢量
等于0或者其方向与这N个矢量中之一的矢量同方向，则
V1一定与Vn相交。

你每画一条线段就保证它和前所有线段都不相交即可。Top

10 楼I_Love_CPP（Never stop!）回复于 2005-01-11 21:15:52 得分 0

注：我是改进的我前面所说的方法哦，那两位高人的方法还没有研究。Top

11 楼idau7（(小i不怕)我爱Eva）回复于 2005-01-11 21:41:21 得分 0

I_Love_CPP(我爱C++)
用你的方法,我可不可以这样理解:

有1至N+1,N+1个点.
第一个点与第二个点之间的线段称之为矢量V1
第二个点与第三个点之间的线段称之为矢量V2
....
第n-1个点与第n个点之间的线段称之为矢量Vn

当我再加入一个新的点N+2时,为了判断这个点与N+1之间形成的线段(矢量Vn+1)是否与已经存在的线段相交,我只需要判断矢量和V1+V2+...+V(n+1)是否为零,再判断矢量Vn+1与已经存在的n个向量的方向是否有相同的,若和为零或者有方向相同的方向向量的时候,线段与其不相交

是应该这样理解不?
Top

12 楼I_Love_CPP（Never stop!）回复于 2005-01-12 01:37:12 得分 0

有1至N+1,N+1个点.
第一个点与第二个点之间的线段称之为矢量V1
第二个点与第三个点之间的线段称之为矢量V2
....
第n-1个点与第n个点之间的线段称之为矢量Vn-1

当你再加入第n+1时，第n个点与第n+1个点之间的线段称之为矢量Vn。
现在只需判断Vn与V1,V2,....Vn-1是否相交:

CMyVector V[] = {V1,V2,...,Vn-1};依次写
（建议使用vector,我写CMyVector仅为了叙述方便）

for(int i=1;i<n;i++)
{
if(intersect(i))
return (相交了);
}

bool intersect(int Num)
{
if(V[n-Num-1],...,V[n-1]的和矢量等于0或者和矢量与V[n-Num-1]方向相同)
return true;//V[n-1]与V[n-Num-1]相交了

return false;//没有相交呢
}

Top

13 楼idau7（(小i不怕)我爱Eva）回复于 2005-01-12 05:32:32 得分 0

为了搞这个东西,偶一夜没睡了,好困...

谢谢兄弟们了.

东西搞出来就散分.Top

14 楼I_Love_CPP（Never stop!）回复于 2005-01-12 12:22:08 得分 0

分数并不重要的 :)
我对算法的东东比较感兴趣。

////////////////////////////////////////////
我那个“判断Vn与V1,V2,....Vn-1是否相交”的判定考虑的还不周全
也就是bool intersect(int)没有搞对。

bool intersect(int Num)
{
return(线段Vn与线段Vn-Num相交 == TRUE）;
}
判断2个线段相交容易，你自己细化一下。
////////////////////////////////////////////

其实原理很简单
就是你每画一条线段时保证它和前面所有的线段都不相交，
那么你画出的图形肯定都不相交了。
Top

15 楼idau7（(小i不怕)我爱Eva）回复于 2005-01-12 20:40:44 得分 0

今天晚上再搞不定还是不睡觉!!Top

16 楼I_Love_CPP（Never stop!）回复于 2005-01-12 22:05:11 得分 0

身体要紧。
算法已经解决，就是编码的问题了，不要这么急。Top

17 楼idau7（(小i不怕)我爱Eva）回复于 2005-01-12 22:25:16 得分 0

其实我觉得算法好像并没有实质性的进展.
比如说;
新假如的一个点与已经存在的最后一个点形成的线段 V(n+1)
依次与前面所形成的线段进行测试,看是否相交.

这个比较如何进行?

有例子代码就更好了,谢谢...

Top

18 楼idau7（(小i不怕)我爱Eva）回复于 2005-01-13 00:47:40 得分 0

计算几何算法概览
http://search.csdn.net/Expert/topic/2483/2483852.xml?temp=.5336725

BlueSky2008 (懒惰是程序员的美德)发表于2003-11-22 14:56:07Z

csdn的搜索引擎一点儿都不好用...
关键字输入多了,长期找不到东东....

刨了半天,总算找到了..把链接发出来,帮助后人吧.

再次感谢回帖帮忙的兄弟.

Top