CODEWITHSUNDEEP
c#algorithmmath
Kyle Dama
Kyle Dama

Reputation: 49

Comparing Numbers Algorithm

I'm trying to compare two sets of number. I'll be given the numbers in a random order. The objective is to take the numbers in the second list, and locate them in the first list. The numbers are the X Coordinates from a list of points that are given from a file for the first list, and then selected by a user by clicks on an image for the second list. For example X Coord Set 1:

  1. 177
  2. 150
  3. 212
  4. 45
  5. 91
  6. 330

And then X Coord Set 2 (not always 3 points, could be 2, could be 5):

  1. 212
  2. 91
  3. 150

This part is easy, since you just compare which ones in the second list are equal to the ones in the first. However it gets harder when the points are offset. For example in the image below, the original image in red is the default position, and the blue is a different image that is offset by +20px, which makes the the X points offset by +20px. I marked the original image points in red, the user clicks in blue, and finished off what the image should look like in black.

enter image description here

My question is what is the most effective way to find out which points have been clicked if there is an image offset like the one in the image. It won't always be 20px, and it won't always be a positive number. Maybe subtract the points and find the most common number?

Upvotes: 2

Views: 290

Answers (2)

Saeed Amiri
Saeed Amiri

Reputation: 22555

As I understand you always have a fixed offset in each run, but you don't know what is the offset, any greedy geometrical solution, like matching closest pairs together, may lead to a wrong answer.

Sort numbers in both lists, then find the one to one correspondence. Doesn't matter how the offset changes, in the sorted lists always numbers are in the correct place. To retrieve it in the original format you can do as follows (pseudo code):

struct item 
{
int value;
int position;
}

List<item> inputs = new List<item>()
List<item> original = new List<item>()

for i=1 ... n :

original[i] = new item{lst1[i],i}
inputs[i] = new item{lst2[i],i}

Sort inputs and originals w.r.t. their values,

For i=1...n
input[i].position = original[i].position;

For i=1..n
lst2[inputs[i].position] = inputs[i].value;

Note that the above pseudo code works only if two list have the same size, for the case they have different sizes I'll update my answer later.

Consider we have two sorted lists of different sizes:

Original: 200 211 222 233 244 255 ..... 299

and

Input: 224, 257, 279

First we assume 224 is corresponding to 200, then 257 should be corresponding to 257-24 = 223, but there is no 223 in the list, move the pointer forward, assume 224 corresponds to 211 then 257 should be correspond to the 257 - 13 = 244, we have 244 in the original list, then 279 should be corresponding to 279 - 13 = 256, but we don't have 256 in the original list, so move the pointer forward ... , we can see that 224 -> 244, 257->277, 279->299. Certainly there can be multiple correspondence in some circumstances but it's not possible to distinguish between them by the information that we have. Suppose the first list has size n and the second list has size m, the algorithm runs in time O(m.n), as usually the second list is small (user clicks) this is almost linear. On the other finding longest common subsequence is O(n^2) so the mentioned algorithm is reasonably good.

Upvotes: 3

Wicher Visser
Wicher Visser

Reputation: 1543

This is called the closest pair of points problem in computational geometry. It is similar to finding nearest neighbors combined with evaluating the sum of least squares of their distances.

Upvotes: 1

Related Questions