[C]点がどの三角形内に居るか判断したいです

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら
閉鎖
よろしくお願いいたします。

[C]点がどの三角形内に居るか判断したいです

#1

投稿記事 by よろしくお願いいたします。 » 8年前

青点がどの三角形の中にいるか判断するプログラムを作っています。
この状態では、うまくいくのですが、particle のパラメータを変えると　iti　にうまく sankaku の値が代入されません。

なげっぱで申し訳ないのですが、どのようにすればよいかアドバイスいただけませんか？

画像

コード: 

#include <stdio.h>
#define N 0

struct point {
	double zahyou[2];
	double sokudo[2];
};

struct tri {
	struct point ten[3];
};



int main(void)
{
	struct point particle[4]={
	{{0.0,0.8},{0.0,0.0}},
	{{0.0,0.6},{0.0,0.0}},
	{{0.0,0.4},{0.0,0.0}},
	{{0.0,0.2},{0.0,0.0}}
	};
	
	struct point tyouten[15]={
	{{0.0,1.0},{1.0,1.0}},
	{{0.0,0.5},{1.0,0.0}},
	{{0.0,0.0},{1.0,-1.0}},
	
	{{0.5,1.0},{1.0,0.5}},
	{{0.5,0.5},{1.0,-0.5}},
	{{0.5,0.0},{1.0,-1.0}},
	
	{{1.0,1.0},{1.0,0.0}},
	{{1.0,0.5},{1.0,-1.0}},
	{{1.0,0.0},{1.0,-0.5}},
	
	{{1.5,1.0},{1.0,-0.5}},
	{{1.5,0.5},{1.0,-0.5}},
	{{1.5,1.0},{1.0,0.0}},
	
	{{2.0,1.0},{1.0,-1.0}},
	{{2.0,0.5},{1.0,0.0}},
	{{2.0,0.0},{1.0,0.5}},
	};
	
	struct tri sankaku[16];
	
	sankaku[0].ten[0]=tyouten[0];
	sankaku[0].ten[1]=tyouten[1];
	sankaku[0].ten[2]=tyouten[4];
	
	sankaku[1].ten[0]=tyouten[0];
	sankaku[1].ten[1]=tyouten[3];
	sankaku[1].ten[2]=tyouten[4];
	
	sankaku[2].ten[0]=tyouten[1];
	sankaku[2].ten[1]=tyouten[2];
	sankaku[2].ten[2]=tyouten[5];
	
	sankaku[3].ten[0]=tyouten[1];
	sankaku[3].ten[1]=tyouten[4];
	sankaku[3].ten[2]=tyouten[5];
	
	sankaku[4].ten[0]=tyouten[3];
	sankaku[4].ten[1]=tyouten[4];
	sankaku[4].ten[2]=tyouten[7];
	
	sankaku[5].ten[0]=tyouten[3];
	sankaku[5].ten[1]=tyouten[6];
	sankaku[5].ten[2]=tyouten[7];
	
	sankaku[6].ten[0]=tyouten[4];
	sankaku[6].ten[1]=tyouten[5];
	sankaku[6].ten[2]=tyouten[8];
	
	sankaku[7].ten[0]=tyouten[4];
	sankaku[7].ten[1]=tyouten[7];
	sankaku[7].ten[2]=tyouten[8];
	
	sankaku[8].ten[0]=tyouten[6];
	sankaku[8].ten[1]=tyouten[7];
	sankaku[8].ten[2]=tyouten[10];
	
	sankaku[9].ten[0]=tyouten[6];
	sankaku[9].ten[1]=tyouten[9];
	sankaku[9].ten[2]=tyouten[10];
	
	sankaku[10].ten[0]=tyouten[7];
	sankaku[10].ten[1]=tyouten[8];
	sankaku[10].ten[2]=tyouten[11];
	
	sankaku[11].ten[0]=tyouten[7];
	sankaku[11].ten[1]=tyouten[10];
	sankaku[11].ten[2]=tyouten[11];
	
	sankaku[12].ten[0]=tyouten[9];
	sankaku[12].ten[1]=tyouten[10];
	sankaku[12].ten[2]=tyouten[13];
	
	sankaku[13].ten[0]=tyouten[9];
	sankaku[13].ten[1]=tyouten[12];
	sankaku[13].ten[2]=tyouten[13];
	
	sankaku[14].ten[0]=tyouten[10];
	sankaku[14].ten[1]=tyouten[11];
	sankaku[14].ten[2]=tyouten[14];
	
	sankaku[15].ten[0]=tyouten[10];
	sankaku[15].ten[1]=tyouten[13];
	sankaku[15].ten[2]=tyouten[14];
	
	struct tri iti;	
	double dT = 0.1;
	
	printf("%f\n%f\n\n",particle[N].zahyou[0],particle[N].zahyou[1]);
	
	
	while(1){
		if(particle[N].zahyou[0]<=0.5 && particle[N].zahyou[1]<=1.0 && particle[N].zahyou[1]>=0.5 )
			if((1.0-particle[N].zahyou[0])>= particle[N].zahyou[1])
				iti = sankaku[0];
			else if((1.0-particle[N].zahyou[0]) < particle[N].zahyou[1])
				iti = sankaku[1];
	
		else if(particle[N].zahyou[0]<=0.5 && particle[N].zahyou[1]<= 0.5 && particle[N].zahyou[1]>=0 )
			if((0.5-particle[N].zahyou[0]) > particle[N].zahyou[1])
				iti = sankaku[2];
			else if((0.5-particle[N].zahyou[0]) < particle[N].zahyou[1])
				iti = sankaku[3];
		
		else if(particle[N].zahyou[0]<=1.0 && particle[N].zahyou[1]<=1.0 && particle[N].zahyou[1]>=0.5 )
			if((1.5-particle[N].zahyou[0])>= particle[N].zahyou[1])
				iti = sankaku[4];
			else if((1.5-particle[N].zahyou[0]) < particle[N].zahyou[1])
				iti = sankaku[5];
		
		else if(particle[N].zahyou[0]<=1.0 && particle[N].zahyou[1]< 0.5 && particle[N].zahyou[1]>=0 )
			if((1.0-particle[N].zahyou[0])>= particle[N].zahyou[1])
				iti = sankaku[6];
			else if((1.0-particle[N].zahyou[0]) < particle[N].zahyou[1])
				iti = sankaku[7];
		
		else if(particle[N].zahyou[0]<=1.5 && particle[N].zahyou[1]<=1.0 && particle[N].zahyou[1]>=0.5 )
			if((2.0-particle[N].zahyou[0])>= particle[N].zahyou[1])
				iti = sankaku[8];
			else if((2.0-particle[N].zahyou[0]) < particle[N].zahyou[1])
				iti = sankaku[9];
	
		else if(particle[N].zahyou[0]<=1.5 && particle[N].zahyou[1]< 0.5 && particle[N].zahyou[1]>=0 )
			if((1.5-particle[N].zahyou[0])>= particle[N].zahyou[1])
				iti = sankaku[10];
			else if((1.5-particle[N].zahyou[0]) < particle[N].zahyou[1])
				iti = sankaku[11];
				
		else if(particle[N].zahyou[0]<=2.0 && particle[N].zahyou[1]<=1.0 && particle[N].zahyou[1]>=0.5 )
			if((2.5-particle[N].zahyou[0])>= particle[N].zahyou[1])
				iti = sankaku[12];
			else if((2.5-particle[N].zahyou[0]) < particle[N].zahyou[1])
				iti = sankaku[13];
	
		else if(particle[N].zahyou[0]<=2.0 && particle[N].zahyou[1]< 0.5 && particle[N].zahyou[1]>=0 )
			if((2.0-particle[N].zahyou[0])>= particle[N].zahyou[1])
				iti = sankaku[14];
			else if((2.0-particle[N].zahyou[0]) < particle[N].zahyou[1])
				iti = sankaku[15];
		
		else break;
		
		printf("%f\n%f\n%f\n%f\n\n",iti.ten[0].zahyou[0],iti.ten[0].zahyou[1],iti.ten[0].sokudo[0],iti.ten[0].sokudo[1]);
		printf("%f\n%f\n%f\n%f\n\n",iti.ten[1].zahyou[0],iti.ten[1].zahyou[1],iti.ten[1].sokudo[0],iti.ten[1].sokudo[1]);
		printf("%f\n%f\n%f\n%f\n\n",iti.ten[2].zahyou[0],iti.ten[2].zahyou[1],iti.ten[2].sokudo[0],iti.ten[2].sokudo[1]);
		break;
	}
		




				
	printf("%f",iti.ten[1].zahyou[1]);
		
	
	
	return 0;
}
ページトップ
アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:
みけCAT に連絡する

Re: [C]点がどの三角形内に居るか判断したいです

#2

投稿記事 by みけCAT » 8年前

残念ながらよろしくお願いいたします。さんのコードは理解しにくそうですが、
2次元平面上で点が三角形の中(周を含む)にあるかは、三角形のある頂点(基準頂点とする)から別の2頂点への2本のベクトルの線形結合で基準頂点から判定したい点のベクトルを表した時、
2本のベクトルの係数がそれぞれ0以上、かつ2本のベクトルの係数の和が1以下であるかどうかで判定できます。
コードにするとこんな感じだと思います。(テストはしていません)

コード: 

#define EPS 1e-9

/* 点(px, py)が点(tx[0], ty[0]), (tx[1], ty[1]), (tx[2], ty[2])を頂点とする三角形の周または内部にあるかを判定する */
int in_triangle(const double tx[3], const double ty[3], double px, double py) {
	/* 連立方程式a*s + b*t = e, c*s + d*t = fの係数 */
	double a = tx[1] - tx[0];
	double b = tx[2] - tx[0];
	double e = px - tx[0];
	double c = ty[1] - ty[0];
	double d = ty[2] - ty[0];
	double f = py - ty[0];
	/* 連立方程式を解く */
	double det = a * d - b * c; /* 行列式 */
	/* (a b ; c d)の逆行列は、行列式をdetとして(1/det) * (d -b ; -c a) */
	double s = (d * e - b * f) / det;
	double t = (-c * e + a * f) / det;
	/* s >= 0 && t >= 0 && s + t <= 1 */
	return s + EPS > 0 && t + EPS > 0 && s + t < 1.0 + EPS;
}
オフトピック
その場限りの名前を用いての投稿は、フォーラムルール違反であると思われます。

時々「あああ」とか「あいうえお」などという名前で投稿される方がいますが、

ふざけているように捉えられる場合が多く、熱心に回答してあげようという気を殺いでしまいます。

また、「初心者です」「初心者」「初めまして」「名無し」のような

その場だけの名前、また、多くの人が重複して使うであろう名前は避けてください。

なるべくオリジナルな名前を決め、以後同じ名前を使い続けてください。
複雑な問題？マシンの性能を上げてOpenMPで殴ればいい！(死亡フラグ)
ページトップ
ＣＯＤＥＮ

Re: [C]点がどの三角形内に居るか判断したいです

#3

投稿記事 by ＣＯＤＥＮ » 8年前

オフトピック
フォーラムルールの方、読んでおりませんでした。
大変申し訳ありません。

今後はCODＥＮ　と名乗らせていただきます。
返答ありがとうございます。
このようなやり方があるのですね。
簡易的ですが、実装させていただきました。
これを各三角形で判定させてみようと思います。
お世話になりました。ありがとうございます。

コード: 

#define EPS 1e-9
 
/* 点(px, py)が点(tx[0], ty[0]), (tx[1], ty[1]), (tx[2], ty[2])を頂点とする三角形の周または内部にあるかを判定する */
int in_triangle(const double tx[3], const double ty[3], double px, double py) {
    /* 連立方程式a*s + b*t = e, c*s + d*t = fの係数 */
    double a = tx[1] - tx[0];
    double b = tx[2] - tx[0];
    double e = px - tx[0];
    double c = ty[1] - ty[0];
    double d = ty[2] - ty[0];
    double f = py - ty[0];
    /* 連立方程式を解く */
    double det = a * d - b * c; /* 行列式 */
    /* (a b ; c d)の逆行列は、行列式をdetとして(1/det) * (d -b ; -c a) */
    double s = (d * e - b * f) / det;
    double t = (-c * e + a * f) / det;
    /* s >= 0 && t >= 0 && s + t <= 1 */
    return s + EPS > 0 && t + EPS > 0 && s + t < 1.0 + EPS;
}


int main(void)
{
	double tx[3] = {0.0, 1.0, 0.5};
	double ty[3] = {0.0, 0.0, 1.0};
	
	double px = 0.5;
	double py = 0.5;
	
	printf("%d\n",in_triangle(tx, ty, px, py));
	
	return 0;
}
ページトップ
閉鎖

“C言語何でも質問掲示板” へ戻る