Page 1 of 1

Finding intersecting grid squares

Posted: Tue Jun 22, 2010 12:50 pm
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?

Re: Finding intersecting grid squares

Posted: Tue Jun 22, 2010 2:12 pm
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.

Re: Finding intersecting grid squares

Posted: Tue Jun 22, 2010 2:26 pm
by Cronje
I meant an array, yes.

Re: Finding intersecting grid squares

Posted: Tue Jun 22, 2010 2:41 pm
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?

Re: Finding intersecting grid squares

Posted: Tue Jun 22, 2010 2:50 pm
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.

Re: Finding intersecting grid squares

Posted: Tue Jun 22, 2010 9:44 pm
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.

Re: Finding intersecting grid squares

Posted: Wed Jun 23, 2010 8:01 am
by AbraCadaver
Holy crap! 8O

Re: Finding intersecting grid squares

Posted: Wed Jun 23, 2010 9:10 am
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.

Re: Finding intersecting grid squares

Posted: Wed Jun 23, 2010 10:36 am
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