Fitting data to a square lattice (discrete points by multiple parameters)

Question

I have measured points on a two dimensional square lattice.

.

How can I fit the data to a square lattice? I guess some methods like curve fitting or least square approximation would work, but I couldn't find any literature for the same problem.

• the lattice has discrete points
• the lattice is modeled with multiple parameters: translation (x0 and y0), rotation (θ), lattice spacing (d), and it cannot be represented as y=f(x; a,b,...) form.

Answer 1

TLDR; not possible (without punishment for fine lattices)

So I had the same question and I researched why it isn't possible. I show that for every n rational points, x1, ... , xn there exists some rational q, b such that for every i there exists an integer z such that xi = z * q + b.

Proof by induction:

base case:

We start at n=2, for that, choose q = x1 - x0 and b = x0

assumption:

let there be x1, ..., xn+1 rational points. Then for the first n points, there exists some rational q, b such that for every i<=n there exists an integer z such that xi = z * q + b

inductive step:

take q, b from the assumption. We find a natural number beta such that q' := q / s, b satisfies the assumption for i<=n+1.

Indeed, for every natural number and i<=n, when xi = z * q + b, then also xi = z * s * q' + b

Now we have to choose a natural s, such that x := xn+1 = z * q' + b for an integer z.

I will derive s and it will also be a proof that such a s exists. Define beta through x = beta * q + b. Because every number except beta is rational, so is beta:

beta = u / v

define s := v

Then it holds: x = beta * q + b = u / v * q + b = u / v * s * q' + b = u * q' + b where u is an integer.

Empirical Proof

using the formulas from the proof, I made a python program that finds for arbitrary fractions the perfect lattice:

from fractions import Fraction
import random

def random_fract():
    return Fraction(
        random.randint(2, 1_000),
        random.randint(2, 100)
    )

def test_one_lattice():
    x_vals = [random_fract() for i in range(1_000)]
    # remove duplicates -- the algorithm doesn't work for them
    x_vals = list(set(x_vals))
    q = x_vals[1] - x_vals[0]

    b = x_vals[0]
    for fract in x_vals[2:]:
        q /= ((fract-b) / q).denominator
    for x in x_vals:
        z = (x - b) / q
        assert z * q + b == x
        assert z % 1 == 0

if __name__ == "__main__":
    for _ in range(50):
        test_one_lattice()

keep in mind this also holds for multiple dimensions of the space (they are independent) and also for multiple dimensions of the lattice (just set the other vectors to zero)