4

そこで、ポイント グループの凸包を見つけるためのギフト ラッピング アルゴリズムの例に基づいて、次のコードを作成しました。

std::vector<sf::Vector2f> convexHull(const std::vector<sf::Vector2f>& _shape)
{
    std::vector<sf::Vector2f> returnValue;    
    returnValue.push_back(leftmostPoint(_shape));
    for (std::vector<sf::Vector2f>::const_iterator it = _shape.begin(), end = _shape.end(); it != end; ++it)
    {
        if (elementIncludedInVector(*it, returnValue)) continue;
        bool allPointWereToTheLeft = true;
        for (std::vector<sf::Vector2f>::const_iterator it1 = _shape.begin(); it1 != end; ++it1)
        {
            if (*it1 == *it || elementIncludedInVector(*it1, returnValue)) continue;
            if (pointPositionRelativeToLine(returnValue.back(), *it, *it1) > 0.0f)
            {
                allPointWereToTheLeft = false;
                break;
            }
        }
        if (allPointWereToTheLeft)
        {
            returnValue.push_back(*it);
            it = _shape.begin();
        }
    }
    return returnValue;
}

3 番目の点が線のどちら側にあるかを判断するための関数は次のとおりです。

float pointPositionRelativeToLine(const sf::Vector2f& A, const sf::Vector2f& B, const sf::Vector2f& C)
{
    return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
}

負の数を返すと、ポイントが片側にあり、正の数が反対側にあることを意味します。0 は、3 つのポイントが同一線上にあることを意味します。そして今、質問: _shape に共線点がある場合でも正しく機能するように、上記のコードをどのように変更できますか?

4

3 に答える 3

7

いくつかの点が同一線上にある場合、それらから最も遠い点を選択する必要があります (現在の点までの最大距離で)

于 2015-08-31T18:26:02.303 に答える
1

A と B の相対的な配置が B が凸包上にないことを証明する場合、A は B を除外するという意味で、2 つの点 (共通の中心の周り) 間の「除外」関係に基づいて推論することができます。

図では、緑のポイントは青のポイントを除外していますが、赤のポイントは除外していません。整列された 2 つのポイントのうち、中心から最も遠いポイントが他のポイントを除外します。排除軌跡は、開いた半平面と半直線です。

ここに画像の説明を入力

「除外」は推移的であり、全体の順序を定義することに注意してください。

于 2015-09-02T08:33:29.357 に答える
0

これは、デモンストレーションするコードよりも正しく行うのが少し難しいです。述語の安定性のみに焦点を当て、共線点の処理方法には焦点を当てません。述語は、幾何学的計算を行う場所です - pointPositionRelativeToLine。

コードは、述語で幾何学的計算のみを行うという点で適切に設計されています。それはそれを堅牢にするために必須です。残念ながら、述語は float を返すべきではありませんが、1 つの結果は小さなセットから返されます: いずれかLEFT,RIGHTまたはCOLLINEAR:

enum RelPos { LEFT, RIGHT, COLLINEAR };

RelPos pointPositionRelativeToLine(const sf::Vector2f& A, const sf::Vector2f& B, const sf::Vector2f& C)
{
    auto result = (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
    if (result < 0.0) return LEFT;
    else if (result > 0.0) return RIGHT;
    return COLLINEAR;
}

次に、任意の 3 つのポイントが与えられた場合に、それらの任意の順列に対して正しい答えが返されることを保証する方法を理解できます。そうしないと、アルゴリズムの動作が保証されません。

2 つの一般的なアプローチがあります。

  1. 述語で使用した場合に正確な結果を保証する適切なデータ型を使用してください。

  2. 使用している不正確なデータ型では、結果を計算できない入力がいくつかあることを受け入れてください。具体的には、述語に 4 番目の値 を提供INDETERMINATEさせ、そのような場合にそれを返すことができます。

2 番目のアプローチは、入力のすべての順列に対して元の述語を呼び出すことで簡単に実装できます。

enum RelPos { LEFT, RIGHT, COLLINEAR, INDETERMINATE };
typedef sf::Vector2f Point_2;

RelPos ppImpl(const Point_2 & A, const Point_2 & B, const Point_2 & C)
{
    auto result = (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
    if (result < 0.0) return LEFT;
    else if (result > 0.0) return RIGHT;
    return COLLINEAR;
}

bool inverse(RelPos a, RelPos b) {
  return a == LEFT && b == RIGHT || a == RIGHT && b == LEFT;
}

bool equal(RelPos a, RelPos b, RelPos c, RelPos d, RelPos e, RelPos f) {
  return a==b && b==c && c==d && d==e && e==f;
}

RelPos pointPositionRelativeToLine(const Point_2 & A, const Point_2 & B, const Point_2 & C) {
  auto abc = ppImpl(A, B, C);
  auto bac = ppImpl(B, A, C);
  auto acb = ppImpl(A, C, B);
  auto cab = ppImpl(C, A, B);
  auto bca = ppImpl(B, C, A);
  auto cba = ppImpl(C, B, A);
  if (abc == COLLINEAR) return equal(abc, bac, acb, cab, bca, cba) ?
    COLLINEAR : INDETERMINATE;
  if (!inverse(abc, bac) || !inverse(acb, cab) || !inverse(bca, cba))
    return INDETERMINATE;
  if (abc != bca || abc != cab)
    return INDETERMINATE;
  return abc;
}

上記のロジックに誤りがある可能性があります。正しく理解できることを願っています。しかし、それがここでの一般的なアプローチです。アルゴリズムがデータセットで機能するには、少なくとも特定のデータセットに対する上記のテストに合格する必要があります。しかし、それが十分条件であるかどうかは覚えていません。

もちろん、アルゴリズムINDETERMINATEは述語から結果が得られたときに終了する必要があります。

const auto errVal = std::vector<sf::Vector2f>();
...
auto rel = pointPositionRelativeToLine(returnValue.back(), *it, *it1);
if (rel == INDETERMINATE) return errVal;
if (rel == RIGHT) {
  allPointWereToTheLeft = false;
  break;
}
于 2015-08-31T19:04:54.390 に答える