矢量线相交算法

《矢量线相交算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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、直线关系的判断，只是在必要的时候进行直线相交的判断。通过点与直线的判断提升了部分算法的效率。不足则是循环嵌套过多，较为繁琐。结果展示：