杭州交通信息网2017初中数学课程标准:请教检测2个多边形相交的算法
来源：百度文库 编辑：杭州交通信息网 时间：2024/04/28 14:18:33
我自己写过一个，是基于线段相交算法的。这样就使得算法的复杂度增加。有没有更好的算法，能最大程度降低算法的复杂度。
楼下的算法有问题啊！如果两个矩形横竖跨越相交，你这个算法是检测不出来的
楼下的算法有问题啊！如果两个矩形横竖跨越相交，你这个算法是检测不出来的
设A多边形点子：
int npol;
float xp[npol],yp[npol];
设B多边形点子 NN 个，坐标：
float x[NN],y[NN];
做循环，判断B多边形有无任何一点落在A多边形中，有则相交或重叠:
for (i=0;i<NN;i++) {
调用pnpoly( npol, &xp[0], &yp[0],x[i],y[i]);
}
判断一点落在多边形中的子程序：
int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
int i, j, c = 0;
for (i = 0, j = npol-1; i < npol; j = i++) {
if ((((yp[i]<=y) && (y<yp[j])) ||
((yp[j]<=y) && (y<yp[i]))) &&
(x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
c = !c;
}
return c;
}