Testing equality of vectors in a 2 dimensional array

p5.js Coding Questions
1

Hello together,
I have a problem testing equality of one line of a 2D array against a possible new line.

My goal is to add a new line only if a line with the same elements does not yet exist.
To achieve this I wrote the following code:

class Evaluation {
  constructor() {
    this.lines = [];

  }

  addLines(cell) {
    for (let newLine of cell.neighbors) {
      // Suchen, ob es diese Zeile schon gibt
      let pushIt = true;
      for (let i = 0; i < this.lines.length; i++) {
        let lineExists = 0;
        for (let j = 0; j < newLine.length; j++) {
          if (this.lines[i].includes(newLine[j])) {
            //passenden Merker setzen
            lineExists += 1;
          }
        }
        if (lineExists == newLine.length) {
          pushIt = false;
        }
      }
      if (pushIt) {
        this.lines.push(newLine);
      }
    }
  }
}

cell is an object that contains a 2D array neighbors. Each element cell.neighbors[i] is an array of 4 p5.Vectors. I have 64 instances of cell objects, Evaluation.addLines is called for each of them.
The cells live in a 444 grid.
Evaluation.lines should become a list of all straight lines covering 4 cells, each line should be present once.
After calling addLines for all 64 cells Evaluation.lines is a list of all straight lines covering 4 cells, each line is present 4 times.

I do not care for the order of elements in each line and I can not ensure that the order is equal in 2 representations of any given line.
That is why I thought it would be a good idea to loop over all existing lines (for(let i…) with a nested inner loop (for(let j…) where I count how many of the vectors in newLine are present in that particular existing line.
If all Vectors are present (lineExists == newLine.length) I set the pushIt-flag false to not push that line into the lines-array.

While debugging I saw that sometimes pushIt is set to false, but after adding the neighbors of all 64 cells I still get 304 lines instead of the 76 lines I expect.

Can anybody tell me where my error lies and point me in the right direction please?

Best regards from Germany

PS: I edited the title to include “of vectors”

2

Basically we shouldn’t use method Array::includes() to compare objects.

B/c object comparison in JS doesn’t check their contents (properties & their values).

Instead such comparison action merely checks whether both memory addresses match:

'use strict';

function setup() {
  noCanvas();

  const vec = createVector(), arr = [ vec ];

  print(arr.includes(vec)); // true
  print(arr.includes(createVector())); // false

  print(arr[0] == vec, arr[0] == createVector()) // true, false

  print(createVector() == createVector()); // false
  print(createVector().x == createVector().x); // true
}

That actually makes the algorithm slightly more complex.

Just coded a double function which relies on method Array::some() for a customized object comparison:

The idea is to clone the 2nd vector array row and then invoke Array::some() inside the 1st vector array row’s loop.

Inside Array::some()'s callback we use method p5.Vector.equals() to check whether the contents of both vectors match.

Every time both vectors match we Array::splice() that vector outta the cloned 2nd vector array row:

Otherwise, if Array::some() fails to find a match, we break from the loop.

That function returns true only if the cloned 2nd vector array row becomes empty:

'use strict';

function setup() {
  noCanvas();

  const
    row = [
      createVector(PI, TAU),
      createVector(),
      createVector(RAD_TO_DEG, DEG_TO_RAD, Math.SQRT2),
      createVector(PI, TAU)
    ],
    
    equal = [
      createVector(RAD_TO_DEG, DEG_TO_RAD, Math.SQRT2),
      createVector(PI, TAU),
      createVector(PI, TAU),
      createVector()
    ],

    diff = [
      createVector(RAD_TO_DEG, DEG_TO_RAD, Math.SQRT2),
      createVector(PI, TAU),
      createVector(TAU, PI),
      createVector()
    ],

    same = [
      createVector(PI, TAU),
      createVector(PI, TAU),
      createVector(PI, TAU),
      createVector(PI, TAU)
    ];

  print(rowsContainSameVecs(row, equal));  // true
  print(rowsContainSameVecs(row, diff));   // false

  print(rowsContainSameVecs(row, row));    // true
  print(rowsContainSameVecs(equal, row));  // true
  print(rowsContainSameVecs(equal, diff)); // false

  print(rowsContainSameVecs(row, same));   // false
  print(rowsContainSameVecs(same, row));   // false
}

function rowsContainSameVecs(vecRowOne, vecRowTwo) {
  if (vecRowOne?.length != vecRowTwo?.length)  return false;

  vecRowTwo = vecRowTwo.slice();

  for (const vecOne of vecRowOne)
    if (!vecRowTwo.some(removeIfSameVec, vecOne))  break;

  return !vecRowTwo.length;
}

function removeIfSameVec(vec, idx, arr) {
  const same = vec.equals(this);
  same && arr.splice(idx, 1);
  return same;
}
2 Likes
3

Thank you for your input and the coding you provided.
I will implement and test it in my program and report back.

4

Here I am again…

I ended up not quite using the algorithm you provided. I may do so in the future and it may well be better than my algorithm, but…

  • I´m a beginner in js
  • I´m not (yet) comfortable with the idea and use of callback functions
  • I don´t fully understand the benefit of your algorithm compared to mine.

What did I do?

  addLines(cell) {
    for (let newLine of cell.neighbors) {
      // Suchen, ob es diese Zeile schon gibt
      let pushIt = true;
      for (let i = 0; i < this.lines.length; i++) {
        let lineExists = 0;
        for (let j = 0; j < newLine.length; j++) {

//          if (this.lines[i].includes(newLine[j])) {
//            //passenden Merker setzen
//            lineExists += 1;
//          }
          for (let k = 0; k < this.lines[i].length; k++) {
            if (this.lines[i][k].equals(newLine[j])) {
              //count number of identical vectors per line
              lineExists += 1;
            }
          }

        }
        // if all vectors are identical
        if (lineExists == newLine.length) {
          pushIt = false;
          break;
        }
      }
      if (pushIt) {
        this.lines.push(newLine);
      }
    }
  }

I added a 4th layer of nested loops to go throug the elements of the existing line(s) and the new line to compare them.
I used p5.Vector.equals() instead of == to compare the vectors. This is the core point I took from your suggestion and I´m sure it was my main mistake.

As far as I understand it the explicit check for same length in your function rowsContainSameVecs() is an improvement over my algorithm.
I think that one is minor in my special case, as I ensure lines of length 4 at creation of my inputs.
And your use of array.some() with your callback is presumably faster than my additional loop.

One point I don´t really understand is:
what does the “this” point to in the line

  const same = vec.equals(this);
```?
5

That keyword this inside the callback removeIfSameVec(vec, idx, arr) refers to the 2nd parameter from method Array::some(callbackFn, thisArg):

So it’s comparing each p5.Vector object from vecRowTwo[] cloned array to the current p5.Vector object (represented by loop’s iterator vecOne) from vecRowOne[] array.

If they’re equals(), I use Array::splice(startIndex, deleteCount) method to delete the current index from vecRowTwo[] cloned array (represented by callback’s parameter arr) to make sure that p5.Vector isn’t found again for the rest of the loop:

At the end of the loop it’s expected for vecRowTwo[] cloned array to be empty (its length = 0):

If so, it means that each p5.Vector object from vecRowOne[] array has found an equals() among vecRowTwo[] cloned array.

1 Like
6

Thank you again for the additional explanations.

At the moment my problem is solved.
I will make a note to try out your suggested algorithm to see if it makes an improvement over the solution I chose for now.

I have a lot more to learn about javascript and your explanations helped me a lot to that end.

1 Like