Finding intersecting grid squares

[Cronje]

Is there a way, through PHP, that I could find which squares a line being drawn from square X to square Y would intersect?

 

For example:

 

You can clearly see that the line runs through A1, A2, A3, B3, B4, B5. How can I make PHP determine the same thing?

[Cronje]

Woops, just realized that I didn't clarify - the image is just for demonstration purposes. What I intend to use is a multidimensional array.

[Alex]

Okay so here's a rough example on how you could do it:

 

class Point {
private
	$_x,
	$_y;

public function __construct($x, $y) {
	$this->_x = $x;
	$this->_y = $y;
}

public function getX() {
	return $this->_x;
}

public function getY() {
	return $this->_y;
}
}

function slope($p1, $p2) {
return ($p2->getY() - $p1->getY()) / ($p2->getX() - $p1->getX());
}

function getBoxAt($x, $y, $xScale, $yScale) {
if($y == (int) $y && $x == (int) $x) {
	return; // On a line, not in a box
}
return $xScale[floor(abs($x))] . $yScale[floor(abs($y))];
}

$xScale = range('A', 'E');
$yScale = range(1, 5);

$p1 = new Point(0.5, -0.5);
$p2 = new Point(1.5, -4.5);

// y = mx + b

// m = deltaY / deltaX
$m = slope($p1, $p2); // m = -4

// b = y - mx
$b = $p1->getY() - $m * $p1->getX(); // b = 1.5

// y = -4x + 1.5

$boxes = array();
for($i = $p1->getX();$i <= $p2->getX();$i += 1/8) {
if(($box = getBoxAt($i, -4 * $i + 1.5, $xScale, $yScale)) !== false) {
	$boxes[] = $box;
}
}

print_r(array_unique($boxes));

 

Output:

 

Array
(
    [0] => A1
    [1] => A2
    [3] => A3
    [4] => B3
    [5] => B4
    [7] => B5
)

 

And now I'll break everything down..

 

This defines a simple Point object, if you're not familiar with Object-Oriented PHP don't worry, you really don't need to know anything to understand this. All you need to know is that it represents a point, so it has an X and Y property.

class Point {
private
	$_x,
	$_y;

public function __construct($x, $y) {
	$this->_x = $x;
	$this->_y = $y;
}

public function getX() {
	return $this->_x;
}

public function getY() {
	return $this->_y;
}
}

 

This function takes 2 points as parameters and returns the slope of the resulting line they form.

function slope($p1, $p2) {
return ($p2->getY() - $p1->getY()) / ($p2->getX() - $p1->getX());
}

 

This function will take standard graph points and determine which box on your graph it would fall in.

function getBoxAt($x, $y, $xScale, $yScale) {
if($y == (int) $y && $x == (int) $x) {
	return; // On a line, not in a box
}
return $xScale[floor(abs($x))] . $yScale[floor(abs($y))];
}

 

Here we define and create the two points we're dealing with.

$p1 = new Point(0.5, -0.5);
$p2 = new Point(1.5, -4.5);

 

We know that the standard equation for a line is y = mx + b, so now, given the two points, we need to figure out the 2 variables in this equation, m (slope) and b (y-intercept). Now we simply plug in our 2 points into our slope function that we declared earlier to easily determine the slope between the tow points, we find that m = -4, we declare that to be the value of $m.

// y = mx + b

// m = deltaY / deltaX
$m = slope($p1, $p2); // m = -4

 

Now we find b, the y-intercept value. To do this we simply plug in x, y (both taken from one of the two points we were given) and m, the slope we already determined. We find b = 1.5.

// b = y - mx
$b = $p1->getY() - $m * $p1->getX(); // b = 1.5

 

Now we have the equation y = -4x + 1.5 for our line.

 

Now what we want to do is take this equation and find out all possible boxes that the points of this line fall in, that are within the small segment we have (between point 1 and point 2). We start the loop at our first point, and go to the second point incrementing the X by 1/8 each time (this increment will depend on the slope of the line you're dealing with). Within this loop we call the getBoxAt function we defined earlier on each point to determine which point that box lands on in your graph. After checking to make sure the function didn't result false (if it did return false it means that it did not land in a box, but rather directly on a line) and store it in the $boxes array. After all this we print_r out our array after calling array_unique on it to ensure that no box is listed twice.

$boxes = array();
for($i = $p1->getX();$i <= $p2->getX();$i += 1/8) {
if(($box = getBoxAt($i, -4 * $i + 1.5, $xScale, $yScale)) !== false) {
	$boxes[] = $box;
}
}
print_r(array_unique($boxes));

[Cronje]

For the most part, I understand the math (and the parts I don't, I have faith are accurate). After reviewing what the range() function does, can I assume that the code will still work if I increased the size of the grid? The only part I'm truly confused about is the setting of the points. What specifically do the numbers mean? How do I determine what number corresponds with each grid square?

[Alex]

Imagine your graph part of a typical coordinate plane like shown in the attached image.

 

Now we'll example line this step by step, since it's where you're confused:

 

return $xScale[floor(abs($x))] . $yScale[floor(abs($y))];

 

First we'll show what $xScale and $yScale contain:

 

$xScale = array('A', 'B', 'C', 'D', 'E');
$yScale = array(1, 2, 3, 4, 5);

 

The values in these arrays correspond to your graph. Let's look at how the $xScale value is picked.

 

$xScale[floor(abs($x))]

 

First we take the absolute value of $x (|$x|). If $x is -1.5 it becomes 1.5, if it's 2.0 it stays 2.0. Then floor that value. We do this because say the value is 4.5, 4.9, or 4.65, 4.xx, ... that means that it's located somewhere in the 4th box, which is what we're trying to determine.  So if the math came out and we determined that it was in box 1, that would be $xScale[1], which is B.

 

Essentially the arrays are just lists of the names for each scale. floor(abs($x)) or floor(abs($y)) determines which box we're dealing with. The by plugging that into the corresponding array we get the name for that box.

 

[attachment deleted by admin]

[Psycho]

I had a solution yesterday, but AlexWD beat me to it. After a couple of modifications this morning I think this solution is a little easier to work with. This solution allows you to pass the actual grid square "points" instead of having to calculate the midpoints. Simply pass the starting and endpoints in the format ('A', 1, 'B', 5):

 

<?php
    
function getGrids($startX, $startY, $endX, $endY)
{
    //Create output array
    $gridSquares = array();
    
    //Convert X letter values to number
    $xRange = range('A', 'J');
    $startX = array_search(strtoupper($startX), $xRange) + 1;
    $endX   = array_search(strtoupper($endX), $xRange) + 1;
    
    //Determine slope and offset
    $m = ($endY-$startY) / ($endX-$startX);
    $b = $startY - ($m * $startX);
    
    //Calculate a step value to find all grid squares
    $step = 1/(ceil(abs($m))+1);
    
    //Find the grid squares
    for($x=min($startX, $endX); $x<=max($startX, $endX); $x=$x+$step)
    {
        $y = ($m * $x) + $b;
        $grid_y = round($y);
        $grid_x = $xRange[round($x)-1];
        $gridPosition = "$grid_x, $grid_y";
        if(!in_array($gridPosition, $gridSquares))
        {
            $gridSquares[] = $gridPosition;
        }
    }
    return $gridSquares;
}
    
$grids = getGrids('A', 1, 'B', 5);
    
echo "<pre>";
print_r($grids);
echo "</pre>";
    
?>

 

Output:

Array
(
    [0] => A, 1
    [1] => A, 2
    [2] => A, 3
    [3] => B, 3
    [4] => B, 4
    [5] => B, 5
)

[Daniel0]

I'm sure AlexWD's and mjdamato's solutions work fine, but you can also try taking a look at line drawing algorithms such as Bresenham's line algorithm.

[Psycho]

I'm sure AlexWD's and mjdamato's solutions work fine, but you can also try taking a look at line drawing algorithms such as Bresenham's line algorithm.

 

I suspected there might be something like that out there, I just relied on the old standby y = mx +b. However, that algorithm does have a flaw for what the OP wanted since it does not count grid squares that the line "barely" intersects since it is trying to approximate a strait line. It does give me an idea on how the previous code I created could be optimized though.

[Alex]

Hm.. I was thinking of a better solution where you don't have to check any points on the line at all.

 

What you could do is take your first point and from that through some simple calculations you can determine where on that grid box it will hit. If it hits on the vertical line then you know the next box that the line will occupy is the current box + 1 on the x scale. If it hits the horizontal line then you know that the next box is the current box + 1 on the y scale, and if it hits on the corner perfectly then the next one is +1 on both the x and y scales. You can just continue to loop through until you've reached the ending point on your line. Using this method you wouldn't have to deal with any repetitive calculations that might tell you that a point on the line occupies a box you already know.

[Psycho]

I was thinking of a slightly different approach as well which only require you to do two checks for each x point or each y point (whichever is shorter). In the example above you would just check the position at the point just above the first grid (such as 1.1) and then at the very end of the grid (1.9). You could then get the number of y grids that are included in that range. Then do the same thing for the grids in the x position of 2. The only thing you would have to calculate is the amount of offset to check at the boundires. That could be done using the slope of the line.

 

The example above would only require four calculations.