两线段相交的相关算法
徐明龙
2013-01-24
前提：
1)
点的大小比较
a)
设
p1(x1,y1),p2(x2,y2)
b)
如果
x1 > x2
则
p1 > p2
c)
如果
x1 = x2
且
大小由
y1
与
y2
的关系决定
d)
如果
x1
则
p1
2)
线的大小比较
a)
设
L1(p1,p2),L2(p3,p4)
b)
如果
p1
则
L1
c)
如果
p1 = p3
则大小有
p2,p4
关系决定
d)
如果
p1 > p3
则
L1>L2
3)
线的约束，线
p1
始终小于
p2
且
p1 <> p2
算法：
1
)
获取线的直线斜率(
X
轴垂直时返回无穷大
,X
轴平行时为零。
)
(p2.y
–
p1.y)/(p2.x-p1.x)
2
)
判断点是否在线的直线上
a)2
中特殊情况需要先考虑，一直垂直于
X
轴，和平行于
X
轴。
如果垂直于
X
轴，则
p.x=p1.x
即可。
如果平行于
X
轴，则
p.y=p1.y
即可。
b)
其他情况根据点斜公式判断(
p.y-p1.y
)
=
斜率
*(p.x-p1.x)
3
)
判断点是否在线段上
.
a)
先判断点是否在线段的直线上。
b)
再判断点是否在线段的起始点与终止点之间。即(
p1
且
p
在
p1
—
>p2
的直线上，如果
p>=p1
且
p <=p2
则
p
必定在
p1
—
p2
的线段上。
)
4
)
两点的向量公式：
x=p1.x-p2.x
y=p1.y-p2.y
5
)
向量的叉积(即向量相乘
V1*V2
)
：
v1*v2=v1.x*v2.y-v1.y*v2.x
6
)
获取两线段相交的类型。方法如下：
a)
先判断是否端点相交的情况
端点相交有以下几种模式：
(
1
)
p3
在
p1
—
p2
的线段上，
p4
不在
p1
—
p2
的直线上
| 
转播
