We study the exact counting problem for all lattice rectangles contained in the square [0,n)×[0,n), including non-axis-parallel ones. Starting from the standard parametrization by a primitive direction (u,v) and two side lengths, we derive a sequence of exact algorithms of complexity O(n²), O(n^{3/2} log n), O(n^{4/3} log n), and finally O(n log³n). The main idea behind the near-linear algorithm is to reduce the geometric summation to a constant-size family of weighted floor sums closed under Euclidean-style affine and reciprocal transformations, and hence evaluable in O(log n) time per query. The intermediate algorithms expose the structural reductions leading to this final kernel and provide independent cross-checks for the implementation.