Line segment intersection

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.

 

You will need to specify how a random line segment is chosen, to avoid
falling into a Bertrand paradox
http://en.wikipedia.org/wiki/Bertrand_paradox_(probability)

 

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?

 

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
lead to the result.

Can you post the code for your simulation?

Cheers,
Bastian

 

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

 

I found the answer below. It's exactly 25/108
http://www.mathkb.com/Uwe/Forum.aspx/research/3958

 

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