{"id":286,"date":"2011-08-29T15:25:20","date_gmt":"2011-08-29T15:25:20","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/2011\/08\/29\/intersecting-lines\/"},"modified":"2016-08-07T13:40:36","modified_gmt":"2016-08-07T18:40:36","slug":"intersecting-lines","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2011\/08\/29\/intersecting-lines\/","title":{"rendered":"Intersecting Lines"},"content":{"rendered":"<div xmlns:mwsh=\"https:\/\/www.mathworks.com\/namespace\/mcode\/v1\/syntaxhighlight.dtd\" class=\"content\">\r\n   <introduction>\r\n      <p>Today I am writing this post in collaboration with my friend and colleague, <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/answers\/contributors\/222043-lucio-cetto\">Lucio Cetto<\/a>. Ever need to know if two line segments intersect?  There are lots of ways to do this, and I thought I would show a few solutions\r\n         here.  I haven't put much thought into how to set up the data so I can vectorize the case for finding out which segments among\r\n         many intersect and with which ones.  At least for now :-)\r\n      <\/p>\r\n   <\/introduction>\r\n   <h3>Contents<\/h3>\r\n   <div>\r\n      <ul>\r\n         <li><a href=\"#1\">Example<\/a><\/li>\r\n         <li><a href=\"#3\">First Algorithm<\/a><\/li>\r\n         <li><a href=\"#17\">Second Algorithm<\/a><\/li>\r\n         <li><a href=\"#24\">Ignored Issues and Other Algorithms<\/a><\/li>\r\n         <li><a href=\"#25\">Ever Run Into This Problem Yourself?<\/a><\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <h3>Example<a name=\"1\"><\/a><\/h3>\r\n   <p>Let's start with with some simple line segments.  The first column represents to x-values of the line segment, the second\r\n      column represents the y-values.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">line1 = [.5 1; 1 0];\r\nline2 = [.5 0; 1 1];<\/pre><p>Plot the data.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">h = plot(line1(:,1),line1(:,2));\r\nhold <span style=\"color: #A020F0\">all<\/span>\r\nh(2) = plot(line2(:,1),line2(:,2));\r\nset(h,<span style=\"color: #A020F0\">'linewidth'<\/span>,2)\r\naxis([0 1 0 1])<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/286\/lineIntersect_01.png\"> <h3>First Algorithm<a name=\"3\"><\/a><\/h3>\r\n   <p>Using equation y = mx+b, solve for x assuming 2 lines intersect.  Then see if that x value is in the necessary range.  Special\r\n      cases: vertical lines (m==inf) and parallel lines (m1 == m2)\r\n   <\/p>\r\n   <p>First find slopes and intercepts for both line segments. Here are slopes.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">slope = @(line) (line(2,2) - line(1,2))\/(line(2,1) - line(1,1));\r\nm1 = slope(line1)\r\nm2 = slope(line2)<\/pre><pre style=\"font-style:oblique\">m1 =\r\n    -2\r\nm2 =\r\n     2\r\n<\/pre><p>Here are the intercepts.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">intercept = @(line,m) line(1,2) - m*line(1,1);\r\nb1 = intercept(line1,m1)\r\nb2 = intercept(line2,m2)\r\nxintersect = (b2-b1)\/(m1-m2)\r\nyintersect = m1*xintersect + b1<\/pre><pre style=\"font-style:oblique\">b1 =\r\n     2\r\nb2 =\r\n    -1\r\nxintersect =\r\n         0.75\r\nyintersect =\r\n          0.5\r\n<\/pre><p>Plot results.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">plot(xintersect,yintersect,<span style=\"color: #A020F0\">'m*'<\/span>,<span style=\"color: #A020F0\">'markersize'<\/span>,8)\r\nlegend({<span style=\"color: #A020F0\">'line1'<\/span>,<span style=\"color: #A020F0\">'line2'<\/span>,<span style=\"color: #A020F0\">'intersection'<\/span>},<span style=\"color: #A020F0\">'Location'<\/span>,<span style=\"color: #A020F0\">'West'<\/span>)\r\nhold <span style=\"color: #A020F0\">off<\/span><\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/286\/lineIntersect_02.png\"> <p>Now check that the intersection point is on the line segment and not past the end.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">isPointInside = @(xint,myline) <span style=\"color: #0000FF\">...<\/span>\r\n    (xint &gt;= myline(1,1) &amp;&amp; xint &lt;= myline(2,1)) || <span style=\"color: #0000FF\">...<\/span>\r\n    (xint &gt;= myline(2,1) &amp;&amp; xint &lt;= myline(1,1));\r\ninside = isPointInside(xintersect,line1) &amp;&amp; <span style=\"color: #0000FF\">...<\/span>\r\n         isPointInside(xintersect,line2)\r\n<span style=\"color: #228B22\">%<\/span><\/pre><pre style=\"font-style:oblique\">inside =\r\n     1\r\n<\/pre><p>Try with different lines now.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">line1 = [.5 1; <span style=\"color: #0000FF\">...<\/span>\r\n        1 0];\r\nline2 = [.5 0; <span style=\"color: #0000FF\">...<\/span>\r\n        0 -1];<\/pre><p>Compute new intersection.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">m1 = slope(line1);\r\nm2 = slope(line2);\r\nb1 = intercept(line1,m1);\r\nb2 = intercept(line2,m2);\r\nxintersect = (b2-b1)\/(m1-m2)\r\nyintersect = m1*xintersect + b1<\/pre><pre style=\"font-style:oblique\">xintersect =\r\n         0.75\r\nyintersect =\r\n          0.5\r\n<\/pre><p>Show the plot.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">figure\r\nh = plot(line1(:,1),line1(:,2));\r\nhold <span style=\"color: #A020F0\">all<\/span>\r\nh(2) = plot(line2(:,1),line2(:,2));\r\nset(h,<span style=\"color: #A020F0\">'linewidth'<\/span>,2)\r\nlegend(h,{<span style=\"color: #A020F0\">'line1'<\/span>,<span style=\"color: #A020F0\">'line2'<\/span>},<span style=\"color: #A020F0\">'Location'<\/span>,<span style=\"color: #A020F0\">'West'<\/span>)\r\nplot(xintersect,yintersect,<span style=\"color: #A020F0\">'g*'<\/span>)\r\nhold <span style=\"color: #A020F0\">off<\/span>\r\naxis([-1 1 -1 1])<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/286\/lineIntersect_03.png\"> <p>Is the intersect point on both line segments?<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">inside = isPointInside(xintersect,line1) &amp;&amp; <span style=\"color: #0000FF\">...<\/span>\r\n         isPointInside(xintersect,line2)<\/pre><pre style=\"font-style:oblique\">inside =\r\n     0\r\n<\/pre><p>No. The intersect point lies on only one line segment, meaning that the two segments don't intersect.<\/p>\r\n   <p>There's still more to think about.  What if the two lines segments have the same slope?  There are 3 cases for this.  First\r\n      case: the segments are parallel and therefore no intersection.  Second and third cases, they are part of the same line, in\r\n      which case, we have to check to see if they overlap or not (in other words, they may intersect or not, for 2 more cases).\r\n   <\/p>\r\n   <p>Here are two parallel lines with different values for their y-intercept.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">line1 = [.5 1; <span style=\"color: #0000FF\">...<\/span>\r\n        1 0];\r\nline2 = [.5 3; <span style=\"color: #0000FF\">...<\/span>\r\n        1 2];<\/pre><p>Plot the line segments.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">figure\r\nh = plot(line1(:,1),line1(:,2));\r\nhold <span style=\"color: #A020F0\">all<\/span>\r\nh(2) = plot(line2(:,1),line2(:,2));\r\nset(h,<span style=\"color: #A020F0\">'linewidth'<\/span>,2)\r\nlegend(h,{<span style=\"color: #A020F0\">'line1'<\/span>,<span style=\"color: #A020F0\">'line2'<\/span>},<span style=\"color: #A020F0\">'Location'<\/span>,<span style=\"color: #A020F0\">'West'<\/span>)\r\nhold <span style=\"color: #A020F0\">off<\/span><\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/286\/lineIntersect_04.png\"> <p>See that slopes are equal, and intercepts are not.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">m1 = slope(line1);\r\nm2 = slope(line2);\r\nb1 = intercept(line1,m1);\r\nb2 = intercept(line2,m2);\r\nsameSlope = abs(m1-m2) &lt; eps(m1)\r\ndifferentIntercept = abs(b1-b2) &gt; eps(b1)\r\nisParallel = sameSlope &amp;&amp; differentIntercept<\/pre><pre style=\"font-style:oblique\">sameSlope =\r\n     1\r\ndifferentIntercept =\r\n     1\r\nisParallel =\r\n     1\r\n<\/pre><h3>Second Algorithm<a name=\"17\"><\/a><\/h3>\r\n   <p>Here's another algorithm for seeing if two lines intersect.  The idea is to choose one line, and see if the end points from\r\n      the other line lie on the same side.  If they do, there's no way the lines have a point of intersection.  If not, the second\r\n      line might intersect the first one, or the point of intersection may fall outside the limits of the first line segment.  A\r\n      way to test that is to reverse the roles of lines 1 and 2 and do the test again.\r\n   <\/p>\r\n   <p>The test for checking which side of the line a point falls on is simple. Plug in the values for the end points of line 2 into\r\n      the equation for line 1.  If they are both the same sign, then they both fall on the same side.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">line1 = [.5 1; <span style=\"color: #0000FF\">...<\/span>\r\n        1 0];\r\nline2 = [.5 0; <span style=\"color: #0000FF\">...<\/span>\r\n        0 -1];\r\nfigure\r\nh = plot(line1(:,1),line1(:,2));\r\nhold <span style=\"color: #A020F0\">all<\/span>\r\nh(2) = plot(line2(:,1),line2(:,2));\r\nset(h,<span style=\"color: #A020F0\">'linewidth'<\/span>,2)\r\naxis([0 1 -1 2])<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/286\/lineIntersect_05.png\"> <p>Get slope and intercept of both lines.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">m1 = slope(line1)\r\nm2 = slope(line2)\r\nb1 = intercept(line1,m1)\r\nb2 = intercept(line2,m2)<\/pre><pre style=\"font-style:oblique\">m1 =\r\n    -2\r\nm2 =\r\n     2\r\nb1 =\r\n     2\r\nb2 =\r\n    -1\r\n<\/pre><p>Evaluate the x value of end-points of the second line using the equation y = m*x + b of the first line<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">lineEq = @(m,b, myline) m * myline(:,1) + b\r\nyEst2 = lineEq(m1, b1, line2)\r\nplot(line2(:,1),yEst2,<span style=\"color: #A020F0\">'om'<\/span>)<\/pre><pre style=\"font-style:oblique\">lineEq = \r\n    @(m,b,myline)m*myline(:,1)+b\r\nyEst2 =\r\n     1\r\n     2\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/286\/lineIntersect_06.png\"> <p>Subtract the end values from the ends of <tt>line2<\/tt> and we find that both values are positive, meaning we don't find that the segment straddles <tt>line2<\/tt>.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">enderr = @(ends,line) ends - line(:,2)\r\nerrs1 = enderr(yEst2,line2)<\/pre><pre style=\"font-style:oblique\">enderr = \r\n    @(ends,line)ends-line(:,2)\r\nerrs1 =\r\n     1\r\n     3\r\n<\/pre><p>Next reverse the roles of lines 1 and 2 and check to see if the end points of line 2 fall on the same side of line 1.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">yEst1 = lineEq(m2, b2, line1)\r\nplot(line1(:,1),yEst1,<span style=\"color: #A020F0\">'or'<\/span>)\r\nerrs2 = enderr(yEst1,line1)<\/pre><pre style=\"font-style:oblique\">yEst1 =\r\n     0\r\n     1\r\nerrs2 =\r\n    -1\r\n     1\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/286\/lineIntersect_07.png\"> <p>In this case we find that the differences between the predicted y values and the real y values of line 1 have different signs,\r\n      which means that if line 2 was long enough there would exist an intersection.\r\n   <\/p>\r\n   <p>To test for an actual intersection, we now just need to verify that the condition applies in both directions.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">possibleIntersection =  sum(sign(errs1))==0 &amp;&amp; sum(sign(errs2))==0<\/pre><pre style=\"font-style:oblique\">possibleIntersection =\r\n     0\r\n<\/pre><h3>Ignored Issues and Other Algorithms<a name=\"24\"><\/a><\/h3>\r\n   <p>Here are a list of issues that this post does not solve:<\/p>\r\n   <div>\r\n      <ul>\r\n         <li>Vertical line(s) (infinite slope)<\/li>\r\n      <\/ul>\r\n   <\/div><pre>        Can work around this by rotating the lines to avoid\r\n        verticals (try random rotations, or perhaps rotate\r\n        through a computed angle so largest angle is bisected\r\n        vertically.<\/pre><div>\r\n      <ul>\r\n         <li>Degenerate line (single point)<\/li>\r\n         <li>Parallel lines with same intercept<\/li>\r\n         <li>More than two line segments<\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <p>In addition, there is at least one more algorithm that we haven't talked about here, called Sweep Line Algorithm.\r\n   <\/p>\r\n   <h3>Ever Run Into This Problem Yourself?<a name=\"25\"><\/a><\/h3>\r\n   <p>How did you solve it?  Let us know <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p=286#respond\">here<\/a>.\r\n   <\/p><script language=\"JavaScript\">\r\n<!--\r\n\r\n    function grabCode_fc8413fa750e45d09f7ca054752decf3() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='fc8413fa750e45d09f7ca054752decf3 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' fc8413fa750e45d09f7ca054752decf3';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        author = 'Loren Shure';\r\n        copyright = 'Copyright 2011 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add author and copyright lines at the bottom if specified.\r\n        if ((author.length > 0) || (copyright.length > 0)) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (author.length > 0) {\r\n                d.writeln('% _' + author + '_');\r\n            }\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n      \r\n      d.title = title + ' (MATLAB code)';\r\n      d.close();\r\n      }   \r\n      \r\n-->\r\n<\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_fc8413fa750e45d09f7ca054752decf3()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n            the MATLAB code \r\n            <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; 7.12<br><\/p>\r\n<\/div>\r\n<!--\r\nfc8413fa750e45d09f7ca054752decf3 ##### SOURCE BEGIN #####\r\n%% Intersecting Lines\r\n% Today I am writing this post in collaboration with my friend and\r\n% colleague,\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/answers\/contributors\/222043-lucio-cetto\r\n% Lucio Cetto>. Ever need to know if two line segments intersect?  There\r\n% are lots of ways to do this, and I thought I would show a few solutions\r\n% here.  I haven't put much thought into how to set up the data so I can\r\n% vectorize the case for finding out which segments among many intersect\r\n% and with which ones.  At least for now :-)\r\n\r\n%% Example\r\n% Let's start with with some simple line segments.  The first column\r\n% represents to x-values of the line segment, the second column represents\r\n% the y-values.\r\nline1 = [.5 1; 1 0];\r\nline2 = [.5 0; 1 1];\r\n%%\r\n% Plot the data.  \r\nh = plot(line1(:,1),line1(:,2));\r\nhold all\r\nh(2) = plot(line2(:,1),line2(:,2));\r\nset(h,'linewidth',2)\r\naxis([0 1 0 1])\r\n\r\n \r\n%% First Algorithm\r\n% Using equation y = mx+b, solve for x assuming 2 lines intersect.  Then\r\n% see if that x value is in the necessary range.  Special cases: vertical\r\n% lines (m==inf) and parallel lines (m1 == m2)\r\n%%\r\n% First find slopes and intercepts for both line segments.\r\n% Here are slopes.\r\nslope = @(line) (line(2,2) - line(1,2))\/(line(2,1) - line(1,1));\r\nm1 = slope(line1)\r\nm2 = slope(line2)\r\n%%\r\n% Here are the intercepts.\r\nintercept = @(line,m) line(1,2) - m*line(1,1);\r\nb1 = intercept(line1,m1)\r\nb2 = intercept(line2,m2)\r\nxintersect = (b2-b1)\/(m1-m2)\r\nyintersect = m1*xintersect + b1\r\n%%\r\n% Plot results.\r\nplot(xintersect,yintersect,'m*','markersize',8)\r\nlegend({'line1','line2','intersection'},'Location','West')\r\nhold off\r\n%%  \r\n% Now check that the intersection point is on the line segment and not past\r\n% the end.  \r\nisPointInside = @(xint,myline) ...\r\n    (xint >= myline(1,1) && xint <= myline(2,1)) || ...\r\n    (xint >= myline(2,1) && xint <= myline(1,1));\r\ninside = isPointInside(xintersect,line1) && ...\r\n         isPointInside(xintersect,line2)\r\n%\r\n%% \r\n% Try with different lines now.\r\nline1 = [.5 1; ...\r\n        1 0];\r\nline2 = [.5 0; ...\r\n        0 -1];\r\n%%\r\n% Compute new intersection.\r\nm1 = slope(line1);\r\nm2 = slope(line2);\r\nb1 = intercept(line1,m1);\r\nb2 = intercept(line2,m2);\r\nxintersect = (b2-b1)\/(m1-m2)\r\nyintersect = m1*xintersect + b1\r\n%%\r\n% Show the plot.\r\nfigure\r\nh = plot(line1(:,1),line1(:,2));\r\nhold all\r\nh(2) = plot(line2(:,1),line2(:,2));\r\nset(h,'linewidth',2)\r\nlegend(h,{'line1','line2'},'Location','West')\r\nplot(xintersect,yintersect,'g*')\r\nhold off\r\naxis([-1 1 -1 1])\r\n%%\r\n% Is the intersect point on both line segments?\r\ninside = isPointInside(xintersect,line1) && ...\r\n         isPointInside(xintersect,line2)\r\n%%\r\n% No. The intersect point lies on only one line segment, meaning that the\r\n% two segments don't intersect.\r\n%%\r\n% There's still more to think about.  What if the two lines segments have\r\n% the same slope?  There are 3 cases for this.  First case: the segments\r\n% are parallel and therefore no intersection.  Second and third cases, they\r\n% are part of the same line, in which case, we have to check to see if they\r\n% overlap or not (in other words, they may intersect or not, for 2 more\r\n% cases).\r\n%%\r\n% Here are two parallel lines with different values for their y-intercept.\r\nline1 = [.5 1; ...\r\n        1 0];\r\nline2 = [.5 3; ...\r\n        1 2];\r\n%%\r\n% Plot the line segments.\r\nfigure\r\nh = plot(line1(:,1),line1(:,2));\r\nhold all\r\nh(2) = plot(line2(:,1),line2(:,2));\r\nset(h,'linewidth',2)\r\nlegend(h,{'line1','line2'},'Location','West')\r\nhold off\r\n%%\r\n% See that slopes are equal, and intercepts are not.\r\nm1 = slope(line1);\r\nm2 = slope(line2);\r\nb1 = intercept(line1,m1);\r\nb2 = intercept(line2,m2);\r\nsameSlope = abs(m1-m2) < eps(m1)\r\ndifferentIntercept = abs(b1-b2) > eps(b1)\r\nisParallel = sameSlope && differentIntercept\r\n\r\n%% Second Algorithm\r\n% Here's another algorithm for seeing if two lines intersect.  The idea is\r\n% to choose one line, and see if the end points from the other line lie on\r\n% the same side.  If they do, there's no way the lines have a point of\r\n% intersection.  If not, the second line might intersect the first one, or\r\n% the point of intersection may fall outside the limits of the first line\r\n% segment.  A way to test that is to reverse the roles of lines 1 and 2 and\r\n% do the test again.\r\n%\r\n% The test for checking which side of the line a point falls on is simple.\r\n% Plug in the values for the end points of line 2 into the equation for\r\n% line 1.  If they are both the same sign, then they both fall on the same\r\n% side.\r\nline1 = [.5 1; ...\r\n        1 0];\r\nline2 = [.5 0; ...\r\n        0 -1];\r\nfigure    \r\nh = plot(line1(:,1),line1(:,2));\r\nhold all\r\nh(2) = plot(line2(:,1),line2(:,2));\r\nset(h,'linewidth',2)\r\naxis([0 1 -1 2])\r\n\r\n%%\r\n% Get slope and intercept of both lines.\r\nm1 = slope(line1)\r\nm2 = slope(line2)\r\nb1 = intercept(line1,m1)\r\nb2 = intercept(line2,m2)\r\n\r\n%%\r\n% Evaluate the x value of end-points of the second line using the equation\r\n% y = m*x + b of the first line\r\nlineEq = @(m,b, myline) m * myline(:,1) + b\r\nyEst2 = lineEq(m1, b1, line2)\r\nplot(line2(:,1),yEst2,'om')\r\n\r\n%%\r\n% Subtract the end values from the ends of |line2| and we find that both\r\n% values are positive, meaning we don't find that the segment straddles\r\n% |line2|.\r\nenderr = @(ends,line) ends - line(:,2)\r\nerrs1 = enderr(yEst2,line2)\r\n%%\r\n% Next reverse the roles of lines 1 and 2 and check to see if the end\r\n% points of line 2 fall on the same side of line 1. \r\nyEst1 = lineEq(m2, b2, line1)\r\nplot(line1(:,1),yEst1,'or')\r\nerrs2 = enderr(yEst1,line1)\r\n%%\r\n% In this case we find that the differences between the predicted y values\r\n% and the real y values of line 1 have different signs, which means that if\r\n% line 2 was long enough there would exist an intersection.\r\n%%\r\n% To test for an actual intersection, we now just need to verify that the\r\n% condition applies in both directions.\r\npossibleIntersection =  sum(sign(errs1))==0 && sum(sign(errs2))==0\r\n%%  Ignored Issues and Other Algorithms\r\n% Here are a list of issues that this post does not solve:\r\n% \r\n% * Vertical line(s) (infinite slope)\r\n%\r\n%          Can work around this by rotating the lines to avoid\r\n%          verticals (try random rotations, or perhaps rotate\r\n%          through a computed angle so largest angle is bisected \r\n%          vertically.\r\n%\r\n% * Degenerate line (single point)\r\n% * Parallel lines with same intercept\r\n% * More than two line segments\r\n%\r\n% In addition, there is at least one more algorithm that we haven't talked\r\n% about here, called \r\n% <http:\/\/compgeom.cs.uiuc.edu\/~jeffe\/teaching\/373\/notes\/x06-sweepline.pdf\r\n% Sweep Line Algorithm>. \r\n%% Ever Run Into This Problem Yourself?\r\n% How did you solve it?  Let us know\r\n% <https:\/\/blogs.mathworks.com\/loren\/?p=286#respond here>.\r\n\r\n##### SOURCE END ##### fc8413fa750e45d09f7ca054752decf3\r\n-->","protected":false},"excerpt":{"rendered":"<p>\r\n   \r\n      Today I am writing this post in collaboration with my friend and colleague, Lucio Cetto. Ever need to know if two line segments intersect?  There are lots of ways to do this, and I... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2011\/08\/29\/intersecting-lines\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[32,39,29],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/286"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/comments?post=286"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/286\/revisions"}],"predecessor-version":[{"id":1985,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/286\/revisions\/1985"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=286"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=286"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=286"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}