求算法（喜欢挑战的勇士入！！！）

Question

有一条由离散的点（每相邻2个点是4邻居相连的）组成的曲线L；
任给一个直线的方程，要判断直线和L的交点。要求：
穷举法除外

Answer 1

1、数字图像都是以离散方式存储的。
一张2值图片0表示白色1表示黑色，
那么下面这个矩阵就是一个曲线(十字形）的离散表示形式。  00100
00100
11111
00100
00100  图12、什么是4邻居呢？已知点A,标号为B的那些点都是A的4邻居（上下左右，一共4个）00100
00B00
1BAB1
00B00
00100 图2例如：图1中第一行第3列的点（1，3）与（2，3）就是4邻居相连的；随便再举个例子：（3，3）与（3，2）、（3，4）都是4邻接（4邻居相连）的.....//////////////////////////////////////////////////////////我现在的问题是有这么一个离散方式表示的曲线（图1中可以看着有2条离散的曲线：横着和竖着各一条），任给一个直线的方程，要判断直线和L的交点。/////////////////////////////////////////////////////////
如果只有少数几个点，当然可以用穷举法；但图像很大用穷举法就
没有意义了，而且，我想既然离散的曲线是相连的，那么就一定有
规律可寻。让我们一起挑战吧！！！

Answer 2

只能扫描直线 上的所有点把n*n 的图复杂度大概是 O(n) 
还可以接受把没想出什么好办法 仅给楼主参考

Answer 3

谢谢大家的发言。既然参加者多了，我把分数再提高一倍！如果只有一个那样的直线方程，用遍历的方法也可以；
关键是我有k*n个这样的直线(假设曲线L上有n个离散的点），对每一个直线都要得到和该离散曲线的交点。补充一下：这k*n个直线是这样产生的：平面上有不在曲线L上的另外n个不重合点，过每个点做k条直线。（可以理解为有n个直线族)///////////////////////////////////////////////////////
我目前的方法是将每个直线族中的直线按斜率从小到大排列，先从端点遍历斜率最小的，找到交点后，从该交点出发继续遍历斜率稍大的直线....
然后再第2个直线族.....
......
///////////////////////////////////////////////////////但我还是觉得能再简化，因为我一直深信好的方法是没有穷尽的！！！

Answer 4

回复人： I_Love_CPP(我爱C++) ( ) 信誉：100  2004-11-14 9:56:41  得分: 0  ------------------------------------------------------------------------
关键是我有k*n个这样的直线(假设曲线L上有n个离散的点），对每一个直线都要得到和该离散曲线的交点。
补充一下：这k*n个直线是这样产生的：平面上有不在曲线L上的另外n个不重合点，过每个点做k条直线。（可以理解为有n个直线族)------------------------------------------------------------------------
////////////////////////////////////////////////////////////////////////////////(假设曲线L上有n个离散的点）？？？这个假设有点不理解
是不是直线族数和曲线L上的离散点数一样多？

Answer 5

不过还有更快的方法， 首先把曲线离散成直线段 d1,d2 ... dm，然后求直线和直线的交点，这个只要计算  k * n * m 次的交点就可以了

Answer 6

Re:handwolf(初学者):
   要算出交点坐标的。
   我是假设离散曲线上有n个点，过每个定点的直线族中的直线数目为k.
   这么假设是为了方便叙述：
  其实就是有一条离散的曲线，另外平面上有很多定点，过每个定点画直线，求这些直线和曲线的交点
  
  我把我的算法也提供出来，就是想有一个比我的更好的算法；因为我不算聪明，知识也不丰富，所以一定有人比我的方法更好的。
  
Re:tiaoci(我挑刺，我快乐) :   你确定你说的是算法吗？！你真幽默！！！
  

Answer 7

Re: ghl200(小面人) ( )曲线上的点很好求，用搜索算法就可以得到；
另外，先考虑非交叉的。

Answer 8

我的程序有一部分是和你相同的，不知道对你有没有帮助，现在贴出来。
long m,n,e,q,s,t;
long d0,d1,d2;
int a;//记录等级线数组最后一个不为0的元素下标
CRect rect1,rect2;
d0=20;
if(LineDot[i][0].x!=0)
{
m=LineDot[i][1].x-LineDot[i][0].x;
n=LineDot[i][1].y-LineDot[i][0].y;
e=LineDot[i][3].x-LineDot[i][2].x;
q=LineDot[i][3].y-LineDot[i][2].y;
if(LineDot[i][1].x>=LineDot[i][0].x)
{
rect1.SetRect(LineDot[i][0].x,LineDot[i][0].y,
LineDot[i][1].x,LineDot[i][1].y);
}
else
{
rect1.SetRect(LineDot[i][1].x,LineDot[i][0].y,
LineDot[i][0].x,LineDot[i][1].y);
}
if(LineDot[i][3].x>=LineDot[i][2].x)
{
rect2.SetRect(LineDot[i][2].x,LineDot[i][2].y,
LineDot[i][3].x,LineDot[i][3].y);
}
else
{
rect2.SetRect(LineDot[i][3].x,LineDot[i][2].y,
LineDot[i][2].x,LineDot[i][3].y);
}
}
else
{
break;
}
for(int j=0;j<100;j++)
{
if(arrayLevel[i][j].x!=0)
{
a=j;
}
else
{
break;
}
}
//求直线和边界的交点
for(j=0;j<4000;j++)
{
if(arrayDot[j].x!=0)
{
if(rect1.PtInRect(arrayDot[j]))
{
s=arrayDot[j].x-LineDot[i][0].x;
t=arrayDot[j].y-LineDot[i][0].y;
d1=abs(m*t-n*s);
if(d1<=d0)
{
arrayLevel[i][0]=arrayDot[j];
//记录交点坐标
IntersectDot[i][0]=arrayDot[j];
//InterDot1=j;
}
}
if(rect2.PtInRect(arrayDot[j]))
{
s=arrayDot[j].x-LineDot[i][2].x;
t=arrayDot[j].y-LineDot[i][2].y;
d2=abs(e*t-q*s);
if(d2<=d0)
{
arrayLevel[i][a]=arrayDot[j];
IntersectDot[i][1]=arrayDot[j];
//InterDot2=j;
}
}

}
else
{
break;
}
}

}