零、代码来源
Point in Polygon Strategies的网格法一节。
一、源代码
原作者大名已经在源代码中。
/* Faster Line Segment Intersection */
/* Franklin Antonio */
/* return values */
#define DONT_INTERSECT 0
#define DO_INTERSECT 1
#define PARALLEL 2
/* The SAME_SIGNS macro assumes arithmetic where the exclusive-or */
/* operation will work on sign bits. This works for twos-complement,*/
/* and most other machine arithmetic. */
#define SAME_SIGNS( a, b ) \
(((long) ((unsigned long) a ^ (unsigned long) b)) >= 0 )
/* The use of some short working variables allows this code to run */
/* faster on 16-bit computers, but is not essential. It should not */
/* affect operation on 32-bit computers. The short working variables*/
/* to not restrict the range of valid input values, as these were */
/* constrained in any case, due to algorithm restrictions. */
int lines_intersect(x1,y1,x2,y2,x3,y3,x4,y4,x,y)
long x1,y1,x2,y2,x3,y3,x4,y4,*x,*y;
{
long Ax,Bx,Cx,Ay,By,Cy,d,e,f,num,offset;
short x1lo,x1hi,y1lo,y1hi;
Ax = x2-x1;
Bx = x3-x4;
if(Ax<0) { /* X bound box test*/
x1lo=(short)x2; x1hi=(short)x1;
} else {
x1hi=(short)x2; x1lo=(short)x1;
}
if(Bx>0) {
if(x1hi < (short)x4 || (short)x3 < x1lo) return DONT_INTERSECT;
} else {
if(x1hi < (short)x3 || (short)x4 < x1lo) return DONT_INTERSECT;
}
Ay = y2-y1;
By = y3-y4;
if(Ay<0) { /* Y bound box test*/
y1lo=(short)y2; y1hi=(short)y1;
} else {
y1hi=(short)y2; y1lo=(short)y1;
}
if(By>0) {
if(y1hi < (short)y4 || (short)y3 < y1lo) return DONT_INTERSECT;
} else {
if(y1hi < (short)y3 || (short)y4 < y1lo) return DONT_INTERSECT;
}
Cx = x1-x3;
Cy = y1-y3;
f = Ay*Bx - Ax*By; /* both denominator*/
if(f==0) return PARALLEL;
d = By*Cx - Bx*Cy; /* alpha numerator*/
if(f>0) { /* alpha tests*/
if(d<0 || d>f) return DONT_INTERSECT;
} else {
if(d>0 || d<f) return DONT_INTERSECT;
}
e = Ax*Cy - Ay*Cx; /* beta numerator*/
if(f>0) { /* beta tests*/
if(e<0 || e>f) return DONT_INTERSECT;
} else {
if(e>0 || e<f) return DONT_INTERSECT;
}
/*compute intersection coordinates*/
num = d*Ax; /* numerator */
offset = SAME_SIGNS(num,f) ? f/2 : -f/2; /* round direction*/
*x = x1 + (num+offset) / f; /* intersection x */
num = d*Ay;
offset = SAME_SIGNS(num,f) ? f/2 : -f/2;
*y = y1 + (num+offset) / f; /* intersection y */
return DO_INTERSECT;
}
二、尝试理解
/* Faster Line Segment Intersection */
/* 更快的线段相交 */
/* Franklin Antonio */
/* return values */
/* 返回值*/
#define DONT_INTERSECT 0
#define DO_INTERSECT 1
#define PARALLEL 2
/* The SAME_SIGNS macro assumes arithmetic where the exclusive-or */
/* operation will work on sign bits. This works for twos-complement,*/
/* and most other machine arithmetic. */
/*SAME_SIGNS宏假定算术运算，其中异或操作将处理符号位。这适用于2补码和大多数其他机器算术。*/
/*这操作感觉有一点厉害*/
#define SAME_SIGNS( a, b ) \
(((long) ((unsigned long) a ^ (unsigned long) b)) >= 0 )
/* The use of some short working variables allows this code to run */
/* faster on 16-bit computers, but is not essential. It should not */
/* affect operation on 32-bit computers. The short working variables*/
/* to not restrict the range of valid input values, as these were */
/* constrained in any case, due to algorithm restrictions. */
/*使用一些短的工作变量可以让这段代码在16位计算机上运行得更快，但这并不是必需的。它不应该影响32位计算机上的操作。短工作变量不限制有效输入值的范围，因为这些值在任何情况下都受到算法限制。*/
int lines_intersect(x1,y1,x2,y2,x3,y3,x4,y4,x,y)
long x1,y1,x2,y2,x3,y3,x4,y4,*x,*y;
{
long Ax,Bx,Cx,Ay,By,Cy,d,e,f,num,offset;
short x1lo,x1hi,y1lo,y1hi;
/*这儿开始大概在快排*/
Ax = x2-x1;
Bx = x3-x4;
if(Ax<0) { /* X bound box test*/
x1lo=(short)x2; x1hi=(short)x1;
} else {
x1hi=(short)x2; x1lo=(short)x1;
}
if(Bx>0) {
if(x1hi < (short)x4 || (short)x3 < x1lo) return DONT_INTERSECT;
} else {
if(x1hi < (short)x3 || (short)x4 < x1lo) return DONT_INTERSECT;
}
Ay = y2-y1;
By = y3-y4;
if(Ay<0) { /* Y bound box test*/
y1lo=(short)y2; y1hi=(short)y1;
} else {
y1hi=(short)y2; y1lo=(short)y1;
}
if(By>0) {
if(y1hi < (short)y4 || (short)y3 < y1lo) return DONT_INTERSECT;
} else {
if(y1hi < (short)y3 || (short)y4 < y1lo) return DONT_INTERSECT;
}
/*这儿开始大概在做跨立实验*/
Cx = x1-x3;
Cy = y1-y3;
f = Ay*Bx - Ax*By; /* both denominator*/
//叉积为零则两条线段平行
if(f==0) return PARALLEL;
d = By*Cx - Bx*Cy; /* alpha numerator*/
if(f>0) { /* alpha tests*/
if(d<0 || d>f) return DONT_INTERSECT;
} else {
if(d>0 || d<f) return DONT_INTERSECT;
}
e = Ax*Cy - Ay*Cx; /* beta numerator*/
if(f>0) { /* beta tests*/
if(e<0 || e>f) return DONT_INTERSECT;
} else {
if(e>0 || e<f) return DONT_INTERSECT;
}
/*compute intersection coordinates*/
/*计算交点坐标*/
/*这下面的都没有懂*/
/*总算看懂了，计算alpha和beta的公式是以同底不同面积的三角形面积之比来算比例，f/2是用来取整的，不是用来参与计算的*/
num = d*Ax; /* numerator */
offset = SAME_SIGNS(num,f) ? f/2 : -f/2; /* round direction*/
*x = x1 + (num+offset) / f; /* intersection x */
num = d*Ay;
offset = SAME_SIGNS(num,f) ? f/2 : -f/2;
*y = y1 + (num+offset) / f; /* intersection y */
return DO_INTERSECT;
}
网友评论