线段的基本问题

线段的基本问题

两条线段恰有唯一一个不是端点的公共点,称为规范相交. 对于一对线段,由于计算机计算的误差,如果使用解析几何的方法,那么运算效率比较低,并且误差可能会比较大,所以我们需要使用一种全新的计算方法——计算几何。

两个向量的左右手螺旋

  我们先定义一种运算——叉积。(x1,y1)×(x2,y2)＝x1*y2-x2*y1;
  我们发现如果叉积为正，则第二个向量为第一个向量的右手系方向（逆时针），为负则为左手系方向.

判断线段规范相交   

  我们发现如果两条线段相交时，每条线段的两个端点都在另一条线段的两侧，所以我们可以利用这一点判断规范相交。
  对于线段ab和线段cd，如果我们发现向量ad×cd和bd×cd正负情况相反，且向量cb×ab和bdb×ab正负情况相反，那么线段规范相交

浮点误差处理

  因为浮点误差的存在，使得在结果非常接近0的时候我们将其视为0，并用1，-1表示正负，所以需要设计一个三出口函数。

参考程序

function dblcmp(x:double):double;          {三出口函数}
begin
    if abs(x)<10e-10 then sgn:=0
    else if x>0 then sgn:=1
    else sgn:=-1;
end;

function crossdet(x1,y1,x2,y2:double):double;	{叉积}
begin
	det:=dblcmp(x1*y2-x2*y1);
end;

function cross(a,b,c:node):double;      	{判断a是否在bc的哪一侧,或在bc直线上}  
begin
	cross:=crossdet(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);
end.

{狭义线段相交=每条线段的两个端点都在另一条线段的异侧}
function segcross(a,b,c,d:node):boolean;
begin
	segcross:=(dlbcmp(cross(a,c,d))*dlbcmp(cross(b,c,d))=-1)
		   and(dlbcmp(cross(c,a,b))*dlbcmp(cross(d,a,c))=-1);	
end;