問題タブ [geometry]

ポリゴンを三角形に分解するためのアルゴリズムまたはライブラリ（より良い）を探しています。Direct3Dアプリケーションでこれらの三角形を使用します。利用可能な最良のオプションは何ですか？

これが私がこれまでに見つけたものです：

1. ベンディスコーのメモ
2. FIST：ポリゴンの高速工業用強度三角形分割
3. CGALが三角測量を提供することは知っていますが、穴をサポートするかどうかはわかりません。

この分野での経験のある方からのご意見をいただければ幸いです。

編集：これは2Dポリゴンです。

これは、ここに投稿された質問の続き です。例として、ブール行列で重心を見つけることについて説明した2Dビットマップでの重心の検索。

ここで、行列を次の形式に展開するとします。

ご覧のとおり、4つの異なるクラスターに対して4つの重心があります。

重心が1つしかない場合、重心を見つける方法はすでにわかっています。この行列でそのアルゴリズムを実行すると、行列の中央にある点が得られますが、これは役に立ちません。

これらの質量のクラスターを見つけるための、優れた、正確で高速なアルゴリズムは何でしょうか？

指定された幅が与えられた場合、ポイントのパス内にある、たとえば約 5,00 から座標のセットを見つけるための最良のアプローチは何でしょうか。たとえば、いくつかのウェイポイントをたどる航空機。

ルートと同じ順序で並べ替える良い方法はありますか。

私は提案のリストを作成しようとしているので、計算速度は正確さよりも重要です。

私が見てきたことから、それは簡単ではなく、質問は少し広いと思いますが、次のような提案/ポインタは大歓迎です:

1. 緯度/経度を保存する、または球座標を使用する最良の方法
2. 座標セットに追加のクラスタリング情報を持つ
3. 範囲チェックを簡素化するために何らかの変換を使用できますか
4. ポイントを注文する最良の方法は何ですか

ここでは、パスに沿って等距離にあるいくつかの点で円形/正方形のチェックを行うよりも優れたアプローチがあります。

整数座標を持つ 2D の 2 つの二次ベジエが与えられた場合、それらの交点を見つける最良の方法は何ですか? また興味深いのは、交差しない場合の早期拒否です。簡単に言えば、x と y の両方で単調であると見なすことができます。入力曲線の整数への再分割によって表現できる交点のみが有効です。

自己交差しない 2 次元空間内の一連のポイントを想定すると、結果のポリゴンの面積を決定する効率的な方法は何ですか?

補足として、これは宿題ではなく、コードを探しているわけではありません。独自のメソッドを実装するために使用できる説明を探しています。ポイントのリストから一連の三角形を引き出すことについてのアイデアはありますが、凸面ポリゴンと凹面ポリゴンに関しては、おそらくキャッチできないエッジケースがたくさんあることを知っています。

点の集合s (x,y 座標の集合) と、点の集合lを結ぶ線分で構成されるパスが与えられたとき、 sから点のサブセットを見つけるために使用できる効率的なアルゴリズムを説明してください。パスlの指定された距離d内。

これの実用的なアプリケーションは、都市間のロードトリップ パスに沿った 10 マイル以内のレストランのリストを見つけることです。

たとえば、次の図では、緑色のポイントが検索結果に含まれます。

ソリューションは C# で優先されますが、SQL ベースのアプローチにはボーナス ポイントが与えられる可能性があります :-)

のマニュアルページからXFillPolygon：

• shapeがComplexの場合、パスは自己交差する可能性があります。パス内の隣接する一致点は、自己交差として扱われないことに注意してください。

• shapeが凸である場合、ポリゴン内のポイントのすべてのペアについて、それらを結ぶ線分はパスと交差しません。クライアントに認識されている場合は、Convexを指定するとパフォーマンスを向上させることができます。凸状ではないパスに凸状を指定すると、グラフィックスの結果は未定義になります。

• shapeが非凸の場合、パスは自己交差しませんが、形状は完全に凸ではありません。クライアントに認識されている場合、Complexの代わりにNonconvexを指定すると、パフォーマンスが向上する場合があります。自己交差パスに非凸を指定した場合、グラフィックスの結果は未定義です。

塗りつぶしでパフォーマンスの問題が発生してXFillPolygonいます。マニュアルページに示されているように、最初に実行したいステップは、ポリゴンの正しい形状を指定することです。私は現在、安全のためにComplexを使用しています。

ポリゴン（一連の座標で定義される）が凸型、非凸型、または複雑であるかどうかを判断するための効率的なアルゴリズムはありますか？

2D建設エリアジオメトリを操作するための最良のツール/ライブラリ（任意の言語）は何ですか？

つまり、多かれ少なかれ任意の2次元形状を処理し、和集合、共通部分、差、およびXORを提供するライブラリです。

私のベースラインはjava.awt.geom.Areaクラスであり、遅い場合はそれを使用できます。そこにあるより良いものは何ですか？私が特に興味を持っているのは、Java、ActionScript / Flex、およびCライブラリですが、どんな来場者にも門戸を開いています。

(center_x, center_y)centerと radiusを持つ円があるradius場合、座標を持つ特定の点が(x, y)円の内側にあるかどうかをどのようにテストしますか?