已知8个点(编号和坐标分别为:1(13,-4)、2(18,-4)、3(26,-20)、4(37,-20)、5(40,-23)、6(27,-26)、7(18,-26)、8(7,-22)。),10条线段(分别为点1——2、2——3、3——4、4——5、5——6、6——7、7——8、8——1、3——6、3-7),形成了三个区域,请问,如何判断各个区域由哪些点依次连接而成?
调试欢乐多
http://77607058.spaces.msn.com/
我举例说明,比如从点1开始组成图形1,是这样形成的:
1).把点1加入点集A里(这里的点集就是组成多边形的依次的点),上一个已处理直线段preLine=NULL;
2).查找过点1的直线段得到线1-2和线1-8,因为preLine=NULL,我们可以取点8或1,这里取点8,即将点8加入点集A里,preLine=线1-8;
3).查找过点8的直线段(除preLine外),只有线8-7,我们将点7加入点集A里,preLine=线8-7;
4).查找过点7的直线段(除preLine外),有线7-3、线7-6,得到这两条线的与preLine的夹角分别为角8-7-3(线7-8以点7为中心顺时钟转到线7-3的夹角)、角8-7-6(线7-8以点7为中心顺时钟转到线7-6的夹角),我们取最小者得到点3,即将点3加入点集A里,preLine=线7-3;
5).查找过点3的直线段(除preLine外),有线3-2、线3-4和线3-6,得到这三条线的与preLine的夹角分别为角7-3-2(注意顺时钟转,下同)、角7-3-4和角7-3-6,我们取最小者得到点2,即将点2加入点集A里,preLine=线3-2;
6).这样继续找下去,我们就会找到点1,发现已经加过,则表示需要闭合形成图形1了,该循环结束。
我们按1-6遍历所有其它的点,在找到一个最小夹角时给个已处理标志(事先需要定义一个夹角的类,得到该类的对象数组),这样遍历后,不仅不会出现死循环,而且一个都不漏的生成所有的图形!
将这些生成图形的点集保存起来,就是楼主你想要的。