如果比较快的判断一堆线段是否两两相交,可用以下方法:
首先,用所谓的快速排斥试验排除掉肯定不相交的两条线段;
然后,用向量叉乘判断两条线段是否相交即可。
note:
1,所谓快速排斥试验,是我在一个网名“怒火之袍”的文章里看到的名词。
意思就是说,如果两条线段分别确定的矩形不想交,则这两条线段一定不想交。
如果,分别给出两条线段的起始点坐标,具体实现,可以这样:
如果一条线段的起始点的两个方向的坐标的最大值大于或等于另一条线段的起始点的两个方向的坐标的最小值,则它们确定的矩形相交。
举个例子,s代表始点,e代表终点,两线段a,b满足如下关系
max(a.s.x,a.e.x)>=min(b.s.x,b.e.x)&&
max(a.s.y,a.e.y)>=min(b.s.y,b.e.y)&&
max(b.s.x,b.e.x)>=min(a.s.x,a.e.x)&&
max(b.s.y,b.e.y)>=min(a.s.y,a.e.y);
则a,b分别对应的矩形相交。
2,向量叉乘的话,利用它判断折向即可得出一个方程式。在这里,不做赘述。另外,“怒火之袍”在这里的解说上有一点小错误,由于不在本文内容范围内,依旧不赘述。
附上“怒火之袍”的计算几何网址:http://dev.gameres.com/Program/Abstract/Geometry.htm