计算点云凸包

计算点云凸包其主要思路为：1）搜寻X坐标最小的点，在此称为startPoint，从该点开始搜寻下一点，本例中以逆时针方向来搜寻边界；2）现定义一个虚拟点（该点并不存在）位置为startPoint正北方向，该点与startPoint形成一个向量Vector1，下一点（判断是否为边界点的点，或称选取的点）与startPoint也形成一个向量Vector2，则判断该选取的点是外围边界点所要满足的条件为向量Vector2与向量Vector1之间的夹角最大；3）按同样的方式，新形成的向量Vector1为新选取的外围边界点与上一个外围边界点形成的向量，向量Vector2为选取的点与新选取的外围边界点形成的向量，判断该选取的点是外围边界点所要满足的条件仍然为向量Vector2与向量Vector1之间的夹角最大；4）按此思路循环进行，直到找到一个边界点与startPoint相同。

code:

function out = ConvexHull(pt)
% 获取二维点集凸包
len = size(pt,1);
[~, minDex] = min(pt,[],1);
startIndex = minDex(1);
lastIndex = startIndex - 1;
tempIndex = startIndex;
vector1=[0, 100];
edge.start = startIndex;
angleMax = 0;
out = [];
while lastIndex ~= startIndex
v1Len = norm(vector1);
lengthMin = inf;
for i = 1: len
    if i ~= edge.start
        vector2 = [pt(i, 1) - pt(tempIndex, 1), pt(i,2) - pt(tempIndex,2)];
        v2Len = norm(vector2);
        angle = acos(dot(vector1, vector2) / (v1Len * v2Len));
        if angle > angleMax
            angleMax = angle;
            edge.end = i;
            lengthMin = v2Len;
        elseif angle == angleMax && v2Len < lengthMin
            edge.end = i;
            lengthMin = v2Len;
        end
    end
end
edge.lefttri = -1;
edge.righttri = -1;
out = [out edge];
lastIndex = edge.end;
edge.start = lastIndex;
edge.end = -1;
angleMax = 0;
vector1 = [pt(tempIndex,1) - pt(lastIndex,1), pt(tempIndex,2) - pt(lastIndex,2)];
tempIndex = lastIndex;
end