www.gusucode.com > matlab 案例源码 matlab代码程序 > matlab/ConvexHullsVsNonconvexPolygonsExample.m

    %% Convex Hulls vs. Nonconvex Polygons
% The convex hull of a set of points in N-D space is the smallest convex
% region enclosing all points in the set. If you think of a 2-D set of
% points as pegs in a peg board, the convex hull of that set would be
% formed by taking an elastic band and using it to enclose all the pegs.

% Copyright 2015 The MathWorks, Inc.


x = gallery('uniformdata',20,1,20);
y = gallery('uniformdata',20,1,30);
plot(x,y,'r.','MarkerSize',10)
hold on
k = convhull(x,y);
plot(x(k),y(k))
title('The Convex Hull of a Set of Points')
hold off

%%
% A convex polygon is a polygon that does not have concave vertices, for
% example:

x = gallery('uniformdata',20,1,30);
y = gallery('uniformdata',20,1,40);
k = convhull(x,y);
plot(x(k),y(k))
title('Convex Polygon')

%%
% You can also create a boundary of a point set that is nonconvex. If you
% "vacuum pack" the convex hull from above, you can enclose
% all of the points in a nonconvex polygon with concave vertices:

k = boundary(x,y,0.9);
plot(x(k),y(k))
title('Nonconvex Polygon')

%%
% The convex hull has numerous applications. You can compute the upper
% bound on the area bounded by a discrete point set in the plane from the
% convex hull of the set. The convex hull simplifies the representation of
% more complex polygons or polyhedra. For instance, to determine whether
% two nonconvex bodies intersect, you could apply a series of fast
% rejection steps to avoid the penalty of a full intersection
% analysis:
%%
% 
% * Check if the axis-aligned bounding boxes around each body intersect.
% * If the bounding boxes intersect, you can compute the convex hull of
% each body and check intersection of the hulls.
% 
% If the convex hulls did not intersect, this would avoid the expense of a
% more comprehensive intersection test.
%
% While convex hulls and nonconvex polygons are convenient ways to
% represent relatively simple boundaries, they are in fact specific
% instances of a more general geometric construct called the alpha
% shape.