Effectively identify connected cells / voxels

Question

I am trying to determine the most efficient way to check if two cells \ voxels are connected. I will look at the problem in two dimensions for simplicity and look at the cells in the diagram ...

Now I just limit the problem to the vertical axis, call it the y axis.

The bottom left corner of each cell is its coordinate, and it is always a positive integer (if that helps).

The y-axis estimates for A and B can be written,

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

Now, what is the most efficient way to check if A and B / are connected along the y axis? Note that it should also work if you switch labels A and B in the diagram around.

Here is my undoubtedly 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 the projections of the cells on the axis intersect each other (similar to @coproc's answer). But this time, calculate the "vector" size of each intersection, and then check to see if they are all non-negative. Then, to check with regard only to angles, you can request that at least one such length be positive. For example, with something similar (for clarity, I changed the structure of the bounding box):

 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(ax, bx); axis_t y_overlap = overlap(ay, by); return x_overlap >= 0 && y_overlap >= 0 && x_overlap + y_overlap > 0; } 

It is up to 7 comparisons and 3 additions / subtractions, but there are 8 values, so this is probably not so bad.

Answer 2

Assuming that you are connected, you mean "share a non-trivial border", I would think about it this way: two of these fields are connected if they separate two different points. If you adhere to rectangular fields, you simply check the corners of each cell and see if at least two of the eight corners are in both sets. To use this approach to parse a plane into a graph representing related fields, you can also use this to check if an edge should be inserted (assuming that this is your final goal), but you should probably consider some sorting method so you won’t get many square comparisons in the number of cells.

Answer 3

Only with geometry checks are you close to optimal.

You need 4 comparisons (in 2d) to determine which, if any, the boundary pair is adjacent. If adjacency is detected, you need to detect the presence or absence of 2d overlap. You do this with two inclusion checks using <= and> =. You will not do much better. If true answers are more likely than false, it may be worth checking first whether one endpoint is strictly contained in another edge. If all of these tests fail, the logic must pass before the final verification of identical edges. (This additional check makes the method more expensive if false answers are common.)

Efficiency is available if you add “depth” to each node. This will quickly tell you which cell is larger or if they are the same size, which allows you to do only one of two inclusion checks. A single depth comparison avoids several comparisons with the coordinates of the edge.

Finally, if you put parent pointers in nodes, you can do this comparison by looking for paths to the least common ancestor. You can check these paths to get an answer. However, since it is unlikely that finding and testing them will be faster than the numerical comparison that you already have, I will not go into this.

Answer 4

In my opinion, your code is the best.

No more than 6 comparisons are required.

I'm afraid that the search for radius / distance / overlap involves more calculations.

One alternative is caching. If you cache neighboring nodes while storing each box coordinate, you can later simply see if B is in adjacent list A with fewer comparisons. Building an initial cache is overhead, but later performance may be good.

Otherwise, I do not see a better way.