凸边形检测

检测凸性的方法是检测多边形上是否有凹点，如果一个都没有找到，就是凸多边形。它的基本想法是每个顶点的转向应该一致，任何转向不一致的点都是凹点。

怎样检测一个点的转向呢？技巧是利用边向量的叉乘，左手坐标系中，如果向量的转向是顺指针，它们的叉乘就会指向你。什么是指向你呢？我们从多边形的正面看，正面由法向量指明。如果没有提供法向量，就必须做一些计算来得到。一旦有了法向量，检查多边形的每个顶点。用相邻的两个边向量计算该顶点的法向量，接着用多边形的法向量和顶点的法向量点乘，检测它们的方向是否相反。如果是（点乘为负），那么这个顶点就是一个凹点。

function isConvex = checkConvex(pts)

% Given a set of points determine if they form a convex polygon

% Inputs 

%  px, py: x and y coordinates of the vertices for a given polygon

% Output 

%  isConvex: 1 or 0 for polygon being convex or concave

    py = pts(:,1);

    px = pts(:,2);

    numPoints = size(px,1);

    if numPoints < 4

        isConvex = 1;

        return

    end

    % can determine if the polygon is convex based on the direction the angles

    % turn.  If all angles are the same direction, it is convex.

    v1 = [px(1) - px(end), py(1) - py(end)];

    v2 = [px(2) - px(1), py(2) - py(1)];

    signPoly = sign(det([v1; v2]));

    % check subsequent vertices

    for k = 2:numPoints-1

        v1 = v2;

        v2 = [px(k+1) - px(k), py(k+1) - py(k)]; 

        curr_signPoly = sign(det([v1; v2]));

        % check that the sign matches the first vectors or is 0

        if curr_signPoly * signPoly < 0

            isConvex = 0;

            return

        end

    end

    % check the last vectors

    v1 = v2;

    v2 = [px(1) - px(end), py(1) - py(end)];

    curr_signPoly = sign(det([v1; v2]));

    if curr_signPoly * signPoly < 0

        isConvex = 0;

    else

        isConvex = 1;

    end

end