問題タブ [qhull]

緯度/経度のいくつかのペアでボロノイ図を作成したいのですが、(不正確な) ピタゴラス距離ではなく、それらの間の大円距離を使用したいと考えています。

qhull/qvoronoi または他の Linux プログラムでこれを行うことはできますか?

点を 3D にマッピングし、qvoronoi で 3D ボロノイ図 [1] を作成し、その結果を単位球と交差させることを検討しましたが、簡単ではありません。

[1] 2 つの緯度/経度 (「地球を通過する」パス) 間の 3D 距離は大圏距離と同じではないことは認識していますが、この変換が相対距離を維持することを証明するのは簡単です。ボロノイ図の場合。

平面のボロノイ テッセレーションには、常に境界のないポリゴン (無限の領域) があります。

元の点の凸包、または明示的に指定した多角形 (おそらく長方形) とテッセレーションを交差させるように qhull/qvoronoi に指示するにはどうすればよいですか。

具体例 ( https://github.com/barrycarter/bcapps/blob/master/bc-temperature-voronoi.pl ):

• 緯度/経度を (不正確に) 2 次元の四角形 (-180,180)*(-90,90) にマッピングし、その結果に qvoronoi を適用します。

• 境界のないポリゴンを扱うことができず、Google Maps API は (-180,180) (-90,90) の外をさまよっているポリゴンを嫌います[実際には、(-180,180) (-85,85) に似ています。なぜなら、Google はメルカトルを使用しているからです]

• qhull/qvoronoi をポイントの凸包および/または (-180,180)*(-90,90) 長方形でポリゴンと交差させることはできますか? もちろん、凸包は長方形の中に完全に含まれています。

• そうでない場合、別のプログラムで実行できますか? 私はこれを自分で書くことができると思いますが、既存のソリューションを好むでしょう。

xyz座標を使用した3Dのポイントのセットがあります。これらの点の凸包を計算したいと思います。私は利用可能なアルゴリズムを試しましたが、Perlではできませんでした。Perl Math：ConvextHullモジュールもチェックしましたが、これらの3Dポイントを入力として与える方法がわかりませんでした。私を助けてください。

3D で平面 (平行四辺形) のボロノイ図を計算できるコード/ライブラリはありますか? Qhullをチェックしたところ、ポイントでしか機能しないようです。その例では、Voro ++はさまざまなサイズの球で機能しますが、ポリゴンについては何も見つかりませんでした。

この画像(3D のサンプル平面) では、平行四辺形は厚みがあるため 3D ですが、この場合、厚みはゼロになります。

scipy で griddata 関数を使用して、3 次元および 4 次元のデータを補間しています。チャンピオンのように機能しますが、必要なポイントの一部が入力データの範囲外であるため、多数の NaN が返される点が異なります。とにかく、Nd データは「線形」モードの補間でのみ機能するため、NaN を返すだけでなく、griddata に外挿を実行させるのは簡単です。誰かがこれを実行したか、回避策を見つけましたか? 明確にするために: 非構造化データがあるため、通常のグリッドを必要とする機能を使用できません。ありがとう！アレックス

私の目標は、Qhull の qvoronoi サブルーチンの出力から個々の 3D ボロノイ セル (頂点とエッジの両方) を取得することです。ただし、ボロノイ リッジ (出力 'Fv') を理解するのに苦労しています。出力のサンプル行は次のとおりです。

最初の数字は線の頂点の数、次の 2 つは稜線で区切られた頂点のインデックス、残りの数字は稜線上の頂点のインデックスです。単純に隣接する頂点 ( 、 、 など) を接続4->5し5->3て 3->1みましたが、それが正しいかどうかはわかりませんでしたが、機能しているように見えました。ポイントはどのように相互に接続されますか?

さらに、qvoronoi の出力 (オプション 'FN') から、各領域の頂点を取得できますが、頂点間の接続に関する情報はありません。この情報はどこにあるのか気になります。ridges 出力にありますか、それとも別の qvoronoi 出力オプションにありますか?

Qhull を使用して、どのボロノイ セル (インデックスによる) が「適切な」(「既存の頂点」で構成されている) かを判断する方法

Lloyds アルゴリズムと scipy.spatial Voronoi (Qhull のラッパー) によって生成された入力を使用して、制約付き緩和を実行しようとしています。

コード的には次のようになります。

コードによって生成された出力グラフは問題ないように見えますが (以下を参照)、vor 構造体のデータはロイズ緩和を実行するのに十分ではありません。これは、有効なボロノイ セル (画像の #4) 内にあるポイントのみを移動する必要があるためです。もう一方はそのままにしておく必要があります。Qhull はポイント/リージョンの順序を乱すため、どのリージョンがどのポイントに属しているかを推定できません。

問題の図を次に示します。

これで、vor.regions[7] がポイント vor.points[4] に属する領域であることがわかります。これを達成する方法は？