私は次の方法でデータ構造をしたい：球の表面上の近点を照会するための高速アルゴリズム/データ構造とは何ですか？
insert :: Point3D -> a -> SphereMap a -> SphereMap a
remove :: Point3D -> a -> SphereMap a -> SphereMap a
query :: Float -> Point3D -> SphereMap a -> [a]
insertとremoveはqueryは角度やポイントを受け取り、そして内にあるすべての値のリストを返し、データ構造に3Dインデックス値を追加原点（0,0,0）に対する点のその角度距離。
このような要件には、どのような種類のデータ構造が存在しますか？
通常の方法では、2dデータの場合はクワッドツリーを、3次元データの場合は8進法を使用します。クワッドツリーは、XとYのしきい値に基づいて、関心領域を4象限に分割します。各象限について、ゼロ点または1点が含まれている場合は終了し、そうでない場合は象限をサブ象限に細分して繰り返す。これにより、ツリーのジオメトリがネガティブなジオメトリを反映する点のツリーが表示されます。ツリーを走査するアルゴリズムを作成して、検索の半径と交差するすべての象限を見つけることができます。 Oct-treesは3次元で同じですが、X、Y、Zで分割します。 詳細はhttp://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374を参照してください。
クワッドツリーの仕組みを理解していますが、球の表面上の3D点をクォードツリー範囲の意味のある2D点にどのように変換すればよいのでしょうか？ – MaiaVictor
@Viclibオクトリーアプローチの場合、球を³3の単位球として埋め込み、そこでルックアップを実行します（挿入する任意の点のベクトルを正規化するだけです）。おそらく実際の_S²_マニホールドで作業するよりもエレガントではありませんが、これはうまくいくでしょう。もしあなたがそれを使うなら、私はquad/_k_-dツリーに頼っていません。理論的には極座標表現でquadtreeに及ぶことができますが、そのシステムの²²メトリックは球面上の自然なものに同意する。 – leftaroundabout
より簡単に言えば、あなたの最近傍が球の表面にあるはずであるという事実を無視することができます。どちらの点でも、通常の3次元空間内の最近傍点は自動的に球面上の最も近い点になります。したがって、オクトリー、kd-treeまたはR-Tree（R * Tree、...）を使うことができます。たくさんのデータ（10e5点以上）や頻繁な更新がある場合は、PH-Tree（クワッドツリーの 'trie'変形）を提案します。 – TilmannZ
したがって、原点は常に同じですか？ – Bergi
私の 'manifolds'パッケージの[' ShadeTree']（http://hackage.haskell.org/package/manifolds-0.2.2.0/docs/Data-Manifold-TreeCover.html#g:6）の構造は、まさにこの種の仕事。しかし、実際には[球面の種類]（http://hackage.haskell.org/package/manifolds-0.2.2.0/docs/Data-Manifold-Types.html）の点を使って3D点で作業することはありません#t：S-178-）。これは私が「ShadeTree」で正直にはまだテストしていませんが、実際のベクトル空間と同じように球でも同様に動作します。 – leftaroundabout
実際には、 'SphereMap'は、' 'PointsWeb'（http://hackage.haskell.org/package/manifolds-0.2.2.0/docs/Data-Manifold-Web.html）で表現され、' ShadeTree 'を基本的な空間ルックアップ構造として使用しますが、距離内ルックアップを実行するために使用できる追加のトポロジ情報があります。 - **これらのタイプの**どちらも 'insert'と' remove'をサポートしていません。ビルドワンスはそのままです。ポイントを変更する唯一の方法は、構造を分解してゼロから構築することです（ツリーノードは重心に基づいているため、リーフを移動すると構造全体が変化します）。 – leftaroundabout