World's most popular travel blog for travel bloggers.

# Group points by given shapes

, ,
Problem Detail:

I am using a sensing board able to detect magnetic signals between the board and a display.

I have a set of objects that are represented (each of them) by a unique set of points (magnets) with a particular shape. For example: object #1 is made by three points that form an equilateral triangle with side length 1cm; object #2 is made by three points that form a right triangle with sides 3cm, 4cm, 5cm; object #3 is made by three aligned points with distance 2cm; and so on. I can have a multiplicity of objects with unique patterns.

Now I have a list of points with the coordinates w.r.t. the Cartesian plane, and I need to match them referring to the patterns I got from the objects. I also know that every point must be matched, therefore I can minimize the overlapping errors. In practice, every point in the set can belong to maximum one object, and at the same time also it must belong to an object of the initial set.

Any idea on how to do that in an efficient way?

###### Answered By : Karolis Juodelė

In the general case a problem like this is NP, however in the vast majority of real cases it should be easy.

20 points make 1140 triangles so it shouldn't be hard to pick out the triangles most similar to your basic shapes (unless the shapes can be more complicated). A little ugly backtracking may be needed when the top scoring triangles overlap.

Also, if most magnets move continuously, you can easily map old points to new points and old triangles to new triangles.

What I'm talking about are fairly obvious methods. There may be smarter ways to do this, but you don't necessarily need them.