連続したポリゴンを格納するための最善のデータ構造ですか？

Question

申し訳ありませんが、私はこの問題の言葉に多くの問題を抱えています。私は（任意の実際の世界地図のように）互いに隣接するポリゴンの配置を保存するために使用する必要があり、私はどのようなデータ構造（またはデータ構造の組み合わせ）にこだわっている

。

私は明確にすべき：私は何を意味することは、これらの多角形のマップ（ランドスケープ）を介して一定の速度で移動するポイントを持っています。風景全体がポリゴンで覆われています。スペースは分類されていません。マップの各点は多角形に属します。これは、すべてのポリゴンが、すべての辺で、別のポリゴンまたはマップの端の境界にあることを意味します。マップは限定されていますが、マップの大きさやポリゴンの数などは関係ありません。各ポリゴンには名前が付いています（これは、各ポイントが少なくとも2つの名前付きポリゴンに属するため、重要です）。マップ内を移動するポイントは、そのポリゴンの名前を常に知っている必要があります。また、あるポリゴンから別のポリゴンに境界線を横切るたびにポイントに通知する必要があります。 （他の説明が必要な場合は、ご意見ください）

これを行う方法はありますか？

--EDIT--

ポリゴンが固定されています。すべてのポイントとエッジを事前にハードコードする必要があります。ポイントとエッジは、決して予期せずまたはランダムに変更されることはありません（まったく変更されていない場合は、まれな固定イベントに応答します）。各2D間隔はポリゴンのバウンディングボックスと値型に対応する

Answer 1

ビルドa 2D segment treeポリゴン自体（そのエッジのリスト）に対応します。

エージェントがp1からp2に移動した後、セグメントツリーに対してwindow-queryを実行します.p1とp2で定義された矩形と交差するすべての2D間隔（境界ボックス）を検索します。

これらのバウンディングボックス内の各ポリゴンに対して、p2が含まれているかどうかを確認します。

Answer 2

これを説明する技術用語はplanar straight-line graphであり、適切な表現はdoubly connected edge list（DCEL）です。

データ構造の要件の1つは、（高速な）ポイントロケーションクエリを実行する可能性があるようです。 （この点はどのポリゴンに属していますか？）古典的な解決策がありますが、その中でtrapezoidal decompositionをお勧めします。

私はすなわち、（おそらく）線形軌道で交差点を見つけ、「国境」のクエリに適したソリューションを知りません。あなたはおそらくポイントの場所の問題から適応することができますが、これは難しいことを約束します。あなたのポリゴン頂点の合理的な数を持っている場合

はとにかく、順番にすべてのエッジを試みることによって与えられた直線との全ての交点を見つけるために大したことではありません。 DCEL表現を使用すると、ポリゴンを離れるときに、入力したポリゴンを知ることができます。

私はあなただったら、DCEL構造、point-in-polygonアルゴリズム、線 - 多角形交差アルゴリズム（本質的には同じもの）から始めます。