Compute lattice points in rectangular region Let $M \subset \mathbb R^2$ be a lattice of rank $2$ given by a basis $b_1,b_2\in \mathbb R^2$. So $M = \mathbb Z b_1 +\mathbb Z b_2$. I'm looking for an algorithm which computes every lattice point in a rectangular region $[a,b] \times [c,d]$. So we are interested in the finite set $M \cap ([a,b] \times [c,d])$.
In case $b_1 = (r_1,0)$ and $b_2 = (0,r_2)$ for $r_1,r_2 \in \mathbb R$ that would be quite simple. But my basis is of course not in that form (in fact for my lattices there is no basis of that form since $(0,0) \in M$ is the only lattice point with a zero in a coordinate).
Do you have ideas how to proceed? I guess I should transform my basis somehow into a basis which is more suitable. But what does more suitable mean in this situation and how can I do that?
 A: Let $m=(m_1,m_2)\in M$. You can represent $m=(m_1b_{11}+m_2b_{21}, m_2b_{12}+m_2b_{22})\in\mathbb R^2$. Now proceed to find all pairs $(m_1,m_2)\in\mathbb Z^2$.
A: We have a rank-$2$ lattice in $\mathbb R^2$
$$\mathcal L := \left\{ z_1 \begin{bmatrix} |\\ \mathrm b_1\\ |\end{bmatrix} + z_2 \begin{bmatrix} |\\ \mathrm b_2\\ |\end{bmatrix} : z_1, z_2 \in \mathbb Z \right\} = \{ \mathrm B \mathrm z : \mathrm z \in \mathbb Z^2 \} = \mathrm B \mathbb Z^2$$
where $2 \times 2$ matrix $\mathrm B = \begin{bmatrix} | & |\\ \mathrm b_1 & \mathrm b_2\\ | & |\end{bmatrix}$ has full column rank and, thus, is invertible, and a rectangle
$$\mathcal R := [c_1, d_1] \times [c_2, d_2]$$
We would like to determine the cardinality of the finite set $\mathcal L \cap \mathcal R$, which we denote by $| \mathcal L \cap \mathcal R |$.
There is a quadrilateral $\mathcal Q \subset \mathbb R^2$ such that $\mathcal R = \mathrm B \mathcal Q$. Hence, 
$$| \mathcal L \cap \mathcal R | = | \mathrm B \mathbb Z^2 \cap \mathrm B \mathcal Q| = | \mathbb Z^2 \cap \mathcal Q|$$
Since the vertices of $\mathcal R$ are
$$\left\{ \begin{bmatrix} c_1\\ c_2\end{bmatrix}, \begin{bmatrix} d_1\\ c_2\end{bmatrix}, \begin{bmatrix} c_1\\ d_2\end{bmatrix}, \begin{bmatrix} d_1\\ d_2\end{bmatrix} \right\}$$
the vertices of $\mathcal Q$ are
$$\left\{ \mathrm B^{-1} \begin{bmatrix} c_1\\ c_2\end{bmatrix}, \mathrm B^{-1} \begin{bmatrix} d_1\\ c_2\end{bmatrix}, \mathrm B^{-1} \begin{bmatrix} c_1\\ d_2\end{bmatrix}, \mathrm B^{-1} \begin{bmatrix} d_1\\ d_2\end{bmatrix} \right\}$$
Taking the minimum and the maximum along each axis, we obtain a minimal bounding box $\mathcal B$ that contains $\mathcal Q$. Hence, $| \mathbb Z^2 \cap \mathcal B|$ gives us an upper bound on the cardinality $| \mathbb Z^2 \cap \mathcal Q |$. Using $2$ for loops, we can count the number of integer points inside $\mathcal Q$ and, thus, obtain $| \mathbb Z^2 \cap \mathcal Q | = | \mathcal L \cap \mathcal R |$.
A: There are two relevant metrics in the problem, one is in ${\Bbb R}^2$ coming from the rectangle, the second in ${\Bbb Z}^2$ induced by your lattice basis.
In order to avoid carrying around on annoying constants (from the rectangle), the first reduction is to multiply $x,y$ coordinates by $1/(b-a)$ and $1/(d-c)$, respectively.
Your rectangle then becomes a unit square centered at $C=\left( \frac{a+b}{2(b-a)}, \frac{c+d}{2(d-c)}\right)$. For the lattice basis in these new coordinates we write:
$$ (b_1\;\; b_2) = (e_1\;\; e_2) \left( \begin{matrix} u_1 & v_{1} \\ u_2 & v_2 \end{matrix} \right)$$
with $e_1,e_2$ being the canonical basis in ${\Bbb R}^2$. The idea is now to perform change of lattice basis in order to make $b_1,b_2$ as 'orthogonal' as possible (with respect to the Euclidean metric, since we have rescaled the rectangle to a square). Thus we multiply on the right with integer matrices of determinant $\pm 1$ (to preserve the basis property) in order to reduce the angle between $b_1$ and $b_2$. A bit like Gram-Schmidt orthogonalization except that we have to stick to integer matrices.
A kind of Euclidean algorithm:
Order first $b_1$ and $b_2$ so that  $|b_1| \geq |b_2|$. Now, determine the integer $n$ that minimizes the length of
$$ b'_1 = b_1 - n b_2$$
Also set $b'_2=b_2$ and reverse the roles of $b_1$ and $b_2$, repeating the algorithm until $|b_1| |b_2|$ becomes smaller than or equal to $2|\det (b_1 \;\; b_2)|$. Note that the determinant is preserved under the algorithm and that the algorithm terminates. When terminated the angles between the resulting vectors $(b_1,b_2)$ is at least $60$ degrees.
It follows that (if I didn't make a mistake in the calculations):
$$ \frac{1}{4} \left( n_1^2 |b_1|^2 + n_2^2 |b_2|^2\right) \leq \left|n_1 b_1 + n_2 b_2\right|^2 \leq \frac{7}{4} \left( n_1^2 |b_1|^2 + n_2^2 |b_2|^2\right)$$
If centered at the origin the left hand inequality shows that is suffices to look at points with coordinates $|n_1|\leq 2/|b_1|$ and $|n_2|\leq 2/|b_2|$. I leave it to you the case when centered at a different point. Asymptotically, when both  $|b_1|$ and $|b_2|$ are much smaller than one, the right hand inequality shows that our method checks at most a factor of $\sqrt{7}$ too many points. The constant is probably not optimal, though.
