Identifying that two planes touch and "merging" them

Question

I have a series of finite planes defined by 4 corner points. Some of the planes are "touching" (to a certain small tolerance), and I would like to identify these touching planes and "merge" them into a single one that approximates the combined planes. Note that they always touch with an edge, in a parallel way. What would be the smartest way to do this?

Example of touching planes

Answer 1

From your picture, it seems calculating the midpoint of each edge (so 4 per rectangle), and ordering them lexigraphically (according to $x$-value, then, if $x$ value is equal, according to $y$ value) might do the trick.

Go through this list, for each midpoint on the list, find the midpoints that come after it in the list that are 'near enough' according to your criteria. The ordering makes sure that once the difference of the $x$-values is bigger than you want, you don't need to continue further in the list.

If you have found a 'match' of midpoints, you need to check that the endpoints of the corresponding edges are the same (up to tolerance), also remember to compare poth pairs of endpoints (if the midpoints of $AB$ and $CD$ are the same, it could be $A=C, B=D$ or $A=D, B=C$).

If that also works, the next test would be that the two rectangles or coplanar (not at and angle with each other). If the 2 recangles are $AXYB$ and $XCDY$ (with $XY$ being the common edge), the lenght of the normalized cross product

$$\left\lvert\frac{\overrightarrow{XA}}{\lVert\overrightarrow{XA}\rVert} \times \frac{\overrightarrow{XC}}{\lVert\overrightarrow{XC}\rVert}\right\rvert$$

should be close to zero (it is the sine of the angle excompassed by $\overrightarrow{XA}$ and $\overrightarrow{XC}$).

If that also works out, the final test would be to check that the recangles are actuelly on opposite sides of their common edge, not on the same (that would mean one is inside the other, which might also allow an optimization.). To do that calculate the normalized dot product of the previous vectors:

$$\frac{\overrightarrow{XA}}{\lVert\overrightarrow{XA}\rVert} \cdot \frac{\overrightarrow{XC}}{\lVert\overrightarrow{XC}\rVert}$$

It should be $-1$ (or near it) for rectangles on opposite sides of their common edge (good), and $1$ (or near it) for rectangles on the same side of their common edge (bad).

If all those checks work out, you can now replace $AXYB$ and $XCDY$ with their union $ACDB$. You need to update your data structures and probably restart the process, in case the new $ACDB$ would fit with another rectangle that had been previously considered but did not fit with $AXYB$ and $XCDY$.

Another idea might be to just remove the midpoints of the original $AXYB$ and $XCDY$ from the list and continue, then at the end rerun the entire process, where you remove $AXYB$ and $XCDY$ from and add $ACDB$ to the list of rectangles (and of course do the same for all the other rectangles that you found to be touching). Then your algorithms stops when one such process didn't find any new rectangles that touch.