Algorithm for identifying polygons (set of points)

Question

Are there any known algorithms for uniquely identifying some set of points despite scaling, moving and with some amount of threshold?

I have an "ideal" set of points with coordinates and I need to check if other set matches the ideal one. Other set could be rotated, scaled or distorted a bit (points could be placed with slight offset).

All sets have one common property: there are 2 points located farthest apart. This can be used to, at least, negate rotation. We do know angle (45deg) that line between farthest points create with axis, and we do know needed distance between them.

I've tried following algorithm:

1. Rotate "other" set to some point (so that farthest points create line that is 45 degrees to "x" axis);
2. Scale set so farthest points distance = "ideal" distance;
3. Use sort of GeoHashing algorithm to get point hash with some accuracy (like threshold).

But that approach gave nothing. "GeoHashing" produces semi random results and probably not suitable for 1000x1000 calculations. And using geometric operations furthermore reduced accuracy (initial distortion of points + inaccuracy of some geometric methods).

EDIT:

I want to add some details to it:

1. Points set contains only 5 points (including those distant ones);
2. There could be several "ideal" point sets and I want to find if given set matches something (that's why I used GeoHash);
3. Basically task is to find matching polygon/set of points with given accuracy. If points do not match exactly (not located in the same coordinates), but are pretty close to ideal location (like +-2) it's a match.

Answer 1

I'll assume you are given two sets of points and want to determine whether one can be transformed to match the other. This is the pointset registration problem in computer vision. There are standard algorithms for this problem.

One of the crucial challenges is outliers -- e.g., points in the first set that don't have any corresponding point in the second set, or that have a large amount of error in their location. If you don't have outliers in your setting, then the problem becomes noticeably easier: simple least-squares linear regression might suffice.

If you have to deal with outliers, one standard way is to use RANSAC to find a rigid transformation that, when applied to the first set, makes it match the second set. A rigid transformation is determined by the correspondence between two points. So, you can use RANSAC: repeatedly pick a pair of points in the first set, choose a candidate pair of points in the second set for them to be matched to, compute the rigid transformation that maps the first two points to the latter two points, apply it to all points in the first set, find all inliers (points that are well-matched), update your estimate of the rigid transformation, count the number of inliers, and do this many times and keep the best rigid transformation you've found.

There are many other approaches as well. If you do some research, you should be able to find many algorithms, techniques, and even existing tools.