二次元上にある点群を読み込み、ドロネー三角形を作成したいのですが、紙の上で絵を描いて考えるのと、プログラム上で考えるのとではまったく違うことに気づき、初っ端から手が止まっています。
点群を入れる大きな三角形は作成しました。
struct coo // 座標の構造体
{
float x;
float y;
}
struct tri // 頂点を入れる構造体
{
struct coo top[3];
}
main (){
float **prj; // ここに点群がある
float M_prj[3][2]; // 点群を入れる大きな三角形の3つの頂点
int Q; // 読み込んだ頂点が他の三角形の外接円の中に含まれているか判断する
struct tri triangle[100]; // 三角形をを入れる構造体
// まず、大きな三角形を三角形の配列(triangle)に入れる
for(i=0; i<3; i++){
triangle[0].top[i].x = M_prj[i][0];
triangle[0].top[i].y = M_prj[i][1];
}
// 外接円の中に点Pを含むものを探す
Q = hantei;
// 含むなら分割する
if(Q > 0){
}
}
というように続いていくと思うのですが。。。
ドロネー三角形については理解しているつもりですが、プログラムになると全くです。そして、プログラミングは初心者です。
ここから先、どのように考えていけばよいでしょうか。
A 回答 (1件)
- 最新から表示
- 回答順に表示
No.1
- 回答日時:
ドロネー図、ボロノイ図について、
効率の良いアルゴリズムがどんなものだったか、
参考書を参照しないと思い出せないので、
参考意見にもならないかもしれませんが、書くだけ書きます。
まず、「hantei」とある関数はかけているのでしょうか?
各三角形の外接円の中心および半径を求めることが出来れば良いので、
垂直二等分線の式を2つ求めて、交点を計算すれば中心が求まるという感じでしょうか。
これは簡単な方程式で行けそうだな、と思いました。
「分割する」というのは、点が3角形に含まれる場合と
外接円には含まれるけれど3角形には含まれない、
という場合とで、難しさが違う様な気がしますが、
とりあえず3本線をつないで、
辺が交差してしまったら交差した辺を消せば良さそう気がするので、
何とかなるのかな、と思います。
後は、考えているアルゴリズムが正しくドロネー図を計算出来るのか、
言い替えると、3角形を分割することによって、外接円の形が変わって、
分割が連鎖する、と言った状況について、考えられているのか、
というのが気になります。
知識がないので、要らない心配だったらごめんなさい。
読むのは大変かもしれませんが、
http://www2s.biglobe.ne.jp/~kaz_h/Tech/engineer. …
http://www.simplex.t.u-tokyo.ac.jp/~sugihara/ope …
のソースは参考になるのではないのでしょうか
また、有名なアルゴリズムだと思うので、本屋でアルゴリズム辞典的なものを探すのも良いように思います
ごめんなさい。返信遅くなりました。
回答ありがとうございます。
hanteiの関数は行列式の関数でかけています。
私は座標での計算が必要だと思ったのですが、そうではなくて、点と点の番号でリスト構造でプログラムしていくと良いみたいです。それでも?がいっぱいなのですが。。。
結ぶというよりは、点3つを1つの箱に入れる、といった感じです。
その点の出し入れで、メッシュ/ポリゴンができます。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 場合の数、確率 29 導入問題 ( 円周上の鋭角三角形) 4 2023/07/06 18:00
- 数学 問題文 正n角形がある(nは3以上の整数)。この正n角形のn個の頂点のうちの3個を頂点とする三角形に 4 2023/03/22 14:57
- 数学 角度当てクイズVol.225の解き方おしえてください 1 2023/06/23 17:45
- 高校 数学Aの問題で、円に内接するN角形(N>4)の対角線の総数は ア 本である。また、Fの頂点三つからで 1 2023/04/13 17:47
- 数学 三角形の3つの頂点から出る3本の直線が1点で交わる条件で 「少なくとも1本の直線は、角の二等分線であ 2 2023/02/21 21:24
- 数学 点Oを中心とし、半径が5である円Oがある。この円周上に2点A、B をAB=6となるようにとる。また、 5 2023/08/16 23:32
- 数学 中3 円周角の定理の問題です 3 2022/06/29 22:21
- 数学 場合の数、確率 28 円周上の鋭角三角形 6 2023/07/06 08:51
- 数学 三角形ABCの辺BCを4 : 3に内分する点をTとし、点Tを接点として辺BCに接する円が点Aで直線A 3 2023/02/12 21:03
- 数学 数学 三角形の3つの頂点から出る3本の直線が1点で交わる この場合3本の線は「角の二等分線」以外あり 2 2023/02/21 21:01
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
正しい五十音順について
-
Stuck
-
Dijkstraて
-
[ EXCEL VBA ] 図形を読み込む...
-
プログラミングの才能のある無...
-
Fotranで最小公倍数
-
アルゴリズムの将来性について
-
多変数関数の最小値を求めるプ...
-
よくプログラミングをやるにあ...
-
アルゴリズムのB木について
-
確率論的な麻雀の勝ち方を教え...
-
5人のテストの点数を入力すると...
-
【VisualBasic】ユークリッドの...
-
OpenCVのライセンスについて
-
バケット法による文字列ソート
-
ガウス・ジョルダン法のプログ...
-
アルゴリズムとプロトコールの違い
-
A*アルゴリズム
-
迷路プログラム
-
C++行列計算プログラム
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正しい五十音順について
-
Dijkstraて
-
Stuck
-
[ EXCEL VBA ] 図形を読み込む...
-
BCDについて
-
アルゴリズムとプロトコールの違い
-
期間重複チェックがわかりません
-
グループを均等に分けるには?...
-
三次元形状曲面の導出法
-
あいまい検索(文字列一致率)
-
Visual studio2019 C#で生まれ...
-
gooという検索エンジンの後にGo...
-
フリーセルの難易度について
-
CRC-CCITT16の算出法
-
経路探索について
-
C♯で電卓を作成しています。演...
-
理系の高校生です。大学で情報...
-
OpenCVのライセンスについて
-
偏りのある乱数のアルゴリズム
-
詰め将棋をとくのは、アルゴリ...
おすすめ情報