# Line segment intersection

Discussion in 'Probability' started by Peter Bone, Jun 7, 2010.

1. ### Peter BoneGuest

There are 2 random line segments in a rectangular region. What is the
probability that they intersect? Based on testing 10,000,000 examples
I have estimated 0.2315 +- 0.0001. I'd like an exact answer based on
logic.

Peter Bone, Jun 7, 2010

2. ### HenryGuest

You will need to specify how a random line segment is chosen, to avoid

Henry, Jun 8, 2010

3. ### Peter BoneGuest

OK. You generate 8 random numbers with a uniform probability
distribution over the range and from them you define the X and Y
coordinates of the 4 points. Is that adequate to define the problem?

Peter Bone, Jun 8, 2010
4. ### Bastian ErdnuessGuest

Strange. My first guess was, that it should be exactly 1/3.

Given four points A, B, C, D assuming no two of them are on one line
(probability for that should be zero) there are three ways to make two
linesegments with them: AB and CD, AC and BD, or AD and BC:

A---B A B A B
, | | , or X .
C---D C D C D

Only in one case the segments cross. Given the four points, each of the
three possibilities should have the same probablility and that should

Can you post the code for your simulation?

Cheers,
Bastian

Bastian Erdnuess, Jun 8, 2010
5. ### Peter BoneGuest

I see where you're coming from but I think it's much more complex. You
won't get each of your 3 combinations with equal probability. Here's
the Matlab code. Maybe a solution could come from the line crossing
test which uses determinants.

count = 0;
reps = 10000000;
for rep = 1 : reps
l1p1 = rand(1,2);
l1p2 = rand(1,2);
l2p1 = rand(1,2);
l2p2 = rand(1,2);
if lines_cross(l1p1, l1p2, l2p1, l2p2)
count = count + 1;
end
end
count / reps

function cross = lines_cross(l1p1, l1p2, l2p1, l2p2)
cross = false;
diff_l1 = l1p2 - l1p1;
diff_l2 = l2p2 - l2p1;
compare1 = diff_l1(1)*l1p1(2) - diff_l1(2)*l1p1(1);
compare2 = diff_l2(1)*l2p1(2) - diff_l2(2)*l2p1(1);
if ( xor((diff_l1(1)*l2p1(2) - diff_l1(2)*l2p1(1)) < compare1, ...
(diff_l1(1)*l2p2(2) - diff_l1(2)*l2p2(1)) < compare1) && ...
xor((diff_l2(1)*l1p1(2) - diff_l2(2)*l1p1(1)) < compare2, ...
(diff_l2(1)*l1p2(2) - diff_l2(2)*l1p2(1)) < compare2) )
cross = true;
end

Peter Bone, Jun 8, 2010
6. ### Peter BoneGuest

Peter Bone, Jun 8, 2010
7. ### Bastian ErdnuessGuest

Right, the argument above only works for the cases where the convex hull
of the four points spans a quadrilateral. But I forgot about the cases
where they just span a triangle. Thank's for the link with the solution.

Cheers,
Bastian

Bastian Erdnuess, Jun 9, 2010