Given a hexagonal grid enumerated from a center point (see example), how can one mathematically determine if two hexagons are adjacent to another?
Edit: Asked another way, Given two non negative integers are the corresponding hexagons adjacent?
combinatorial-geometrycombinatoricsgeometry
Given a hexagonal grid enumerated from a center point (see example), how can one mathematically determine if two hexagons are adjacent to another?
Edit: Asked another way, Given two non negative integers are the corresponding hexagons adjacent?
My attempt:
The hexagon has four degrees of freedom so that four points should suffice, but you can expect a finite number of solutions.
Take two of the points and make an hypothesis on the edges they belong to. This gives you the angle aperture between these edges. Knowing the two points and the angle aperture, you know that the apex of the angle belongs to a circular arc that joins the point and you can determine its center.
The center of the hexagon lies on the line from the apex to the center of the arc, so it belongs to a circle of unknown radius with the same center as the arc. Repeating the construction for three point pairs, the hexagon center is the point equidistant to the three centers.
In the case of two points on the same edge, the locus of the hexagon center is a straight line parallel to that formed by the two points, and the solution will be found as the point equidistant to the line and two points, or two lines and a point.
Other combinations are degenerate, such as two pairs of points belonging to two parallel sides.
UPDATE: the statement "The center of the hexagon lies on the line from the apex to the center of the arc" is wrong, so that the locus of the center is another curve.
I have assumed that “$2\times3$” means “$2$ rows and $3$ columns”. Is my assumption correct?
It depends on the context. In general I'd agree, but since the counts you quote doesn't include a separate handling of the $3\times2$ case, in this situation I'd rather assume that $2\times3$ is meant to cover both orientations, both two rows and three columns and two columns and three rows.
Can someone help me to find how many rectangles there are in the rectangular grid below?
If all you are interested in is the total number of non-square rectangles, then it doesn't matter how you write down each individual count. In fact, I'd not iterate over all possible shapes, but instead use a different approach.
For a grid of $m\times n$ tiles, there are $(m+1)\times(n+1)$ tile corners. If you consider each of them as a possible corner of a rectangle, and define each rectangle by two opposite corners, then you have a total of
$$\bigl((m+1)(n+1)\bigr)^2$$
possible combinations of two points. Obviously, that number is way too large, because we counted some things we shouldn't, and counted others more than once. So let's address those issues.
You don't want either dimension of such a rectangle to be zero. So if you picked the first point, then there are $m+n+1$ possible positions where that second point would be in the same row and/or the same column as the first. Subtract that and you are at
$$(m+1)(n+1)\bigl((m+1)(n+1)-(m+n+1)\bigr)=(m+1)(n+1)mn\;.$$
As Arthur pointed out in a comment, you can think of this as picking the second point from the $m\times n$ possible corner positions which you obtain by removing the “forbidden” row and column. At this point you have two points in distinct rows and columns, but nothing is sorted yet. So every possible rectangle is counted four times: any of its four corners might be the first point, with the opposite corner as the second point. So the number of rectangles is
$$\tfrac14(m+1)(n+1)mn\;.$$
Now you still have to get rid of those squares. How many are there? Let's look for a pattern. There are $m\times n$ squares of size $1$. There are $(m-1)\times(n-1)$ squares of size $2$, and so on. The maximal size such a square can have is the smaller of the dimensions of your tile grid. So there are
$$\sum_{i=1}^{\min(m,n)}(m+1-i)(n+1-i)$$
squares in total. Assuming $m\le n$ this simplifies to
$$\sum_{i=1}^{m}(m+1-i)(n+1-i)=\tfrac16 m(m+1)(3n-m+1)\;.$$
Now take the number of all rectangles, subtract all squares, and you are done. If you expand and then factor the result, you get a total count of
$$\tfrac1{12}m(m+1)(3n^2 + 2m - 3n - 2)= \tfrac1{12}m(m+1)\bigl(3n(n-1) + 2(m-1)\bigr)\;.$$
For $m=n=3$ this indeed yields a count of $22$. For $m=5,n=7$ (remember to ensure $m\le n$) this gives a count of $335$ non-square rectangles. You can verify that count with a brute-force computation.
If you want to, it might be interesting to think about why that formula always results in an integer if $m,n$ are integers.
Either $m$ or $m+1$ is divisible by two, so their product is even. For the same reason, $n(n-1)$ is even, and since $2(m-1)$ is even, too, $\bigl(3n(n-1) + 2(m-1)\bigr)$ must be even. So the whole thing is the product of two even numbers, and therefore divisible by four.
Exactly one of $m,(m+1),(m-1)$ is divisible by three. In the first two cases, the whole product is obviously divisible by three. In the last case, $\bigl(3n(n-1) + 2(m-1)\bigr)$ is divisible by three since it's the sum of two integers which are divisible by three. As the whole thing is divisible by four and by three, it is divisible by twelve.
Best Answer
Think in terms of rings around the central hexagon:
In the image above, darker tone indicates corner hexagon, and lighter tone an edge hexagon.
You can label all hexagons using a single nonnegative integer $i$, $0 \le i \in \mathbb{Z}$; or, equivalently, using the ring number $r$, $0 \le r \in \mathbb{Z}$, and position within the ring $p$, $0 \le p \in \mathbb{Z}$: $$i = \begin{cases} 0, & r = 0 \\ 3 r (r - 1) + 1 + p, & r \ge 1 \end{cases} \tag{1}\label{1}$$ and inversely $$r = \begin{cases} 0, & i = 0 \\ \left \lfloor \frac{3 + \sqrt{12 i - 3}}{6} \right \rfloor, & i \ge 1 \end{cases} \tag{2}\label{2}$$ where $\lfloor \, \rfloor$ denote rounding towards zero, and $$p = i - 3 r ( r - 1 ) - 1 \tag{3}\label{3}$$
Ring $r = 0$ is special, because it has only one hexagon (the center hexagon in white). It's neighbours are the six hexagons in ring $r = 1$; I suggest you number the neighbors in the same order you number the hexagons in ring $r = 1$.
Ring $r = 1$ is kind of special, because it consists of only corner hexagons, but it turns out the same rules below handle this ring as well as all outer rings just fine.
All rings except ring $r = 0$ have $r - 1$ edge hexagons between consecutive corner hexagons.
Using OP's numbering, hexagons $p = r - 1$, $p = 2 r - 1$, $p = 3 r - 1$, $p = 4 r - 1$, $p = 5 r - 1$, and $p = 6 r - 1$ are the corner hexagons, in order, in ring $r$.
When given $i$ for a specific hexagon, I do believe you have three separate cases you need to handle:
If $i = 0$, then $r = 0$, $p = 0$, and the neighbors are $1$, $2$, $3$, $4$, $5$, and $6$
Otherwise, calculate $r$ according to $\eqref{2}$, and then $p$ according to $\eqref{3}$.
If $p \mod r = r - 1$, this is a corner hexagon, with one neighbor in ring $r-1$, two in the current ring ($i-1$ and $i+1$), and three in ring $r+1$.
Otherwise,
This is an edge hexagon, which has two neighbors in ring $r-1$, two in the current ring ($i-1$ and $i+1$), and two in ring $r+1$.
It should not be difficult to formulate the rules for the $(r, p)$ for the neighboring inner and outer ring hexagons; I'm just too lazy to work it out for myself right now.
In particular, remember that each outer ring has one more edge hexagon between corner hexagons: that allows you to compensate for the $p$ indexing along the ring in different rings. One way to do this is to number the edges along the ring from $e = 0$ to $e = 5$, so that $e = \lfloor p / r \rfloor$.