• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Line intersection

keverman Jan 12th, 2019 (edited) 64 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.
Not a member of Pastebin yet?