Lattice fitting to points

Question

I have a set of points (shown as little black circles) which ideally form a hexagonal lattice shape, each point having an equal distance to all of its neighboring points. (Sorry for my drawing, some of the line intersections are off, but I hope you get the idea).

(These points are actually acquired through image processing, by calculating the center of gravity of some circular blobs in an image. And I am trying to figure out how close these points are to being an ideal.)

My question is: Is there a way to find the "best fit" lattice so that the total distances of points to their ideal position is minimized? I honestly don't know how a lattice is expressed, but I'm thinking if I have a distance d (the equal distance between all lattice points), a slope m, and an X,Y displacement, I should be able to calculate the ideal point corresponding to each real point.

Answer 1

I think it would be easier to analyze if you apply the (inverse) Fourier transform to get the spacial frequency (complex) spectrum, known as the reciprocal lattice of your "crystal", as in http://en.wikipedia.org/wiki/X-ray_crystallography#Diffraction_theory. That picture will describe the lattice fully, including main direction and spacing, whether it's indeed hexagonal, and how big the possible deviations from a perfect lattice. I realize that this replaces one problem with another, but then there must be a well developed physical methodology for analyzing diffraction images, maybe even to automatically determine the lattice type and spacing.

Answer 2

Here's how I ended up solving (hacking my way through) this for now:

1) calculated the average distance between points (d).

2) In my case, the lattice is almost horizontal. I clustered the points by their Y axis values to group them into "rows".

3) Foreach row, I calculated a least squares regression line. And calculated an average line angle [-90,90] of all rows.

4) I assigned a "lattice coordinate" to each point on the lattice. Each point is expressed as au+bv (thanks @Aleks Vlasev) where a and b are intergers, and u,v are vectors. (a,b) is the lattice coordinate (as I call it) for the point.

5) I created an "ideal lattice" starting from the real origin 0,0. Calculated an ideal point corresponding to each real point by calculating the au+bv where u is a vector with a magnitude of d and angle of 60 degrees, and v is vector with mag of d and angle of 0 degrees.

6) overlapped the ideal lattice with the real lattice points. I did this by calculating the center of gravity for both lattices and moving each point on the real lattice by the difference vector of those 2 center of gravities. Additionally, I applied a rotation matrix to the ideal points in order to rotate them around the center of gravity by the angle calculated in step 3.

I'm sure this is solution is far from perfect but it seems to produce pretty good results.