algorithm - How to generate the stair step curve(outline) for any 2d shape(or curve)?

Question

If I have the coordinates of the points on the outline of an arbitrary 2D shape, how can I find the coordinates of points composing the outline of a stair step curve, which best represents the original outline, but only use a set of known coordinates (xi, i=1,...,n and yi, i=1,...,m). For example the original triangle is represented by the thick solid blue line. it's different from the matlab stairs function, if my understanding is correct. matlab code will be nice, but in other language is also ok, algorithm is most important.Thanks.

Answer 1

I'll start by defining a set of sample data based on your plot. Assuming that the pixel centers are aligned at integer values (the convention MATLAB follows) and that the lower left corner is at (0.5, 0.5), here's the data we get:

vx = [1.5; 9.7; 3.7; 1.5];  % X values of triangle vertices
vy = [8.3; 6.0; 1.7; 8.3];  % Y values of triangle vertices
x = 1:10;                   % X pixel center coordinates
y = 1:9;                    % Y pixel center coordinates

Note that the vertex coordinates are ordered starting at the top left corner of the triangle and proceeding clockwise, repeating the first vertex at the end to close the polygon.

Getting the mask (the easy part):

There is an easy way to compute the dark gray mask if you have the Image Processing Toolbox: use poly2mask:

mask = poly2mask(vx, vy, numel(y), numel(x));

The algorithm this function uses is discussed here. However, if you'd like to use a pure MATLAB approach that requires no special toolboxes, you can use inpolygon instead:

[cx, cy] = meshgrid(x, y);         % Generate a grid of x and y values
mask = inpolygon(cx, cy, vx, vy);

In this case, a pixel is included in the mask as long as its center point lies within the polygon. In this particular example these two approaches yield the same resulting mask, but they won't always due to the differences in their criteria for deciding if a pixel is included or not.

Getting the outline coordinates:

It's a little more involved to get the coordinates of the mask outline, ordered appropriately around the perimeter. To accomplish this, we can represent the mask as a series of vertices and triangular facets (using the triangulation function), then compute the free boundary (i.e. edges that are only present on one triangular facet):

% Create raw triangulation data:
[cx, cy] = meshgrid(x, y);
xTri = bsxfun(@plus, [0; 1; 1; 0], cx(mask).');
yTri = bsxfun(@plus, [0; 0; 1; 1], cy(mask).');
V = [xTri(:) yTri(:)];
F = reshape(bsxfun(@plus, [1; 2; 3; 1; 3; 4], 0:4:(4*nnz(mask)-4)), 3, []).';

% Trim triangulation data:
[V, ~, Vindex] = unique(V, 'rows');
V = V-0.5;
F = Vindex(F);

% Create triangulation and find free edge coordinates:
TR = triangulation(F, V);
freeEdges = freeBoundary(TR).';
xOutline = V(freeEdges(1, [1:end 1]), 1);  % Ordered edge x coordinates
yOutline = V(freeEdges(1, [1:end 1]), 2);  % Ordered edge y coordinates

And we can plot this like so:

imagesc(x, y, mask);
axis equal
set(gca, 'XLim', [min(x)-0.5 max(x)+0.5], ...
         'YLim', [min(y)-0.5 max(y)+0.5], ...
         'XTick', x, 'YTick', y, 'YDir', 'normal');
colormap([0.9 0.9 0.9; 0.6 0.6 0.6]);
hold on;
plot(xOutline, yOutline, 'b', 'LineWidth', 2);
plot(xOutline(1), yOutline(1), 'go', 'LineWidth', 2);
plot(vx, vy, 'r', 'LineWidth', 2);

The outline coordinates in xOutline and yOutline are ordered starting from the green circle going counter-clockwise around the mask region.