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?
-
$\begingroup$ Does your representation have accurate scale (can you tell 3 cm distance from 4 cm, or are we talking about detecting ratios 3:4:5)? How efficient does this need to be (how big is the number of points N, and would a $N^3$ algorithm be too slow)? $\endgroup$Karolis Juodelė– Karolis Juodelė2016年11月17日 12:41:54 +00:00Commented Nov 17, 2016 at 12:41
-
$\begingroup$ The representation is accurate enough to distinguish between 3cm and 4cm, so we do not need to guess the 3:4:5 ratios independently from the distances. I am using this in Processing (processing.org) therefore it needs to be fast as this calculations need to be done tens of times per second. $N$ should not be greater than 20, I think that $N^3$ is enough. Thank you! $\endgroup$Alessio Palmero Aprosio– Alessio Palmero Aprosio2016年11月17日 13:17:14 +00:00Commented Nov 17, 2016 at 13:17
1 Answer 1
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.