Finding intersecting grid squares

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
Cronje
Forum Newbie
Posts: 6
Joined: Tue Jun 22, 2010 12:29 pm

Finding intersecting grid squares

Post by 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:
Image

You can clearly see that the line runs through A1, A2, A3, B3, B4, B5. How can I make PHP determine the same thing?
User avatar
AbraCadaver
DevNet Master
Posts: 2572
Joined: Mon Feb 24, 2003 10:12 am
Location: The Republic of Texas
Contact:

Re: Finding intersecting grid squares

Post by AbraCadaver »

If you mean using an actual image, then you can't. If you mean using an algorithm of some sort to simulate this, then you can probably use a multidimensional array and some algorithm to get this result. I'm sure there is a mathematical function to do this, I just don't know it off the top of my head.
mysql_function(): WARNING: This extension is deprecated as of PHP 5.5.0, and will be removed in the future. Instead, the MySQLi or PDO_MySQLextension should be used. See also MySQL: choosing an API guide and related FAQ for more information.
Cronje
Forum Newbie
Posts: 6
Joined: Tue Jun 22, 2010 12:29 pm

Re: Finding intersecting grid squares

Post by Cronje »

I meant an array, yes.
User avatar
McInfo
DevNet Resident
Posts: 1532
Joined: Wed Apr 01, 2009 1:31 pm

Re: Finding intersecting grid squares

Post by McInfo »

Is the line always straight? Does it always begin at the center point of one grid box and end at the center point of another grid box? What determines where the line is drawn? Are you working from an image that has the line already drawn, or is your image a simulation of a line running from A1 to B5? Do lines have thicknesses? Are the grid boxes always square?
Cronje
Forum Newbie
Posts: 6
Joined: Tue Jun 22, 2010 12:29 pm

Re: Finding intersecting grid squares

Post by Cronje »

It would be a straight line from the center of the square labeled point A to the center of the square labeled point B. The image is just a simulation. In reality, the grid could be a different dimension, such as 2x6 or 10x10. That's why I'm having such difficulty. The line itself is as thin as possible.

Edit: Ah, nevermind. One of the awesome gurus at PHP Freaks came up with a great solution.
User avatar
McInfo
DevNet Resident
Posts: 1532
Joined: Wed Apr 01, 2009 1:31 pm

Re: Finding intersecting grid squares

Post by McInfo »

My solution is more complicated, but it was good practice. :D

If you bisect the line, then keep bisecting the smaller line segments until they are shorter than the width of a grid square, each segment will have an endpoint in one of the grid squares.

If you round the coordinates down for each of those endpoints, you get the corner coordinates for the grid squares that the major line passes through. It's fairly easy to then convert the corner coordinates into grid square labels.

The special case where an endpoint lands on a grid line is handled by duplicating the endpoint and shifting the duplicate a small amount so that it will fall into the adjacent grid square, while the original will fall into the other square during rounding.

Code: Select all

<?php
/* You may distribute and create derivatives from this code as long as
 * this notice is retained and attribution is given to the author. If
 * you gain financially from this work, please consider a donation to
 * Charles Snyder <paypal at snydev dot com>
 */

function main () {
    header('Content-Type: text/plain');

    Examples::a();
    Examples::b();
}

class Examples {
    static function a () {
        $line = new Line();
        $line->a()->fromGridSquare('A1');
        $line->b()->fromGridSquare('B5');
        print_r($line->toGridSquares());
    }
    static function b () {
        $line = new Line(
            new Point(0.5, 0.5), // Center of A1
            new Point(1.5, 4.5) // Center of B5
        );
        echo $line;
    }
}

class Point {
    private $x = 0;
    private $y = 0;
    function __construct ($x = null, $y = null) {
        $this->x($x);
        $this->y($y);
    }
    // Gets or sets x
    function x ($x = null) {
        if (! is_null($x) && $x >= 0) {
            $this->x = $x;
        }
        return $this->x;
    }
    // Gets or sets y
    function y ($y = null) {
        if (! is_null($y) && $y >= 0) {
            $this->y = $y;
        }
        return $this->y;
    }
    function shiftRight ($x) {
        $this->x += $x;
        return $this;
    }
    function shiftLeft ($x) {
        $this->x -= $x;
        return $this;
    }
    function shiftDown ($y) {
        $this->y += $y;
        return $this;
    }
    function shiftUp ($y) {
        $this->y -= $y;
        return $this;
    }
    // Snaps the point to the grid line intersection with the smallest coordinates
    function snap () {
        $this->x = floor($this->x);
        $this->y = floor($this->y);
        return $this;
    }
    // Whether the point is snapped to one grid line (but not an intersection)
    function onGridLine () {
        return ((floor($this->x) == $this->x) xor (floor($this->y) == $this->y));
    }
    // Sets coordinates to the center of the given grid square (C2 = 2.5,1.5)
    function fromGridSquare ($gridSquare) {
        list ($col, $row) = str_split(strtoupper($gridSquare), 1);
        $this->x(ord($col) - ord('A') + 0.5);
        $this->y($row - 0.5);
        return $this;
    }
    // Gets the name of the current grid square
    function toGridSquare () {
        $x = chr(ord('A') + floor($this->x));
        $y = floor($this->y) + 1;
        return ($x . $y);
    }
    // What to show when a Point object is echoed
    function __toString () {
        return ('(' . $this->x . ', ' . $this->y . ')');
    }
}

class Line {
    private $a = null;
    private $b = null;
    function __construct ($a = null, $b = null) {
        $this->a($a);
        $this->b($b);
    }
    // Gets or sets the start point
    function a ($a = null) {
        if ($a instanceof Point) {
            $this->a = $a;
        } elseif (is_null($this->a)) {
            $this->a = new Point();
        }
        return $this->a;
    }
    // Gets or sets the end point
    function b ($b = null) {
        if ($b instanceof Point) {
            $this->b = $b;
        } elseif (is_null($this->b)) {
            $this->b = new Point();
        }
        return $this->b;
    }
    // Gets the slope of the line
    function slope () {
        $xDiff = $this->b->x() - $this->a->x();
        if ($xDiff == 0) {
            return null; // Prevents division by zero
        }
        $yDiff = $this->b->y() - $this->a->y();
        return ($yDiff / $xDiff);
    }
    // Gets a Point object located at the midpoint of the line
    function midPoint () {
        return new Point(
            (($this->b->x() + $this->a->x()) / 2),
            (($this->b->y() + $this->a->y()) / 2)
        );
    }
    // Gets the length of the line
    function distance () {
        $xDiff = $this->b->x() - $this->a->x();
        $yDiff = $this->b->y() - $this->a->y();
        return sqrt($xDiff * $xDiff + $yDiff * $yDiff);
    }
    // Snaps both points to grid intersections
    function snap () {
        $this->a->snap();
        $this->b->snap();
        return $this;
    }
    // Returns an array of two bisecting line segments
    function bisect () {
        $pair = array (
            new Line(
                $this->a(),
                $this->midPoint()
            ),
            new Line(
                $this->midPoint(),
                $this->b()
            )
        );
        return $pair;
    }
    // Bisects a line and the resulting segments until the segments are
    // shorter than the specified maximum distance
    static function splitLine (Line $line, $maxDistance, &$segments) {
        if ($line->distance() > $maxDistance) {
            list ($a, $b) = $line->bisect();
            self::splitLine($a, $maxDistance, $segments);
            self::splitLine($b, $maxDistance, $segments);
        } else {
            $segments[] = $line;
        }
        return $segments;
    }
    // Returns an array of grid squares that the line passes through
    function toGridSquares () {
        $gridSquares = array ();
        $segments = array ();
        // Splits the line into segments that are shorter than
        // the width of a grid square so an endpoint will
        // be located in each square the line passes through
        self::splitLine($this, 1, $segments);
        foreach ($segments as $segment) {
            if ($segment->a()->onGridLine()) {
                // When a point falls on a grid line, it touches two
                // grid squares. A clone must be made and shifted so a
                // unique point can be found in the second square
                $clone = clone $segment;
                $gridSquares[] = $clone->a()->shiftLeft(0.1)->shiftUp(0.1)->toGridSquare();
            }
            $gridSquares[] = $segment->a()->toGridSquare();
        }
        // The last point is the end point of the original line
        $gridSquares[] = $this->b()->toGridSquare();
        // Returns array without duplicates and with sequential keys
        return array_values(array_unique($gridSquares));
    }
    // What to show when a Line object is echoed
    function __toString () {
        return (
            'A: ' . $this->a . ' {' . $this->a->toGridSquare() . '}' . PHP_EOL .
            'B: ' . $this->b . ' {' . $this->b->toGridSquare() . '}' . PHP_EOL .
            'Slope: ' . $this->slope() . PHP_EOL .
            'Midpoint: ' . $this->midPoint() . PHP_EOL .
            'Distance: ' . $this->distance() . PHP_EOL .
            'A on line: ' . ($this->a->onGridLine() ? 'yes' : 'no') . PHP_EOL .
            'B on line: ' . ($this->b->onGridLine() ? 'yes' : 'no') . PHP_EOL .
            'Crosses: ' . implode(', ', $this->toGridSquares()) . PHP_EOL
        );
    }
    // What to do when a Line object is cloned
    function __clone () {
        $this->a = clone $this->a;
        $this->b = clone $this->b;
    }
}

main();
Edit: I changed the maximum length of a line segment from sqrt(2) to 1 because I noticed that squares were being missed at steep or flat angles. As a result of the change, more endpoints are generated and array_unique() is needed to filter out duplicates.
User avatar
AbraCadaver
DevNet Master
Posts: 2572
Joined: Mon Feb 24, 2003 10:12 am
Location: The Republic of Texas
Contact:

Re: Finding intersecting grid squares

Post by AbraCadaver »

Holy crap! 8O
mysql_function(): WARNING: This extension is deprecated as of PHP 5.5.0, and will be removed in the future. Instead, the MySQLi or PDO_MySQLextension should be used. See also MySQL: choosing an API guide and related FAQ for more information.
User avatar
McInfo
DevNet Resident
Posts: 1532
Joined: Wed Apr 01, 2009 1:31 pm

Re: Finding intersecting grid squares

Post by McInfo »

Are you commenting on the length of the code? It's really not as much code as it looks at first glance.

My theory gets sillier the more I think about it. Fortunately, most of the code can be reused to solve the problem with a more logical method.
User avatar
AbraCadaver
DevNet Master
Posts: 2572
Joined: Mon Feb 24, 2003 10:12 am
Location: The Republic of Texas
Contact:

Re: Finding intersecting grid squares

Post by AbraCadaver »

McInfo wrote:Are you commenting on the length of the code? It's really not as much code as it looks at first glance.
Yes, but I didn't mean it in a bad way. :D
mysql_function(): WARNING: This extension is deprecated as of PHP 5.5.0, and will be removed in the future. Instead, the MySQLi or PDO_MySQLextension should be used. See also MySQL: choosing an API guide and related FAQ for more information.
Post Reply