欢迎来到天天文库
浏览记录
ID:21812023
大小:343.53 KB
页数:11页
时间:2018-10-20
《矢量线相交算法》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、矢量线相交算法报告第二组算法介绍:1、首先判断多义线的最小外界矩形是否与所画相交,相交的进行下一步判断,不想交的直接舍去。2、我们将所画多义线按照每一部分进行遍历,这样遍历的每一部分都是一条线段。(下文中提到的所画多义线,均为所画多义线的每一线段部分)123因为多义线记录中有部分的总数,且每一部分是主次存在相应的动态数组中的,所以上面的遍历是可以实现。其中任何一个部分与测试数据相交,都能将相交的线段筛选出来。3、因为多义线中的折点是存储在动态数组中的,而且也是依次存储的,这样我们依次遍历每一个折点。判断该折点是在所画的多义线的那一侧。如果相邻的两个折点在所画多义线的不
2、同侧,我们将计算这两个折点的直线,并将得到的直线与所画的多义线直线亮丽求交点。如果有交点,判断交点是否在所画多义线的最小外接矩形中,若在则两条多义线相交,否则不相交。ABCD多义线ABCD与所画多义线关系如上图,两者最小外接矩形相交,其中B、C两点在所画多义线两侧,但是BC与所画多义线的交点不在所画多义线的最小外接矩形内所以不想交。例1例2这里多义线AB的折点分别在所画多义线两侧,且交点也在所画多义线的最小外接矩形内,所以两者相交。AB代码实现:K表示的是所画多义线折点的号码,相邻的折点组成一条直线即所求的直线。rc1、rc2、rc3、rc4保存的是该相邻折点组成的最
3、小外接矩形的坐标,即xmin、xmax、ymin、ymax。先看多义线与所画多义线的最小外接矩形是否相交,否则进行下一遍历,是则进一步进行判断。遍历每一个折点,相邻折点若在直线不同侧则进行交点的判断。这里每判断点与直线的位置一次,就为b赋一次相应的值。C存储的是上一个折点与直线的位置关系,c与b相等则同侧,否则为异侧。求相邻折点的直线,并求交点判断交点是否在最小外接矩形内,是则为unm赋1值。如果unm值为1则将这条多义线的信息记录下来,最后返回到交互层进行显示。算法的特色:将多义线相交的判断,通过循环的方式,转化为直线相交的判断。而在直线相交的判断中主要进行的是点与
4、直线关系的判断,只是在必要的时候进行直线相交的判断。通过点与直线的判断提升了部分算法的效率。不足则是循环嵌套过多,较为繁琐。结果展示:
此文档下载收益归作者所有