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.

Is your end goal to get the coordinates of the blue line, or to generate a mask of the dark gray region? — gnovice, Jul 20 '17 at 04:17
@gnovice, correct. the final target is the mask. but I need the coordinates array of its outline, so that I can generate the mask. Or if the algorithm/function can generate the mask and give me the coordinates of its outline is also ok. Thank you. — george andrew, Jul 20 '17 at 10:44
Do you just need to display the blue outline, or do you need the coordinates of the outline in some specific order (i.e. clockwise around gray region)? — gnovice, Jul 20 '17 at 16:36
yes, I need the coordinates. I have a sequence of coordinates of points of original outline (for example, a circle, a triangle or other closed curve). And I need the new coordinates. so from coordinates to coordinates. — george andrew, Jul 20 '17 at 17:28

gnovice · Accepted Answer · 2017-10-26T16:24:20.333

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.

Thank you very much for your great help@gnovice. I believe in matlab there is a alternative method other than to implement the original algorithm. And your method is superb! — george andrew, Jul 22 '17 at 11:49

score 1 · Answer 2 · answered Jul 20 '17 at 02:33

1

Seems you need any line rasterization algorithm (that gives coordinate of integer grid points approximating line segment).

Consider Bresenham algortihm or DDA one.

answered Jul 20 '17 at 02:33

MBo

77,366
5
53
86

thank you to let me know the idea behind this question @MBo! I also like your answer. – george andrew Jul 22 '17 at 11:51

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

2 Answers2

Getting the mask (the easy part):

Getting the outline coordinates:

Linked

Related