{"id":2788,"date":"2018-02-20T18:30:00","date_gmt":"2018-02-20T23:30:00","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=2788"},"modified":"2019-11-01T19:50:23","modified_gmt":"2019-11-01T23:50:23","slug":"minimum-feret-diameter","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2018\/02\/20\/minimum-feret-diameter\/","title":{"rendered":"Minimum Feret Diameter"},"content":{"rendered":"

Last time<\/a> (if you can remember that long ago), I talked about how to find the maximum Feret diameter<\/i> of a shape. The Feret diameter, sometimes called the caliper diameter<\/i>, is illustrated by the diagram below. In a virtual sense, place the object to be measured inside the jaws of a caliper, with the caliper oriented at a specified angle. Close the jaws tightly on the object while maintaining that angle. The distance between the jaws is the Feret diameter at that angle.<\/p>

\"\" <\/p>

In the last post, I demonstrated how to find all the antipodal<\/i> vertex pairs of a shape, which is a useful step in finding the maximum Feret diameters of a shape.<\/p>

Here is a convex shape with all of the antipodal vertex pairs shown.<\/p>

\"\" <\/p>

It turns out that the minimum<\/b> Feret diameter can also be found by looking at these antipodal pairs. Furthermore, it happens that the minimum-distance Feret calipers touch the shape at three<\/b> of these vertices. I'm not going to try to prove that here, but let me illustrate it with a couple of diagrams.<\/p>

Here is a shape with a couple of \"caliper lines\" drawn at -30 degrees. (Note that the y-axis is reversed; that's why the angle is negative.)<\/p>

hull = [\r\n    2.5000    5.5000\r\n    3.5000    4.5000\r\n    6.5000    2.5000\r\n    9.5000    1.5000\r\n   10.5000    1.5000\r\n   10.5000    3.5000\r\n    9.5000    5.5000\r\n    5.5000    7.5000\r\n    2.5000    7.5000\r\n    2.5000    5.5000  ];\r\n\r\nplot(hull(:,1),hull(:,2),'r'<\/span>,'LineWidth'<\/span>,2)\r\naxis equal<\/span>\r\naxis ij<\/span>\r\naxis([0 15 0 10])\r\nhold on<\/span>\r\nplot(hull(:,1),hull(:,2),'r*'<\/span>)\r\n[x1,y1] = fullLine(gca,[9.5 5.5],-30);\r\n[x2,y2] = fullLine(gca,[6.5 2.5],-30);\r\ncaliper_lines(1) = plot(x1,y1,'k'<\/span>);\r\ncaliper_lines(2) = plot(x2,y2,'k'<\/span>);\r\nhold off<\/span>\r\n<\/pre>\"\" 
You can always rotate these two caliper lines, by the same angle, until at least one of them touches the next<\/b> antipodal vertex. When you do that rotation, the distance between the lines shrinks.<\/p>
set(caliper_lines,'Color'<\/span>,[0.8 0.8 0.8]);\r\n[x3,y3] = fullLine(gca,[9.5 5.5],thetad);\r\n[x4,y4] = fullLine(gca,[6.5 2.5],thetad);\r\nhold on<\/span>\r\nplot(x3,y3,'k'<\/span>)\r\nplot(x4,y4,'k'<\/span>)\r\nhold off<\/span>\r\n<\/pre>\"\" 
The Feret diameter at that rotated angle, then, is the height of the triangle formed by the three vertices, with the base of the triangle defined by the two vertices touched by the same caliper line.<\/p>
delete(caliper_lines);\r\nhold on<\/span>\r\nplot([5.5 9.5 6.5 5.5],[7.5 5.5 2.5 7.5],'Color'<\/span>,'b'<\/span>,'LineWidth'<\/span>,2)\r\nhold off<\/span>\r\n<\/pre>\"\" 
The function minFeretDiameter<\/tt>, which appears at the end of this post, simply walks around the set of adjacent-vertex triangles formed from antipodal vertex pairs, looking for the triangle with the minimum height.<\/p>
Let's look for the minimum Feret diameter in a slightly more interesting shape.<\/p>
load shape<\/span>\r\nplot(bx,by,'LineWidth'<\/span>,1)\r\naxis equal<\/span>\r\naxis ij<\/span>\r\naxis([0 650 0 650])\r\n<\/pre>\"\" 
Find the convex hull, making sure to simplify it, and then find the antipodal pairs. (I showed the function antipodalPairs<\/tt> in my previous post.)<\/p>
hull = convhull(bx,by,'Simplify'<\/span>,true);\r\nS = [bx(hull) by(hull)];\r\npairs = antipodalPairs(S);\r\n<\/pre>
Now we can call minFeretDiameter<\/tt>.<\/p>
[d,tri_points] = minFeretDiameter(S,pairs)\r\n<\/pre>
\r\nd =\r\n\r\n  318.7890\r\n\r\n\r\ntri_points =\r\n\r\n   613   211\r\n   459   443\r\n   239   198\r\n\r\n<\/pre>
Superimpose the minimum-height triangle that minFeretDiameter<\/tt> found.<\/p>
tri_points = [tri_points; tri_points(1,:)];\r\nhold on<\/span>\r\nplot(tri_points(:,1),tri_points(:,2),'LineWidth'<\/span>,2)\r\nhold off<\/span>\r\n<\/pre>\"\" 
Now calculate the caliper angle so that we can visualize the parallel lines of support corresponding to the minimum diameter.<\/p>
dx = tri_points(2,1) - tri_points(1,1);\r\ndy = tri_points(2,2) - tri_points(1,2);\r\nangle = atan2d(dy,dx);\r\n[x5,y5] = fullLine(gca,tri_points(1,:),angle);\r\n[x6,y6] = fullLine(gca,tri_points(3,:),angle);\r\n<\/pre>
hold on<\/span>\r\nplot(x5,y5,'k'<\/span>)\r\nplot(x6,y6,'k'<\/span>)\r\nhold off<\/span>\r\n<\/pre>\"\" 
For next time, I'm tentatively planning to put together some of these concepts and use them to compute the minimum bounding box for an object.<\/p>
function<\/span> [x,y] = fullLine(ax,point,angle_degrees)\r\n% Steve Eddins<\/span>\r\n\r\n\r\nlimits = axis(ax);\r\nwidth = abs(limits(2) - limits(1));\r\nheight = abs(limits(4) - limits(3));\r\nd = 2*hypot(width,height);\r\nx1 = point(1) - d*cosd(angle_degrees);\r\nx2 = point(1) + d*cosd(angle_degrees);\r\ny1 = point(2) - d*sind(angle_degrees);\r\ny2 = point(2) + d*sind(angle_degrees);\r\nx = [x1 x2];\r\ny = [y1 y2];\r\nend<\/span>\r\n\r\nfunction<\/span> [d,triangle_points] = minFeretDiameter(V,antipodal_pairs)\r\n% Steve Eddins<\/span>\r\n\r\n\r\nif<\/span> nargin < 2\r\n    antipodal_pairs = antipodalPairs(V);\r\nend<\/span>\r\n\r\nn = size(antipodal_pairs,1);\r\np = antipodal_pairs(:,1);\r\nq = antipodal_pairs(:,2);\r\n\r\nd = Inf;\r\ntriangle_points = [];\r\n\r\nfor<\/span> k = 1:n\r\n    if<\/span> k == n\r\n        k1 = 1;\r\n    else<\/span>\r\n        k1 = k+1;\r\n    end<\/span>\r\n\r\n    pt1 = [];\r\n    pt2 = [];\r\n    pt3 = [];\r\n\r\n    if<\/span> (p(k) ~= p(k1)) && (q(k) == q(k1))\r\n        pt1 = V(p(k),:);\r\n        pt2 = V(p(k1),:);\r\n        pt3 = V(q(k),:);\r\n\r\n    elseif<\/span> (p(k) == p(k1)) && (q(k) ~= q(k1))\r\n        pt1 = V(q(k),:);\r\n        pt2 = V(q(k1),:);\r\n        pt3 = V(p(k),:);\r\n    end<\/span>\r\n\r\n    if<\/span> ~isempty(pt1)\r\n        % Points pt1, pt2, and pt3 form a possible minimum Feret diameter.<\/span>\r\n        % Points pt1 and pt2 form an edge parallel to caliper direction.<\/span>\r\n        % The Feret diameter orthogonal to the pt1-pt2 edge is the height<\/span>\r\n        % of the triangle with base pt1-pt2.<\/span>\r\n\r\n        d_k = triangleHeight(pt1,pt2,pt3);\r\n        if<\/span> d_k < d\r\n            d = d_k;\r\n            triangle_points = [pt1; pt2; pt3];\r\n        end<\/span>\r\n    end<\/span>\r\nend<\/span>\r\nend<\/span>\r\n<\/pre>