我试图找出如何遍历一个2.5D网格以有效的方式。网格本身是2D的，但在该网格中的每个单元具有一个浮动最小/最大高度。线路穿越由两个3D浮点坐标定义。我想停下来遍历行，如果进入的z值的范围/退出网格单元格不与最小/最大高度为细胞重叠。

我目前使用的二维DDA算法通过网格单元遍历顺序（见图片），但我不知道如何计算Z值，当达到每个网格单元。如果我能做到这一点，我可以进入/离开对最小​​/最大高度的单元格的单元测试时，z值。

有没有办法修改这个算法，允许在每个网格单元输入来计算Z'还是有更好的遍历算法，让我这样做？

下面是目前的code我使用：

 无效网:: TraceGrid（POINT3＆LT;浮动＆GT;＆安培;常量开始，POINT3＆LT;浮动＆GT;＆安培; const的结束，GridCallback回调）
{
    //计算和规范2D方向向量
    点2＆LT;浮动＆GT;方向=年底启动;
    浮长= direction.getLength（）;
    方向/ =长度;

    使用网格分辨率//计算增量
    点2＆LT;浮动＆GT;三角洲（m_gridresolution /晶圆厂（direction.x），m_gridresolution /晶圆厂（direction.y））;

    //计算开始/结束点，在格
    点2＆LT; INT＆GT; startGrid（（int）的（start.x / m_gridresolution），（int）的（start.y / m_gridresolution））;
    点2＆LT; INT＆GT; endGrid（（int）的（end.x / m_gridresolution），（int）的（end.y / m_gridresolution））;
    点2＆LT; INT＆GT; currentGrid = startGrid;

    //计算基于所述方向向量在网格的方向的步骤
    点2＆LT; INT＆GT;步骤（direction.x＆GT; = 0 1：-1，direction.y＆GT; = 0 1：α-1）;

    //计算从开始到下一个网格单元的距离
    点2＆LT;浮动＆GT; currentDistance（（（step.x大于0 start.x：start.x + 1）* m_gridresolution-start.x）/direction.x，（（step.y大于0 start.y：？start.y + 1）的* m_gridresolution-start.y）/direction.y）;

    而（真）
    {
        //传递currentGrid回调
        浮Z = 0.0; //需要计算Z值以某种方式
        布尔BSTOP =回调（currentGrid，Z）;

        //检查回调要停止或结束网格单元达到
        如果（BSTOP || currentGrid == endGrid）打破;

        //遍历到下一个网格单元
        如果（currentDistance.x＆LT; currentDistance.y）{
            currentDistance.x + = delta.x;
            currentGrid.x + = step.x;
        } 其他 {
            currentDistance.y + = delta.y;
            currentGrid.y + = step.y;
        }
    }
}
 

解决方案

我想出了一个好办法做到这一点。加入该功能的启动：

 浮法fzoffset = end.z-start.z;
点2＆LT;浮动＆GT; deltaZ（fzoffset /晶圆厂（end.x-start.x），fzoffset /晶圆厂（end.y-start.y））;
点2＆LT;浮动＆GT; currentOffset（（step.x大于0 start.x：start.x + 1）* m_gridresolution-start.x，（step.y大于0 start.y：？start.y + 1）* m_gridresolution-start.y） ;
 

在那里currentDistance.x / .Y递增循环，增加：

  currentOffset.x + = m_gridresolution; //在x轴步进时
currentOffset.y + = m_gridresolution; //在y轴步进时
 

然后计算ž在每一个步骤：

  Z = currentOffset.x * deltaZ.x + start.z; //在x轴步进时
Z = currentOffset.y * deltaZ.y + start.z; //在y轴步进时
 

I'm trying to figure out how to traverse a 2.5D grid in an efficient manner. The grid itself is 2D, but each cell in the grid has a float min/max height. The line to traverse is defined by two 3D floating point coordinates. I want to stop traversing the line if the range of z values between entering/exiting a grid cell doesn't overlap with the min/max height for that cell.

I'm currently using the 2D DDA algorithm to traverse through the grid cells in order(see picture), but I'm not sure how to calculate the z value when each grid cell is reached. If I could do that, I could test the z value when entering/leaving the cell against the min/max height for the cell.

Is there a way to modify this algorithm that allows z to be calculated when each grid cell is entered? Or is there a better traversal algorithm that would allow me to do that?

Here's the current code I'm using:

void Grid::TraceGrid(Point3<float>& const start, Point3<float>& const end, GridCallback callback )
{
    // calculate and normalize the 2D direction vector
    Point2<float> direction=end-start;
    float length=direction.getLength( );
    direction/=length;

    // calculate delta using the grid resolution
    Point2<float> delta(m_gridresolution/fabs(direction.x), m_gridresolution/fabs(direction.y));

    // calculate the starting/ending points in the grid
    Point2<int> startGrid((int)(start.x/m_gridresolution), (int)(start.y/m_gridresolution));
    Point2<int> endGrid((int)(end.x/m_gridresolution), (int)(end.y/m_gridresolution));
    Point2<int> currentGrid=startGrid;

    // calculate the direction step in the grid based on the direction vector
    Point2<int> step(direction.x>=0?1:-1, direction.y>=0?1:-1);

    // calculate the distance to the next grid cell from the start
    Point2<float> currentDistance(((step.x>0?start.x:start.x+1)*m_gridresolution-start.x)/direction.x, ((step.y>0?start.y:start.y+1)*m_gridresolution-start.y)/direction.y);

    while(true)
    {
        // pass currentGrid to the callback
        float z = 0.0f;     // need to calculate z value somehow
        bool bstop=callback(currentGrid, z);

        // check if the callback wants to stop or the end grid cell was reached
        if(bstop||currentGrid==endGrid) break;

        // traverse to the next grid cell
        if(currentDistance.x<currentDistance.y) {
            currentDistance.x+=delta.x;
            currentGrid.x+=step.x;
        } else {
            currentDistance.y+=delta.y;
            currentGrid.y+=step.y;
        }
    }
}

I figured out a good way to do it. Add to the start of the function:

float fzoffset=end.z-start.z;
Point2<float> deltaZ(fzoffset/fabs(end.x-start.x), fzoffset/fabs(end.y-start.y));
Point2<float> currentOffset((step.x>0?start.x:start.x+1)*m_gridresolution-start.x, (step.y>0?start.y:start.y+1)*m_gridresolution-start.y);

Inside the loop where currentDistance.x/.y are incremented, add:

currentOffset.x+=m_gridresolution;  //When stepping in the x axis
currentOffset.y+=m_gridresolution;  //When stepping in the y axis

Then to calculate z at each step:

z=currentOffset.x*deltaZ.x+start.z;  //When stepping in the x axis
z=currentOffset.y*deltaZ.y+start.z;  //When stepping in the y axis