2

入力として、長方形のリストである任意の「フォーメーション」Fがあります。

形成

また、別の入力として、2D 点の順序付けられていないリストP :

入力

この例では、P がフォーメーション F に一致すると考えます。なぜなら、 Pを反時計回りに 45 度回転させると、Fの各長方形は点を含むことで満たされるからです。Pに四角形に収まらない余分な点があった場合も、一致と見なされます。

フォーメーションもポイント入力も特定の起点を持たず、2 つの縮尺が同じである必要はありません。たとえば、フォーメーションは 1 キロメートルの面積を表し、入力ポイントは 1 センチメートルの面積を表すことができます。 . そして最後に、どのポイントが編隊のどのノードに到達したかを知る必要があります。

これらの制約をすべて満たす汎用アルゴリズムを開発しようとしています。位置情報の大規模なデータベースに対して毎秒数百万回実行されるため、できるだけ早く「失敗」するようにしています。

両方の入力のすべてのポイント間の角度を取得してそれらを比較するか、船体を計算して比較することを検討しましたが、すべてのアプローチは制約の 1 つによってバラバラになるようです。

フォーメーションのポイントは、x、y の原点と許容範囲の半径を持つ円として簡単に表すこともできます。堅実な攻撃計画またはA-Ha! をいただければ幸いです。洞察。

4

2 に答える 2

2

今回は極座標を使用して、別の考えがありました。

説明が複雑/曖昧になってきていたので、うまくいけばアイデアを説明するコードがいくつかあります。

要点は、フォーメーション/ポイントセットの中心を原点として、極座標でフォーメーションとポイントを表現することです。これにより、ポイントとフォーメーション間の変換の回転およびスケーリング係数を見つけるのがはるかに簡単になります。並進成分は、ポイント セットとフォーメーション ゾーン セットの平均を比較することで簡単に見つかります。

このアプローチでは、フォーメーション ゾーンを正方形や円としてではなく、円セグメントのセクションとして扱うことに注意してください。うまくいけば、これはあなたが一緒に暮らすことができるファッジです.

また、有効なマッピング変換の正確なスケーリングおよび回転条件も返しません。フォーメーション ゾーンとポイント間のマッピング、および最終的な回転とスケーリング係数の適切な近似が得られます。この近似は、単純な緩和スキームを介して有効なソリューションに非常に迅速に洗練される可能性があります。また、無効なポイント セットをすぐに無視します。

于 2012-10-05T14:24:16.837 に答える
1

1 つのアプローチは、相対座標系でポイント セットとフォーメーションを表現することです。

各ポイント セットとフォーメーションについて:

  1. 最も相互に離れた点のペアを特定し、それらを A および B と呼びます
  2. A と B を通る線から最も遠い点を特定し、それを C とします。C が線 AB の左側にあることを確認します。これを行うには、A と B を交換する必要がある場合があります。
  3. 残りの点を A、B、C で表します。これは、各点について AB を通る直線上で最も近い点 D を見つけ、すべての距離が A と C の間の距離になるようにスケーリングするという単純な問題です。 B. A から D までの距離は相対的な x 座標であり、D からポイントまでの距離は y です。

たとえば、A と B が 10 単位離れており、C が AB の中点から 5 単位離れていることがわかった場合、相対座標は次のようになります: A: (0,0) B: (1,0) C : (0.5,0.5)

その後、グローバル座標系とは別に、ポイント セットとフォーメーションを比較できます。一致を見つけるための距離の許容誤差も、AB に関してスケーリングする必要があることに注意してください。

A、B、C の選択を明確に行うのが難しい、このアプローチの問題形成は容易に想像できますが、それは始まりです。

于 2012-10-04T08:28:11.360 に答える