{"id":287,"date":"2011-09-08T13:06:33","date_gmt":"2011-09-08T13:06:33","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/2011\/09\/08\/intersecting-lines-part-2\/"},"modified":"2016-08-04T08:41:11","modified_gmt":"2016-08-04T13:41:11","slug":"intersecting-lines-part-2","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2011\/09\/08\/intersecting-lines-part-2\/","title":{"rendered":"Intersecting Lines (Part 2)"},"content":{"rendered":"<div xmlns:mwsh=\"https:\/\/www.mathworks.com\/namespace\/mcode\/v1\/syntaxhighlight.dtd\" class=\"content\">\r\n   <introduction>\r\n      <p>Recently, Lucio and I wrote a post on detecting <a href=\"https:\/\/blogs.mathworks.com\/loren\/2011\/08\/29\/intersecting-lines\/\">line segment intersections<\/a>.  We confessed in the post that we had not been exhaustive in our treatment.  We also received many interesting comments.\r\n         This post introduces a 3rd method, one that several readers had mentioned; the post includes several variations to deal with\r\n         various edge cases as cleanly and numerically soundly as possible, particularly ones related to having a vertical line segment,\r\n         i.e., a segment with infinite slope.\r\n      <\/p>\r\n   <\/introduction>\r\n   <h3>Contents<\/h3>\r\n   <div>\r\n      <ul>\r\n         <li><a href=\"#1\">Third Algorithm to Account for Vertical Segments<\/a><\/li>\r\n         <li><a href=\"#7\">Add Tolerance for Rounding Errors<\/a><\/li>\r\n         <li><a href=\"#9\">Detecting Parallel Lines<\/a><\/li>\r\n         <li><a href=\"#14\">Testing for Collinearity<\/a><\/li>\r\n         <li><a href=\"#19\">Degenerate Lines<\/a><\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <h3>Third Algorithm to Account for Vertical Segments<a name=\"1\"><\/a><\/h3>\r\n   <p>The previous two algorithms fail when there is a vertical line segment. Some research on the web indicates that one of the\r\n      preferred solutions for this problem is to parameterize the line segments as two vectors. Several of our blog readers have already commented about this approach.\r\n   <\/p>\r\n   <p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_eq55885.png\"> <\/p>\r\n   <p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_eq22184.png\"> <\/p>\r\n   <p>where <img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_eq12166.png\">  and <img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_eq14281.png\">  (<tt>2x1<\/tt>) indicate the coordinates of the endpoints of line A, <img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_eq70787.png\">  and <img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_eq08914.png\">  (<tt>2x1<\/tt>) indicate the coordinates of the endpoints of line B, <img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_eq54775.png\">  indicates the coordinates of the intersecting point (if one exists) and <img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_eq01166.png\">  and <img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_eq50913.png\">  are unknown scalars.\r\n   <\/p>\r\n   <p>This leads to a system of equations; testing for an intersection consists on solving for <img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_eq01166.png\">  and <img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_eq50913.png\">  and checking that both are in <tt>[0,1]<\/tt>. Note that we use <a href=\"https:\/\/www.mathworks.com\/help\/releases\/R2011b\/techdoc\/ref\/linsolve.html\"><tt>linsolve<\/tt><\/a> rather than left matrix divide (or <a href=\"https:\/\/www.mathworks.com\/help\/releases\/R2011b\/techdoc\/ref\/inv.html\"><tt>inv<\/tt><\/a>) as <tt>linsolve<\/tt> has better numerical properties when the system of equations is ill-conditioned.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">A = @(lineA,lineB) [lineA(1,:) - lineA(2,:); lineB(2,:) - lineB(1,:)]';\r\npq = @(lineA,lineB) linsolve(A(lineA,lineB),(lineB(2,:) - lineA(2,:))');\r\nisIntersect = @(lineA,lineB) all(all(pq(lineA,lineB)*[1 -1]+[0 1;0 1]&gt;=0));<\/pre><p>where <img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_eq97875.png\">  and <img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_eq66767.png\">  (x-coordinates are the first column and y-coordinates are the second column, as in our previous post).\r\n   <\/p>\r\n   <p>In order to simplify our writing, we put all plot commands inside a utility function:<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">dbtype <span style=\"color: #A020F0\">plotlines<\/span><\/pre><pre style=\"font-style:oblique\">\r\n1     function plotlines(line1, line2)\r\n2     % Plots two line segments and annotates the endpoints\r\n3       figure\r\n4       hold all\r\n5       h(1) = plot(line1(:,1),line1(:,2),'b^-');\r\n6       h(2) = plot(line2(:,1),line2(:,2),'rs-');\r\n7       set(h,'linewidth',2)\r\n8       g(1) = text(line1(1,1),line1(1,2),...\r\n9           sprintf('  (%1.20g,%1.20g)  ',line1(1,1),line1(1,2)),...\r\n10          'verticalalignment','top','color','b');\r\n11      g(2) = text(line1(2,1),line1(2,2),...\r\n12          sprintf('  (%1.20g,%1.20g)  ',line1(2,1),line1(2,2)),...\r\n13          'verticalalignment','top','color','b');\r\n14      g(3) = text(line2(1,1),line2(1,2),...\r\n15          sprintf('  (%1.20g,%1.20g)  ',line2(1,1),line2(1,2)),...\r\n16          'verticalalignment','bottom','color','r');\r\n17      g(4) = text(line2(2,1),line2(2,2),...\r\n18          sprintf('  (%1.20g,%1.20g)  ',line2(2,1),line2(2,2)),...\r\n19          'verticalalignment','bottom','color','r');\r\n20      ext = cell2mat(get(g,'Extent'));\r\n21      axis([min(ext(:,1)),max(ext(:,1)+ext(:,3)),...\r\n22          min(ext(:,2)),max(ext(:,2)+ext(:,4))])\r\n23      hold off\r\n24    end\r\n<\/pre><p>Now we test the new algorithm with two intersecting segments with one of them having infinite slope:<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">lineA = [.5 1; <span style=\"color: #0000FF\">...<\/span>\r\n        .5 0];\r\nlineB = [0.6 0.5; <span style=\"color: #0000FF\">...<\/span>\r\n        0 0.5];\r\nplotlines(lineA,lineB)\r\nplotlines(lineB,lineA)\r\n\r\nisIntersect(lineA,lineB)\r\nisIntersect(lineB,lineA)<\/pre><pre style=\"font-style:oblique\">ans =\r\n     1\r\nans =\r\n     1\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_01.png\"> <img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_02.png\"> <p>Test with two non-intersecting segments:<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">lineA = [.5 1; <span style=\"color: #0000FF\">...<\/span>\r\n        .5 0];\r\nlineB = [0.4 0.5; <span style=\"color: #0000FF\">...<\/span>\r\n        0 0.5];\r\nplotlines(lineA,lineB)\r\nplotlines(lineB,lineA)\r\nisIntersect(lineA,lineB)\r\nisIntersect(lineB,lineA)<\/pre><pre style=\"font-style:oblique\">ans =\r\n     0\r\nans =\r\n     0\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_03.png\"> <img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_04.png\"> <h3>Add Tolerance for Rounding Errors<a name=\"7\"><\/a><\/h3>\r\n   <p>In many applications, the computer numerical precision is not sufficient to represent an exact quantity; therefore special\r\n      care needs to be taken when testing if an intersection point exists.  For example observe the following inconsistency with\r\n      our current algorithm:\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">lineA = [0 0; <span style=\"color: #0000FF\">...<\/span>\r\n        1 3];\r\nlineB = [1\/3 1; <span style=\"color: #0000FF\">...<\/span>\r\n        0 1];\r\nlineC = [1\/3 1; <span style=\"color: #0000FF\">...<\/span>\r\n        1 1];\r\nplotlines(lineA,lineB)\r\nisIntersect(lineA,lineB)\r\nplotlines(lineA,lineC)\r\nisIntersect(lineA,lineC)<\/pre><pre style=\"font-style:oblique\">ans =\r\n     0\r\nans =\r\n     1\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_05.png\"> <img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_06.png\"> <p>One endpoint for both <tt>lineB<\/tt> and <tt>lineC<\/tt> lies on the segment <tt>lineA<\/tt>. This should result in an intersection in both cases. We can fix this problem by introducing a tolerance in our final testing.\r\n      A conservative tolerance to use is <tt>sqrt(eps)<\/tt>, however one may prefer to do something more robust that depends on the values involved in the computations. This has already\r\n      been discussed in a previous blog <a href=\"https:\/\/blogs.mathworks.com\/loren\/2009\/07\/15\/computational-geometry-in-matlab-r2009a-part-i\/#20\">post<\/a>.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">isIntersect = @(lineA,lineB) all(all(pq(lineA,lineB)*[1 -1]+[0 1;0 1]&gt;=-sqrt(eps)));\r\nisIntersect(lineA,lineB)\r\nisIntersect(lineA,lineC)<\/pre><pre style=\"font-style:oblique\">ans =\r\n     1\r\nans =\r\n     1\r\n<\/pre><h3>Detecting Parallel Lines<a name=\"9\"><\/a><\/h3>\r\n   <p>One of the nice properties of the formulation we are using is that parallel lines (segments with the same slope) can be easily\r\n      detected by testing if A is singular. This can be calculated by checking that <a href=\"https:\/\/www.mathworks.com\/help\/releases\/R2011b\/techdoc\/ref\/det.html\"><tt>det(A)<\/tt><\/a>==0. For example:\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">lineA = [0 0; <span style=\"color: #0000FF\">...<\/span>\r\n         1 1];\r\nlineB = [1 2; <span style=\"color: #0000FF\">...<\/span>\r\n         2 3];\r\nplotlines(lineA,lineB)\r\ndet(A(lineA,lineB))<\/pre><pre style=\"font-style:oblique\">ans =\r\n     0\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_07.png\"> <p>The astute reader will promptly notice that this straightforward calculation is also vulnerable to numerical precision problems,\r\n      for instance:\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">lineC = [0 1; <span style=\"color: #0000FF\">...<\/span>\r\n         1 1\/3];\r\nlineD = [1 2\/3; <span style=\"color: #0000FF\">...<\/span>\r\n         2 0];\r\nplotlines(lineC,lineD)\r\ndet(A(lineC,lineD))<\/pre><pre style=\"font-style:oblique\">ans =\r\n -1.1102e-016\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_08.png\"> <p>The proper way to test for singularity is to use the function <a href=\"https:\/\/www.mathworks.com\/help\/releases\/R2011b\/techdoc\/ref\/rank.html\"><tt>rank<\/tt><\/a>, as it incorporates proper tolerances to overcome rounding errors.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">isParallel = @(lineA,lineB) rank(A(lineA,lineB))&lt;2;\r\nisParallel(lineA,lineB)\r\nisParallel(lineC,lineD)<\/pre><pre style=\"font-style:oblique\">ans =\r\n     1\r\nans =\r\n     1\r\n<\/pre><p>We now incorporate the test for parallel lines. For clarity, we now created a function in a file rather than an anonymous\r\n      function.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">dbtype <span style=\"color: #A020F0\">isIntersect2<\/span><\/pre><pre style=\"font-style:oblique\">\r\n1     function tf = isIntersect2(lineA, lineB) \r\n2     A = [lineA(1,:) - lineA(2,:); lineB(2,:) - lineB(1,:)]'; \r\n3     if rank(A) &lt; 2\r\n4         disp('Parallel')\r\n5         tf = false;\r\n6     else\r\n7         pq = linsolve(A,(lineB(2,:) - lineA(2,:))');\r\n8         tf = all(pq&gt;=-sqrt(eps)) &amp; all(pq&lt;=1+sqrt(eps));\r\n9     end\r\n<\/pre><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">isIntersect2(lineA,lineB)\r\nisIntersect2(lineC,lineD)<\/pre><pre style=\"font-style:oblique\">Parallel\r\nans =\r\n     0\r\nParallel\r\nans =\r\n     0\r\n<\/pre><h3>Testing for Collinearity<a name=\"14\"><\/a><\/h3>\r\n   <p>Collinearity is a special case of parallel lines; when this occurs, it the line segments might overlap. In a previous <a href=\"https:\/\/blogs.mathworks.com\/loren\/2008\/06\/06\/collinearity\/\">blog<\/a> post, we have already talked about testing for collinearity; we'll incorporate our previous findings here. Notice that we\r\n      also use <tt>rank<\/tt> for numerical stability. Also observe that since collinearity implies parallel segments, we only need to test any three end-points\r\n      of the two line segments for collinearity. In our implementation the second endpoint of <tt>lineB<\/tt> is not used for testing collinearity.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">lineA = [0 1; <span style=\"color: #0000FF\">...<\/span>\r\n        1 1\/3];\r\nlineB = [2.5 -2\/3; <span style=\"color: #0000FF\">...<\/span>\r\n        1.5 0];\r\n\r\nplotlines(lineA,lineB)\r\ndbtype <span style=\"color: #A020F0\">isIntersect3<\/span><\/pre><pre style=\"font-style:oblique\">\r\n1     function tf = isIntersect3(lineA, lineB) \r\n2     A = [lineA(1,:) - lineA(2,:); lineB(2,:) - lineB(1,:)]'; \r\n3     if rank(A) &lt; 2\r\n4         disp('Parallel')\r\n5         B = [lineA(1,:) - lineA(2,:); lineA(1,:) - lineB(1,:)]'; \r\n6         if rank(B) &lt; 2\r\n7             disp('Collinear')\r\n8             tf = NaN;\r\n9         else\r\n10            tf = false;\r\n11        end\r\n12    else\r\n13        pq = linsolve(A,(lineB(2,:) - lineA(2,:))');\r\n14        tf = all(pq&gt;=-sqrt(eps)) &amp; all(pq&lt;=1+sqrt(eps));\r\n15    end\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_09.png\"> <pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">isIntersect3(lineA,lineB)<\/pre><pre style=\"font-style:oblique\">Parallel\r\nCollinear\r\nans =\r\n   NaN\r\n<\/pre><p>Once we confirm that two segments are collinear, then the segments can be projected either to the x- or y-axis. We now need\r\n      to determine if the endpoints of the segments are interleaved or not, to figure out if they overlap and hence intersect. Once\r\n      again, a tolerance must be incorporated into the testing.\r\n   <\/p>\r\n   <p>To check if the x-coordinates of the points are interleaved, we implement the following tests; both inequalities must be false\r\n      in order to discard an intersection (or segment overlapping):\r\n   <\/p>\r\n   <p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_eq71774.png\"> <\/p>\r\n   <p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_eq16268.png\"> <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">dbtype <span style=\"color: #A020F0\">isIntersect4<\/span><\/pre><pre style=\"font-style:oblique\">\r\n1     function tf = isIntersect4(lineA, lineB) \r\n2     A = [lineA(1,:) - lineA(2,:); lineB(2,:) - lineB(1,:)]'; \r\n3     if rank(A) &lt; 2\r\n4         disp('Parallel')\r\n5         B = [lineA(1,:) - lineA(2,:); lineA(1,:) - lineB(1,:)]'; \r\n6         if rank(B) &lt; 2\r\n7             disp('Collinear')\r\n8             if all( (sort(lineA(:,1),'descend')-sort(lineB(:,1))) ...\r\n9                     .*[-1;1] &lt;= sqrt(eps) )\r\n10                tf = true;\r\n11            else\r\n12                tf = false;\r\n13            end\r\n14        else\r\n15            tf = false;\r\n16        end\r\n17    else\r\n18        pq = linsolve(A,(lineB(2,:) - lineA(2,:))');\r\n19        tf = all(pq&gt;=-sqrt(eps)) &amp; all(pq&lt;=1+sqrt(eps));\r\n20    end\r\n\r\n<\/pre><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">isIntersect4(lineA,lineB)<\/pre><pre style=\"font-style:oblique\">Parallel\r\nCollinear\r\nans =\r\n     0\r\n<\/pre><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">lineA = [0 1; <span style=\"color: #0000FF\">...<\/span>\r\n         1-2*eps 1\/3-eps];\r\nlineB = [1+2*eps 1\/3; <span style=\"color: #0000FF\">...<\/span>\r\n         1.5 eps];\r\nplotlines(lineA,lineB)\r\nisIntersect4(lineA,lineB)<\/pre><pre style=\"font-style:oblique\">Parallel\r\nCollinear\r\nans =\r\n     1\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_10.png\"> <h3>Degenerate Lines<a name=\"19\"><\/a><\/h3>\r\n   <p>Observe that the tests for singularity and collinearity take care properly of the degenerate lines:<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">lineA = [0 0;2 2];\r\nlineB = [1 1;1 1];\r\nlineC = [1 2;1 2];\r\nlineD = [2 2;2 2];\r\nplotlines(lineA,lineB)\r\nisIntersect4(lineA,lineB)\r\nplotlines(lineA,lineC)\r\nisIntersect4(lineA,lineC)\r\nplotlines(lineB,lineD)\r\nisIntersect4(lineB,lineD)<\/pre><pre style=\"font-style:oblique\">Parallel\r\nCollinear\r\nans =\r\n     1\r\nParallel\r\nans =\r\n     0\r\nParallel\r\nCollinear\r\nans =\r\n     0\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_11.png\"> <img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_12.png\"> <img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/287\/lineIntersect3_13.png\"> <p>We are almost done, however there is one edge case that will still break our algorithm. Can you identify it (HINT: it is not\r\n      associated with our conservative tolerances)?  Let us know what you find <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p=287#respond\">here<\/a>.\r\n   <\/p><script language=\"JavaScript\">\r\n<!--\r\n\r\n    function grabCode_8360c5a681a347fc9aeff292ba072f6b() {\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='8360c5a681a347fc9aeff292ba072f6b ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 8360c5a681a347fc9aeff292ba072f6b';\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_8360c5a681a347fc9aeff292ba072f6b()\"><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.13<br><\/p>\r\n<\/div>\r\n<!--\r\n8360c5a681a347fc9aeff292ba072f6b ##### SOURCE BEGIN #####\r\n%% Intersecting Lines (Part 2)\r\n% Recently, Lucio and I wrote a post on detecting\r\n% <https:\/\/blogs.mathworks.com\/loren\/2011\/08\/29\/intersecting-lines\/ line\r\n% segment intersections>.  We confessed in the post that we had not been\r\n% exhaustive in our treatment.  We also received many interesting comments.\r\n% This post introduces a 3rd method, one that several readers had\r\n% mentioned; the post includes several variations to deal with various edge\r\n% cases as cleanly and numerically soundly as possible, particularly ones\r\n% related to having a vertical line segment, i.e., a segment with infinite\r\n% slope.\r\n\r\n%% Third Algorithm to Account for Vertical Segments \r\n% The previous two algorithms fail when there is a vertical line segment.\r\n% Some research on the web indicates that one of the preferred solutions\r\n% for this problem is to parameterize the line segments as two vectors, for\r\n% example <http:\/\/paulbourke.net\/geometry\/lineline2d\/ this post> by Paul\r\n% Bourke. Several of our blog readers have already commented about this\r\n% approach.\r\n%\r\n% $$ XY_{Intersection} = XY_{A1} + p (XY_{A2}-XY_{A1}) $$\r\n%\r\n% $$ XY_{Intersection} = XY_{B1} + q (XY_{B2}-XY_{B1}) $$\r\n%\r\n% where $XY_{A1}$ and $XY_{A2}$ (|2x1|) indicate the coordinates of the\r\n% endpoints of line A, $XY_{B1}$ and $XY_{B2}$ (|2x1|) indicate the\r\n% coordinates of the endpoints of line B, $XY_{Intersection}$ indicates the\r\n% coordinates of the intersecting point (if one exists) and $p$ and $q$ are\r\n% unknown scalars.\r\n\r\n%%\r\n% This leads to a system of equations; testing for an intersection consists\r\n% on solving for $p$ and $q$ and checking that both are in |[0,1]|.\r\n% Note that we use\r\n% <https:\/\/www.mathworks.com\/help\/releases\/R2011b\/techdoc\/ref\/linsolve.html\r\n% |linsolve|> rather than left matrix divide (or\r\n% <https:\/\/www.mathworks.com\/help\/releases\/R2011b\/techdoc\/ref\/inv.html\r\n% |inv|>) as |linsolve| has better numerical properties when the system\r\n% of equations is ill-conditioned.\r\n\r\nA = @(lineA,lineB) [lineA(1,:) - lineA(2,:); lineB(2,:) - lineB(1,:)]';\r\npq = @(lineA,lineB) linsolve(A(lineA,lineB),(lineB(2,:) - lineA(2,:))');\r\nisIntersect = @(lineA,lineB) all(all(pq(lineA,lineB)*[1 -1]+[0 1;0 1]>=0));\r\n\r\n%%\r\n% where $lineA = [XY_{A1} XY_{A2}]'$ and $lineB = [XY_{B1} XY_{B2}]'$\r\n% (x-coordinates are the first column and y-coordinates are the second\r\n% column, as in our previous post).\r\n\r\n%%\r\n% In order to simplify our writing, we put all plot commands inside\r\n% a utility function:\r\ndbtype plotlines\r\n\r\n%%\r\n% Now we test the new algorithm with two intersecting segments with one of\r\n% them having infinite slope:\r\n \r\nlineA = [.5 1; ...\r\n        .5 0];\r\nlineB = [0.6 0.5; ...\r\n        0 0.5];\r\nplotlines(lineA,lineB)\r\nplotlines(lineB,lineA)\r\n\r\nisIntersect(lineA,lineB)\r\nisIntersect(lineB,lineA)\r\n\r\n%%\r\n% Test with two non-intersecting segments:\r\nlineA = [.5 1; ...\r\n        .5 0];\r\nlineB = [0.4 0.5; ...\r\n        0 0.5];\r\nplotlines(lineA,lineB)\r\nplotlines(lineB,lineA)\r\nisIntersect(lineA,lineB)\r\nisIntersect(lineB,lineA)\r\n\r\n%% Add Tolerance for Rounding Errors\r\n% In many applications, the computer numerical precision is not sufficient\r\n% to represent an exact quantity; therefore special care needs to be taken\r\n% when testing if an intersection point exists.  For example observe the\r\n% following inconsistency with our current algorithm:\r\n\r\nlineA = [0 0; ...\r\n        1 3];\r\nlineB = [1\/3 1; ...\r\n        0 1];\r\nlineC = [1\/3 1; ...\r\n        1 1];\r\nplotlines(lineA,lineB)\r\nisIntersect(lineA,lineB)\r\nplotlines(lineA,lineC)\r\nisIntersect(lineA,lineC)\r\n\r\n%%\r\n% One endpoint for both |lineB| and |lineC| lies on the segment |lineA|.\r\n% This should result in an intersection in both cases. We can fix this\r\n% problem by introducing a tolerance in our final testing. A conservative\r\n% tolerance to use is |sqrt(eps)|, however one may prefer to do something\r\n% more robust that depends on the values involved in the computations. This\r\n% has already been discussed in a previous blog\r\n% <https:\/\/blogs.mathworks.com\/loren\/2009\/07\/15\/computational-geometry-in-matlab-r2009a-part-i\/#20\r\n% post>.\r\n \r\nisIntersect = @(lineA,lineB) all(all(pq(lineA,lineB)*[1 -1]+[0 1;0 1]>=-sqrt(eps)));\r\nisIntersect(lineA,lineB)\r\nisIntersect(lineA,lineC)\r\n\r\n%% Detecting Parallel Lines\r\n% One of the nice properties of the formulation we are using is that\r\n% parallel lines (segments with the same slope) can be easily detected by\r\n% testing if A is singular. This can be calculated by checking that\r\n% <https:\/\/www.mathworks.com\/help\/releases\/R2011b\/techdoc\/ref\/det.html\r\n% |det(A)|>==0. For example:\r\n \r\nlineA = [0 0; ...\r\n         1 1];\r\nlineB = [1 2; ...\r\n         2 3];\r\nplotlines(lineA,lineB)\r\ndet(A(lineA,lineB))\r\n\r\n%%\r\n% The astute reader will promptly notice that this straightforward\r\n% calculation is also vulnerable to numerical precision problems, for\r\n% instance: \r\n \r\nlineC = [0 1; ...\r\n         1 1\/3];\r\nlineD = [1 2\/3; ...\r\n         2 0];\r\nplotlines(lineC,lineD)\r\ndet(A(lineC,lineD))\r\n\r\n%%\r\n% The proper way to test for singularity is to use the function\r\n% <https:\/\/www.mathworks.com\/help\/releases\/R2011b\/techdoc\/ref\/rank.html\r\n% |rank|>, as it incorporates proper tolerances to overcome rounding\r\n% errors.\r\n \r\nisParallel = @(lineA,lineB) rank(A(lineA,lineB))<2;\r\nisParallel(lineA,lineB)\r\nisParallel(lineC,lineD)\r\n\r\n%%\r\n% We now incorporate the test for parallel lines. For clarity, we now\r\n% created a function in a file rather than an anonymous function.\r\ndbtype isIntersect2\r\n\r\n%%\r\nisIntersect2(lineA,lineB)\r\nisIntersect2(lineC,lineD)\r\n\r\n%% Testing for Collinearity\r\n% Collinearity is a special case of parallel lines; when this occurs, it\r\n% the line segments might overlap. In a previous\r\n% <https:\/\/blogs.mathworks.com\/loren\/2008\/06\/06\/collinearity\/ blog> post, we\r\n% have already talked about testing for collinearity; we'll incorporate our\r\n% previous findings here. Notice that we also use |rank| for numerical\r\n% stability. Also observe that since collinearity implies parallel\r\n% segments, we only need to test any three end-points of the two line\r\n% segments for collinearity. In our implementation the second endpoint of\r\n% |lineB| is not used for testing collinearity.\r\n\r\nlineA = [0 1; ...\r\n        1 1\/3];\r\nlineB = [2.5 -2\/3; ...\r\n        1.5 0];\r\n\r\nplotlines(lineA,lineB)\r\ndbtype isIntersect3\r\n%%\r\nisIntersect3(lineA,lineB)\r\n\r\n%%\r\n% Once we confirm that two segments are collinear, then the segments can be\r\n% projected either to the x- or y-axis. We now need to determine if the\r\n% endpoints of the segments are interleaved or not, to figure out if they\r\n% overlap and hence intersect. Once again, a tolerance must be incorporated\r\n% into the testing.\r\n%\r\n% To check if the x-coordinates of the points are interleaved, we implement\r\n% the following tests; both inequalities must be false in order to discard\r\n% an intersection (or segment overlapping): \r\n%\r\n% $$ max(x_{A1},x_{A2}) + tolerance > min(x_{B1},x_{B2}) $$\r\n%\r\n% $$ min(x_{A1},x_{A2}) < max(x_{B1},x_{B2}) + tolerance $$\r\n\r\ndbtype isIntersect4\r\n\r\n%%\r\nisIntersect4(lineA,lineB)\r\n\r\n%%\r\nlineA = [0 1; ...\r\n         1-2*eps 1\/3-eps];\r\nlineB = [1+2*eps 1\/3; ...\r\n         1.5 eps];\r\nplotlines(lineA,lineB)\r\nisIntersect4(lineA,lineB)\r\n\r\n%% Degenerate Lines\r\n% Observe that the tests for singularity and collinearity take care\r\n% properly of the degenerate lines:\r\n\r\nlineA = [0 0;2 2];\r\nlineB = [1 1;1 1];\r\nlineC = [1 2;1 2];\r\nlineD = [2 2;2 2];\r\nplotlines(lineA,lineB)\r\nisIntersect4(lineA,lineB)\r\nplotlines(lineA,lineC)\r\nisIntersect4(lineA,lineC)\r\nplotlines(lineB,lineD)\r\nisIntersect4(lineB,lineD)\r\n\r\n%%\r\n% We are almost done, however there is one edge case that will still break\r\n% our algorithm. Can you identify it (HINT: it is not associated with our\r\n% conservative tolerances)?  Let us know what you find\r\n% <https:\/\/blogs.mathworks.com\/loren\/?p=287#respond here>.\r\n\r\n##### SOURCE END ##### 8360c5a681a347fc9aeff292ba072f6b\r\n-->","protected":false},"excerpt":{"rendered":"<p>\r\n   \r\n      Recently, Lucio and I wrote a post on detecting line segment intersections.  We confessed in the post that we had not been exhaustive in our treatment.  We also received many interesting... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2011\/09\/08\/intersecting-lines-part-2\/\">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\/287"}],"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=287"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/287\/revisions"}],"predecessor-version":[{"id":1948,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/287\/revisions\/1948"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=287"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=287"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=287"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}