{"id":25834,"date":"2017-10-25T20:58:56","date_gmt":"2017-10-25T15:28:56","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25834"},"modified":"2017-10-25T20:58:56","modified_gmt":"2017-10-25T15:28:56","slug":"how-to-check-if-two-given-line-segments-intersect","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/how-to-check-if-two-given-line-segments-intersect\/","title":{"rendered":"How to check if two given line segments intersect?"},"content":{"rendered":"

Given two line segments (p1, q1) and (p2, q2), find if the given line segments intersect with each other.<\/span><\/p>\n

Before we discuss solution, let us define notion of orientation<\/strong><\/a>. Orientation of an ordered triplet of points in the\u00a0plane can be
\n\u2013counterclockwise
\n\u2013clockwise
\n\u2013colinear
\nThe following diagram shows different possible orientations of (a, b, c)<\/p>\n

\"How<\/p>\n

\n

[ad type=\u201dbanner\u201d]<\/h4>\n

How is Orientation useful here?<\/strong><\/h4>\n<\/div>\n

Two segments (p1,q1) and (p2,q2) intersect if and only if\u00a0one of the following two conditions is verified<\/p>\n

1.\u00a0General Case:<\/em><\/strong>
\n\u2013 (p1, q1, p2) and (p1, q1, q2) have different\u00a0orientations and
\n\u2013 (p2, q2,\u00a0p1) and (p2, q2,\u00a0q1) have different\u00a0orientations.<\/p>\n

\"How<\/p>\n

\u00a0<\/p>\n

\"How<\/p>\n

\u00a0<\/p>\n[ad type=\u201dbanner\u201d]\n

2. Special Case <\/em><\/strong>
\n\u2013 (p1, q1, p2), (p1, q1, q2), (p2, q2, p1), and (p2, q2, q1) are\u00a0all collinear and
\n\u2013\u00a0the x-projections of (p1, q1) and (p2, q2) intersect
\n\u2013 the y-projections of (p1, q1) and (p2, q2) intersect<\/p>\n

\"How<\/p>\n

Following is C++ implementation based on above idea.<\/p>\n

\n
\n\n\n\n
\n
\n
\n

\/\/ A C++ program to check if two given line segments intersect<\/code><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%23include%20%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0Astruct%20Point%0A%7B%0A%20%20%20%20int%20x%3B%0A%20%20%20%20int%20y%3B%0A%7D%3B%0A%20%0A%2F%2F%20Given%20three%20colinear%20points%20p%2C%20q%2C%20r%2C%20the%20function%20checks%20if%0A%2F%2F%20point%20q%20lies%20on%20line%20segment%20\u2019pr\u2019%0Abool%20onSegment(Point%20p%2C%20Point%20q%2C%20Point%20r)%0A%7B%0A%20%20%20%20if%20(q.x%20%3C%3D%20max(p.x%2C%20r.x)%20%26%26%20q.x%20%3E%3D%20min(p.x%2C%20r.x)%20%26%26%0A%20%20%20%20%20%20%20%20q.y%20%3C%3D%20max(p.y%2C%20r.y)%20%26%26%20q.y%20%3E%3D%20min(p.y%2C%20r.y))%0A%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20return%20false%3B%0A%7D%0A%20%0A%2F%2F%20To%20find%20orientation%20of%20ordered%20triplet%20(p%2C%20q%2C%20r).%0A%2F%2F%20The%20function%20returns%20following%20values%0A%2F%2F%200%20\u2013%3E%20p%2C%20q%20and%20r%20are%20colinear%0A%2F%2F%201%20\u2013%3E%20Clockwise%0A%2F%2F%202%20\u2013%3E%20Counterclockwise%0Aint%20orientation(Point%20p%2C%20Point%20q%2C%20Point%20r)%0A%7B%0A%20%20%20%20%2F%2F%20See%20http%3A%2F%2Fwww.geeksforgeeks.org%2Forientation-3-ordered-points%2F%0A%20%20%20%20%2F%2F%20for%20details%20of%20below%20formula.%0A%20%20%20%20int%20val%20%3D%20(q.y%20-%20p.y)%20*%20(r.x%20-%20q.x)%20-%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20(q.x%20-%20p.x)%20*%20(r.y%20-%20q.y)%3B%0A%20%0A%20%20%20%20if%20(val%20%3D%3D%200)%20return%200%3B%20%20%2F%2F%20colinear%0A%20%0A%20%20%20%20return%20(val%20%3E%200)%3F%201%3A%202%3B%20%2F%2F%20clock%20or%20counterclock%20wise%0A%7D%0A%20%0A%2F%2F%20The%20main%20function%20that%20returns%20true%20if%20line%20segment%20\u2019p1q1\u2019%0A%2F%2F%20and%20\u2019p2q2\u2019%20intersect.%0Abool%20doIntersect(Point%20p1%2C%20Point%20q1%2C%20Point%20p2%2C%20Point%20q2)%0A%7B%0A%20%20%20%20%2F%2F%20Find%20the%20four%20orientations%20needed%20for%20general%20and%0A%20%20%20%20%2F%2F%20special%20cases%0A%20%20%20%20int%20o1%20%3D%20orientation(p1%2C%20q1%2C%20p2)%3B%0A%20%20%20%20int%20o2%20%3D%20orientation(p1%2C%20q1%2C%20q2)%3B%0A%20%20%20%20int%20o3%20%3D%20orientation(p2%2C%20q2%2C%20p1)%3B%0A%20%20%20%20int%20o4%20%3D%20orientation(p2%2C%20q2%2C%20q1)%3B%0A%20%0A%20%20%20%20%2F%2F%20General%20case%0A%20%20%20%20if%20(o1%20!%3D%20o2%20%26%26%20o3%20!%3D%20o4)%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%2F%2F%20Special%20Cases%0A%20%20%20%20%2F%2F%20p1%2C%20q1%20and%20p2%20are%20colinear%20and%20p2%20lies%20on%20segment%20p1q1%0A%20%20%20%20if%20(o1%20%3D%3D%200%20%26%26%20onSegment(p1%2C%20p2%2C%20q1))%20return%20true%3B%0A%20%0A%20%20%20%20%2F%2F%20p1%2C%20q1%20and%20p2%20are%20colinear%20and%20q2%20lies%20on%20segment%20p1q1%0A%20%20%20%20if%20(o2%20%3D%3D%200%20%26%26%20onSegment(p1%2C%20q2%2C%20q1))%20return%20true%3B%0A%20%0A%20%20%20%20%2F%2F%20p2%2C%20q2%20and%20p1%20are%20colinear%20and%20p1%20lies%20on%20segment%20p2q2%0A%20%20%20%20if%20(o3%20%3D%3D%200%20%26%26%20onSegment(p2%2C%20p1%2C%20q2))%20return%20true%3B%0A%20%0A%20%20%20%20%20%2F%2F%20p2%2C%20q2%20and%20q1%20are%20colinear%20and%20q1%20lies%20on%20segment%20p2q2%0A%20%20%20%20if%20(o4%20%3D%3D%200%20%26%26%20onSegment(p2%2C%20q1%2C%20q2))%20return%20true%3B%0A%20%0A%20%20%20%20return%20false%3B%20%2F%2F%20Doesn\u2019t%20fall%20in%20any%20of%20the%20above%20cases%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20struct%20Point%20p1%20%3D%20%7B1%2C%201%7D%2C%20q1%20%3D%20%7B10%2C%201%7D%3B%0A%20%20%20%20struct%20Point%20p2%20%3D%20%7B1%2C%202%7D%2C%20q2%20%3D%20%7B10%2C%202%7D%3B%0A%20%0A%20%20%20%20doIntersect(p1%2C%20q1%2C%20p2%2C%20q2)%3F%20cout%20%3C%3C%20%22Yes%5Cn%22%3A%20cout%20%3C%3C%20%22No%5Cn%22%3B%0A%20%0A%20%20%20%20p1%20%3D%20%7B10%2C%200%7D%2C%20q1%20%3D%20%7B0%2C%2010%7D%3B%0A%20%20%20%20p2%20%3D%20%7B0%2C%200%7D%2C%20q2%20%3D%20%7B10%2C%2010%7D%3B%0A%20%20%20%20doIntersect(p1%2C%20q1%2C%20p2%2C%20q2)%3F%20cout%20%3C%3C%20%22Yes%5Cn%22%3A%20cout%20%3C%3C%20%22No%5Cn%22%3B%0A%20%0A%20%20%20%20p1%20%3D%20%7B-5%2C%20-5%7D%2C%20q1%20%3D%20%7B0%2C%200%7D%3B%0A%20%20%20%20p2%20%3D%20%7B1%2C%201%7D%2C%20q2%20%3D%20%7B10%2C%2010%7D%3B%0A%20%20%20%20doIntersect(p1%2C%20q1%2C%20p2%2C%20q2)%3F%20cout%20%3C%3C%20%22Yes%5Cn%22%3A%20cout%20%3C%3C%20%22No%5Cn%22%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<\/div>\n<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Output:<\/p>\n

No\r\nYes\r\nNo<\/pre>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
How to check if two given line segments intersect? – Geometric Algorithms – Orientation of an ordered triplet of points in the plane.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1,73905],"tags":[75746,75745,75751,75747,75748,75750,75752,75753,75749],"class_list":["post-25834","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","category-geometric-algorithms","tag-a-line-that-intersects-two-non-intersecting-planes","tag-a-line-that-intersects-two-or-more-lines","tag-intersecting-lines-definition","tag-intersection-of-two-lines-in-3d","tag-line-line-intersection","tag-line-segment-intersection","tag-parallel-lines-definition","tag-perpendicular-line","tag-what-is-the-intersection-of-two-planes"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25834","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25834"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25834\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25834"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25834"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25834"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}