ポリゴンの最大長と最小長の対角線を取得するために、力ずくで比較するよりも良い方法はありますか? より具体的には、比率を見つけたいので、ポリゴンの「細さ」でソートできます。
ポリゴンはそれほど大きくはありませんが (通常、ポリゴンごとに 4 ～ 8 面)、多くのポリゴンがあります。SOに確認して、これを行うより良い方法があるかどうかを確認したいと思いました。
前もって感謝します
1004 次
1 に答える
2
ポリゴンはそれほど大きくはありませんが (通常、ポリゴンごとに 4 ～ 8 面)、多くのポリゴンがあります。
O(n^2) よりも速い解決策があるかどうかはわかりませんが、n <= 8それは問題ではありません。の場合n = 8は、20 個の対角線をチェックするだけです ( 8 * 5 / 2)。それ自体はそれほど大きな乗数ではなく、複雑なアルゴリズムには多くの計算オーバーヘッドがかかる可能性があります (データ構造、高度なループとチェック)。
ただし、速度を上げるためにできることの 1 つは、2 点間の距離の公式で平方根を捨てることです。最初に の最小値/最大値を見つけてから(xi-xj)*(xi-xj) + (yi-yj)*(yi-yj)、平方根を適用します。これは非常にコストのかかる操作であり、20 回ではなく 2 回実行すると違いが生じる可能性があります。
于 2010-08-15T21:06:18.290 に答える