{"id":102,"date":"2006-12-13T15:43:26","date_gmt":"2006-12-13T20:43:26","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=102"},"modified":"2019-10-22T16:37:38","modified_gmt":"2019-10-22T20:37:38","slug":"poly2mask-and-roipoly-part-2","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2006\/12\/13\/poly2mask-and-roipoly-part-2\/","title":{"rendered":"POLY2MASK and ROIPOLY – Part 2"},"content":{"rendered":"
\r\n

I'm familiar with two basic ways to determine whether a point is inside a polygon. The first is to compute the winding number<\/a>, which is the number of times that a closed curve encircles the point. This technique is used by the MATLAB function inpolygon<\/a>.\r\n <\/p>\r\n

When computing point-inside-polygon for all the points on a pixel grid, the crossing test is more commonly used. You follow\r\n a ray from one side of the image to the other, counting the number of times the ray crosses an edge of the polygon.\r\n <\/p>

x1 = [30 80 60 30];\r\ny1 = [30 50 90 30];\r\nray_x = [20 90];\r\nray_y = [70 70];\r\npoints_x = [30 60 80];\r\npoints_y = [70 70 70];\r\nplot(x1,y1)\r\nhold on<\/span>\r\nplot(ray_x,ray_y, 'r'<\/span>)\r\nplot(points_x,points_y,'Marker'<\/span>,'o'<\/span>,'MarkerSize'<\/span>,4,'Color'<\/span>,'k'<\/span>,...<\/span>\r\n    'MarkerFaceColor'<\/span>,'k'<\/span>,'LineStyle'<\/span>,'none'<\/span>)\r\ntext(30,70,'A'<\/span>,'VerticalAlignment'<\/span>,'bottom'<\/span>)\r\ntext(60,70,'B'<\/span>,'VerticalAlignment'<\/span>,'bottom'<\/span>)\r\ntext(80,70,'C'<\/span>,'VerticalAlignment'<\/span>,'bottom'<\/span>)\r\naxis off<\/span>\r\nhold off<\/span>\r\ntitle('Polygon 1'<\/span>)<\/pre> 
At point A, the ray has not crossed a polygon edge; A is outside the polygon.  At point B, the ray has crossed a polygon edge\r\n      one time; B is inside.  At point C, the ray has crossed a polygon edge twice; C is outside.\r\n   <\/p>\r\n   
Polygons can get much more complex than a triangle, of course.  Here are a couple of convex, nonsimple polygons.<\/p>
subplot(2,1,1)\r\nplot([30 70 70 30 30], [30 70 30 70 30])\r\nhold on<\/span>\r\nplot([20 80],[60 60],'r'<\/span>)\r\nhold off<\/span>\r\naxis off<\/span>\r\ntitle('Polygon 2'<\/span>)\r\n\r\nsubplot(2,1,2)\r\nplot([30 70 70 40 40 60 60 30 30], ...<\/span>\r\n    [30 30 55 55 35 35 60 60 30])\r\nhold on<\/span>\r\nplot([20 80],[45 45],'r'<\/span>)\r\nplot(50,45,'Marker'<\/span>,'o'<\/span>,'MarkerSize'<\/span>,4,'MarkerFaceColor'<\/span>,'k'<\/span>)\r\ntext(50,45,'D'<\/span>,'VerticalAlignment'<\/span>,'bottom'<\/span>)\r\nylim([25 75])\r\nhold off<\/span>\r\naxis off<\/span>\r\ntitle('Polygon 3'<\/span>)<\/pre> 
In polygon 2, the ray crosses into and then out of the polygon twice.  Polygon 3 is even more interesting.  Is point D inside\r\n      or outside the polygon? The answer is a matter of convention.  A commonly-used convention is the even-odd<\/i> rule.  A point is outside the polygon if there have been an even number of edge crossings.  A point is inside there have\r\n      been an odd number.  By this rule, point D is outside the polygon.\r\n   <\/p>\r\n   
The crossing test and the even-odd rule are easy to understand.  The challenge is to avoid getting tripped up in the special\r\n      cases.  The troublesome cases include rays intersecting vertices, edge intersections, and coincident edges.  Another case\r\n      is when a ray is coincident with an edge.  Here are some diagrams to illustrate.  (Note that in polygon 7 there are two coincident\r\n      edges on the left side of the polygon.)\r\n   <\/p>
subplot(2,2,1)\r\nplot([20 30 40 30 20], [30 20 30 40 30]);\r\nhold on<\/span>\r\nplot([10 50], [30 30], 'r'<\/span>)\r\nhold off<\/span>\r\naxis off<\/span>\r\ntitle('Polygon 4'<\/span>), ylim([10 50])\r\n\r\nsubplot(2,2,2)\r\nplot([20 30 40 50 60 20], [30 10 20 10 30 30]);\r\nhold on<\/span>\r\nplot([10 70], [10 10], 'r'<\/span>)\r\nhold off<\/span>\r\naxis off<\/span>\r\ntitle('Polygon 5'<\/span>), ylim([0 40])\r\n\r\nsubplot(2,2,3)\r\nplot([20 50 20 50 20], [20 20 60 60 20]);\r\nhold on<\/span>\r\nplot([10 60], [40 40], 'r'<\/span>)\r\nhold off<\/span>\r\naxis off<\/span>\r\ntitle('Polygon 6'<\/span>), ylim([10 70])\r\n\r\nsubplot(2,2,4)\r\nplot([20 60 60 20 20 50 20 20], ...<\/span>\r\n    [20 20 50 50 20 35 50 20]);\r\nhold on<\/span>\r\nplot([10 70],[35 35],'r'<\/span>)\r\nhold off<\/span>\r\naxis off<\/span>\r\ntitle('Polygon 7'<\/span>), ylim([10 60])<\/pre> 
In my next post on this topic, I'll get into the specific algorithm used by the Image Processing Toolbox functions polymask<\/tt> and roipoly<\/tt>.\r\n   <\/p>\r\n   
Here's Part 1<\/a> of this topic.\r\n   <\/p>