FIlter array of rectangles so that there are no collisions-CodePudding

I have an array of rectangles that might collide with each other. I want to filter out the collided ones with minimal reduction. What's an optimal way of doing this?

Here is some code for context:

type Rect = {
  x: number;
  y: number;
  width: number;
  height: number;
};

function isRectsColliding(rect1: Rect, rect2: Rect) {
  return !(
    rect1.x > rect2.x   rect2.width ||
    rect1.x   rect1.width < rect2.x ||
    rect1.y > rect2.y   rect2.height ||
    rect1.y   rect1.height < rect2.y
  );
}

const rects = [
  { x: 0, y: 181, width: 6, height: 6 },
  { x: 6, y: 147, width: 6, height: 6 },
  { x: 32, y: 124, width: 6, height: 6 },
  { x: 34, y: 7, width: 6, height: 6 },
  { x: 35, y: 11, width: 6, height: 6 },
  { x: 36, y: 0, width: 6, height: 6 },
  { x: 39, y: 15, width: 6, height: 6 },
];

const filteredRectIndexes = rects.reduce(?).map((_, idx) => idx); // should be [0, 1, 2, 3, 5, 6]

Thanks.

CodePudding user response：

Here is an example of a reduce function that you can use to get the result that you've mentioned:

function isRectsColliding(rect1, rect2) {
  return !(
    rect1.x > rect2.x   rect2.width ||
    rect1.x   rect1.width < rect2.x ||
    rect1.y > rect2.y   rect2.height ||
    rect1.y   rect1.height < rect2.y
  );
}

const rects = [{
    x: 0,
    y: 181,
    width: 6,
    height: 6
  },
  {
    x: 6,
    y: 147,
    width: 6,
    height: 6
  },
  {
    x: 32,
    y: 124,
    width: 6,
    height: 6
  },
  {
    x: 34,
    y: 7,
    width: 6,
    height: 6
  },
  {
    x: 35,
    y: 11,
    width: 6,
    height: 6
  },
  {
    x: 36,
    y: 0,
    width: 6,
    height: 6
  },
  {
    x: 39,
    y: 15,
    width: 6,
    height: 6
  },
];

const filteredRectIndexes = rects.reduce((a, c) => {
    if (a.length && a.some((r) => isRectsColliding(r, c))) {
      return a;
    }
    return [...a, c];
  }, [])
  .map((r) => rects.indexOf(r)); // should be [0, 1, 2, 3, 5, 6]

console.log(filteredRectIndexes);

I've modified the callback passes to .map(..) because .map((_, idx) => idx) will always return an empty array or an array of consecutive numbers.

Like @derpirscher mentioned, this will not give you the biggest set of non-colliding rectangles because it processes rectangles in the order that they are in the original array (current rectangle does not collide with any of the previous rectangles).

Keeping the maximum number of non-colliding rectangles can get quite complex, a simple way of doing it will be to first sort the original array of rectangles by the number of collisions each of them has, here is an example:

function isRectsColliding(rect1, rect2) {
  return !(
    rect1.x > rect2.x   rect2.width ||
    rect1.x   rect1.width < rect2.x ||
    rect1.y > rect2.y   rect2.height ||
    rect1.y   rect1.height < rect2.y
  );
}

const rects = [{
    x: 0,
    y: 181,
    width: 6,
    height: 6
  },
  {
    x: 6,
    y: 147,
    width: 6,
    height: 6
  },
  {
    x: 32,
    y: 124,
    width: 6,
    height: 6
  },
  {
    x: 34,
    y: 7,
    width: 6,
    height: 6
  },
  {
    x: 35,
    y: 11,
    width: 6,
    height: 6
  },
  {
    x: 36,
    y: 0,
    width: 6,
    height: 6
  },
  {
    x: 39,
    y: 15,
    width: 6,
    height: 6
  },
];

const rectsWithCount = rects.map((c, _, arr) => {
  const count = arr.filter((r) => r !== c && isRectsColliding(r, c)).length;
  return { ...c, count };
});

rectsWithCount.sort((a, b) => a.count - b.count);

const filteredRectIndexes = rects.reduce((a, c) => {
    if (a.length && a.some((r) => isRectsColliding(r, c))) {
      return a;
    }
    return [...a, c];
  }, [])
  .map((r) => rects.indexOf(r));

console.log(filteredRectIndexes);

CodePudding user response：

Your goal of maximizing the number of non-colliding rectangles is hard, but you could approach it like this:

Treat this as a graph theory problem, where rectangles are nodes and nonoverlapping rectangles are joined by edges.

Every clique (set of pairwise connected) vertices in the graph represents a set of non-colliding rectangles. You want to find the maximum clique.

This is a hard problem, but there are good heuristics. Tabu search is fast randomized approach that has worked well for me when I needed to find a large clique.

The approach is:

Initalize by assigning every vertex to a clique of size 1
Repeatedly do the following:
Permute your cliques
greedily assign the vertices of the cliques to the first clique they can fit into (don't have any non-edges)
repeat

This is fast, simple, and does well at finding approximation of the optimal solution.

Notice that on each iteration the number of cliques can only go down or stay the same.

You'll need to decide when to stop -- some number of iterations without improving the number of cliques is a reasonable threshold. What that threshold is depends on your data.

This is subject to being trapped in local optima, so simulated annealing may help.