daily pastebin goal
35%
SHARE
TWEET

Line intersection

keverman Jan 12th, 2019 (edited) 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct point
  2. {
  3.     int x, y;
  4.  
  5.     point(int new_x, int new_y)
  6.     {
  7.         x = new_x;
  8.         y = new_y;
  9.     }
  10.  
  11.     point operator-(point &other)
  12.     {
  13.         return point(x - other.x, y - other.y);
  14.     }
  15. };
  16.  
  17. long long cp(point a, point b)
  18. {
  19.     return (long long)a.x * b.y - (long long)a.y * b.x;
  20. }
  21.  
  22. bool intersect(point a, point b, point c, point d)
  23. {
  24.     // Create change vectors and their cross product
  25.     point r = b - a, s = d - c;
  26.     long long cp_rs = cp(r, s);
  27.  
  28.     if(cp_rs == 0) // Lines are parallel
  29.     {
  30.         if(cp(c - a, r) == 0) // Lines are colinear
  31.         {
  32.             if(r.x == 0 && s.x == 0) // Check if they're overlaping
  33.             {
  34.                 if(a.y > b.y) std::swap(a, b);
  35.                 if(c.y > d.y) std::swap(c, d);
  36.  
  37.                 return (b.y - c.y >= 0 && d.y - a.y >= 0);
  38.             }
  39.  
  40.             else
  41.             {
  42.                 if(a.x > b.x) std::swap(a, b);
  43.                 if(c.x > d.x) std::swap(c, d);
  44.  
  45.                 return (b.x - c.x >= 0 && d.x - a.x >= 0);
  46.             }
  47.         }
  48.  
  49.         return false;
  50.     }
  51.  
  52.     else // Lines aren't parallel
  53.     {
  54.         // Check where they intersect
  55.         double t = (double)cp(c - a, s) / cp_rs;
  56.         double u = (double)cp(c - a, r) / cp_rs;
  57.  
  58.         if(t <= 1 && t >= 0 && u <= 1 && u >= 0) return true; // Intersect without prolongation
  59.         return false; // Intersect with prolongation
  60.     }
  61. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top