PHP Find Coordinates between two points

simple question here. Lets say I have two points:

point 1

x = 0
y = 0


point 2

x = 10
y = 10

How would i find out all the coordinates开发者_开发百科 inbetween that programmatically, assuming there is a strait line between two points... so the above example would return:

0,0
1,1
2,2
3,3
...
8,8
9,9
10,10

Thanks :)

You need to find the slope of the line first:

m = (y1 - y2) / (x1 - x2)

Then you need to find the equation of the line:

y = mx + b

In your example you we get:

y = 1x + b
0 = 1(0) + b

or

y = x

To get all of the coordinates you simply need to plug in all values x1 -> x2. In PHP this entire thing looks something like:

// These are in the form array(x_cord, y_cord)
$pt1 = array(0, 0);
$pt2 = array(10, 10);
$m = ($pt1[1] - $pt2[1]) / ($pt1[0] - $pt2[0]);
$b = $pt1[1] - $m * $pt1[0];

for ($i = $pt1[0]; $i <= $pt2[0]; $i++)
    $points[] = array($i, $m * $i + $b);

This will of course give you the coordinates for all points that fall on integer values of X, and not "all coordinates" between the two points.

thanks for all your help but non of the answers posted worked how i wanted it to. For example, lets say my points were:

0, 0

0, 10

There would only be a start and a finish coordinate... it wouldnt find the ones inbetween.

Maybe i did something wrong :S but i came up with my own solution:

// Points
$p1 = array(
    'x' => 50,
    'y' => 50
);

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

// Work out distances
$pxd = $p2['x'] - $p1['x'];
$pyd = $p2['y'] - $p1['y'];

// Find out steps
$steps = max($p1['x'], $p1['y'], $p2['x'], $p2['y']);

$coords = array();

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

print_r($coords);

1. Use the line equation, y = mx + c
2. Put (0,0) and and (10,10) to get two equations and solve to get values of m and c. (you will be able to find the direct equations to get m and c somewhere).
3. Then create a loop to start from x = x1 (0) till x = x2 (10)
4. Using y=mx+c, get the value of y (now that you know m and c)

To generate all the lattice points (points with integral coordinates) on the segment between (x1,y1) and (x2,y2), where x1, x2, y1, and y2 are integers:

function gcd($a,$b) {
    // implement the Euclidean algorithm for finding the greatest common divisor of two integers, always returning a non-negative value
    $a = abs($a);
    $b = abs($b);
    if ($a == 0) {
        return $b;
    } else if ($b == 0) {
        return $a;
    } else {
        return gcd(min($a,$b),max($a,$b) % min($a,$b));
    }
}

function lattice_points($x1, $y1, $x2, $y2) {
    $delta_x = $x2 - $x1;
    $delta_y = $y2 - $y1;
    $steps = gcd($delta_x, $delta_y);
    $points = array();
    for ($i = 0; $i <= $steps; $i++) {
        $x = $x1 + $i * $delta_x / $steps;
        $y = $y1 + $i * $delta_y / $steps;
        $points[] = "({$x},{$y})";
    }
    return $points;
}

A simpler algorithm would be, find the midpoint by averaging out the coordinates, repeat until you're done. Just wanted to point out because no one did.