写了三个选择直线的函数不知道哪一个快(STL)

Question

为了不让你失去耐心，我尽量让代码简化，如果你没有时间看代码 
请直接转到最后一行，问题在那里。 
我已经将直线的每个点储存到vector容器中（我已经存好了， 
现在要选中它） 
这是第一个版本： 
bool CObject::CheckSelectLine(const POINT &pt1) 
{ 
if (P->empty())  return false; vector < POINT >::iterator it=P->begin(); for (; it!=P->end();++it) 
{ 
if ((*it).x==pt1.x||(*it).y==pt1.y) 
return true; 
} 
return false; 
} 
很简洁不是吗？P是类CObject中的一个成员变量,（你可以把它当成一个 
可以改变长度的数组或者链表利用迭代器it遍历容器， 
如果点的坐标有重合的就返回true，否则返回false。 
但是....如果这条直线有1000个点那就要循环1000次，而且每一次 
都要取出成员变量，我觉得这样肯定慢，因此我写了 
第二个版本： 
bool CObject::CheckSelectLine(const POINT &pt1) 
{ 
if (P->empty())  return false; 
        vector < POINT >::iterator Head=P->begin(); 
vector < POINT >::iterator Tail=P->end()-1; 
long  sx=(*Head).x;//start x 
long  sy=(*Head).y;//start y 
long  ex=(*Tail).x;//end  x 
long  ey=(*Tail).y;//end  y 
long  px=pt1.x; 
long  py=pt1.y; 
        long  vx=abs(ex-sx);//x轴矢量 
long  vy=abs(ey-sy);//y轴矢量 
        long  vpx=abs(px-sx); 
long  vpy=abs(py-sy); 
if (sx <=ex)//开始点在左边 
{ 
if (px <sx||px>ex)return false;//在区域以外 
goto level2; 
} 
else//if (sx>ex)//开始点在右边 
{ 
if (px <ex||px>sx)return false;//在区域以外 
goto level2; 
} 
level2: 
if (sy <=ey)//开始点在上边 
{ 
if (py <sy||py>ey)return false;//在区域以外 
goto level3; 
} 
else//if (sy>ey)开始点在下边 
{ 
if (py <ey||py>sy)return false;//在区域以外 
goto level3; 
} 
level3: 
if (vx>=vy)//近x轴 
{ 
if ((*(Head+vpx)).y==py)return true; 
} 
else//if(vx <vy)近Y轴 
{ 
if ((*(Head+vpy)).x==px)return true; 
} return false; 
} 
因为我储存直线的时候它的每一个点都是连续的，所以改进后的版本 
经过几次判断就可以了，虽然goto语句已经不提倡使用了但它确实 
能够减少代码的数量增加可读性，直线是用Bresenham算法储存的 
因此要考虑到是近X轴还是近Y轴。你可能会注意到函数开头时申请了 
很多变量，这纯粹是为了增加代码的可读性，但是每执行一次这个函数 
就要申请这么多变量我觉得有点浪费因此我写了可读性级差的第三个版本： 
bool CObject::CheckSelectLine(const POINT &pt1) 
{ 
if (P->empty()) 
{ 
return false; 
} 
vector < POINT >::iterator Head=P->begin(); 
vector < POINT >::iterator Tail=P->end()-1; 
/////////////////////////开始点在左边//////////////////////////// 
if ((*Head).x <=(*Tail).x) 
{ 
if (pt1.x <(*Head).x||pt1.x>(*Tail).x) 
return false;//在X轴区域以外 /////////////////////////开始点在上边//////////////////////////// 
if ((*Head).y <=(*Tail).y)///////// 
{ 
if (pt1.y <(*Head).y||pt1.y>(*Tail).y)//在Y轴区域以外 
return false; if ((*Tail).x-(*Head).x>=(*Tail).y-(*Head).y)//近X轴 
{ 
if ((*(Head+(pt1.x-(*Head).x))).y==pt1.y) 
return true; 
} 
else//近Y轴 
{ 
if ((*(Head+(pt1.y-(*Head).y))).x==pt1.x) 
return true; 
} } 
/////////////////////////开始点在下边//////////////////////////// 
else// 
{ 
if (pt1.y <(*Tail).y||pt1.y>(*Head).y)//在Y轴区域以外 
return false; if ((*Tail).x-(*Head).x>=(*Head).y-(*Tail).y)//近x轴 
{ 
if ((*(Head+(pt1.x-(*Head).x))).y==pt1.y) 
return true; 
} 
else//近Y轴 
{ 
if ((*(Head+((*Head).y-pt1.y))).x==pt1.x) 
return true; 
} 
} 
} 
/////////////////////////开始点在右边//////////////////////////// 
else//if ((*Head).x>(*Tail).x) 
{ 
if (pt1.x <(*Tail).x||pt1.x>(*Head).x) 
return false;//在X轴区域以外 /////////////////////////开始点在上边//////////////////////////// 
if ((*Head).y <=(*Tail).y)///////// 
{ 
if (pt1.y <(*Head).y||pt1.y>(*Tail).y)//在Y轴区域以外 
return false; if ((*Head).x-(*Tail).x>=(*Tail).y-(*Head).y)//近X轴 
{ 
if ((*(Head+((*Head).x)-pt1.x)).y==pt1.y) 
return true; 
} 
else//近Y轴 
{ 
if ((*(Head+(pt1.y-(*Head).y))).x==pt1.x) 
return true; 
} } 
/////////////////////////开始点在下边//////////////////////////// 
else// 
{ 
if (pt1.y <(*Tail).y||pt1.y>(*Head).y)//在Y轴区域以外 
return false; if ((*Head).x-(*Tail).x>=(*Head).y-(*Tail).y)//近x轴 
{ 
if ((*(Head+((*Head).x-pt1.x))).y==pt1.y) 
return true; 
} 
else//近Y轴 
{ 
if ((*(Head+((*Head).y-pt1.y))).x==pt1.x) 
return true; 
} 
        }   
} 
return false; 
} 
写完了之后连我自己看了都迷糊，（其实我是先写的第三个版本） 
我不知道第三个版本和第二个版本哪一个效率高这是问题的所在， 
也就是说利用申请的临时变量来减少取成员变量所耗费的时钟周期 
值不值得，请教高人。 

Answer 1

我又改进了一下：
bool CObject::CheckSelectLine(const POINT &pt1)
{
if (P->empty()) return false; vector< POINT >::iterator Head=P->begin();
vector< POINT >::iterator Tail=P->end()-1;
long  sx=(*Head).x;//start x
long  sy=(*Head).y;//start y
long  ex=(*Tail).x;//end   x
long  ey=(*Tail).y;//end   y
long  px=pt1.x;
long  py=pt1.y;    //判断是否在矩形区域以外
if (px<min(ex,sx)||px>max(ex,sx))return false;
if (py<min(ey,sy)||py>max(ey,sy))return false;

if (abs(ex-sx)>=abs(ey-sy))//近x轴
{
if ((*(Head+abs(px-sx))).y==py)return true;
}
else//近Y轴
{
if ((*(Head+abs(py-sy))).x==px)return true;
}

return false;
}

Answer 2

另外我非常怀疑你的计算结果，这个if ((*it).x==pt1.x||(*it).y==pt1.y) 
最起码应当是if ((*it).x==pt1.x&&(*it).y==pt1.y) 或者是if (（(*it).x-pt1.x）<0.0001&&((*it).y-pt1.y)<0.0001) 

Answer 3

感谢楼上的支持，if ((*it).x==pt1.x||(*it).y==pt1.y) 
的作用是无论X点重合或者Y点重合都代表选中了。
另外我刚说了如果直线的象素超过1000个的话就算折中也需要判断500次
每次都要执行if ((*it).x==pt1.x||(*it).y==pt1.y) 
如果屏幕上同时出现100条这样的直线就要判断5000次，是不是有点太慢了？

Answer 4

假设这是平面上的直线，你用某个画线的算法（具体能用哪些算法我也不记得了:D）来绘制这条直线，并存储了要绘制的点。 
首先，对这些点按照x,y大小进行排序;然后，进行二分查找。 最后，这条语句if ((*it).x==pt1.x||(*it).y==pt1.y) 的操作手感不好:D

Answer 5

求斜率不错，但要想不使用乘法还是考判断。
你说的没错1000是最差的情况，平均下来也是500次，
也就是要判断500次，我改进的那一个可以看出最多10次（max也算一次）
另外就是申请临时变量的损耗了，那个看起来很繁琐的也是10次
这几个函数都没有错误我测试过多次了。