7

GeneralPathJavaのクラスは、ポイントが一般的なパス(具体的には、直線セグメントを持つポリゴン)内にあるかどうかを確認するメソッドのみを提供することがわかりました。ポイントが一般的なパスの境界上にあるかどうかを効率的にチェックする方法を誰かが知っていますか?

ありがとう

ダミーの解決策 1:半径が $\epsilon$ の円を定義できます ($\epsilon$ は非常に小さい正の実数値です)。次に、円上の十分な数の点をチェックして、そのうちの 1 つまたはいくつかが一般的なパスに該当するかどうかを確認します。しかし、そのようなダミーの方法は、かなりの量の計算作業を必要とする可能性があり、あまり望ましくありません。

ダミーの解決策 2: (境界上の) ポイントからポリゴンの各辺までの距離を計算できます。最小距離が十分に小さい場合、この点は境界上にあります。そうでない場合は、そうではありません。繰り返しますが、この方法でも計算負荷が高くなる可能性があります。

4

2 に答える 2

4

私はライブラリメソッドに出くわしていません...または問題の解決策を鉢植えにしています。その理由は、問題を正確に解決することは根本的に不可能だからだと思います。

このクラスは、からGeneralPath呼び出されたメソッドを継承します。javadoc を見ると、オブジェクトが一連の直線セグメントとしてパスをモデル化していることがわかります。このメソッドは、次のように指定されたパラメーターを受け取ります。getPathIteratorShape2DPathIteratorgetPathIteratorflatness

平坦度 - 曲線セグメントを近似するために使用される線セグメントが元の曲線上の任意の点から逸脱できる最大距離。

ここで、見ている形状が直線セグメントで構成されている場合、パス反復子がそれらの線セグメントを提供する可能性が高くなります。ただし、形状に曲線セグメントがある場合、線セグメントは近似値にすぎません。また、正確な境界が何であるかがわからない場合、点が正確に境界上にあるかどうかをテストすることは明らかに不可能です。

線分が実際の曲線を正確にモデル化していると仮定しても、(特殊なケースを除いて) Java プリミティブ データ型 (int、double など) を使用して実際の曲線上のほとんどの点を正確に表すことができないという問題がまだあります。繰り返しになりますが、「正確さ」は問題です。

期待できる最善の方法は、ポイントが境界の小さなデルタ内にあるかどうかをテストすることだと思います...そしてflatnessそのデルタよりも小さい値を選択し、パスラインセグメントを繰り返し、各セグメントからのポイント。

注:flatness非常に小さくすると、非常に多数の線分をテストする必要が生じることが予想されます。GeneralPath APIに固執している間、この計算上の懸念を回避する方法はないと思います。


問題を真の (つまり、直線の) 多角形に限定する場合は、単純に線分を反復し、点から線までの距離が適切なイプシロンよりも小さいかどうかをテストするだけです。 このウィキペディアのエントリは、数学を提供します。ここでは正確さが依然として懸念されることに注意してください...

非常にコストのかかる計算はありませんが、正確な平方根の計算は無料ではなく、N 辺の多角形に対して最大 N 回実行する必要があります。

それよりもうまくやること (つまり、より良くなることO(N)) は難しいでしょう。ただし、ポリゴンが固定されていて、それに対して膨大な数のポイントをテストする場合は、四分木データ構造の事前計算を使用して解決を行うことを検討できます。四分木の事前計算にはコストがかかりますが、N が十分に大きい場合、ポイントのテストは安価になります。(平均O(log(1/epsilon))ではなく、おおよそ最悪の場合O(N)です。また、点が境界から離れているほど、答えは安くなります。)

しかし、私が言ったように、四分木は限られた状況でしか役に立ちません...

于 2012-11-27T03:39:50.487 に答える
1

ストロークパスを使用できます。BasicStrokeメソッドを持っています

public Shape createStrokedShape(Shape s)

したがって、太い線BasicStrokeを定義し、ストロークされた形状を取得し、ストロークShapeにポイントが含まれているかどうかを確認してください。

于 2012-11-27T06:39:22.003 に答える