# Detect if square in grid is within a diamond shape

So I have a game in which basically everything is a square inside a big grid. It's easy to check if a square is inside a box whose center is another square:

``````*** x
*o*      --> x is not in o's square
***

**x
*o*      --> x IS in o's square
***
``````

This can be done by simply subtracting the coordinates of o and x, then taking the largest coordinate of that and comparing it with the half side length.

Now I want to do the same thing but check if x is in o's diamond, like so:

``````  *
**x
**o**    --> x IS in o's diamond
***
*
``````

What would be the best way to check if a square is in another square's surrounding diamond-shaped area, given the diamond's half width/height?

-

The diamond shape here has 2 useful properties:

1. A diamond that has a width of x fits completely within the square of width x
2. A diamond like this (ie. a square rotated through 90 degrees) based on a grid pattern can be defined by the Manhattan distance from the centre of the diamond.

So, an efficient check to see if a value is within this diamond would be this:

1. Iterate through each position in the containing square of the equivalent size. You can quickly calculate these bounds by subtracting/adding the square size to the centre position.
2. For each of those possible positions, it is in range if the Manhattan distance to the centre is less than or equal to the half-width/height of the diamond.
-
Are you sure this is THE way to do it? You're not really covering the alternatives ;) Kidding. – Byte56 Jul 2 '12 at 23:16
Ah, Manhattan distance! That's it! So I have: `(x - o).abs().sum() <= half` where abs() returns the coordinates' absolute values and sum() returns the sum of the coordinates. – slartibartfast Jul 3 '12 at 2:25
Excellent answer +1 – Valmond Jul 3 '12 at 14:01