4

この形式で指定された長方形内に点があるかどうかを確認する最も速い方法は何ですか。長方形の反対側
の中心である2つの点と、それらの辺の高さである数値があります。これが明確であることを願っています。 長方形は（おそらく）軸と整列していません。このデータを前提として、四隅の計算、回転など、より高速なアルゴリズムがあるのではないかと思います。

私が考えたが、実装方法がわからない（数学に問題がある）アイデアは、点から2つの中心の間をトレースする線までの距離を見つけることでした。それが、辺の長さの半分未満の場合は、長方形と線上にある場合、それは長方形の中にあります。これをもっとよく説明する方法がわかりません。

たぶん、写真は説明に役立つでしょう：説明
A、B、C、およびサイドA/Bの長さが示されています。基本的に、CDが辺Aの半分未満でDがABにある場合、点は長方形の中にあると思いました。しかし、どうすればこれを行うことができますか？
別の考え： Dを見つけてAB上にあるかどうかを確認する代わりに、角度ABCとBACが鋭角であるかどうかを確認しますが、これを行う方法はまだわかりません。

4

5 に答える 5

3

次の方法は非常に簡単ですが、1つのベクトルの長さを見つける必要があります（複数のチェックのためにキャッシュできます）

  1. 計算ベクトルAB=B-A

  2. ABの長さの計算-長方形の幅になります

  3. AB_length <TOLERANCE（許容値が小さい値、たとえばTOLERANCE = 0.00000001）の場合、長方形の幅はゼロであるため、ポイントは長方形内に配置できません。

  4. ABを正規化する：AB_normalized = AB / AB_length

  5. 軸投影を計算する

    Calc ABプロジェクション：

    AB_proj =内積（AB_normalized、C-A）

    Calc AB正射影（写真では「CD」と表示）：

    AB_orthogonal =（-AB.y、AB.x）

    AB_orthogonal_proj =内積（AB_orthogonal、C-A）

  6. （0 <= AB_proj <= AB_length）および（ABS（AB_orthogonal_proj）<= AB_height / 2）の 場合、ポイントは長方形内にあり、それ以外の場合はありません。

于 2011-06-02T12:19:02.567 に答える
2

ドット積は、このような問題に対する信頼できる友人です。それと少しのピタゴラスはあなたが2つの質問に答えるために必要なすべてをあなたに与えるはずです：

  1. ACのABへの投影はAB内ですか？
  2. |DC|です <高さ/2？

平方根を実行するのではなく、正方形の距離で作業し、角度を計算する必要はありません。

于 2011-06-02T08:18:04.297 に答える
1

鋭角三角形のアイデアはABC機能しません。たとえば、ポイントCがラインABのすぐ横にある場合、角度はCほぼ180°になります。一方、B長方形の高さがかなり小さい場合、での角度は非常に小さい可能性がありますが、長方形のC外側にあります。

それにもかかわらず、他のアプローチはこれを実装するための1つの基本的な方法です。

ポイントDはとを通る線のどこかにAありB、したがって

D = A + t * (B-A)

（大文字はスペース内のベクトルを表し、小文字は数字を表します）。同時に、からの接続はDへの接続にC垂直であり、したがってAB

(C-D) . (B-A) == 0

つまり、2つの差分ベクトルの内積はゼロです。両方を組み合わせると、

(C-A-t*(B-A)) . (B-A) = (C-A) . (B-A) - t * (B-A) . (B-A) == 0

または解決されたときt：

t = (C-A).(B-A) / (B-A).(B-A)

（つまり、AC線へのベクトルの射影の相対的な長さAB）。

の場合、点Dは長方形内にある0 <= t <= 1ため、これが最初の条件です。

その後、toの距離を計算Cし（最初のeqnにD挿入して取得するだけです）、これをと比較できます。つまり、最後の条件は次のようになります。tDh/2

(C-D).(C-D) <= (h/2)^2
于 2011-06-02T08:49:42.877 に答える
1

最速かどうかは完全にはわかりませんが、これでうまくいく可能性があります。

Dを2つの中心の間に半分配置するのではなく、AB軸に沿ってCをDとして投影します。次に、a）DがAとBの間にあり、b）CDが長方形の高さの半分以下であることを確認します。

角度を使用するというあなたの考えを再確認してください...ピタゴラスやアルカシの定理を使用することは実際には理にかなっているかもしれません：

http://en.wikipedia.org/wiki/Law_of_cosines

ABC急性とBAC急性の両方が前提条件であり、それらを指定すると、同じアルファ/ベータで長方形にC2を配置します（wikiページを参照）。そこから、ガンマ（pi / 2、長方形上にあるため）とベータ/アルファ（pi / 2-ベータ）もわかります。これにより、[A,C]または[B,C]距離がまたはの距離以下[A,C2]かどうか疑問になり[B,C2]ます。

于 2011-06-02T07:50:56.937 に答える
0

正方形は4つの半空間の交点です。各半空間は、2点線の式を使用して長方形の1つの辺から導出されます。問題の詳細によっては、並べて確認することもできますが、各ステップで簡単に拒否することもできます。

これは投影よりも速いですか？それは、最初のステップの後で簡単に拒否する確率に依存すると思います。

于 2011-06-02T08:17:53.440 に答える