問題タブ [computational-geometry]

3D ポイントクラウドで回転軸を自動検出しようとしています。

つまり、小さな 3D ポイントクラウドを取得し、単一の回転軸を選択して、異なる回転角度でポイントのコピーをいくつか作成すると、より大きなポイントクラウドが得られます。

私のアルゴリズムへの入力はより大きな点群であり、目的の出力は単一の対称軸です。そして最終的には、互いの回転であるポイント間の対応を計算します。

大きな点群のサイズは 100K ポイントのオーダーで、作成される回転コピーの数は不明です。

私の場合、回転角度には一定のデルタがありますが、必ずしも 360 度に及ぶとは限りません。たとえば、私は 0、20、40、60 を持っているかもしれません。または、0、90、180、270 を持っているかもしれません。それを検出します）。

これはコンピューター ビジョンの問題のようですが、軸を正確に見つける方法がわかりません。通常、入力は非常にクリーンで、フロートの精度に近くなります。

大きなポイントクラウドを作成するために回転/コピーされた元の小さなポイントクラウドはありません。私は、データがほとんどノイズのない合成データであることを知っています (通常、別のプログラムの出力です)。

残念ながら、軸に沿って点が重複していないため、小さな雲で可能な点の数を簡単に計算することはできません。どの点が軸に沿っているかがわかっていれば、考えられる要因を考え出すことができますが、その場合、問題はすでに解決されています。

--

皆さんの提案に感謝します。私の最終的なアルゴリズムは、k-nn メトリックを使用して一致するポイントのクリークを考え出そうとしているようです。各クリークは軸を与えます。次に、RANSAC を使用して、軸をすべてのクリークの結果に適合させることができます。

産業界では、布地、木材、金属など、材料の最も効率的な使用法を計算する必要があるという問題がよくあります。したがって、出発点は、ポリゴンおよび/または曲線で作成された、指定された寸法の形状の X 量です。ラインであり、ターゲットは指定された次元の別のポリゴンです。

現在の CAM スイートの多くがこれを実装していると思いますが、それらやその内部を使用した経験がないので、スペースの最も効率的な使用法を見つけるためにどのような種類の計算アルゴリズムが使用されているのでしょうか? このトピックについて説明している本やその他の参考文献を教えてもらえますか?

うまくいけば、次の問題で私を助けることができる計算幾何学の人々がここにいます-

私が3空間で自由に動くボールを取り、その周りに通行不能な座標のセットSc（つまり、拡散するボールの一部が重ならない3空間のポイント）を定義することによって「ケージ」を作成することを想像してください。これらの点は、V（ケージ）>> V（ボール）である、より大きな球のボリュームV（ケージ）内にあります。

通行不能な座標のセットScが提供された場合、ボールがケージから逃げることができるかどうかを判断するための計算効率の高い、および/または優れた方法はありますか？

MathOverflowの以前の投稿をご覧ください-https ://mathoverflow.net/questions/21911/when-can-a-freely-moving-sphere-escape-from-a-cage-defined-by-a-set-of- impassib

線分、光線などを含む画像があります。ブレゼンハム アルゴリズムを使用してこれらの線分を表しています(このアルゴリズムを使用して 2 点間で取得した座標を意味します)。今、私は2つの線分の交点を見つけたり、あるベクトルを他のベクトルに投影したりするなどの操作をしたいと思っています...問題は、連続空間で作業していないことです。Bresenham アルゴリズムを使用して線分を近似しています。

それで、これを行うための最良かつ最も効率的な方法について提案が欲しいですか? C++ ライブラリまたは実装へのリンクでも十分です。また、そのような問題を扱っている本をいくつか教えてください。

私のアプリケーションは、地球の表面 (球体を使用すれば十分です) の形状を表すことです。それらは、ポイント、ライン、およびポリゴンです。座標は、(地理座標と同様に) 度またはラジアンを使用して定義する必要があります。

球面上の 2 点間の線分は、その大円上にある必要があります。ポリゴンは、そのような線のコレクションで構成されている必要があります。さらに、上記の形状に対して、交差、結合、差、補数などのセット - 基本操作を実行したいと思います。これらの操作は、ポイントのコレクションを出力するだけで済みます。

CGAL の3D Spherical Geometry Kernelと2D Boolean Operations on Nef Polygons Embedded on the Sphereを使用して、それを理解しようとしました。実は、球体に線を引くのにはすでに問題がありました。さらに、CGAL はユークリッド空間で動作しますが、球体上に配置された大円を操作するために必要な幾何学的操作が残っています。

私の質問は、CGAL に記載されている機能を実現するのを手伝ってくれるか、それを行う C/C++ 用の別のライブラリを推奨できるかどうかです。どうもありがとうございました！

三角形を形成する 2D の点のセットが与えられる小さなコンテストの問題があります。この三角形は、任意の回転、任意の並進 (両方とも 2D 平面内) の影響を受ける可能性があり、ミラーでの反射の影響を受ける可能性がありますが、その寸法は変更されていません。次に、それらは平面内の一連の点を与えてくれます。これらの幾何学的操作を 1 つ以上実行した後、三角形を形成する 3 つの点を見つける必要があります。

例：

既知のアルゴリズムを適用することになっているに違いありませんが、どれかはわかりません。最も一般的なものは、凸包、スイープ平面、三角形分割などです。

誰かがヒントを与えることができますか？コードは必要ありません。プッシュのみでお願いします。

私は次のようなアルゴリズムを探しています：

重なり合う可能性のある長方形のセット（すべて「回転されていない」、（左、上、右、下）の連符などとして均一に表すことができる）が与えられると、（回転されていない）最小のセットが返されます。同じ領域を占める重複しない長方形。

一見簡単そうに見えますが、注意が必要です（少なくとも効率的に実行するため）。

この/アイデア/ポインタの既知の方法はありますか？

必ずしも最小ではないが、ヒューリスティックに小さいセットのメソッドも興味深いので、有効な出力セットを生成するメソッドも興味深いものです。

Point1 と Point2 の 2 つの点があるとします。これらのポイントは常に異なる位置にある可能性があり、必ずしも静的であるとは限りません。

Point1 は時間 t のある位置にあり、その位置は時間 t での x 座標と y 座標を与える連続関数 x1(t) と y1(t) によって定義されます。これらの関数は微分可能ではなく、線分から区分的に構築されます。

Point2 は同じで、x2(t) と y2(t) があり、各関数は同じプロパティを持ちます。

可視性を妨げる可能性のある障害物は、単純な (そして動かない) ポリゴンです。

可視性の境界点を見つけるにはどうすればよいですか?

つまり、点が見えるようになる場所と見えなくなる場所の 2 種類の境界があります。

可視化境界 i の場合、いくつかの ϵ>0 が存在し、任意の実数 a, a ∈ (i-ϵ, i) に対して、Point1 と Point2 が表示されません (つまり、接続する線分がいくつかの障害物(x1(a), y1(a))を横切ります) (x2(a), y2(x))）。

b ∈ (i, i+ϵ) の場合、それらは可視です。

そして、見えなくなるのはその逆です。

しかし、そのような正確な境界を見つけることはできますか?もしそうなら、どのように?

線分を形成するx1、y1とx2、y2があります。写真のように最初の線に平行な別の線x3、y3-x4、y4を取得するにはどうすればよいですか。x1とx2にnを追加するだけで平行線を得ることができますが、それは私が望んでいたことではありません。写真の線を平行にしたいと思います。

平面上で「N」個の円盤/円の交点/和集合を見つける問題は、1978年の論文でMIShamosによって最初に提案されました。

シャモス、ミシガン州「計算幾何学」博士号 論文、イェール大学、ニューヘブン、コネチカット州1978年。

それ以来、1985年に、Micha Sharirは、ディスク交差/和集合問題（修正ボロノイ図に基づく）のO（n log2n）時間およびO（n）空間決定論的アルゴリズムを提示しました。平面ディスクのセット。SIAM.J計算。14（1985）、pp.448-468。

1988年、Franz Aurenhammerは、パワーダイアグラム（ボロノイダイアグラムの一般化）を使用した円の交差/和集合のためのより効率的なO（n log n）時間とO（n）空間アルゴリズムを発表しました：Aurenhammer、F.パワーを使用したディスクとボールのアルゴリズムの改善ダイアグラム。Journal of Algorithms 9（1985）、pp.151-161。

1983年の初めに、Paul G. Spirakisは、O（n ^ 2）時間決定論的アルゴリズム、およびO（n）確率的アルゴリズムも発表しました。担当者98、部門計算。Sci。、Courant Institute、ニューヨーク大学、1983年。

計算幾何学パッケージに焦点を当てて、上記のアルゴリズムの実装を探していましたが、まだ何も見つかりませんでした。どちらも実践するのは簡単ではないように思われるので、誰かが私を正しい方向に向けることができれば、それは本当に素晴らしいことです！

おそらく、Constructive Solid Geometry（CSG）パッケージには、円プリミティブをオーバーラップさせるための表面積機能がありますか？