下記内容を実現するため良いアルゴリズムがどうしても思いつかず質問させていただきました。
良い方法をご存じであればご教授願います。
【内容】
10×10のマス目があり、マス目に沿って縦、横に線を引くことで囲まれた領域を部屋を作成します。
(例)
9┌---------┬-┬-----┐
| | |■■■■■|
8| ┌-┐ |部|■■■■■|
| | | 部屋G |屋|■■■■■|
7| | | |E| ┌-┐ |
| |部| | | | | |
6| |屋| └-┘ | | |
| |D|■■■■■■■■■|部| |
5| | | ┌-┐ |屋| |
| | | |■| |F| |
4| └-┘ ┌-┐ |■| | | |
| | | |■| | | |
3├-----┘ | |■| └-┘ |
|■■■■■■■| |■| |
2| ┌---┐ | |■└---┐ |
| |部屋B| | |■ 部屋C| |
1| └---┘ | └-----┘ |
| 部屋A | |
0└-------┴---------┘
0 1 2 3 4 5 6 7 8 9
各部屋が持つ頂点の座標
部屋A: (0, 0) - (4, 0) - (4, 4) - (3, 4) - (3, 3) - (0, 3)
部屋B: (1, 1) - (3, 1) - (3, 2) - (1, 2)
部屋C: (5, 1) - (8, 1) - (8, 2) - (6, 2) - (5, 2) - (5, 5)
部屋D: (1, 4) - (2, 4) - (2, 8) - (1, 8)
部屋E: (5, 6) - (6, 6) - (6, 9) - (5, 9)
部屋F: (7, 3) - (8, 3) - (8, 7) - (7, 7)
部屋G: (0, 3) - (3, 3) - (3, 4) - (4, 4) - (4, 0) - (9, 0) -
(9, 9) - (6, 9) - (6, 6) - (5, 6) - (5, 9) - (0, 9)
そのうち、任意の長方形(例の■部分)がどの部屋に含まれるかを判断し、その名称を取得する関数を作成しようとしています。
(例)
長方形1: (0, 2) - (4, 2) - (4, 3) - (0, 3) → 部屋A
長方形2: (5, 1) - (6, 1) - (6, 5) - (5, 5) → 部屋C
長方形3: (2, 5) - (7, 5) - (7, 6) - (2, 6) → 部屋G
長方形4: (6, 7) - (9, 7) - (9, 9) - (6, 9) → 部屋G
// 2次元座標構造体
struct point2d {
int x;
int y;
}
// 部屋構造体
struct room {
char name[255]; // 部屋名称
point2d* corner; // 部屋の頂点座標配列
}
// 長方形座標構造体
struct point4d {
int x1; // 左側の座標
int y1; // 下側の座標
int x2; // 右側の座標
int y2; // 上側の座標
}
// 長方形の存在する部屋の名称を取得する関数
// 第1引数:長方形座標
// 第2引数:部屋データ配列
// 戻り値: この長方形
char* getRoomName(point4d rect, room[] r) {
// この部分を作成
}
部屋の持つ頂点座標を使用して判断するシンプルな方法がないかを検討しております。
長文となり失礼致しましたが、ご協力の程、宜しくお願い致します。[/font]