{"id":108,"date":"2006-12-22T13:56:38","date_gmt":"2006-12-22T18:56:38","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=108"},"modified":"2019-10-22T16:38:55","modified_gmt":"2019-10-22T20:38:55","slug":"poly2mask-and-roipoly-part-3","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2006\/12\/22\/poly2mask-and-roipoly-part-3\/","title":{"rendered":"POLY2MASK and ROIPOLY &#8211; Part 3"},"content":{"rendered":"<div xmlns:mwsh=\"https:\/\/www.mathworks.com\/namespace\/mcode\/v1\/syntaxhighlight.dtd\" class=\"content\">\r\n   <p>This is the final post in a series discussing the algorithm underlying Image Processing Toolbox functions <tt>poly2mask<\/tt> and <tt>roipoly<\/tt>.  (See <a href=\"https:\/\/blogs.mathworks.com\/steve\/?p=99\">Part 1<\/a> and <a href=\"https:\/\/blogs.mathworks.com\/steve\/?p=102\">Part 2<\/a>.)\r\n   <\/p>\r\n   <p>There are several desirable properties for a polygon scan conversion algorithm to have.  It helps to visualize some of these\r\n      properties if you look first at a set of polygons that completely covers the image region, with no gaps and no overlaps.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">imshow(ones(20,20), <span style=\"color: #A020F0\">'InitialMag'<\/span>, <span style=\"color: #A020F0\">'fit'<\/span>);\r\nhold <span style=\"color: #A020F0\">on<\/span>\r\n<span style=\"color: #0000FF\">for<\/span> x = 0.5:20.5\r\n    <span style=\"color: #0000FF\">for<\/span> y = 0.5:20.5\r\n        plot([x x], [0.5 20.5], <span style=\"color: #A020F0\">'Color'<\/span>, [.8 .8 .8]);\r\n        plot([0.5 20.5], [y y], <span style=\"color: #A020F0\">'Color'<\/span>, [.8 .8 .8]);\r\n    <span style=\"color: #0000FF\">end<\/span>\r\n<span style=\"color: #0000FF\">end<\/span>\r\n\r\nx1 = [0.5 10 0.5 0.5];\r\ny1 = [0.5 0.5 20.5 0.5];\r\n\r\nx2 = [10 20.5 20.5 0.5 10];\r\ny2 = [0.5 0.5 4 20.5 0.5];\r\n\r\nx3 = [20.5 20.5 0.5 20.5];\r\ny3 = [4 20.5 20.5 4];\r\n\r\nplot(x1, y1, <span style=\"color: #A020F0\">'Color'<\/span>, <span style=\"color: #A020F0\">'r'<\/span>, <span style=\"color: #A020F0\">'LineWidth'<\/span>, 3, <span style=\"color: #A020F0\">'Clipping'<\/span>, <span style=\"color: #A020F0\">'off'<\/span>);\r\nplot(x2, y2, <span style=\"color: #A020F0\">'Color'<\/span>, <span style=\"color: #A020F0\">'r'<\/span>, <span style=\"color: #A020F0\">'LineWidth'<\/span>, 3, <span style=\"color: #A020F0\">'Clipping'<\/span>, <span style=\"color: #A020F0\">'off'<\/span>);\r\nplot(x3, y3, <span style=\"color: #A020F0\">'Color'<\/span>, <span style=\"color: #A020F0\">'r'<\/span>, <span style=\"color: #A020F0\">'LineWidth'<\/span>, 3, <span style=\"color: #A020F0\">'Clipping'<\/span>, <span style=\"color: #A020F0\">'off'<\/span>);\r\n\r\ntext(4, 4, <span style=\"color: #A020F0\">'Polygon 1'<\/span>, <span style=\"color: #A020F0\">'HorizontalAlignment'<\/span>, <span style=\"color: #A020F0\">'center'<\/span>)\r\ntext(12, 7, <span style=\"color: #A020F0\">'Polygon 2'<\/span>, <span style=\"color: #A020F0\">'HorizontalAlignment'<\/span>, <span style=\"color: #A020F0\">'center'<\/span>)\r\ntext(16, 16, <span style=\"color: #A020F0\">'Polygon 3'<\/span>, <span style=\"color: #A020F0\">'HorizontalAlignment'<\/span>, <span style=\"color: #A020F0\">'center'<\/span>)\r\nhold <span style=\"color: #A020F0\">off<\/span><\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/108\/roipoly3_01.png\"> <p>Here's what we would like to achieve from our polygon scan conversion:<\/p>\r\n   <div>\r\n      <ul>\r\n         <li>There should be no gaps.  That is, since the three polygons cover the entire image, every pixel should be assigned to at least\r\n            one polygon.\r\n         <\/li>\r\n         <li>There should be no overlaps.  That is, since the three polygons do not overlap in area, no pixel should be assigned to more\r\n            than polygon.\r\n         <\/li>\r\n         <li>Pixel assignment to the three polygons should be insensitive to vertex ordering.  It should make no difference which polygon\r\n            vertex is listed first, or whether the vertices are listed in clockwise or counterclockwise order.\r\n         <\/li>\r\n         <li>Pixel assignment to the three polygons should be unaffected by floating-point round-off.<\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <p>So what rule should we use to decide how to assign pixels that are partially inside and outside of a polygon?  One possible\r\n      rule is that a pixel is considered to be inside a polygon if it is partially inside the polygon. But that violates the no-overlap\r\n      rule, since a pixel can be partially inside more than one polygon.\r\n   <\/p>\r\n   <p>Another possible rule is that a pixel is considered to be inside a polygon if at least half of the pixel (by area) is inside\r\n      the polygon. That violates the no-gap rule, though.  Consider the lower-left corner of the image above:\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">axis([0.5 2.5 18.5 20.5])<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/108\/roipoly3_02.png\"> <p>None of the three polygons covers more than half of the lower-left pixel.<\/p>\r\n   <p>The rule used by <tt>poly2mask<\/tt> is that a pixel is inside a polygon if and only if its center is inside the polygon.\r\n   <\/p>\r\n   <p>Now we have to consider how to deal cleanly with all the special cases I mentioned in <a href=\"https:\/\/blogs.mathworks.com\/steve\/?p=102\">Part 2<\/a>. Basically, trouble happens whenever a ray passes directly through one or more vertices, or along an edge.  <tt>poly2mask<\/tt> basically avoids these problems entirely by approximating the polygon by tiny horizontal and vertical line segments that\r\n      lie on the edges of a 5-by-5 subpixel grid. It looks like this:\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">clf\r\nhold <span style=\"color: #A020F0\">on<\/span>\r\n<span style=\"color: #0000FF\">for<\/span> x = linspace(0.5,1.5,6)\r\n    <span style=\"color: #0000FF\">for<\/span> y = linspace(0.5,1.5,6)\r\n        plot([x x], [0.5 1.5], <span style=\"color: #A020F0\">'Color'<\/span>, [.8 .8 .8]);\r\n        plot([0.5 1.5], [y y], <span style=\"color: #A020F0\">'Color'<\/span>, [.8 .8 .8]);\r\n    <span style=\"color: #0000FF\">end<\/span>\r\n<span style=\"color: #0000FF\">end<\/span>\r\nplot([0.5 1.5], [0.5 1.5], <span style=\"color: #A020F0\">'b'<\/span>, <span style=\"color: #A020F0\">'LineWidth'<\/span>, 2)\r\naxis <span style=\"color: #A020F0\">equal<\/span>\r\naxis <span style=\"color: #A020F0\">ij<\/span>\r\nplot([0.5 0.5 0.7 0.7 0.9 0.9 1.1 1.1 1.3 1.3 1.5], <span style=\"color: #0000FF\">...<\/span>\r\n    [0.5 0.7 0.7 0.9 0.9 1.1 1.1 1.3 1.3 1.5 1.5], <span style=\"color: #0000FF\">...<\/span>\r\n    <span style=\"color: #A020F0\">'r'<\/span>, <span style=\"color: #A020F0\">'LineWidth'<\/span>, 2, <span style=\"color: #A020F0\">'Clipping'<\/span>, <span style=\"color: #A020F0\">'off'<\/span>)\r\nplot(1.0, 1.0, <span style=\"color: #A020F0\">'*'<\/span>)\r\nhold <span style=\"color: #A020F0\">off<\/span><\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/108\/roipoly3_03.png\"> <p>The plot above shows a single pixel.  The blue line represents an original edge of the polygon.  The red line approximates\r\n      the blue line using horizontal and vertical segments that lie on the gray grid.\r\n   <\/p>\r\n   <p>Notice how none of the edges or vertices of the approximation can ever intersect the center of the pixel.  Therefore, if we\r\n      follow rays along pixel centers, we will never encounter vertices of the modified polygon, nor will any ray be coincident\r\n      with an edge.  That way, the algorithm can be coded with no special cases.\r\n   <\/p>\r\n   <p>To visualize <tt>poly2mask<\/tt> in action, I wrote the function <tt>vispoly2mask<\/tt>, which you can download from <a href=\"https:\/\/blogs.mathworks.com\/images\/steve\/108\/vispoly2mask.m\">here<\/a>.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">x = [10 35 40 10];\r\ny = [10 40 15 10];\r\nvispoly2mask(x,y,50,50)<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/108\/roipoly3_04.png\"> <p>We need to zoom into a corner of the polygon to see more detail.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">axis([8 15 8 15])<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/108\/roipoly3_05.png\"> <p>The red bars are the horizontal edges of the polygon approximation. <tt>poly2mask<\/tt> scans down the center of each image column, keeping track of the number of edge crossings, and using the even-odd rule to\r\n      decide whether each pixel is inside the polygon.\r\n   <\/p>\r\n   <p>Here's the final result displayed as a binary image with the polygon superimposed.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">bw = poly2mask(x,y,50,50);\r\nimshow(bw, <span style=\"color: #A020F0\">'InitialMag'<\/span>, <span style=\"color: #A020F0\">'fit'<\/span>)\r\nhold <span style=\"color: #A020F0\">on<\/span>\r\nplot(x,y,<span style=\"color: #A020F0\">'r'<\/span>,<span style=\"color: #A020F0\">'LineWidth'<\/span>,2)\r\nhold <span style=\"color: #A020F0\">off<\/span><\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/108\/roipoly3_06.png\"> <script language=\"JavaScript\">\r\n<!--\r\n\r\n    function grabCode_ecd6545af9594243a272d1ffc1502644() {\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='ecd6545af9594243a272d1ffc1502644 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' ecd6545af9594243a272d1ffc1502644';\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 = 'Steve Eddins';\r\n        copyright = 'Copyright 2006 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_ecd6545af9594243a272d1ffc1502644()\"><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.3<br><\/p>\r\n<\/div>\r\n<!--\r\necd6545af9594243a272d1ffc1502644 ##### SOURCE BEGIN #####\r\n%% POLY2MASK and ROIPOLY - Part 3\r\n% This is the final post in a series discussing the algorithm underlying\r\n% Image Processing Toolbox functions \r\n% <https:\/\/www.mathworks.com\/help\/images\/index.htmlpoly2mask.html \r\n% |poly2mask|> and \r\n% <https:\/\/www.mathworks.com\/help\/images\/index.htmlroipoly.html \r\n% |roipoly|>.  (See <https:\/\/blogs.mathworks.com\/steve\/?p=99 Part 1> and \r\n% <https:\/\/blogs.mathworks.com\/steve\/?p=102 Part 2>.)\r\n%\r\n% There are several desirable properties for a polygon scan conversion\r\n% algorithm to have.  It helps to visualize some of these properties if you\r\n% look first at a set of polygons that completely covers the image region,\r\n% with no gaps and no overlaps.\r\n\r\nimshow(ones(20,20), 'InitialMag', 'fit');\r\nhold on\r\nfor x = 0.5:20.5\r\n    for y = 0.5:20.5\r\n        plot([x x], [0.5 20.5], 'Color', [.8 .8 .8]);\r\n        plot([0.5 20.5], [y y], 'Color', [.8 .8 .8]);\r\n    end\r\nend\r\n\r\nx1 = [0.5 10 0.5 0.5];\r\ny1 = [0.5 0.5 20.5 0.5];\r\n\r\nx2 = [10 20.5 20.5 0.5 10];\r\ny2 = [0.5 0.5 4 20.5 0.5];\r\n\r\nx3 = [20.5 20.5 0.5 20.5];\r\ny3 = [4 20.5 20.5 4];\r\n\r\nplot(x1, y1, 'Color', 'r', 'LineWidth', 3, 'Clipping', 'off');\r\nplot(x2, y2, 'Color', 'r', 'LineWidth', 3, 'Clipping', 'off');\r\nplot(x3, y3, 'Color', 'r', 'LineWidth', 3, 'Clipping', 'off');\r\n\r\ntext(4, 4, 'Polygon 1', 'HorizontalAlignment', 'center')\r\ntext(12, 7, 'Polygon 2', 'HorizontalAlignment', 'center')\r\ntext(16, 16, 'Polygon 3', 'HorizontalAlignment', 'center')\r\nhold off\r\n\r\n%%\r\n% Here's what we would like to achieve from our polygon scan conversion:\r\n% \r\n% * There should be no gaps.  That is, since the three polygons cover the\r\n% entire image, every pixel should be assigned to at least one polygon.\r\n% * There should be no overlaps.  That is, since the three polygons do not\r\n% overlap in area, no pixel should be assigned to more than polygon.\r\n% * Pixel assignment to the three polygons should be insensitive to vertex\r\n% ordering.  It should make no difference which polygon vertex is listed\r\n% first, or whether the vertices are listed in clockwise or\r\n% counterclockwise order.\r\n% * Pixel assignment to the three polygons should be unaffected by\r\n% floating-point round-off.\r\n%\r\n% So what rule should we use to decide how to assign pixels that are\r\n% partially inside and outside of a polygon?  One possible rule is that a\r\n% pixel is considered to be inside a polygon if it is partially inside the\r\n% polygon. But that violates the no-overlap rule, since a pixel can be\r\n% inside more than one polygon.\r\n%\r\n% Another possible rule is that a pixel is considered to be inside a\r\n% polygon if at least half of the pixel (by area) is inside the polygon.\r\n% That violates the no-gap rule, though.  Consider the lower-left corner of\r\n% the image above:\r\n\r\naxis([0.5 2.5 18.5 20.5])\r\n\r\n%%\r\n% None of the three polygons covers more than half of the lower-left pixel.\r\n%\r\n% The rule used by |poly2mask| is that a pixel is inside a polygon if and\r\n% only if its center is inside the polygon.\r\n%\r\n% Now we have to consider how to deal cleanly with all the special cases I\r\n% mentioned in <https:\/\/blogs.mathworks.com\/steve\/?p=102 Part 2>.\r\n% Basically, trouble happens whenever a ray passes directly through one or\r\n% more vertices, or along an edge.  |poly2mask| basically avoids these\r\n% problems entirely by approximating the polygon by tiny horizontal and\r\n% vertical line segments that lie on the edges of a 5-by-5 subpixel grid.\r\n% It looks like this:\r\n\r\nclf\r\nhold on\r\nfor x = linspace(0.5,1.5,6)\r\n    for y = linspace(0.5,1.5,6)\r\n        plot([x x], [0.5 1.5], 'Color', [.8 .8 .8]);\r\n        plot([0.5 1.5], [y y], 'Color', [.8 .8 .8]);\r\n    end\r\nend\r\nplot([0.5 1.5], [0.5 1.5], 'b', 'LineWidth', 2)\r\naxis equal \r\naxis ij\r\nplot([0.5 0.5 0.7 0.7 0.9 0.9 1.1 1.1 1.3 1.3 1.5], ...\r\n    [0.5 0.7 0.7 0.9 0.9 1.1 1.1 1.3 1.3 1.5 1.5], ...\r\n    'r', 'LineWidth', 2, 'Clipping', 'off')\r\nplot(1.0, 1.0, '*')\r\nhold off\r\n\r\n%%\r\n% The plot above shows a single pixel.  The blue line represents an\r\n% original edge of the polygon.  The red line approximates the blue line\r\n% using horizontal and vertical segments that lie on the gray grid.\r\n%\r\n% Notice how none of the edges or vertices of the approximation can ever\r\n% intersect the center of the pixel.  Therefore, if we follow rays along\r\n% pixel centers, we will never encounter vertices of the modified polygon,\r\n% nor will any ray be coincident with an edge.  That way, the algorithm can\r\n% coded with no special cases.\r\n%\r\n% To visualize |poly2mask| in action, I wrote the function \r\n% <https:\/\/blogs.mathworks.com\/images\/steve\/108\/vispoly2mask.m \r\n% |vispoly2mask|>, which you can download from here.\r\n\r\nx = [10 35 40 10];\r\ny = [10 40 15 10];\r\nvispoly2mask(x,y,50,50)\r\n\r\n%%\r\n% We need to zoom into a corner of the polygon to see more detail.\r\n\r\naxis([8 15 8 15])\r\n\r\n%%\r\n% The red bars are the horizontal edges of the polygon approximation.\r\n% |poly2mask| scans down the center of each image column, keeping track of\r\n% the number of edge crossings, and using the even-odd rule to decide\r\n% whether each pixel is inside the polygon.\r\n%\r\n% Here's the final result displayed as a binary image with the polygon\r\n% superimposed.\r\n\r\nbw = poly2mask(x,y,50,50);\r\nimshow(bw, 'InitialMag', 'fit')\r\nhold on\r\nplot(x,y,'r','LineWidth',2)\r\nhold off\r\n\r\n##### SOURCE END ##### ecd6545af9594243a272d1ffc1502644\r\n-->","protected":false},"excerpt":{"rendered":"<p>\r\n   This is the final post in a series discussing the algorithm underlying Image Processing Toolbox functions poly2mask and roipoly.  (See Part 1 and Part 2.)\r\n   \r\n   There are several desirable... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/steve\/2006\/12\/22\/poly2mask-and-roipoly-part-3\/\">read more >><\/a><\/p>","protected":false},"author":42,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[28,1],"tags":[50,178,90,36,32,288,68,296,78],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/108"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/users\/42"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/comments?post=108"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/108\/revisions"}],"predecessor-version":[{"id":2229,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/108\/revisions\/2229"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/media?parent=108"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/categories?post=108"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/tags?post=108"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}