Efficiently identifying connected cells\voxels

Question

I'm trying to identify the most efficient way to test if two cells\voxels are connected. I'll discuss the issue in 2 dimensions for simplicity and consider the cells in the diagram...

Now I'll just confine the problem to the vertical axis, call it the y-axis.

The bottom left corner of each cell is its co-ordinate, and it is always a positive integer (if this helps).

The y-axis bounds of A and B can be written,

A.y1 = 4
A.y2 = 8
B.y1 = 7
B.y2 = 8

Now what's the most efficient way to test if A and B are connected/overlap on the y-axis? Note that it should also work if you switch the A and B labels in the diagram around.

Here's my no doubt naive attempt...

IF B.x2 == A.x1
    IF (A.y1 <= B.y1) AND (A.y2 >= B.y2) THEN
        connected = true
    ELSE 
    IF (A.y1 >= B.y1) AND (A.y2 <= B.y2) THEN
        connected = true
    ELSE 
        connected = false
    END
END

Answer 1

You can analyze how projections of the boxes onto the axes intersect with each other (similarly to @coproc's answer). But this time calculate the "vector" size of each intersection and then check if all are non-negative. Then to check for corners-only-touching you can request that at least one such length is positive. For example, with something like this (I have rearranged the bounding box structure for clarity):

typedef int axis_t; // some signed type
struct range { axis_t low, high; };
struct box { range x, y; }

axis_t overlap(const range &a, const range &b)
{
  return min(a.high, b.high) - max(a.low, b.low);
}

bool overlap(const box &a, const box &b)
{
  axis_t x_overlap = overlap(a.x, b.x);
  axis_t y_overlap = overlap(a.y, b.y);
  return x_overlap >= 0 && y_overlap >= 0 && x_overlap + y_overlap > 0;
}

This is up-to 7 comparisons and 3 additions/subtractions, but there are 8 values to consider, so probably it's not that bad.

Answer 2

Assuming by connected you mean "share a non-trivial border", I would think about it this way: two of these fields are connected iff they share two distinct points. If you stick to rectangular fields, you just check for the corners of each cell and see whether at least two of the eight corners are in both sets. To use this approach to parse the partition of the plane into a graph representing connected fields, you can also use this to check whether you should insert an edge (assuming that is your ultimate goal), but you probably should think about some way of sorting them so you don't get quadratically many comparisons in the number of cells.

Answer 3

With geometry checks alone, you are close to optimal.

You need 4 comparisons (in 2d) to identify which, if any, edge pair is adjacent. If an adjacency is found, you need to detect presence or absence of a 2d overlap. You are doing this with the two inclusion checks using <= and >=. You won't do much better. If true answers are more likely than false, it might be worthwhile first to check whether one end point is stictly contained in the other edge. If all these tests fail, the logic must fall through to a final check for identical edges. (This extra check makes the method more expensive if false answers are common.)

An efficiency is available if you add a "depth" number to each node. This will tell you quickly which cell is bigger or if they are of equal size, allowing you to make only one of the two inclusion checks. The single depth comparison will avoid several edge coordinate comparisons.

Finally, if you put parent pointers in the nodes, then you can do this comparison by looking for the paths up to the least common ancestor. These paths can be tested to get the answer. However, since it is unlikely that finding and testing them will be faster than the numerical comparision you already have, I won't go further into this.

Answer 4

According to me, your code is the best.

It requires at the most 6 comparisons.

Am afraid, finding radius / distance / overlap involve more computations.

One alternate is caching. If you cache the adjacent nodes at the time of storing each box coordinates, later you can just do a look up whether B is in the adjacent list of A with lesser number of comparisons. Building initial cache is the overhead, but later performance may be good.

Otherwise, i do not see a better way.