以前、C++(stl)の正規表現について質問させていただき、お世話になりました。ご協力くださったh2so5さんとみけCATさん、その節はありがとうございました。今回の質問は、以下のとおりで、C++とDXライブラリを使っております。私がやりたいことは、任意の始点、終点を持つ直線が、任意の本数だけある場合、これらに囲まれた矩形の座標を求めたいというものです。※ここで扱う直線は以下のとおりです。各直線の始点と終点は、構造体で管理して、この構造体自体をstl::vectorで管理しています。矩形の座標も、起点と対角点を構造体で管理したいと考えており、プログラム内でどうにかして、直線の座標をもとに、これらに囲まれた全ての矩形の座標を知りたいのですが、このときのアルゴリズムが思いつかないので、お聞きしたいのです。考え方やヒントでもかまわないのですが、ご教授ください。以下に現在制作中のソースコードを挙げておきます。これらに囲まれた矩形の座標を求めたいというものです。※ここで扱う直線は以下のとおりです。このときのアルゴリズムが思いつかないので、お聞きしたいのです。数学の用語が怪しいので、何をしたいのか確信が持てませんが、以下の解釈であってますか?『縦横の線分で区切られた領域が1つある。矩形(長方形)がいくつかある。領域内の矩形を全て求めたい。問題を整理すると、このような形式でいいでしょうか?簡単に言うと、「線分のデータを入力する→矩形のデータを出力する」ということです。コード:線分の情報が与えられる。その線分によって囲まれる矩形全ての座標を出力せよ。入力1行目に線分の個数nが与えられる。2行目からn+1行目までは、それぞれx1,y1,x2,y2がこの順番で半角空白区切りで与えられ、この線分が(x1,y1)と(x2,y2)を結んでいることを示す。各線分について、x1==x2またはy1==y2出力1行目に線分で囲まれる矩形の数mを出力せよ。2行目からm+1行目までは、それぞれxx1,yy1,xx2,yy2をこの順番で1個の半角空白区切りで出力せよ。右下の頂点の座標が(xx2,yy2)であることを表す。各行について、xx1<=xx2、yy1<=yy2を満たしていなければならない。この条件を満たしていれば、矩形はどのような順番で出力してもよい。さんご返信くださりありがとうございます。最大本数は、100本程度で、1本の長さは、最大でも500pxです。多少パフォーマンス的に難があるアルゴリズムでも分かりすいものがよいなぁと考えています。>たいちろうさんご返信くださりありがとうございます。ご質問してくださった内容に対して、私の理解に誤りがあればご指摘ください。⇒これは、スクリーン(DXライブラリによって生成されるウィンドウ)のことだと思うので、1つで間違いありません。⇒はい、スクリーン内に0個もしくは任意の数だけあります。・「領域内の矩形を全て求めたい。スクリーン内のすべての矩形について、求めたいです。回答としましては、できれば領域内とみなしたい(矩形の1つとしてカウントはしたくない)と考えています。さんご返信くださりありがとうございます。はい、問題の認識としては、その通りです。入力について、「半角空白区切り」というのは仕様としてはありませんが、プログラム内で動的にx1,y1,x2,y2がこの順番で与えられるので、お書きくださった内容で問題ありません。制限、出力についても、その通りで間違いありません。>このそれぞれに対する出力はどうなってほしいですか?間違いのないように書くために吟味しますので少々お時間ください。次の書き込みで回答いたします。6年前No.4のみけCATさんの解釈が正しいとすると、No.3の私の解釈は全く間違っていましたね。複雑な形状の領域を私は考えていました。さんご提示いただいた入力パターンについて、希望する出力は以下のとおりです。>たいちうさんすみません。私の質問の仕方が誤解をまねくような質問の仕方であったと思います。貴重なお時間を割いてくださったのに申し訳ありません。ご協力してくださり、ありがとうございました。6年前ありがとうございます。これから考えましょう。さんこちらこそありがとうございます。分かりやすい図まで作っていただいてすみません。(私が提示させていただくべきでした・・・)私もいまいちど、考えてみます。さんお返事くださりありがとうございます。>別に4辺そろってなくても矩形とみなすのですよね.いいえ、4辺がそろっているものを矩形とみなします。辺がとぎれているものは矩形と扱いたくないです。>2個の大きい四角形の立場が逆転した場合(出力例の絵を180°回転したようなの)もあり得る気がするのですがなるほど、盲点でした。おっしゃるとおりです。Dの出力は4パターンありえますね。図を添付させていただきます。(勝手ながら、みけCATさんが作ってくださった図を改良しております。さしつかえございましたらご指摘ください。)添付ファイル期待する出力パターンです。上記までで、私の知識不足ゆえ、用語を誤っている箇所がございました。「直線」と書いていたのは、正しくは「線分」です。私がなかなかやりたいことのイメージを説明しづらく、ご協力くださる方々の混乱を招いてしまうので、改めて図を用意させていただきました。下図のように、いろんな線分(斜めは無し)があって、4辺がとぎれることなくそろっている矩形(赤い部分)を知りたい、というものです。赤い部分を表すために必要な座標を知りたいのです。他にも説明で至らないことがございましたらおっしゃっていただけると助かります。添付ファイルイメージ図です(赤い部分を表すための座標を知りたいです)。4辺がとぎれることなくそろっている矩形(赤い部分)を知りたい、というものです。線分をグリッド上に描くこのとき、1を行ったあとの座標が0~1000なら、グリッドは-1~1001の範囲を用意する(周り1マスを空ける)のが大切。上記Bのケースに対応するため、線分の座標を2倍して描画するとよい。印が付いていない場所で、線分が描かれていない部分(すなわち、矩形で埋めるべき部分)を矩形に分割するという案があります。4の具体的な手順は後で考えます。さんたびたび貴重なお時間を割いてご協力くださり、ありがとうございますm(__)m>上の入力Bでは(50,100)-(51,100)がつながっていませんが、この説明だとこれは矩形ではないのではないでしょうか?はい、そこに矩形は無いものとしたいです。Bの期待する出力は、二つの矩形が中央の線分(1px)で区切られているという考えです。>また、入力Dに対し、な、なるほど。おっしゃるとおり、その出力も正しいです。ご教授いただいたアルゴリズム1~3(4)に対し、理解を深めたいと思います。申し訳ないのですが、しばらくお時間をください。>上の入力Bでは(50,100)-(51,100)がつながっていませんが、この説明だとこれは矩形ではないのではないでしょうか?はい、そこに矩形は無いものとしたいです。Bの期待する出力は、二つの矩形が中央の線分(1px)で区切られているという考えです。申し訳ありませんが、よくわかりません。さん>「中央の線分(1px)」とはなんですか?失礼しました。私の表現が間違えているのだと思いました。赤色と緑色の間の1pxの隙間は矩形として扱いたくないということです。No.19でご提示いただいた件につきまして、回答させていただきます。区切れる数としては3つしかない見込みですので、3パターンを提示させていただきます。下図のように、いろんな線分(斜めは無し)があって、4辺がとぎれることなくそろっている矩形(赤い部分)を知りたい、というものです。赤い部分を表すために必要な座標を知りたいのです。いう条件に対し、Bは1辺が途切れているので矩形ではない(矩形は0個)のではないか、ということです。16のアルゴリズムは間違いになると思います。6年前>みけCATさん、usaoさん大変失礼しました!私が間違っていました。Bは、矩形なしです!(存在しない線分を頭の中で無意識に補完してしまったまま、気づかずに回答し続けておりました(><)!!!!)もうなんとお詫びすればよいやら・・・きっとこれがみなさんを混乱させてしまった最大の原因だと思います。申し訳ありませんでした。データ(これを入力Eとします)に対する出力から考えると、使う矩形の数は最小でなくてもいいということですね?はい、そうです。最小でなくてもかまわないです。