c++ - Efficiently identifying connected cells\voxels -

i'm trying identify efficient way test if 2 cells\voxels connected. i'll discuss issue in 2 dimensions simplicity , consider cells in diagram...

i'll confine problem vertical axis, call y-axis.

the bottom left corner of each cell co-ordinate, , positive integer (if helps).

the y-axis bounds of , b can written,

a.y1 = 4
a.y2 = 8
b.y1 = 7
b.y2 = 8

now what's efficient way test if , b connected/overlap on y-axis? note should work if switch , b labels in diagram around.

here's no doubt naive attempt...

if b.x2 == a.x1     if (a.y1 <= b.y1) , (a.y2 >= b.y2)         connected = true     else      if (a.y1 >= b.y1) , (a.y2 <= b.y2)         connected = true     else          connected = false     end end 

you can analyze how projections of boxes onto axes intersect each other (similarly @coproc's answer). time calculate "vector" size of each intersection , check if non-negative. check corners-only-touching can request @ least 1 such length positive. example, (i have rearranged bounding box structure clarity):

typedef int axis_t; // 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 up-to 7 comparisons , 3 additions/subtractions, there 8 values consider, it's not bad.