Get points of intersection of 2 Rectangles

Question

How can I get the points of intersection of 2 rectangles. I have gotten this so far:

module.exports.boxIntersection = function(box1, box2) {
    var xMin1 = box1.x - box1.width;
    var xMin2 = box2.x - box2.width;
    var xMax1 = box1.x + box1.width;
    var xMax2 = box2.x + box2.width;
    var zMin1 = box1.z - box1.length;
    var zMin2 = box2.z - box2.length;
    var zMax1 = box1.z + box1.length;
    var zMax2 = box2.z + box2.length;
    var xMin = Math.max(xMin1, xMin2);
    var xMax = Math.min(xMax1, xMax2);
    if (xMax > xMin) {
        var zMin = Math.max(zMin1, zMin2);
        var zMax = Math.min(zMax1, zMax2);
        if (zMax > zMin) return [xMin, zMin, xMax, zMax];
    } return null;
};

This only returns 2 points of intersection. But I need all the points of intersections to be returned like this:

In a case like this however it should only return 2 points:

I saw this question here: Get the points of intersection from 2 rectangles

But it only returns 2 points.

EDIT: In a case where the rectangle aligns with a side of another is should only return the points that are at a true intersection like so:

AnT stands with Russia · Accepted Answer · 2018-07-12T04:24:16.057

The answer that you linked actually "intersects" the rectangles as polygons, as polygonal sets of points on the plane, and returns lower-left and upper-right corners of the resultant rectangle (as a polygonal set). The two returned points actually trivially define all four corners of the resultant rectangle. So, no it does not "return two points". It actually returns four points.

In order to solve your problem you have to decide which ones of these four points to keep and which to discard. The rule is pretty simple: you have to keep only those points that do not coincide with corresponding vertices of the original rectangles. You can simply check this directly, in trivial and tedious fashion. Eight checks (if I'm not missing any) and you are done.

Or you can use a slightly more tricky approach.

Let's say we have two rectangles: (x11, y11)-(x12, y12) and (x21, y21)-(x22, y22). The rectangles are normalized (as defined at the link). We still use the same min-max technique when calculating the overlap rectangle, but at the same time we also memorize which original rectangle(s) supplied the extreme values

int x1 = max(x11, x21);
unsigned flags_x1 = (x1 == x11) | ((x1 == x21) << 1);

int y1 = max(y11, y21);
unsigned flags_y1 = (y1 == y11) | ((y1 == y21) << 1);

int x2 = min(x12, x22);
unsigned flags_x2 = (x2 == x12) | ((x2 == x22) << 1);

int y2 = min(y12, y22);
unsigned flags_y2 = (y2 == y12) | ((y2 == y22) << 1);

Now we check whether these rectangles even have a proper overlap

if (x1 >= x2 || y1 >= y2)
 /* No overlap. Done */;

But if overlap exists, we use our flags_... variables to output only those points that are formed by extreme values that came from two different rectangles

/* Lower-left */
if ((flags_x1 & flags_y1) == 0)
  /* Output (x1, y1) as intersection point */;

/* Lower-right */
if ((flags_x2 & flags_y1) == 0)
  /* Output (x2, y1) as intersection point */;

/* Upper-left */
if ((flags_x1 & flags_y2) == 0)
  /* Output (x1, y2) as intersection point */;

/* Upper-right */
if ((flags_x2 & flags_y2) == 0)
  /* Output (x2, y2) as intersection point */;

Note that if one rectangle lies completely inside another rectangle the no-overlap test above will pass (since rectangles actually do overlap), but the flags_... tests will discard all four vertices.

As usual, extra effort might be needed (or not) to properly process boundary cases, such as touching rectangles (inside or outside touch).

I have added a third figure to the question. Would this also work in that use case? And my apologies but im not familiar with this syntax in the answer; < — , Jul 12 '18 at 04:00
@Sidney de Vries: My current solution will handle that third case exactly as you pictured it: it does not consider inner/outer "touch" as intersection. — AnT stands with Russia, Jul 12 '18 at 04:04
Would you mind explaining this operation: if ((flags_x1 & flags_y1) == 0) And this operator: << im only familiar with javascript and java syntax — , Jul 12 '18 at 04:08
`<<` is bitwise left shift. I'm using bit 0 and bit 1 in `flags_...` variables to encode, which rectangle supplied the extreme value (not that it is possible that both supplied the same value - we have to memorize that as well, which is why I use two bits). `&` is a bitwise-and operation. `((flags_x1 & flags_y1) == 0)` indicates that lower-left extremes (`x1` and `y1`) came from two different rectangles (there are no common `1` bits in `flags_x1` and `flags_y1`). — AnT stands with Russia, Jul 12 '18 at 04:14
Is this solution limited to C? Because I cant use C. I am looking for a more simple pseudo code solution that other people may also benefit from the answer. Sorry for taking your time — , Jul 12 '18 at 04:26
@Sidney de Vries: The above is actually intended as pseudo-code. I just used C-like syntax to express it. (Moreover, I think it is immediately or almost immediately usable as Java, which also has all these operators). — AnT stands with Russia, Jul 12 '18 at 04:28
How would I possible handle outside touch? It looks like its a requirement in this case. — , Jul 12 '18 at 04:56

Get points of intersection of 2 Rectangles

1 Answers1