C++ Program to Use Above Below Primitive to Test Whether Two Lines Intersect

«
»
This is a C++ Program to check whether two lines intersect to each other. The above-below primitive can be used to test whether a line intersects a line segment. It does iff one endpoint of the segment is to the left of the line and the other is to the right. Segment intersection is similar but more complicated, and we refer you to implementations described below. The decision whether two segments intersect if they share an endpoint depends upon your application and is representative of the problems of degeneracy.

Here is source code of the C++ Program to Use Above Below Primitive to Test Whether Two Lines Intersect. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<time.h>
  2. #include<stdlib.h>
  3. #include<iostream>
  4. #include<math.h>
  5.  
  6. using namespace std;
  7. const int LOW = 0;
  8. const int HIGH = 10;
  9. int main(int argc, char **argv)
  10. {
  11.     time_t seconds;
  12.     time(&seconds);
  13.     srand((unsigned int) seconds);
  14.  
  15.     int x1, x2, y1, y2;
  16.     x1 = rand() % (HIGH - LOW + 1) + LOW;
  17.     x2 = rand() % (HIGH - LOW + 1) + LOW;
  18.     y1 = rand() % (HIGH - LOW + 1) + LOW;
  19.     y2 = rand() % (HIGH - LOW + 1) + LOW;
  20.  
  21.     cout << "The Equation of the 1st line is : (" << (y2 - y1) << ")x+(" << (x1
  22.             - x2) << ")y+(" << (x2 * y1 - x1 * y2) << ") = 0\n";
  23.  
  24.     int p1, p2, q1, q2;
  25.     p1 = rand() % (HIGH - LOW + 1) + LOW;
  26.     p2 = rand() % (HIGH - LOW + 1) + LOW;
  27.     q1 = rand() % (HIGH - LOW + 1) + LOW;
  28.     q2 = rand() % (HIGH - LOW + 1) + LOW;
  29.  
  30.     cout << "The Equation of the 2nd line is : (" << (q2 - q1) << ")x+(" << (p1
  31.             - p2) << ")y+(" << (p2 * q1 - p1 * q2) << ") = 0\n";
  32.  
  33.     int s1 = (y2 - y1) * p1 + (x1 - x2) * q1 + (x2 * y1 - x1 * y2);
  34.     if (s1 < 0)
  35.     {
  36.         int s2 = (y2 - y1) * p2 + (x1 - x2) * q2 + (x2 * y1 - x1 * y2);
  37.         if (s2 >= 0)
  38.             cout << "The lines intersect";
  39.         else if (s2 < 0)
  40.             cout << "The lines doesn't intersect";
  41.  
  42.     }
  43.     else if (s1 > 0)
  44.     {
  45.         int s2 = (y2 - y1) * p2 + (x1 - x2) * q2 + (x2 * y1 - x1 * y2);
  46.         if (s2 <= 0)
  47.             cout << "The lines intersect";
  48.         else if (s2 > 0)
  49.             cout << "The lines doesn't intersect";
  50.     }
  51.     else
  52.         cout << "The point lies on the line";
  53.     return 0;
  54. }

Output:

$ g++ LineIntersection.cpp
$ a.out
 
The Equation of the 1st line is : (4)x+(1)y+(-6) = 0
The Equation of the 2nd line is : (-1)x+(-9)y+(46) = 0
The lines doesn't intersect
 
The Equation of the 1st line is : (3)x+(7)y+(-59) = 0
The Equation of the 2nd line is : (-8)x+(1)y+(56) = 0
The lines intersect
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.