c++ - 凸包アルゴリズム - グラハムスキャン最速の比較関数?

Question

私はすでにグラハム スキャンを実装していますが、私のプログラムのボトルネックは並べ替えです (80% の時間)。私はそれを改善したいと思います、今私は次のことをしています：

 std::sort(intersections.begin() + 1, intersections.end(), [&minElement](Point const& a, Point const& b)
 {return angle (minElement - a, XAxis) < angle (minElement - b,XAxis);});

これで正確な角度が得られますが、角度関数は次のようになるため、安価ではありません。

float angle (const Point& v1, const Point& v2) {
    return dot (v1, v2) / (v1.Length () * v2.Length ());
}

Length 関数では、最もコストのかかる操作の 1 つである平方根を実行する必要があります。しかし、このようにして私は良い注文を得ます。

Slope、dot、ccw で配列を並べ替えてみましたが、比較から sqrt を削除するだけでしたが、どれも同じ並べ替えを提供しませんでした。何かアドバイスをいただけますか？

Answer 1

ポイントを相対的な角度で並べ替える場合、2 つのポイントがなす正確な角度を知る必要はありません。むしろ、あるポイントが他のポイントの左にあるか右にあるかを知る必要があるだけです。

_{イメージ。たとえば、2 つの点 (x 1} , y ₁ ) と (x ₂ , y ₂ )を比較したい場合、一番下の点が (x _p , y _p ) にあると仮定します。2 つのベクトル v ₁ = (x ₁ - x _p , y ₁ - y _p ) と v ₂ = (x ₂ - x _p , y ₂ - y _p ) を見てください。_{v 1が v 2}の左側にあるか右側にあるかを判断するには、つまり、v ₁からv に向かう角度の符号を確認する必要があります。₂ . 正の場合、v ₂は v ₁の左側にあり、負の場合、v _{1は v 2}の左側にあります。

2D 外積には、次の優れた特性があります。

v ₁ × v ₂ = |v ₁ | | v ₂ | 罪(θ)

_{ここで、θ は v 1}から v ₂に向かう角度です。これは、v _{1が v 2}の右側にある場合は θ > 0であり、その逆も同様であることを意味します。これは、外積をとることによって純粋にどちらがどこに行くかを比較できるため、便利です!

言い換えると：

• v ₁ × v ₂ > 0 の場合、v ₂は v ₁の左側にあります。
• v ₁ × v ₂ = 0 の場合、点は同一線上にあります。
• v ₁ × v ₂ < 0 の場合、v ₂は v ₁の右側にあります。

2D 外積式は次の式で与えられます。

(Δx ₁ , Δy ₁ ) × (Δx ₂ , Δy ₂ ) = (Δx ₁ Δy ₂ - Δx ₂ Δy ₁ )

ここで、Δx ₁は x ₁ - x _pなどを表します。

したがって、上記の量を計算し、その符号を見て、2 つの点が互いにどのように関係しているかを判断できます。平方根は必要ありません！