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

[このトピックは解決済みです]

フォーラムルール
フォーラムルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
Name: よろしくお願いいたします。
[URL]
Date: 2017年1月10日(火) 15:46
No: 1
(OFFLINE)

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

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

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

画像

コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#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;
}

Name: みけCAT
[URL]
伝説なるハッカー(624,279 ポイント)
Date: 2017年1月11日(水) 01:30
No: 2
(ONLINE)

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

残念ながらよろしくお願いいたします。さんのコードは理解しにくそうですが、
2次元平面上で点が三角形の中(周を含む)にあるかは、三角形のある頂点(基準頂点とする)から別の2頂点への2本のベクトルの線形結合で基準頂点から判定したい点のベクトルを表した時、
2本のベクトルの係数がそれぞれ0以上、かつ2本のベクトルの係数の和が1以下であるかどうかで判定できます。
コードにするとこんな感じだと思います。(テストはしていません)
コード[C]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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;
}


Offtopic :
その場限りの名前を用いての投稿は、フォーラムルール違反であると思われます。

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

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

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

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

なるべくオリジナルな名前を決め、以後同じ名前を使い続けてください。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

Name: CODEN
[URL]
Date: 2017年1月11日(水) 09:36
No: 3
(OFFLINE)

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

[解決!]

Offtopic :
フォーラムルールの方、読んでおりませんでした。
大変申し訳ありません。

今後はCODEN と名乗らせていただきます。


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

コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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;
}


Return to C言語何でも質問掲示板

オンラインデータ

このフォーラムを閲覧中のユーザー: なし & ゲスト[21人]