在3d笛卡尔图中用直线划分网格线的所有点

I'm using PHP and have generated a 3D cartesian coordinate system (x,y,z). I want to travel a straight line between two points. I call each 1x1x1 square a sector identified by the adjacent lattice point closest to the origin. I'm trying to identify each sector that the line segment passes through.

The following post was helpful, but since it deals with 2D systems, wasn't exactly what I needed.

PHP Find Coordinates between two points

Thanks

Jason

I'd suggest taking a look at a simple DDA algorithm, which allows you to efficiently determine which cells of a regular grid a line segment passes through. This article describes it quite well and also provides a sample implementation:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.3443&rep=rep1&type=pdf

You may want to accomodate the termination condition for the outer loop, since the paper considers rays which, different to your case, don't have a specific termination point other than the grid boundaries.

I'm no expert, but one (stupid?) approach would be to write a function which finds the 'middle point' of two coordinates ((x1 + x2)/2, (y1 + y2)/2, (z1 + z2)/2), then round them to get a real coordinate. Now you could find the whole 'line' by just recursively apply the function to all legs until there's no new middle point.

func findMiddlePoint(a, b)
  return new Point(
        ((a.x + b.x).abs / 2).round, 
        ((a.y + b.y).abs / 2).round, 
        ((a.z + b.z).abs / 2).round)
func findLine(points, a, b)
  if a == b # no new points
    return 
  middle = findMiddlePoint(a, b)
  points.add(middle)
  findLine(points, a, middle)
  findLine(points, middle, b)

func findFullLine(a, b)
  points = []
  points.add(a)
  findLine(points, a, b)
  opints.add(b)
  return points 

I am not an expert for the PHP, but this is the same solution for the 3d system:

// Points
$p1 = array(
    'x' => 50,
    'y' => 50,
    'z' => 20,

);

$p2 = array(
    'x' => 234,
    'y' => 177,
    'z' => 100
);

// Work out distances
$pxd = $p2['x'] - $p1['x'];
$pyd = $p2['y'] - $p1['y'];
$pzd = $p2['z'] - $p1['z'];
// Find out steps
$steps = max(abs($pxd), abs($pyd), abs($pzd));

$coords = array();

for ($i = 0; $i < $steps; ++ $i) {
    $coords[] = array(
        'x' => round($p1['x'] += $pxd / $steps),
        'y' => round($p1['y'] += $pyd / $steps),
        'z' => round($p1['z'] += $pzd / $steps)
    );
}

print_r($coords);