在方格地图中根据两像素点

第一种为根据Bresenham画线算法修改的的算法。源码如下:
void GenerateLine_Bresenham(sCoordinate& kStart, sCoordinate& kEnd, list<sCoordinate>& outList){ outList.push_back(kStart); int nX1 = kStart.x; int nY1 = kStart.y; int nX2 = kEnd.x; int nY2 = kEnd.y; int nDx = abs(nX2 - nX1); int nDy = abs(nY2 - nY1); bool bYDirection = false; if (nDx < nDy) { // y direction is step direction SwapInt(nX1, nY1); SwapInt(nDx, nDy); SwapInt(nX2, nY2); bYDirection = true; } // calculate the x, y increment int nIncreX = (nX2 - nX1) > 0 ? 1 : -1; int nIncreY = (nY2 - nY1) > 0 ? 1 : -1; int nCurX = nX1; int nCurY = nY1; int nTwoDY = 2 * nDy; int nTwoDyDx = 2 * (nDy - nDx); int nIniD = 2 * nDy - nDx; while (nCurX != nX2) // nCurX == nX2 can not use in bitmap { if(nIniD < 0) { nIniD += nTwoDY; // y value keep current state } else { nCurY += nIncreY; nIniD += nTwoDyDx; } if (bYDirection) { sCoordinate kC; kC.x = static_cast<COORDTYPE>(nCurY); kC.y = static_cast<COORDTYPE>(nCurX); outList.push_back(kC); } else { sCoordinate kC; kC.x = static_cast<COORDTYPE>(nCurX); kC.y = static_cast<COORDTYPE>(nCurY); outList.push_back(kC); } nCurX += nIncreX; } outList.push_back(kEnd);}
该算法比较快速,但精确度不高,有时开始节点与结束节点的位置比较近的话,中间会有格子被忽略掉。

2. 根据直线与矩形的相交判断算法进行求取。
根据两个点的连线,可以获取以这条线为对角线的矩形,然后获取所有在矩形内部的方格,依次判断这些方格是否与直线相交,如果是,则是所求结果的其中一个方格。代码如下:

void GenerateLine_LineCrossRect(sCoordinate* pStart,sCoordinate* pEnd,list<sCoordinate>&outList)
{
if(!pStart
|| !pEnd)
{
return ;
}

// 0.计算起始节点与结束节点的像素坐标
int nLineSX= pStart->x *sBaseNode::WIDTH_BY_PIXEL +sBaseNode::WIDTH_BY_PIXEL/2; //该宏为方格的宽度
int nLineSY= pStart->y *sBaseNode::HEIGHT_BY_PIXEL +sBaseNode::HEIGHT_BY_PIXEL/2; // 该宏为方格的高度
int nLineEX= pEnd->x *sBaseNode::WIDTH_BY_PIXEL +sBaseNode::WIDTH_BY_PIXEL/2;
int nLineEY= pEnd->y *sBaseNode::HEIGHT_BY_PIXEL +sBaseNode::HEIGHT_BY_PIXEL/2;

COORDTYPEmaxX = 0;
COORDTYPEmaxY = 0;
COORDTYPEminX = 0;
COORDTYPEminY = 0;

if(pStart->x <pEnd->x)
{
minX = pStart->x;
maxX = pEnd->x;
}
else
{
minX = pEnd->x;
maxX = pStart->x;
}

if(pStart->y <pEnd->y)
{
minY = pStart->y;
maxY = pEnd->y;
}
else
{
minY = pEnd->y;
maxY = pStart->y;
}

sCoordinate tempC;
RECT kTempRect;
for(COORDTYPE x = minX; x <= maxX; ++x)
{
for (COORDTYPE y = minY; y <= maxY; ++y)
{
tempC.x = x;
tempC.y = y;

kTempRect.left = tempC.x *sBaseNode::WIDTH_BY_PIXEL;
kTempRect.top = tempC.y *sBaseNode::HEIGHT_BY_PIXEL;
kTempRect.right = kTempRect.left +sBaseNode::WIDTH_BY_PIXEL;
kTempRect.bottom = kTempRect.top +sBaseNode::HEIGHT_BY_PIXEL;

if(RayRectIntersect(nLineSX,nLineSY,nLineEX,nLineEY,kTempRect)) // 该函数为检测直线与矩形是否相交的判断
{
outList.push_back(tempC);
}
}
}
}

// 检测直线与矩形是否相交
bool RayRectIntersect(int startX, int startY, int endX, int endY,const RECT& rect)
{
int a =startY – endY;
int b = endX- startX;
int c =startX*endY-endX*startY;
int xleft =rect.left;
int ytop =rect.top;
int xr =rect.right;
int yb =rect.bottom;

if((a*xleft+b*ytop+c>=0&&a*xr+b*yb+c<=0)||
(a*xleft+b*ytop+c<=0&&a*xr+b*yb+c>=0)||
(a*xleft+b*yb+c>=0&&a*xr+b*ytop+c<=0)||
(a*xleft+b*yb+c<=0&& a*xr+b*ytop+c>=0)){
if(xleft > xr)
swap(xleft,xr);
if(ytop < yb)
swap(ytop,yb);
if( (startX<xleft &&endX<xleft) ||
(startX>xr &&endX>xr) ||
(startY>ytop &&endY>ytop) ||
(startY<yb &&endY<yb) )
{
return false;
}
else
{
return true;
}
}
else
{
return false;
}
}

此算法较Bresenham速度慢很多,这是很明显的,尤其如果两个点构成的矩形跨度很大的话,速度就会相当明显的慢下来。
可以这样考虑,如果要遍历的方格数没有那么多的话就好了,所以我又搞了下面这个算法,但这个算法属于鸡肋了,因为速度会更慢,不建议使用,此处贴出代码仅供参考:

void GenerateLine_LineCrossRectEx(sCoordinate&kStart, sCoordinate& kEnd,list<sCoordinate>&outList)
{
// 0.是不是同一直线上,如果是就简单的判断好了,不用往下走了
if (kStart.y== kEnd.y)
{
SameYAxisProcess(kStart, kEnd,outList); //同Y轴处理函数
return ;
}
if (kStart.x== kEnd.x)
&
#123;
SameXAxisProcess(kStart, kEnd,outList); // 同X轴处理函数
return;
}

// 1.求出两个节点的中心点坐标
floatnStartX = static_cast<float>(kStart.x* sBaseNode::WIDTH_BY_PIXEL +sBaseNode::WIDTH_BY_PIXEL/2);
floatnStartY = static_cast<float>(kStart.y* sBaseNode::HEIGHT_BY_PIXEL +sBaseNode::HEIGHT_BY_PIXEL/2);
float nEndX= static_cast<float>(kEnd.x *sBaseNode::WIDTH_BY_PIXEL +sBaseNode::WIDTH_BY_PIXEL/2);
float nEndY= static_cast<float>(kEnd.y *sBaseNode::HEIGHT_BY_PIXEL +sBaseNode::HEIGHT_BY_PIXEL/2);
// 2.根据这两个点的坐标求出直线方程。y = ax + b;
float a = 0,b = 0;
GenerateFunc(a, nStartY, nEndY, nStartX, nEndX,b); // 计算出a,b的值

// 3.获取x,y的像素取值范围
int nMinX =static_cast<int>((nStartX> nEndX ? nEndX : nStartX) -sBaseNode::WIDTH_BY_PIXEL/2);
int nMaxX =static_cast<int>((nStartX> nEndX ? nStartX : nEndX) +sBaseNode::WIDTH_BY_PIXEL/2);
int nMinY =static_cast<int>((nStartY> nEndY ? nEndY : nStartY) -sBaseNode::WIDTH_BY_PIXEL/2);
int nMaxY =static_cast<int>((nStartY> nEndY ? nStartY : nEndY) +sBaseNode::WIDTH_BY_PIXEL/2);
// 4.获取x的所有取值
vector<int> kXValueList;
for (int nX= nMinX; nX <= nMaxX; nX +=sBaseNode::WIDTH_BY_PIXEL)
{
kXValueList.push_back(nX);
}
// 5.将X的所有取值带入方程,保存所有Y的取值
vector<int> kYValueList;
GenerateYValue(kXValueList, a, b, nMinY, nMaxY,kYValueList); //根据直线方程,与已知的X值,请求所有的Y值

// 6.对应于每个X值,获取y的取值,并与对应的x组成的所有坐标,既要检查的直线穿过的节点
if(kXValueList.size() == 1)
{
Process(); // 在此省略此种情况的代码了
}
else
{
sCoordinate kCoord;
vector<int>::iteratorxInter =kXValueList.begin();
vector<int>::iteratoryInter =kYValueList.begin();
int nXValueSize = kXValueList.size() – 1;
for (int i = 0; i < nXValueSize; ++i)
{
kCoord.x =static_cast<COORDTYPE>((*(xInter+i))/ sBaseNode::WIDTH_BY_PIXEL);
int nS = (*(yInter+i)) /sBaseNode::HEIGHT_BY_PIXEL;
int nE = (*(yInter+i+1)) /sBaseNode::HEIGHT_BY_PIXEL;
if (nS > nE)
{
int temp = nS;
nS = nE;
nE = temp;
}
for (int nValue = nS; nValue <= nE; ++nValue)
{
kCoord.y = nValue;
outList.push_back(kCoord);
}

}
}
}

此方法计算量比较大,所以虽然检测的方格数比第二种方法少,但速度反而会慢了很多。应该还有优化的余地的,但我还没有研究。

还是推荐使用Bresenham的方法,应该可以根据实际情况而改进一下。

发表评论

邮箱地址不会被公开。 必填项已用*标注

* Copy This Password *

* Type Or Paste Password Here *