# Clean & efficient bounding box non-intersection test

I would like a quick test to tell me that segments $ab$ and $cd$ cannot intersect in the plane. If the maximum $x$-coordinate of $a$ and $b$ is less than the minimum $x$-coordinate of $c$ and $d$, then they cannot intersect. Etc.:

max = Max[a[[1]], b[[1]]];
min = Min[c[[1]], d[[1]]];
(*ab leftof cd*)
If[max < min, Return[False]];
max = Max[c[[1]], d[[1]]];
min = Min[a[[1]], b[[1]]];
(*cd leftof ab*)
If[max < min, Return[False]];
...


I feel this is rather clumsy coding. What is (a) a more concise coding, and (b) recognizing this is for speed, a more efficient bounding-box rejection.

The same question can be asked for $\mathbb{R}^d$ for $d>2$ (athough then it would likely be higher-dimensional objects determining the bounding box).

• I'm in a hurry and I am not quite sure if I understood what you were asking or not, but, if I understand, you might try using RegionIntersection and compare that with EmptyRegion. It would look clean, but I'm not sure how it would do performance-wise. Commented Aug 2, 2015 at 1:14
• There is, as I recall, an undocumented routine for generating axis-aligned bounding boxes, which as you know can be wasteful. I don't remember any function for oriented boxes being built-in. Commented Aug 2, 2015 at 3:25
• Let me know if I am misunderstanding you, but if you are wanting to test if two line segments intersect, you can use IntersectQ[a_, b_, c_, d_] := Not[SameQ[RegionIntersection[Line[{a, b}], Line[{c, d}]], EmptyRegion[n]]] where a-d are points and n is their dimension. If you just want the box surrounding them, then you can use RegionBounds[RegionUnion[Line[{a, b}], Line[{c, d}]]] Commented Aug 2, 2015 at 3:45
• @BenP1192 you should post that as an answer. I found that you can include the bounding box in RegionIntersection, RegionIntersection[Line[ab], Line[cd], Rectangle[]] Commented Aug 2, 2015 at 4:04

Let's assume you have the following points a-f, which form the line segments ab and cd and ef.

a = {0, 0};
b = {3, 3};
c = {1, .5};
d = {2, 1.5};
e = {0, 2};
f = {2, 0};


In order to test whether they intersect you can use RegionIntersection. First form lines from your points, then use RegionIntersection on the two lines. Compare the intersection to an empty region to see if the lines intersect. I built the following functions for 2D points, but you can change that by specifying a different dimension for EmptyRegion

IntersectQ[a_, b_, c_, d_] := Not[SameQ[RegionIntersection[Line[{a, b}],
Line[{c, d}]], EmptyRegion[2]]]

IntersectQ[a,b,c,d];
(*False*)
IntersectQ[a,b,e,f];
(*True*)


The evaluation was quick when I ran it, around 0.014 seconds.

As AndyRoss mentioned, you can use a variety of shapes within the intersection to suit your needs.

If you need to find the box surrounding the lines, use the following:

 RegionBounds[RegionUnion[Line[{a, b}], Line[{c, d}]]]

• Very nice---Thanks! Commented Aug 2, 2015 at 11:08

Starting with M11.1 you can use RegionDisjoint:

a = {0, 0};
b = {3, 3};
c = {1, .5};
d = {2, 1.5};
e = {0, 2};
f = {2, 0};

Not @ RegionDisjoint[Line[{a, b}], Line[{c, d}]] //RepeatedTiming
Not @ RegionDisjoint[Line[{a, b}], Line[{e, f}]] //RepeatedTiming


{0.0020, False}

{0.00083, True}

IntersectQ[a_, b_, c_, d_] := Not[