Simplify BoundingBox.intersect(other: BoundingBox): Vector A LOT

[ikudrickiy]

Context

I looked at the problem from the side of finding the necessary path to leave the box counterpart behind in one of 4 basic directions and got an excellent algorithm - simple and readable! Not sure if it has no flaws yet xD

Link to the original function

Proposal

1) Compute

// compute the pathes needed to get ahead of the other box in that direction
// if path <= 0 it means this box is already ahead in that direction
let topPath = this.bottom - other.top;
let bottomPath = other.bottom - this.top;
let leftPath = this.right - other.left;
let rightPath = other.right - this.left;

if (xPath <= 0), we dont need to shift on the line containing x (vertical/horizontal)

Between pathes of available lines (vertical/horizontal) choose the shortest path to define the direction and it's length

2) Compare and return

if (topPath <= 0 || bottomPath <= 0) {
  // boxes Oy projections don't intersect
  if (leftPath <= 0 || rightPath <= 0)
    // boxes Ox projections don't intersect TOO
    // boxes don't intersect
    return new Vector(0, 0);

  // only Ox boxes projections do intersect
  // TODO: think about giving priority to right shift to do negation less often
  if (leftPath <= rightPath)
    return new Vector(-leftPath, 0);
  return new Vector(rightPath, 0);
}

// boxes Oy projections do intersect
if (leftPath <= 0 || rightPath <= 0) {
  // boxes Ox projections don't intersect
  // only Oy boxes projections do intersect
  // TODO: think about giving priority to bottom shift to do negation less often
  if (topPath <= bottomPath)
    return new Vector(0, -topPath);
  return new Vector(0, bottomPath);
}

// choose the shortest path
let minIndex = SOMETHING.getMinIndex([topPath, bottomPath, leftPath, rightPath]);

switch(minIndex) { 
   case 0:
      return new Vector(0, -topPath);
   case 1:
      return new Vector(0, bottomPath);
   case 2:
      return new Vector (-leftPath, 0);
   case 3:
      return new Vector (rightPath, 0);
} 

[ikudrickiy]

function getMinIndex(arr: Array<number>) {
    if (arr.length === 0)
        return -1; // is it legal?

    let min = arr[0];
    let min_i = 0;

    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
            min_i = i;
        }
    }

    return min_i;
}

[eonarheim]

@ikudrickiy I like this refactor, much more readable. As long as it produces the same results as the previous algorithm (and the tests pass) I see no reason not to make an optimization.

An additional win would be if this has better performance characteristics as well 😎

[ikudrickiy]

@eonarheim I'll honestly be surprised if the new method won't be faster. I'll try to visualize the concept by creating an interactive demo. We can refer to it in the code comments.

[ikudrickiy]

@eonarheim demo is ready: https://www.geogebra.org/m/gx9j4wnd Mirroring ruins the demo xD Don't try to mirror a rectangle!

[ikudrickiy]

After studying the model, it turned out that the code can be simplified to

// compute the pathes needed to get ahead of the other box in that direction
// if path <= 0 it means this box is already ahead in that direction
let topPath = this.bottom - other.top;
let bottomPath = other.bottom - this.top;
let leftPath = this.right - other.left;
let rightPath = other.right - this.left;

if (topPath <= 0 || bottomPath <= 0 || leftPath <= 0 || rightPath <= 0)
  return null;

let minIndex = SOMETHING.getMinIndex([topPath, bottomPath, leftPath, rightPath]);

switch(minIndex) { 
   case 0:
      return new Vector(0, -topPath);
   case 1:
      return new Vector(0, bottomPath);
   case 2:
      return new Vector (-leftPath, 0);
   case 3:
      return new Vector (rightPath, 0);
} 

[ikudrickiy]

Also I found out the function used to send null instead of Vector.Zero, so I did the same

[ikudrickiy]

I think this function comes to the Utils.ts

[ikudrickiy]

if (
  this.bottom <= other.top ||
  other.bottom <= this.top ||
  this.right <= other.left ||
  other.right <= this.left
)
  // there is no collision
  return null;

// the path that must be taken when moving in the direction to escape the collision
// these are positive if return hasn't happen
let topPath = this.bottom - other.top;
let bottomPath = other.bottom - this.top;
let leftPath = this.right - other.left;
let rightPath = other.right - this.left;

let minIndex = SOMETHING.getMinIndex([
  topPath,
  bottomPath,
  leftPath,
  rightPath,
]);

switch (minIndex) {
  case 0:
    return new Vector(0, -topPath);
  case 1:
    return new Vector(0, bottomPath);
  case 2:
    return new Vector(-leftPath, 0);
  case 3:
    return new Vector(rightPath, 0);
}

This fails faster. I prefer this.

P.S: This logic is also so clear no demo comment is needed :)

[github-actions[bot]]

This issue hasn't had any recent activity lately and is being marked as stale automatically.