4
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – BenP1192 Aug 2 '15 at 1:14
  • $\begingroup$ 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. $\endgroup$ – J. M. is away Aug 2 '15 at 3:25
  • 1
    $\begingroup$ 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}]]] $\endgroup$ – BenP1192 Aug 2 '15 at 3:45
  • 2
    $\begingroup$ @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[]] $\endgroup$ – Andy Ross Aug 2 '15 at 4:04
5
$\begingroup$

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};

Picture of line segments

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}]]]
$\endgroup$
  • $\begingroup$ Very nice---Thanks! $\endgroup$ – Joseph O'Rourke Aug 2 '15 at 11:08
2
$\begingroup$

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}

Compare to the accepted answer:

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

IntersectQ[a,b,c,d] //RepeatedTiming
IntersectQ[a,b,e,f] //RepeatedTiming

{0.0035, False}

{0.0023, True}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.