# Algorithm for identifying polygons (set of points)

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.
• What counts as a match? Do you require each point in one set to be aligned with another point in the other set? Or might some points have no match? Are you OK with an algorithm that, given the two sets, checks whether they match? Or do you really need a way to obtain a unique hash / canonical form given a single set of points? I'm not sure what GeoHashing is or why it didn't work; can you share any more about what that is, how it works, and why it didn't work? – D.W. Mar 22 at 1:39
• After your step 2, I would try solving an Assignment problem in which one set (the "workers") are one point set, and the other set (the "tasks") are the other point set, and the cost of each possible pair of points, one from each set, is the Euclidean distance between them. Return YES iff the solution cost (sum of distances of matched point pairs) is under some threshold. – j_random_hacker Mar 22 at 1:41
• Don't add "EDIT:". Just revise our question so it reads well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755. – D.W. Mar 22 at 19:04