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:
- Rotate "other" set to some point (so that farthest points create line that is 45 degrees to "x" axis);
- Scale set so farthest points distance = "ideal" distance;
- 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).
I want to add some details to it:
- Points set contains only 5 points (including those distant ones);
- There could be several "ideal" point sets and I want to find if given set matches something (that's why I used GeoHash);
- 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.