記錄一個(gè)最大凸多邊形生成算法：通過隨機(jī)頂點(diǎn)，生成一個(gè)包含所有頂點(diǎn)的凸多邊形看彼。
多邊形生成算法
通過隨機(jī)頂點(diǎn)襟铭，生成一個(gè)連接所有頂點(diǎn)的多邊形
算法思路：
找到出于平面坐標(biāo)最下面的頂點(diǎn)螃征，以這個(gè)頂點(diǎn)為中心碎绎，對(duì)其他頂點(diǎn)依據(jù)角度進(jìn)行排序蝇狼。排序完成后阅畴，多邊形就已經(jīng)生成了。
C++實(shí)現(xiàn)：
void PolygonHull(std::vector<POINT> & points)
{
auto val = *std::min_element(points.begin(), points.end(), [](const POINT & p1, const POINT & p2)
{
return p1.y < p2.y || p1.x < p2.x;
});
std::sort(points.begin(), points.end(), [&val](const POINT & p1, const POINT & p2)
{
auto a1 = GetAngle(val, p1), l1 = GetLengthSqr(p1 - val);
auto a2 = GetAngle(val, p2), l2 = GetLengthSqr(p2 - val);
return a1 < a2 || a1 == a2 && l1 < l2;
});
}
最大凸包生成算法
算法思路：
在多邊形算法的基礎(chǔ)上迅耘，進(jìn)行以下操作：
- 1 將集合第一個(gè)頂點(diǎn) p0 和第二個(gè)頂點(diǎn) p1 壓棧贱枣，將 p2 指向第三個(gè)頂點(diǎn)
- 2 如果集合沒有遍歷完，則跳到步驟3颤专，否則跳到步驟6
- 3 判斷 p2 處于 p0p1 的左邊則跳到步驟4纽哥，否則跳到步驟5
- 4 將 p2 壓棧，p0栖秕，p1春塌，p2各前進(jìn)1步，跳到步驟2
- 5 將 p1 出棧簇捍，跳到步驟2
- 6 算法結(jié)束
C++實(shí)現(xiàn)：
std::vector<POINT> ConvexHull(std::vector<POINT> & points)
{
auto val = *std::min_element(points.begin(), points.end(), [](const POINT & p1, const POINT & p2)
{
return p1.y < p2.y || p1.x < p2.x;
});
std::sort(points.begin(), points.end(), [&val](const POINT & p1, const POINT & p2)
{
auto a1 = GetAngle(val, p1), l1 = GetLengthSqr(p1 - val);
auto a2 = GetAngle(val, p2), l2 = GetLengthSqr(p2 - val);
return a1 < a2 || a1 == a2 && l1 < l2;
});
std::vector<POINT> set;
auto iter = points.cbegin();
set.push_back(*iter++);
set.push_back(*iter++);
while (iter != points.cend())
{
auto & p0 = *(set.cend() - 2),
& p1 = *(set.cend() - 1),
& p2 = *iter;
if (0 > Corss(p1 - p0, p2 - p1))
set.pop_back();
else
set.push_back(*iter++);
}
return set;
}
