Line segment intersection

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

  1. Peter Bone

    Peter Bone Guest

    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
    #1
    1. Advertisements

  2. Peter Bone

    Henry Guest

    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)
     
    Henry, Jun 8, 2010
    #2
    1. Advertisements

  3. Peter Bone

    Peter Bone Guest

    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
    #3
  4. 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
     
    Bastian Erdnuess, Jun 8, 2010
    #4
  5. Peter Bone

    Peter Bone Guest

    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
    #5
  6. Peter Bone

    Peter Bone Guest

    Peter Bone, Jun 8, 2010
    #6
  7. 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
    #7
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.