アルゴリズム&データ構造-最大バンプ生成
2226 ワード
最大凸ポリゴン生成アルゴリズムを記録します.ランダム頂点によって、すべての頂点を含む凸ポリゴンを生成します.
ポリゴン生成アルゴリズム
ランダム頂点を使用して、すべての頂点を接続するポリゴンを生成します.
アルゴリズムの考え方:
平面座標の一番下にある頂点を見つけ、この頂点を中心に他の頂点を角度に基づいて並べ替えます.並べ替えが完了すると、ポリゴンは生成されます.
C++実装:
最大バンプ生成アルゴリズム
アルゴリズムの考え方:
ポリゴンアルゴリズムに基づいて、次の操作を行います.1は、第1の頂点p 0と第2の頂点p 1とをセットし、p 2を第3の頂点 に向ける.2コレクションが巡回していない場合は、ステップ3にジャンプし、そうでなければステップ6 にジャンプする.3 p 2がp 0 p 1の左側にあると判断するとステップ4にジャンプし、そうでなければステップ5 にジャンプする.4 p 2スタック,p 0,p 1,p 2をそれぞれ1ステップずつ進み、ステップ2 にジャンプする.5 p 1をスタックから出て、ステップ2 にジャンプする6アルゴリズム終了 C++実装:
ポリゴン生成アルゴリズム
ランダム頂点を使用して、すべての頂点を接続するポリゴンを生成します.
アルゴリズムの考え方:
平面座標の一番下にある頂点を見つけ、この頂点を中心に他の頂点を角度に基づいて並べ替えます.並べ替えが完了すると、ポリゴンは生成されます.
C++実装:
void PolygonHull(std::vector & 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 ConvexHull(std::vector & 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 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;
}