C言語関係掲示板

過去ログ

No.1288 四角形を分割していくアルゴリズム

[戻る] [ホームページ]
No.17079

下のaは間違いです・・・。ごめんなさい。
投稿者---hiromi(2004/10/04 17:06:11)


四角形を描き、X,Y方向にそれぞれ分割し、分割した辺に左下から反時計回りに番号をつけ、その辺の両端のx,yデータを書き出すというアルゴリズムを考えています。
 今回はさらに、分割した四角形をさらに細かく分割できるように考えているのですがうまくいきません。
 例えば、最初の四角形をx,y共に2分割すると辺の数は全部で8個になり上辺の番号は5,6ということになります。次にy方向に同じ形状の四角形を増やした時に、1,2(7,8)は6,5と重なるので、若い番号に書き換えます(6=7,8=5)。その次は9から始まるのではなく、書き換えた事により使っていない番号、7から書き出します。今までのプログラムでいける所。
__________________________________
|////6/////|////12////|
|//////////|//////////|
|7////////5|5///////11|
|//////////|//////////|
|_______3_______|______10_______|
|/////////3|////10////|
|//////////|//////////|
|4////////2|2////////9|
|//////////|//////////|
|_______1_______|_______8_______|


今回はさらに、細かく

____________________________________________
|//18/17/16/15/|/36/35/34/33/|
|19//////////14|14/////////32|
|//////////////|/////////////|
|20//////////13|13/////////31|
|__10___9___8___7____|_30__29__28__27_|
|//10//9//8//7/|/30/29/28/27/|
|11///////////6|6//////////26|
|//////////////|/////////////|
|12///////////5|5//////////25|
|___1___2___3___4____|_21__22__23__24_|

上の様に1つの四角形を更に細かく分割したデータの番号を振り替えたいのですが、詳しい方よろしくお願いします。
以下には今までできているプログラムを書いておきます。

//※以下、N は線分の総数
#define no 0
#define INVALID -1//無効値

int count;//通し番号(線分につける番号)
int s, t;

//各線分に割り振られている通し番号を「無効値」で初期化
for(t=0;t<N;t++){
 data[t][no] = INVALID;
}
 
count = 0;//通し番号を初期化

/*以下の2重ループにおいて、
外ループで基準線分data[t][]を決定し、
そのそれぞれに対して
内ループで副線分data[s][]を決定し、
かつ基準線分と副線分を比較する。
*/
for(t=0;t<N;t++){//←tの範囲に注意
 //基準線分の通し番号が既に決定してるなら、
 //以後の処理を行わずループ先頭に返る
 if (data[t][no] != INVALID) {
  continue;
 }
   
 //基準線分に対し、「(正しい)通し番号」を割り振る
 data[t][no] = ++count;
   
 //内側ループ(副線分処理)
 for(s=t+1;s<N;s++){
  if (data[s][no] != INVALID) {
   continue;
  }
  
  //もし基準線分と副線分が一致するなら
  //副線分に対し通し番号を割り振る
  if((data[s][x1]==data[t][x1])
      &&(data[s][y1]==data[t][y1])
      &&(data[s][x2]==data[t][x2])
      &&(data[s][y2]==data[t][y2])){
   //通し番号わりふり
   data[s][no]=count;
  }
 }
}


No.17082

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---Sciggepy(2004/10/04 19:32:00)


________________
|//10//9//8//7/|
|11///////////6|
|//////////////|
|12///////////5|
|__1__2__3__4__|
  1. 1区画に割り当てる数字の数は、どうやって決めるのでしょうか?
  2. ブロック内で数字を割り当てる順番は、左下→右下→右上→左上→左下でよいのですね?
  3. ブロックを移動する順番は、左下→左上→右下→右上でよいのですね?



No.17084

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---hiromi(2004/10/04 20:06:05)


1区画に割り当てる数字の数は、どうやって決めるのでしょうか?

x方向y方向とも使用者に指定してもらいます。
予想ではxy方向ともに10位までの数字を予定しています。


ブロック内で数字を割り当てる順番は、左下→右下→右上→左上→左下でよいのですね?

そうですね。ブロック内は左下から反時計回りです。


ブロックを移動する順番は、左下→左上→右下→右上でよいのですね?
</ol>

そうですね。まずxを固定しy方向に増やし、次にyをxを増やします。

分からない事がありましたらお手数ですがまた、聞いて下さい。
よろしくお願いします。


No.17093

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---たいちう(2004/10/05 10:48:45)


# スレが変わってたのね。おじさん気が付かなかったよ。

やりたいことは大体分かりましたが、
番号をどのように持ちたいのか、ソースを見ても分かりません。
data[][] について、定義、添え字の範囲、実際に取る値を
説明してください。

番号の振り方のアルゴリズムについてですが、
私ならば、小さい四角形についてのみ番号を振る関数を作り、
それを左下から順に4回呼びます。
関数内で、左側や下側の線分に番号を振るときに、その
四角形より左や下に別の四角形が存在するかをチェックします。


No.17094

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---hiromi(2004/10/05 13:30:31)


>data[][] について、定義、添え字の範囲、実際に取る値
>
dara[][]の左側には小さい四角形の番号、この場合では1〜4が入る事になります。また、小さい四角形の数も4個と決まっているわけではなく、userに四角形の長さや数は指定してもらいます。
 右側には0に通し番号。1に左下のxの座標2に左下のyの座標、3に右下のx座標4に右下のy座標を取ります。
座標の決定から番号の振りなおしまでのプログラムを以下に示しておきます。

for(v = 1; v<=soudomeinnynsuux; v++){
for(u = 1; u<=soudomeinnynsuuy; u++){
for(r = 0; r<yousosuux; r++){
data[o][0] = o+1;
data[o][1] = kyoukaijoukenn;
data[o][2] = du4*r+wide*(v-1);        /*du4=wide/yousosuux du1=wide*soudomeinnynsuux*/
data[o][3] = hight*(u-1);
data[o][4] = du4*(r+1)+wide*(v-1);
data[o][5] = hight*(u-1);
o = o+1;
}
for(s = 0; s<yousosuuy; s++){
r = yousosuux;
data[o][0] = o+1;
data[o][1] = kyoukaijoukenn;
data[o][2] = du4*r+wide*(v-1);
data[o][3] = du5*s+hight*(u-1);
data[o][4] = du4*r+wide*(v-1);
data[o][5] = du5*(s+1)+hight*(u-1);
o = o+1;
}
for(r = yousosuux-1; r>-1; r--){
s = yousosuuy;
data[o][0] = o+1;
data[o][1] = kyoukaijoukenn;
data[o][2] = du4*(r+1)+wide*(v-1);
data[o][3] = du5*s+hight*(u-1);
data[o][4] = du4*r+wide*(v-1);
data[o][5] = du5*s+hight*(u-1);
o = o+1;
}
for(s = yousosuuy-1; s>-1; s--){
data[o][0] = o+1;
data[o][1] = kyoukaijoukenn;
data[o][2] = wide*(v-1);
data[o][3] = du5*(s+1)+hight*(u-1);
data[o][4] = wide*(v-1);
data[o][5] = du5*s+hight*(u-1);
o = o+1;
}
}
}
///////////////////////////////////////////////////////////////////
// 並び替え。
////////////////////////////////////////////////////////////////////
#define INVALID -1
int count1;
int p, n;
for(p = 0; p<sou1; p++){
data[p][0] = INVALID;
}
count1 = 0;
for(p=0; p<sou1; p++){
if (data[p][0] != INVALID){
continue;
}
data[p][0] = ++count1;
for(n = p+1; n<sou1+1; n++){
if(data[n][0] != INVALID){
continue;
}
if((data[n][2] == data[p][4]) && (data[n][3] == data[p][5])
&&(data[n][4] == data[p][2]) && (data[n][5] == data[p][3])){
data[n][0] = count1;
}
}

}
}
分かりづらくてごめんなさい。。。


No.17095

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---たいちう(2004/10/05 16:46:26)


> dara[][]の左側には小さい四角形の番号、この場合では1〜4が入る事になります。
> また、小さい四角形の数も4個と決まっているわけではなく、
> userに四角形の長さや数は指定してもらいます。
> 右側には0に通し番号。1に左下のxの座標2に左下のyの座標、
> 3に右下のx座標4に右下のy座標を取ります。

多分このデータの持ち方が無理なのではないかと。
例えば1つめの例では、12本の線分がありますが、各線分についての
両端の座標(+α)を管理したいということだと思いましたが、
1つめの添え字で四角形の番号を使ってしまうと四角形の個数である
4本の線分のデータしか表現できません。

例えば、

data[o][0] = 小さい四角形の番号;
data[o][1] = kyoukaijoukenn;
data[o][2] = du4*r+wide*(v-1); 
data[o][3] = hight*(u-1);
data[o][4] = du4*(r+1)+wide*(v-1);
data[o][5] = hight*(u-1);

として、0 <= o < 12 とすることで、12本の線分を表現することができます。


No.17096

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---hiromi(2004/10/05 17:38:15)


回答ありがとうございます。

>多分このデータの持ち方が無理なのではないかと。

そうですね・・。4個目のデータからうまくデータが書き換わらないのはそのせいだったのでしょうか・・・。

>1つめの添え字で四角形の番号を使ってしまうと四角形の個数である
>4本の線分のデータしか表現できません。

いまいち掴めませんでした(泣)
for()で更に内側でまわせばよいのでしょうか?
少しやってみたのですが、結果はダメでした・・・。



No.17097

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---たいちう(2004/10/05 18:12:02)


> for()で更に内側でまわせばよいのでしょうか?

プログラムの全体がないので(dataの定義もまだ書いてもらっていません)
分かりませんが、多分違うでしょう。

それより手始めに練習として、1つの四角形のみを分割するプログラムを作りましょう。
分割数もx方向に4分割、y方向に2分割と固定してしまいます。

これなら、何とかなるのではないですか?

これができてから、4つの四角形を分割、重複する線分を除去、
分割数を変更可能に、と順に進めばよいでしょう。
始めから完成品を作ろうとせず段階的に作らないと、
どこが間違っているのか分かりにくいものです。


No.17099

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---hiromi(2004/10/05 18:50:46)


何度も申し訳ありません。
前に書いたプログラムで、並び替えのプログラムを除けば、分割数をいくつにしても、完璧にデータは出ていました。
重なるデータについて並び替えをしようと思い、やってみたら、今のプログラムでも3つ目まではうまく並び替えを行います。
でも、4つ目になると急にdata[][0]の並び替えを行わなくなるのは何故なのでしょうか?それもoのとり方に問題があるのでしょうか?
また、最後から2つ目のデータもうまく並べ替えます。何故だかさっぱりなのですが・・・。


No.17098

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---REE(2004/10/05 18:16:35)


>>1つめの添え字で四角形の番号を使ってしまうと四角形の個数である
>>4本の線分のデータしか表現できません。
>
>いまいち掴めませんでした(泣)
>for()で更に内側でまわせばよいのでしょうか?
>少しやってみたのですが、結果はダメでした・・・。

そういう問題ではなく、データの保持方法を見直す必要があるということです。
何をどのように保持するのか、一度整理してみて下さい。

以下は例です。
・一つの四角には、左上と右下の座標と高さ及び、4本の辺がある。
・一つの辺には、始点と終点の座標及び、通し番号がある。
・辺は複数の四角に対し共有されることがある。

struct 辺
{
 始点、終点
} 辺データ[最大の辺の数]; //辺番号は添え字で表す。

struct 四角
{
 左上座標,右下座標,高さ
 int 辺番号[4];
} 四角データ[最大の四角の数];



No.17100

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---Sciggepy(2004/10/05 18:53:19)


>また、小さい四角形の数も4個と決まっているわけではなく、userに四角形の長さや数は指定してもらいます。
この場合、順番はどうなるのでしょうか?最初の例から想像すると、下から上、左の列から順に数字を振ると考えられますが、これで合っていますか?


No.17101

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---hiromi(2004/10/05 19:04:27)


>>また、小さい四角形の数も4個と決まっているわけではなく、userに四角形の長さや数は指定してもらいます。
>この場合、順番はどうなるのでしょうか?最初の例から想像すると、下から上、左の列から順に数字を振ると考えられますが、これで合っていますか?
そうですね。合ってます。私としては番号を振る所まではあっているので、並び替えのプログラムが間違えているものだと思っていました。


No.17111

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---Sciggepy(2004/10/05 22:11:55)


前のブロックが関係するのは、左と下の境界上だけですね。
最左と最下以外は、右と上に順に数字を振り、左と下には隣のブロックの数字をコピー、
最左は左にも振り、最下は下にも振る、でよいと思います。
//最初の例の再現
#include <stdio.h>

#define B_X 2
#define B_Y 2
#define N_X 4
#define N_Y 2
#define ELM(bx,by,i) (((bx)*B_Y+(by))*2*(N_X+N_Y)+(i))
#define BOTTOM(i) (i)
#define RIGHT(i) ((i)+N_X)
#define TOP(i) ((i)+N_Y+N_X)
#define LEFT(i) ((i)+N_Y+2*N_X)

int main(void)
{
    unsigned num[B_X*B_Y*2*(N_X+N_Y)],i,n=1,bx,by;

    for(bx=0;bx<B_X;bx++) for(by=0;by<B_Y;by++) {
        if(by) for(i=0;i<N_X;i++) num[ELM(bx,by,BOTTOM(i))]=num[ELM(bx,by-1,TOP(N_X-i-1))];
        else for(i=0;i<N_X;i++) num[ELM(bx,by,BOTTOM(i))]=n++;
        for(i=0;i<N_Y;i++) num[ELM(bx,by,RIGHT(i))]=n++;
        for(i=0;i<N_X;i++) num[ELM(bx,by,TOP(i))]=n++;
        if(bx) for(i=0;i<N_Y;i++) num[ELM(bx,by,LEFT(i))]=num[ELM(bx-1,by,RIGHT(N_Y-i-1))];
        else for(i=0;i<N_Y;i++) num[ELM(bx,by,LEFT(i))]=n++;
    }
    for(bx=0;bx<B_X;bx++) for(by=0;by<B_Y;by++) {
        printf("B: %d,%d\n",bx,by);
        for(i=0;i<2*(N_X+N_Y);i++) printf("%d\n",num[ELM(bx,by,i)]);
    }
    return 0;
}



No.17116

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---hiromi(2004/10/06 13:55:53)


>前のブロックが関係するのは、左と下の境界上だけですね。
>最左と最下以外は、右と上に順に数字を振り、左と下には隣のブロックの数字をコピー、
>最左は左にも振り、最下は下にも振る、でよいと思います。
><pre>//最初の例の再現
#include <stdio.h>

#define B_X 2
#define B_Y 2
#define N_X 4
#define N_Y 2
#define ELM(bx,by,i) (((bx)*B_Y+(by))*2*(N_X+N_Y)+(i))
#define BOTTOM(i) (i)
#define RIGHT(i) ((i)+N_X)
#define TOP(i) ((i)+N_Y+N_X)
#define LEFT(i) ((i)+N_Y+2*N_X)

int main(void)
{
unsigned num[B_X*B_Y*2*(N_X+N_Y)],i,n=1,bx,by;

for(bx=0;bx<B_X;bx++) for(by=0;by<B_Y;by++) {
if(by) for(i=0;i<N_X;i++) num[ELM(bx,by,BOTTOM(i))]=num[ELM(bx,by-1,TOP(N_X-i-1))];
else for(i=0;i<N_X;i++) num[ELM(bx,by,BOTTOM(i))]=n++;
for(i=0;i<N_Y;i++) num[ELM(bx,by,RIGHT(i))]=n++;
for(i=0;i<N_X;i++) num[ELM(bx,by,TOP(i))]=n++;
if(bx) for(i=0;i<N_Y;i++) num[ELM(bx,by,LEFT(i))]=num[ELM(bx-1,by,RIGHT(N_Y-i-1))];
else for(i=0;i<N_Y;i++) num[ELM(bx,by,LEFT(i))]=n++;
}
for(bx=0;bx<B_X;bx++) for(by=0;by<B_Y;by++) {
printf("B: %d,%d\n",bx,by);
for(i=0;i<2*(N_X+N_Y);i++) printf("%d\n",num[ELM(bx,by,i)]);
}
return 0;
}
</pre>

double型で座標を取っていたので誤差が生じてしまっていたようです。。。
ちゃんと解決しました。ご迷惑をおかけいたしました。ありがとうございました。



No.17102

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---REE(2004/10/05 19:22:54)


>>data[][] について、定義、添え字の範囲、実際に取る値
>>
>dara[][]の左側には小さい四角形の番号、この場合では1〜4が入る事になります。また、小さい四角形の数も4個と決まっているわけではなく、userに四角形の長さや数は指定してもらいます。
> 右側には0に通し番号。1に左下のxの座標2に左下のyの座標、3に右下のx座標4に右下のy座標を取ります。
>座標の決定から番号の振りなおしまでのプログラムを以下に示しておきます。

改めて、下のプログラムを見てみたら・・
data[][]の左側は、線分のindex、右側の0は通し番号、1は境界条件?、2,3に始点座標、4,5に終点座標に見えるのですが・・・

dataを構造体の配列に変更されることをお勧めします。
data[2][2]よりも、data[2].x1 の方が遥かに分かりやすいでしょう。

> for(n = p+1; n<sou1+1; n++){
これが間違いかな?
for(n = p+1; n<sou1; n++){



No.17103

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---hiromi(2004/10/05 19:36:56)


>data[][]の左側は、線分のindex、右側の0は通し番号、1は境界条件?、2,3に始点座標、4,5に終点座標に見えるのですが・・・

その通りです。ここに問題はないと思うのですが・・・。>
>dataを構造体の配列に変更されることをお勧めします。

構造体の配列はまだいまいち分からないので勉強後に変更したいと思います。

>> for(n = p+1; n<sou1+1; n++){
>これが間違いかな?
>for(n = p+1; n<sou1; n++){

これではなかったです。


No.17104

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---REE(2004/10/05 19:57:02)


>>data[][]の左側は、線分のindex、右側の0は通し番号、1は境界条件?、2,3に始点座標、4,5に終点座標に見えるのですが・・・
>
>その通りです。ここに問題はないと思うのですが・・・。

問題はあなたの説明と一致していないことです。

>>> for(n = p+1; n<sou1+1; n++){
>>これが間違いかな?
>>for(n = p+1; n<sou1; n++){
>
>これではなかったです。

では、具体的に、どうなるはずが、どうなっているのですか?



No.17105

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---hiromi(2004/10/05 20:11:59)


具体的には、x方向に4つy方向に2つ10cmの四角形を重ねた場合、
x方向の4つ目が違います。4つ目からが常におかしいのです。

4 0 0
1 0
0.000000e+000 0.000000e+000
1.000000e-001 0.000000e+000
2 0
1.000000e-001 0.000000e+000
1.000000e-001 1.000000e-001
3 0
1.000000e-001 1.000000e-001
0.000000e+000 1.000000e-001
4 0
0.000000e+000 1.000000e-001
0.000000e+000 0.000000e+000
4 0 0
3 0
0.000000e+000 1.000000e-001
1.000000e-001 1.000000e-001
5 0
1.000000e-001 1.000000e-001
1.000000e-001 2.000000e-001
6 0
1.000000e-001 2.000000e-001
0.000000e+000 2.000000e-001
7 0
0.000000e+000 2.000000e-001
0.000000e+000 1.000000e-001
4 0 0
8 0
1.000000e-001 0.000000e+000
2.000000e-001 0.000000e+000
9 0
2.000000e-001 0.000000e+000
2.000000e-001 1.000000e-001
10 0
2.000000e-001 1.000000e-001
1.000000e-001 1.000000e-001
2 0
1.000000e-001 1.000000e-001
1.000000e-001 0.000000e+000
4 0 0
10 0
1.000000e-001 1.000000e-001
2.000000e-001 1.000000e-001
11 0
2.000000e-001 1.000000e-001
2.000000e-001 2.000000e-001
12 0
2.000000e-001 2.000000e-001
1.000000e-001 2.000000e-001
5 0
1.000000e-001 2.000000e-001
1.000000e-001 1.000000e-001
4 0 0
13 0
2.000000e-001 0.000000e+000
3.000000e-001 0.000000e+000
14 0
3.000000e-001 0.000000e+000
3.000000e-001 1.000000e-001
15 0
3.000000e-001 1.000000e-001
2.000000e-001 1.000000e-001
9 0
2.000000e-001 1.000000e-001
2.000000e-001 0.000000e+000
4 0 0
15 0
2.000000e-001 1.000000e-001
3.000000e-001 1.000000e-001
16 0
3.000000e-001 1.000000e-001
3.000000e-001 2.000000e-001
17 0
3.000000e-001 2.000000e-001
2.000000e-001 2.000000e-001
11 0
2.000000e-001 2.000000e-001
2.000000e-001 1.000000e-001
4 0 0
18 0
3.000000e-001 0.000000e+000
4.000000e-001 0.000000e+000
19 0
4.000000e-001 0.000000e+000
4.000000e-001 1.000000e-001
20 0
4.000000e-001 1.000000e-001
3.000000e-001 1.000000e-001
21→本当は14 0
3.000000e-001 1.000000e-001
3.000000e-001 0.000000e+000
4 0 0
22→本当は20 0
3.000000e-001 1.000000e-001
4.000000e-001 1.000000e-001
23→本当は21 0
4.000000e-001 1.000000e-001
4.000000e-001 2.000000e-001
24→本当は22 0
4.000000e-001 2.000000e-001
3.000000e-001 2.000000e-001
25→本当は16 0
3.000000e-001 2.000000e-001
3.000000e-001 1.000000e-001
です。


No.17107

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---REE(2004/10/05 20:26:43)


>具体的には、x方向に4つy方向に2つ10cmの四角形を重ねた場合、
>x方向の4つ目が違います。4つ目からが常におかしいのです。

座標はdouble型だったのですね・・
double型には誤差がつき物ですので、単純に==で判定してはいけません。
例えば、fabs(data[n][2]-data[p][4]) < 0.00001 の様に判定してください。



No.17115

Re:下のaは間違いです・・・。ごめんなさい。
投稿者---hiromi(2004/10/06 13:54:51)



>double型には誤差がつき物ですので、単純に==で判定してはいけません。
>例えば、fabs(data[n][2]-data[p][4]) < 0.00001

これで解決しました。本当にご迷惑をおかけいたしました。ありがとうございました。