Thread: Check if two lines intersect (not touch)?

  1. #1
    Registered User
    Join Date
    Feb 2013
    Location
    Sweden
    Posts
    171

    Question Check if two lines intersect (not touch)?

    So I found this post about how to check if two lines intersect. How to check if two given line segments intersect? - GeeksforGeeks and it works. What I wanted to do is to modify it if possible so that it only tells me if the lines intersect, but it is not supposed to tell me if they touch.

    If the start- or endpoint of both lines touch / intersect with each other the program should not write that they intersect.

    Code from link modified a little bit:
    Code:
    // A C++ program to check if two given line segments intersect 
    #include <iostream> 
    using namespace std; 
      
    struct Point 
    { 
        int x; 
        int y; 
    }; 
      
    // To find orientation of ordered triplet (p, q, r). 
    // The function returns following values 
    // 0 --> p, q and r are colinear 
    // 1 --> Clockwise 
    // 2 --> Counterclockwise 
    int orientation(Point p, Point q, Point r) 
    { 
        // See https://www.geeksforgeeks.org/orientation-3-ordered-points/ 
        // for details of below formula. 
        int val = (q.y - p.y) * (r.x - q.x) - 
                  (q.x - p.x) * (r.y - q.y); 
      
        if (val == 0) return 0;  // colinear 
      
        return (val > 0)? 1: 2; // clock or counterclock wise 
    } 
      
    // The main function that returns true if line segment 'p1q1' 
    // and 'p2q2' intersect. 
    bool doIntersect(Point p1, Point q1, Point p2, Point q2) 
    { 
        // Find the four orientations needed for general and 
        // special cases 
        int o1 = orientation(p1, q1, p2); 
        int o2 = orientation(p1, q1, q2); 
        int o3 = orientation(p2, q2, p1); 
        int o4 = orientation(p2, q2, q1); 
    
    
    	std::cout << "o1: " << o1 << "\n";
    	std::cout << "o2: " << o2 << "\n";
    	std::cout << "o3: " << o3 << "\n";
    	std::cout << "o4: " << o4 << "\n";
        // General case 
        if (o1 != o2 && o3 != o4) 
            return true; 
      
        return false; // Doesn't fall in any of the above cases 
    } 
      
    // Driver program to test above functions 
    int main() 
    { 
        struct Point p1 = {1, 1}, q1 = {10, 1}; 
        struct Point p2 = {1, 2}, q2 = {10, 2}; 
      
        doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; 
      
        p1 = {10, 0}, q1 = {0, 10}; 
        p2 = {0, 0}, q2 = {10, 10}; 
        doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; 
      
        p1 = {-5, -5}, q1 = {0, 0}; 
        p2 = {1, 1}, q2 = {10, 10}; 
        doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; 
    
    
        // These lines should not intersect
        p1 = {-4, -2}, q1 = {4, 4}; 
        p2 = {4, 0}, q2 = {4, 4}; 
        doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; 
    
    
    	getchar();
        return 0; 
    }
    Last edited by Salem; 11-25-2018 at 01:51 PM. Reason: Remove crayola

  2. #2
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Run the function doIntersect on data that you think it should return false; but, it returns true instead.
    Look at the orientation results; I think you will likely see a simple code fix.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  3. #3
    Registered User
    Join Date
    Feb 2013
    Location
    Sweden
    Posts
    171
    So did you mean that I should remove the part that checks for colinear lines?

    Code:
    int orientation(Point p, Point q, Point r) 
    { 
        // See https://www.geeksforgeeks.org/orientation-3-ordered-points/ 
        // for details of below formula. 
        int val = (q.y - p.y) * (r.x - q.x) - 
                  (q.x - p.x) * (r.y - q.y); 
       
         // Remove? if (val == 0) return 0;  // colinear 
       
        return (val > 0)? 1: 2; // clock or counterclock wise 
    } 
    
    It does return what I expected when I removed it, but I don't know
    if that is what you meant or if that is the fix.
    Last edited by DecoratorFawn82; 11-26-2018 at 12:57 PM.

  4. #4
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Quote Originally Posted by DecoratorFawn82 View Post
    So did you mean that I should remove the part that checks for colinear lines?

    Code:
    int orientation(Point p, Point q, Point r) 
    { 
        // See https://www.geeksforgeeks.org/orientation-3-ordered-points/ 
        // for details of below formula. 
        int val = (q.y - p.y) * (r.x - q.x) - 
                  (q.x - p.x) * (r.y - q.y); 
       
         // Remove? if (val == 0) return 0;  // colinear 
       
        return (val > 0)? 1: 2; // clock or counterclock wise 
    } 
    
    It does return what I expected when I removed it, but I don't know
    if that is what you meant or if that is the fix.
    I expect you to run the code and see how it works!!!!!!!
    Using data that you think the code will say yes it intersects; when you think you want it not to return yes.
    After looking at the orientation values I expect a thinking human being to see a pattern.

    This is not a free code service website.

    We expect the posters to show some effort!

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Without, real data it is likely no one will be able to help you.

    Because, it is not clear when you want the results change to me.
    I think that if the line segments are on the same line you want the result to be false; but, without real data I can not be sure.

    Code:
    o1: 2
    o2: 2
    o3: 1
    o4: 1
    No
    o1: 2
    o2: 1
    o3: 1
    o4: 2
    Yes
    o1: 0
    o2: 0
    o3: 0
    o4: 0
    No
    o1: 1
    o2: 0
    o3: 2
    o4: 0
    Yes
    Edit: I was thinking you wanted the last "yes" to be "no"; but, you seem either want something else or you are code blind.

    Tim S.
    Last edited by stahta01; 11-26-2018 at 02:31 PM.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  6. #6
    Registered User
    Join Date
    Feb 2013
    Location
    Sweden
    Posts
    171
    Here is some real data that I've been testing to find the pattern.
    This is correct assumption: "I was thinking you wanted the last "yes" to be "no";"
    And yup, you are probably right: "
    or you are code blind."

    Most output I did get using the modified program was correct, but I tested
    with more data afterwards. Then it was not correct.

    Using the modified version of the program. All that was modified was:

    Code:
    int orientation(Point p, Point q, Point r) 
    { 
        // See https://www.geeksforgeeks.org/orientation-3-ordered-points/ 
        // for details of below formula. 
        int val = (q.y - p.y) * (r.x - q.x) - 
                  (q.x - p.x) * (r.y - q.y); 
       
        //if (val == 0) return 0;  // colinear 
       
        return (val > 1)? 1: 2; // clock or counterclock wise 
    } 
    
    Code:
     
        // These lines should not intersect
        p1 = {-4, -2}, q1 = {4, 4}; 
        p2 = {4, 0}, q2 = {4, 4}; 
        doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; 
     
        std::cout << "\n\n\n\n\n\n\n\n";
        // These lines should not intersect
        p1 = {-4, -2}, q1 = {4, 4}; 
        p2 = {4, 0}, q2 = {4, 4}; 
        doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; 
     
        // No intersection
        p1 = {1, 4}, q1 = {2, 2}; 
        p2 = {2, 2}, q2 = {2, 1}; 
        doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; 
    
    
        // No intersection
        p1 = {1, 4}, q1 = {-1, 5}; 
        p2 = {-1, 5}, q2 = {2, 1}; 
        doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; 
    
    
        // No intersection
        p1 = {1, 4}, q1 = {2, 2}; 
        p2 = {2, 2}, q2 = {2, 1}; 
        doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; 
    
    
        std::cout << "\n\n\n\n\n\n\n\n";
        // Intersects
        p1 = {10, 0}, q1 = {0, 10}; 
        p2 = {0, 0}, q2 = {10, 10}; 
        doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; 
        
        // No intersect
        p1 = {-5, -5}, q1 = {0, 0}; 
        p2 = {1, 1}, q2 = {10, 10}; 
        doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; 
    
    
        std::cout << "\n\n\n\n\n\n\n\n";
        // No touch
        p1 = {-4, 6}, q1 = {-4, 4}; 
        p2 = {-4, 5}, q2 = {-2, 5}; 
        doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; 
     
         // No intersect
        p1 = {-6, 5}, q1 = {-4, 5}; 
        p2 = {-4, 6}, q2 = {-2, 4}; 
        doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; 
    
    
        std::cout << std::string(4, '\n');
    
    
        // Intersection
        p1 = {-6, 1}, q1 = {-4, 3}; 
        p2 = {-6, 2}, q2 = {-4, 2}; 
        doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; 
    
    
        // No intersection (totally off)
        p1 = {-6, 2}, q1 = {-4, 2}; 
        p2 = {-5, 1}, q2 = {-4, 0}; 
        doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; 
    
    
        // No touch
        p1 = {-6, 2}, q1 = {-4, 2}; 
        p2 = {-4, 2}, q2 = {-4, 4}; 
        doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; 
    
    
        // No touch
        p1 = {-6, -2}, q1 = {-4, -2}; 
        p2 = {-4, -2}, q2 = {-4, -4}; 
        doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";
    Output:
    o1: 2
    o2: 2
    o3: 1
    o4: 1
    No
    o1: 2
    o2: 1
    o3: 1
    o4: 2
    Yes
    o1: 2
    o2: 2
    o3: 2
    o4: 2
    No
    o1: 1
    o2: 2
    o3: 2
    o4: 2
    No


    o1: 1
    o2: 2
    o3: 2
    o4: 2
    No
    o1: 2
    o2: 2
    o3: 2
    o4: 2
    No
    o1: 2
    o2: 2
    o3: 2
    o4: 2
    No
    o1: 2
    o2: 2
    o3: 2
    o4: 2
    No


    o1: 2
    o2: 1
    o3: 1
    o4: 2
    Yes
    o1: 2
    o2: 2
    o3: 2
    o4: 2
    No


    o1: 2
    o2: 2
    o3: 2
    o4: 1
    No
    o1: 2
    o2: 1
    o3: 1
    o4: 1
    No

    o1: 2
    o2: 1
    o3: 1
    o4: 2
    Yes
    o1: 1
    o2: 1
    o3: 2
    o4: 2
    No
    o1: 2
    o2: 2
    o3: 2
    o4: 2
    No
    o1: 2
    o2: 1
    o3: 1
    o4: 2
    Yes
    Last edited by DecoratorFawn82; 11-26-2018 at 04:24 PM.

  7. #7
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Do you have any reason to think you should modify "orientation" method/function?

    Edit: Doing random code changes mean you do not have what it takes to learn to program. Note, if you have a real reason; maybe you can learn to program.

    Tim S.
    Last edited by stahta01; 11-26-2018 at 04:33 PM.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  8. #8
    Registered User
    Join Date
    Feb 2013
    Location
    Sweden
    Posts
    171
    I might have misinterpreted something then I guess.
    The reason I thouhght it was in the orientation method was because
    it gives the output to:

    Code:
        int o1 = orientation(p1, q1, p2); 
        int o2 = orientation(p1, q1, q2); 
        int o3 = orientation(p2, q2, p1); 
        int o4 = orientation(p2, q2, q1);
    So I thought that the values that the orientation method returned was
    wrong.

    But I could probably change something in the method doIntersect(...) to
    modify the source code for my purpose. I'll just need some more time to
    figure it out.

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    You have no understanding of the problem domain; and, no idea how to understand the code you have found.
    Try again to do what I suggested and if you can understand the results you should see a fix.

    Run the original program with the new test data and you should see what should be edited in doIntersect.

    Tim S.
    Last edited by stahta01; 11-26-2018 at 04:50 PM. Reason: grammar
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  10. #10
    Registered User
    Join Date
    Feb 2013
    Location
    Sweden
    Posts
    171
    Quote Originally Posted by stahta01 View Post
    You have no understanding of the problem domain; and, no idea how to understand the code you have found.
    Try again to do what I suggested and if you can understand the results you should see a fix.

    Run the original program with the new test data and you should see what should be edited in doIntersect.

    Tim S.
    "And yup, you are probably right: "or you are code blind.""
    I've already admitted that I don't understand the code. No need to push me down even further.

    And yes I will do a run test with different test data again.

  11. #11
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    I watched a person go for an Computer Science major who had no ability because his family said to do so.
    He likely could have been a great business major; but, he had no idea about how to program and was always just copying other people work.
    He had a great memory and likely could have done well in other fields; but, programming is about understanding not just remembering.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Ubuntu Touch
    By siavoshkc in forum Tech Board
    Replies: 7
    Last Post: 08-09-2013, 06:08 AM
  2. Check if two line segments intersect
    By kerrymaid in forum C Programming
    Replies: 7
    Last Post: 02-10-2013, 12:21 AM
  3. Touch typing
    By jacek in forum Tech Board
    Replies: 34
    Last Post: 12-01-2009, 10:27 PM
  4. Intersect-test-solution, whats it called?
    By Raven Arkadon in forum C++ Programming
    Replies: 2
    Last Post: 04-12-2008, 08:09 PM

Tags for this Thread