プログラマ専用SNS ミクプラ

はじめまして。
下記内容を実現するため良いアルゴリズムがどうしても思いつかず質問させていただきました。
良い方法をご存じであればご教授願います。

【内容】
10×10のマス目があり、マス目に沿って縦、横に線を引くことで囲まれた領域を部屋を作成します。

（例）
９┌－－－－－－－－－┬－┬－－－－－┐
　｜　　　　　　　　　｜　｜■■■■■｜
８｜　┌－┐　　　　　｜部｜■■■■■｜
　｜　｜　｜　部屋Ｇ　｜屋｜■■■■■｜
７｜　｜　｜　　　　　｜Ｅ｜　┌－┐　｜
　｜　｜部｜　　　　　｜　｜　｜　｜　｜
６｜　｜屋｜　　　　　└－┘　｜　｜　｜
　｜　｜Ｄ｜■■■■■■■■■｜部｜　｜
５｜　｜　｜　　　　　┌－┐　｜屋｜　｜
　｜　｜　｜　　　　　｜■｜　｜Ｆ｜　｜
４｜　└－┘　┌－┐　｜■｜　｜　｜　｜
　｜　　　　　｜　｜　｜■｜　｜　｜　｜
３├－－－－－┘　｜　｜■｜　└－┘　｜
　｜■■■■■■■｜　｜■｜　　　　　｜
２｜　┌－－－┐　｜　｜■└－－－┐　｜
　｜　｜部屋Ｂ｜　｜　｜■　部屋Ｃ｜　｜
１｜　└－－－┘　｜　└－－－－－┘　｜
　｜　　部屋Ａ　　｜　　　　　　　　　｜
０└－－－－－－－┴－－－－－－－－－┘
　 ０　１　２　３　４　５　６　７　８　９

各部屋が持つ頂点の座標
　部屋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)　→ 部屋Ａ
　長方形2： (5, 1) - (6, 1) - (6, 5) - (5, 5)　→ 部屋Ｃ
　長方形3： (2, 5) - (7, 5) - (7, 6) - (2, 6)　→ 部屋Ｇ
　長方形4： (6, 7) - (9, 7) - (9, 9) - (6, 9)　→ 部屋Ｇ
再起処理を使用して全ての点座標を塗りつぶして判断していくのであれば実現可能とは考えているのですが、
部屋の持つ頂点座標を使用して判断するシンプルな方法がないかを検討しております。

長文となり失礼致しましたが、ご協力の程、宜しくお願い致します。[/font]

部屋の壁が垂直ではなかったり複雑なポリゴンで構成されているならともかく、
水平垂直なグリッドで表されている場合は素直にラスタライズしてピクセルで判断するのがシンプルではないかと思います。
つまり塗りつぶすということですが。

幾何学的にシンプルに判定する方法は僕には思いつきません。
長方形の内包関係だけではなく、部屋同士の内包関係もチェックしないといけないような感じなのでなかなか面倒ではないでしょうか。

[追記]
仕様からすると長方形が部屋を跨ぐことはないようなので、長方形内の任意の点を取りその点と各部屋との内包関係を調べて、
その点を内包する部屋が複数ある場合はその部屋同士の内包関係を調べ、一番内側にある部屋を返すという方法があります。
（あまりシンプルじゃないような気もします）

[追記]
部屋同士の内包関係は面積を比較すればすぐ分かりそうです。

部屋割りはしなくていいんですよね。そこは、どうやって決められるのですか？人間が入力する？

部屋の座標の意味がわからないのですが、壁には厚みがないわけですか？
また、（０，０）の座標や（９，９）の座標があるということは、部屋の壁は座標のエリアの外側を示しているということですよね。
この部屋の座標のあらわし方は、決められているのですね。

調べたいマスから、上下左右のいずれかの方向に直線を伸ばし、その直線と交差する壁の数をカウントします。
そのマスは、交差する壁の数が奇数の部屋に含まれます。

これだけだと部屋Ｇには必ず含まれるので、4方向調べて、交差する中でより近い壁を持つ部屋という条件を加えれば…どうでしょう。

やっぱり、座標の表し方がわかりません。

>部屋C： (5, 1) - (8, 1) - (8, 2) - (6, 2) - (5, 2) - (5, 5)
ここで、(8, 2) - (6, 2) - (5, 2)ってのはなぜですか？

壁はマスの中心を通っていて、長方形は壁で囲まれた領域を指す、のでは？

non さんが書きました:>部屋C： (5, 1) - (8, 1) - (8, 2) - (6, 2) - (5, 2) - (5, 5)
ここで、(8, 2) - (6, 2) - (5, 2)ってのはなぜですか？

(5, 2)は誤りで(6, 5)が正しい、ですかね。

部屋A： (0, 0) - (4, 0) - (4, 4) - (3, 4) - (3, 3) - (0, 3)
部屋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)

ここの(0, 3) - (3, 3)の壁ですが、(0,3)のマスの壁は上でしょうか下でしょうか？

ISLe さんが書きました:壁はマスの中心を通っていて、長方形は壁で囲まれた領域を指す、のでは？

non さんが書きました:>部屋C： (5, 1) - (8, 1) - (8, 2) - (6, 2) - (5, 2) - (5, 5)
ここで、(8, 2) - (6, 2) - (5, 2)ってのはなぜですか？

(5, 2)は誤りで(6, 5)が正しい、ですかね。

申し訳ありません。ご指摘の通りです。
ISLeさん、nonさんありがとうございます。

正しくは下になります。
部屋C： (5, 1) - (8, 1) - (8, 2) - (6, 2) - (6, 5) - (5, 5)

non さんが書きました:部屋A： (0, 0) - (4, 0) - (4, 4) - (3, 4) - (3, 3) - (0, 3)
部屋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)

ここの(0, 3) - (3, 3)の壁ですが、(0,3)のマスの壁は上でしょうか下でしょうか？

こちらの回答は？

また、仮に部屋が（１，１）の１マスのときには座標はどうなりますか？
(1,1)　だけですか？

non さんが書きました:

non さんが書きました:部屋A： (0, 0) - (4, 0) - (4, 4) - (3, 4) - (3, 3) - (0, 3)
部屋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)

ここの(0, 3) - (3, 3)の壁ですが、(0,3)のマスの壁は上でしょうか下でしょうか？

こちらの回答は？

また、仮に部屋が（１，１）の１マスのときには座標はどうなりますか？
(1,1)　だけですか？

> ここの(0, 3) - (3, 3)の壁ですが、(0,3)のマスの壁は上でしょうか下でしょうか？

説明不足でしたので補足させていただきます。
壁は部屋を分断するためのものであり、壁の厚さはないと考えてください。
壁はマスの中にあるというよりは、マス目に沿って引くと考えていただければ良いと思います。
(0, 3) - (3, 3)のマス目に横線を引き、線より上側が部屋Ａ、下側が部屋Ｇとなります。


> また、仮に部屋が（１，１）の１マスのときには座標はどうなりますか？

部屋は必ず4点以上を持つ前提として、1点のみの部屋は存在しないと考えてください。

wik さんが書きました: > ここの(0, 3) - (3, 3)の壁ですが、(0,3)のマスの壁は上でしょうか下でしょうか？

説明不足でしたので補足させていただきます。
壁は部屋を分断するためのものであり、壁の厚さはないと考えてください。
壁はマスの中にあるというよりは、マス目に沿って引くと考えていただければ良いと思います。
(0, 3) - (3, 3)のマス目に横線を引き、線より上側が部屋Ａ、下側が部屋Ｇとなります。

私も、そのように思っているわけですが、どのように書いて良いかわからないのです。
EXCELで絵を書いてみました。私のどこが間違っているか指摘願います。
赤い線のところをどう考えてよいかわからないのです。

座標と壁で部屋を区切るという前提自体は動かせないのでしょうか？

マス目で区切られているのなら、マス目自体に部屋番号を与えてしまったほうが
よりシンプルな構造なると思います。


また、任意の長方形が2つ以上の部屋に属することはありますか？

現状の説明だと、例で示された長方形2は部屋Ｃと部屋Ｇの２つの条件を
満たしていますが、部屋Ｃとしか書かれていません。

non さんが書きました: 私も、そのように思っているわけですが、どのように書いて良いかわからないのです。
EXCELで絵を書いてみました。私のどこが間違っているか指摘願います。
赤い線のところをどう考えてよいかわからないのです。

ファイルに追記致しました。
同シートの横側に2種類の表現方法で追記しておりますので、ご確認をお願いします。

おそらくwikさんの勘違いしているところは部屋の大きさでしょう。
10×10と書いていますが、9×9の間違いではないですか？

アルゴリズムについて興味はありますが、
もう酒を飲んでいるので今日はきっと無理。
近日中に挑戦したいけど先に誰かが解いてくれそう。

peot さんが書きました:座標と壁で部屋を区切るという前提自体は動かせないのでしょうか？

マス目で区切られているのなら、マス目自体に部屋番号を与えてしまったほうが
よりシンプルな構造なると思います。


また、任意の長方形が2つ以上の部屋に属することはありますか？

現状の説明だと、例で示された長方形2は部屋Ｃと部屋Ｇの２つの条件を
満たしていますが、部屋Ｃとしか書かれていません。

> 座標と壁で部屋を区切るという前提自体は動かせないのでしょうか？
申し訳ないのですが、該当部分は既に作りこまれてしまっており
前提を変更するとは不可能となっております。ご了承ください。

> また、任意の長方形が2つ以上の部屋に属することはありますか？
説明が不足しており申し訳ありません。
部屋同士が内包関係にあるというパターンが存在します。
長方形が複数の部屋に含まれるような場合は、もっとも内側の部屋が対象となるようお願い致します。

No.13の添付ファイルを見ましたが、「2種類の表現方法」というのが勘違いの元でしょう。
うまく補い合ってイメージが相手に（回答者とかコンパイラとか）伝わると思ってはいけません。
自分で十分理解できていないから「2種類の表現方法」のいいとこ取りをしようとしているのです。

正しい表現方法が1つだけあれば十分ですし、複数あると矛盾する可能性があります。
というか、現時点では矛盾しています。部屋Eの横幅とか。
表現方法を1つにして下さい。その上で座標を示しましょう。

部屋Ｇの内包関係から部屋ＡＢＥが除外されてるのには
何か明確な理由があるのでしょうか？

特にないのであれば、部屋Ｇの座標を(0,0)-(9,0)-(9,9)-(0,9)
とした方がよりシンプルだと思うのですが。

2種類の表現方法は、基準をマスの中心に取るか格子の交点に取るかの違いだけで、矛盾はないと思いますけど。
わたしの提示したアルゴリズムだと、壁を交点座標、部屋をマス座標とすると、余計コードが複雑になるような？

・部屋を形作らない壁（├　の横棒みたいなの．ループを形成しないやつ）が存在しない
・マスは包括関係にない２つの部屋に共有されない（本来共有部分が別の１部屋になるべきだが，データ上はそんな形もあり得る）
という条件であればISLeさんの示された方法
>調べたいマスから、上下左右のいずれかの方向に直線を伸ばし、その直線と交差する壁の数をカウントします。
>そのマスは、交差する壁の数が奇数の部屋に含まれます。
>これだけだと部屋Ｇには必ず含まれるので、4方向調べて、交差する中でより近い壁を持つ部屋という条件を加えれば…どうでしょう。
で良いように思います．
長方形のいずれかの■から４方向調べ，
その全ての方向において最も近い部屋が答えになるように思います．

やっと意味がわかりました。座標は壁を表していたのですね。空間の数は9×9。

私なら、
まず、MAPを縦19×横19に変換します。偶数の座標が壁、奇数の座標が空間です。
一つ目の部屋（例えばAの部屋）の座標から、壁の場所に印（例えば1）を入れます。for文でLineを引く要領で。
次に、ISLeさんの方法で、すべての空間座標から4方向の壁（1の数をカウント）が奇数か調べ、4方向とも奇数ならその場所に部屋番号を入れます。
同様に他の部屋も同じようにMAPを作ります。
おのおのの部屋別のMAPができあがりますので、これを統合します。ここで、面積から含有関係を考慮します。

後は、調べたい長方形の中の空間座標の部屋番号をすべてチェックして、同一部屋番号なら、その部屋に含まれることになります。

言葉では、わかりにくいと思いましたので、絵を描いてみました。

ISLe さんが書きました:調べたいマスから、上下左右のいずれかの方向に直線を伸ばし、その直線と交差する壁の数をカウントします。
そのマスは、交差する壁の数が奇数の部屋に含まれます。

これだけだと部屋Ｇには必ず含まれるので、4方向調べて、交差する中でより近い壁を持つ部屋という条件を加えれば…どうでしょう。

いただいた方法で作成してみた結果、私の求めていたものを作ることができました。
交差する壁の数で判断するという考えは自力で思いつくことができず感心しました。

今回のアイデアを出していただいたISLeさん、詳細まで落とし込んでいただいたnonさん、
その他ご指摘・アドバイスいただいた方々、本当にありがとうございました。