(C++)直線に囲まれた矩形の座標を知りたい

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
Ketty

(C++)直線に囲まれた矩形の座標を知りたい

#1

投稿記事 by Ketty » 5年前

こんにちは。Kettyです。
以前、C++(stl)の正規表現について質問させていただき、お世話になりました。
ご協力くださったh2so5さんとみけCATさん、その節はありがとうございました。

今回の質問は、以下のとおりで、C++とDXライブラリを使っております。
私がやりたいことは、任意の始点、終点を持つ直線が、任意の本数だけある場合、
これらに囲まれた矩形の座標を求めたいというものです。

※ここで扱う直線は以下のとおりです。
 ななめの線は無いこと(すべて、X軸方向(またはY軸方向)に水平(または垂直))
 長さが0のものは無いこと
 始点および終点に負値はないこと
 始点および終点はいずれも整数であること(小数点なし)

現状としては、
各直線の始点と終点は、構造体で管理して、
この構造体自体をstl::vectorで管理しています。

また、矩形の座標も、起点と対角点を構造体で管理したいと考えており、
プログラム内でどうにかして、直線の座標をもとに、これらに囲まれた全ての矩形の座標を知りたいのですが、
このときのアルゴリズムが思いつかないので、お聞きしたいのです。
考え方やヒントでもかまわないのですが、ご教授ください。

以下に現在制作中のソースコードを挙げておきます。

コード:

#include "DxLib.h"
#include <vector>
#include <string>
#include <sstream>

using namespace std ;

//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 直線の構造体
// ※前提として、斜めにならないものとします
//+++++++++++++++++++++++++++++++++++++++++++++++++++
struct LINE
{
	// 始点
	int pos1X ;
	int pos1Y ;
	// 終点
	int pos2X ;
	int pos2Y ;
} ;

//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 矩形の構造体
//+++++++++++++++++++++++++++++++++++++++++++++++++++
struct SQUARE
{
	// 始点
	int pos1X ;
	int pos1Y ;
	// 始点に対して対角の点
	int pos2X ;
	int pos2Y ;
} ;

//+++++++++++++++++++++++++++++++++++++++++++++++++++
// int型を文字列に変換する関数のプロトタイプ宣言
//+++++++++++++++++++++++++++++++++++++++++++++++++++
string IntToString( const int & number ) ;

// プログラムは WinMain から始まります
int WINAPI WinMain( HINSTANCE hInstance, HINSTANCE hPrevInstance,
						LPSTR lpCmdLine, int nCmdShow )
{
	// ウィンドウモードにする
	ChangeWindowMode( TRUE ) ;

	// DXライブラリ初期化処理
	if( DxLib_Init() == -1 ){ return -1 ; }

	// 直線を複数保持する配列
	vector<LINE *> lines(0) ;		// とりあえずサイズ0としておきます

	// 矩形を複数保持する配列
	vector<SQUARE *> squares(0) ;	// とりあえずサイズ0としておきます

	//+++++++++++++++++++++++++++++++++++++++++++++++++++
	// 直線を思いつくまま追加します
	// ※以下は、実験用に固定で追加しますが、
	//  本来は、長さ、本数、追加順が不定です
	//  斜めの線は無い、ということだけ決まっています
	//+++++++++++++++++++++++++++++++++++++++++++++++++++
	// 配列に追加
	lines.push_back( new LINE ) ;
	lines[0]->pos1X = 100 ; lines[0]->pos1Y = 150 ;	// 始点
	lines[0]->pos2X = 300 ; lines[0]->pos2Y = 150 ;	// 終点

	// 配列に追加
	lines.push_back( new LINE ) ;
	lines[1]->pos1X = 300 ; lines[1]->pos1Y = 250 ;	// 始点
	lines[1]->pos2X = 300 ; lines[1]->pos2Y = 150 ;	// 終点

	// 配列に追加
	lines.push_back( new LINE ) ;
	lines[2]->pos1X = 100 ; lines[2]->pos1Y = 250 ;	// 始点
	lines[2]->pos2X = 300 ; lines[2]->pos2Y = 250 ;	// 終点
	
	// 配列に追加
	lines.push_back( new LINE ) ;
	lines[3]->pos1X = 100 ; lines[3]->pos1Y = 250 ;	// 始点
	lines[3]->pos2X = 100 ; lines[3]->pos2Y = 150 ;	// 終点

	//+++++++++++++++++++++++++++++++++++++++++++++++++++
	// ここで各直線によって囲まれた四角形を見つけて
	// 矩形用の座標に格納したい
	//+++++++++++++++++++++++++++++++++++++++++++++++++++
	for( int i=0, n=lines.size(); i<n; ++i )
	{
		// 以下、どんなアルゴリズムになるのでしょう?

		//if( 直線に囲まれた四角形を見つけたなら )
		//{
		//	// 矩形の配列に追加します
		//	squares.push_back( new SQUARE ) ;
		//	// 矩形の座標をセットします
		//	squares[ squares.size() - 1 ]->pos1X = ? ;
		//	squares[ squares.size() - 1 ]->pos1Y = ? ;
		//	squares[ squares.size() - 1 ]->pos2X = ? ;
		//	squares[ squares.size() - 1 ]->pos2Y = ? ;
		//}
	}

	//+++++++++++++++++++++++++++++++++++++++++++++++++++
	// 画面表示する処理(矩形がなければ何も表示されない)
	//+++++++++++++++++++++++++++++++++++++++++++++++++++
	// 表示する文字色(白)で初期化
	int fontColor = GetColor( 255, 255, 255 ) ;
	// 表示位置(Y座標)を初期化
	int drawPosY = 0 ;
	// 表示する文字列を初期化
	string message ;
	for( int i=0, n=squares.size() ; i<n ; ++i )
	{
		// 表示位置を毎回30ピクセルずつ下に下げる
		drawPosY += 30 ;

		// 表示する文字列を設定する
		// (x,y)(x,y)の形にする
		message = "(" + IntToString( squares[i]->pos1X ) + ", " + IntToString( squares[i]->pos1Y ) + ")" +
				  "(" + IntToString( squares[i]->pos2X ) + ", " + IntToString( squares[i]->pos2Y ) + ")";
		
		// 画面に表示する(あとでDrawStringToHandleに書き換えるべき)
		DrawString( 240 , drawPosY , message.c_str() , fontColor ); 
	}

	// キー入力待ち
	WaitKey() ;

	//+++++++++++++++++++++++++++++++++++++++++++++++++++
	// 構造体の開放
	//+++++++++++++++++++++++++++++++++++++++++++++++++++
	for( int i=0, n=lines.size(); i<n; ++i )
	{
		delete lines[i] ;
	}
	// 念のため配列自体もクリア
	lines.clear() ;

	// DXライブラリ使用の終了処理
	DxLib_End() ;
	// ソフトの終了
	return 0 ;				
}

//+++++++++++++++++++++++++++++++++++++++++++++++++++
// int型を文字列に変換する関数
//+++++++++++++++++++++++++++++++++++++++++++++++++++
string IntToString( const int & number )
{
	stringstream ss ;
	ss << number ;
	
	return ss.str() ;
}


アバター
みけCAT
記事: 6216
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: (C++)直線に囲まれた矩形の座標を知りたい

#2

投稿記事 by みけCAT » 5年前

「直線」(線分?)の最大の本数は、どのくらいを想定していますか?
100本?1000本?100000本?10000000本?それとももっとですか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

たいちう
記事: 418
登録日時: 9年前

Re: (C++)直線に囲まれた矩形の座標を知りたい

#3

投稿記事 by たいちう » 5年前

> 私がやりたいことは、任意の始点、終点を持つ直線が、任意の本数だけある場合、
> これらに囲まれた矩形の座標を求めたいというものです。
> ...
> ※ここで扱う直線は以下のとおりです。
>  ななめの線は無いこと(すべて、X軸方向(またはY軸方向)に水平(または垂直))
> ...
> また、矩形の座標も、起点と対角点を構造体で管理したいと考えており、
> プログラム内でどうにかして、直線の座標をもとに、これらに囲まれた全ての矩形の座標を知りたいのですが、
> このときのアルゴリズムが思いつかないので、お聞きしたいのです。


数学の用語が怪しいので、何をしたいのか確信が持てませんが、以下の解釈であってますか?

『縦横の線分で区切られた領域が1つある。
矩形(長方形)がいくつかある。
領域内の矩形を全て求めたい。』

ちなみに、矩形「(0,0)-(1,0)-(1,1)-(0,1)-(0,0)」は、
領域「(0,0)-(2,0)-(2,2)-(0,2)-(0,0)」に対して、領域内とみなしますか?

アバター
みけCAT
記事: 6216
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: (C++)直線に囲まれた矩形の座標を知りたい

#4

投稿記事 by みけCAT » 5年前

問題を整理すると、このような形式でいいでしょうか?
簡単に言うと、「線分のデータを入力する→矩形のデータを出力する」ということです。

コード:

線分の情報が与えられる。
その線分によって囲まれる矩形全ての座標を出力せよ。

入力
1行目に線分の個数nが与えられる。
2行目からn+1行目までは、それぞれx1,y1,x2,y2が
この順番で半角空白区切りで与えられ、
この線分が(x1,y1)と(x2,y2)を結んでいることを示す。

制限
n,x1,y1,x2,y2は全て非負整数
各線分について、x1==x2またはy1==y2

出力
1行目に線分で囲まれる矩形の数mを出力せよ。
2行目からm+1行目までは、それぞれxx1,yy1,xx2,yy2を
この順番で1個の半角空白区切りで出力せよ。
これは、この矩形の左上の頂点の座標が(xx1,yy1)、
右下の頂点の座標が(xx2,yy2)であることを表す。
各行について、xx1<=xx2、yy1<=yy2を満たしていなければならない。
この条件を満たしていれば、矩形はどのような順番で出力してもよい。

サンプル入力1
4
100 150 300 150
300 250 300 150
100 250 300 250
100 250 100 150

サンプル出力1
1
100 150 300 250
この問題でいい場合、
入力A

コード:

5
10 10 100 10
100 10 100 100
10 10 10 100
10 100 50 100
50 100 100 100
入力B

コード:

5
10 10 100 10
100 10 100 100
10 10 10 100
10 100 50 100
51 100 100 100
入力C

コード:

5
10 10 100 10
100 10 100 100
10 10 10 100
10 100 51 100
50 100 100 100
このそれぞれに対する出力はどうなってほしいですか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

Ketty

Re: (C++)直線に囲まれた矩形の座標を知りたい

#5

投稿記事 by Ketty » 5年前

>みけCAT さん
ご返信くださりありがとうございます。
最大本数は、100本程度で、1本の長さは、最大でも500pxです。
ですので、多少パフォーマンス的に難があるアルゴリズムでも分かりすいものがよいなぁと考えています。

>たいちろうさん
ご返信くださりありがとうございます。以下に回答します。
ご質問してくださった内容に対して、私の理解に誤りがあればご指摘ください。

・「縦横の線分で区切られた領域が1つある」
 ⇒これは、スクリーン(DXライブラリによって生成されるウィンドウ)のことだと思うので、1つで間違いありません。
・「矩形(長方形)がいくつかある」
 ⇒はい、スクリーン内に0個もしくは任意の数だけあります。
・「領域内の矩形を全て求めたい。」
 ⇒そうです。スクリーン内のすべての矩形について、求めたいです。
・矩形「(0,0)-(1,0)-(1,1)-(0,1)-(0,0)」は、領域「(0,0)-(2,0)-(2,2)-(0,2)-(0,0)」に対して、領域内とみなしますか?
 ⇒これは、四角形の中に四角形がある場合についてのご質問だという認識ですが、
  回答としましては、できれば領域内とみなしたい(矩形の1つとしてカウントはしたくない)と考えています。

アバター
みけCAT
記事: 6216
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: (C++)直線に囲まれた矩形の座標を知りたい

#6

投稿記事 by みけCAT » 5年前

入力D

コード:

8
10 10 10 100
10 100 100 100
100 100 100 10
100 10 10 10
50 50 150 50
150 50 150 150
150 150 50 150
50 150 50 50
に対する出力はどうなりますか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

Ketty

Re: (C++)直線に囲まれた矩形の座標を知りたい

#7

投稿記事 by Ketty » 5年前

>みけCAT さん
ご返信くださりありがとうございます。
はい、問題の認識としては、その通りです。
入力について、「半角空白区切り」というのは仕様としてはありませんが、
プログラム内で動的にx1,y1,x2,y2がこの順番で与えられるので、お書きくださった内容で問題ありません。
制限、出力についても、その通りで間違いありません。

>このそれぞれに対する出力はどうなってほしいですか?
間違いのないように書くために吟味しますので少々お時間ください。
次の書き込みで回答いたします。

たいちう
記事: 418
登録日時: 9年前

Re: (C++)直線に囲まれた矩形の座標を知りたい

#8

投稿記事 by たいちう » 5年前

No.4のみけCATさんの解釈が正しいとすると、No.3の私の解釈は全く間違っていましたね。
もっと複雑な形状の領域を私は考えていました。

静観します。

Ketty

Re: (C++)直線に囲まれた矩形の座標を知りたい

#9

投稿記事 by Ketty » 5年前

>みけCAT さん
ご提示いただいた入力パターンについて、希望する出力は以下のとおりです。
 
出力A

コード:

10 10 100 100
出力B

コード:

10 10 50 100
51 10 100 100
出力C

コード:

10 10 100 100
出力D(2つあり、どちらでもよいです)

コード:

10 10 50 100
50 10 100 50
50 50 150 150
または

コード:

10 10 100 50
10 50 50 100
50 50 150 150
以上です。

>たいちうさん
すみません。私の質問の仕方が誤解をまねくような質問の仕方であったと思います。
貴重なお時間を割いてくださったのに申し訳ありません。謝罪いたします。
ご協力してくださり、ありがとうございました。

アバター
みけCAT
記事: 6216
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: (C++)直線に囲まれた矩形の座標を知りたい

#10

投稿記事 by みけCAT » 5年前

ありがとうございます。
とりあえず図示してみました。
これから考えましょう。
添付ファイル
Ketty_output_sample1.png
出力例の図示
Ketty_output_sample1.png (3.53 KiB) 閲覧数: 2324 回
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

Ketty

Re: (C++)直線に囲まれた矩形の座標を知りたい

#11

投稿記事 by Ketty » 5年前

>みけCAT さん
こちらこそありがとうございます。
分かりやすい図まで作っていただいてすみません。(私が提示させていただくべきでした・・・)

私もいまいちど、考えてみます。

アバター
usao
記事: 1552
登録日時: 6年前

Re: (C++)直線に囲まれた矩形の座標を知りたい

#12

投稿記事 by usao » 5年前

「囲まれた矩形」とは何なのか…
説明だけ読むと 4辺が必要に思うけど
やりとりされている例を見るに,別に4辺そろってなくても矩形とみなすのですよね.
どんな条件を満たしたら矩形になるのだろうか.
例えば,2辺しかなかったらどうなんだろう? (心の目で見ればこれらも矩形が見えなくもない)

コード:

2
10 10 10 100
10 100 100 100
だとか
2
10 10 10 100
50 50 50 150
とかいう場合は…?
追記:
あ,でも例Dの絵で右下とか左上には矩形が無いから 「角が1個ではダメ」 というルールっぽいですね.
(平行線だけがある場合は今のところ不明ですが)
それはそうと,何でこの例Dはこの2パターンだけが正解なんでしょう?
大きい四角形2個が重なっているとき,一方の側を大きく取って他方の側がその割を食って細切れになってる
(…という表現で伝わるかな?)んだろうけど,
2個の大きい四角形の立場が逆転した場合(出力例の絵を180°回転したようなの)もあり得る気がするのですが.

コード:

こんなのは…?
4
0 0 100 0
0 0 0 90
100 10 100 100
100 100 0 100

アバター
Ketty
記事: 101
登録日時: 5年前

Re: (C++)直線に囲まれた矩形の座標を知りたい

#13

投稿記事 by Ketty » 5年前

>usao さん
お返事くださりありがとうございます。

>別に4辺そろってなくても矩形とみなすのですよね.
いいえ、4辺がそろっているものを矩形とみなします。
また、辺がとぎれているものは矩形と扱いたくないです。

>2個の大きい四角形の立場が逆転した場合(出力例の絵を180°回転したようなの)もあり得る気がするのですが
なるほど、盲点でした。おっしゃるとおりです。
Dの出力は4パターンありえますね。

usaoさんがみつけてくれたパターンも踏まえまして、
図を添付させていただきます。
(勝手ながら、みけCATさんが作ってくださった図を改良しております。さしつかえございましたらご指摘ください。)
添付ファイル
Ketty_output_sample2.png
期待する出力パターンです。
Ketty_output_sample2.png (8.03 KiB) 閲覧数: 2139 回

アバター
Ketty
記事: 101
登録日時: 5年前

Re: (C++)直線に囲まれた矩形の座標を知りたい

#14

投稿記事 by Ketty » 5年前

上記までで、私の知識不足ゆえ、用語を誤っている箇所がございました。
「直線」と書いていたのは、正しくは「線分」です。

また、私がなかなかやりたいことのイメージを説明しづらく、
ご協力くださる方々の混乱を招いてしまうので、改めて図を用意させていただきました。

下図のように、いろんな線分(斜めは無し)があって、
4辺がとぎれることなくそろっている矩形(赤い部分)を知りたい、というものです。
赤い部分を表すために必要な座標を知りたいのです。

他にも説明で至らないことがございましたらおっしゃっていただけると助かります。
添付ファイル
1.png
イメージ図です(赤い部分を表すための座標を知りたいです)。
1.png (1.04 KiB) 閲覧数: 2137 回

アバター
みけCAT
記事: 6216
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: (C++)直線に囲まれた矩形の座標を知りたい

#15

投稿記事 by みけCAT » 5年前

Ketty さんが書きました:4辺がとぎれることなくそろっている矩形(赤い部分)を知りたい、というものです。
上の入力Bでは(50,100)-(51,100)がつながっていませんが、この説明だとこれは矩形ではないのではないでしょうか?

また、入力Dに対し、

コード:

3
10 10 50 100
50 10 100 150
100 50 150 150
という出力は正しいでしょうか?
Ketty_D_sample_candidate.png
この出力を図示したもの
Ketty_D_sample_candidate.png (1.16 KiB) 閲覧数: 2133 回
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6216
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: (C++)直線に囲まれた矩形の座標を知りたい

#16

投稿記事 by みけCAT » 5年前

アルゴリズムとしては、

1. 線分を座標圧縮する(座標の値が0~1000くらいなら必要ない)
2. 線分をグリッド上に描く
このとき、1を行ったあとの座標が0~1000なら、グリッドは-1~1001の範囲を用意する(周り1マスを空ける)のが大切。
また、上記Bのケースに対応するため、線分の座標を2倍して描画するとよい。
3. 2で空けたマスの上(例:左上)から、線分が描かれていないマスに幅優先探索で印を付ける(ペイントの「塗りつぶし」みたいなイメージ)
4. 印が付いていない場所で、線分が描かれていない部分(すなわち、矩形で埋めるべき部分)を矩形に分割する

という案があります。4の具体的な手順は後で考えます。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
Ketty
記事: 101
登録日時: 5年前

Re: (C++)直線に囲まれた矩形の座標を知りたい

#17

投稿記事 by Ketty » 5年前

>みけCAT さん
たびたび貴重なお時間を割いてご協力くださり、ありがとうございますm(__)m

>上の入力Bでは(50,100)-(51,100)がつながっていませんが、この説明だとこれは矩形ではないのではないでしょうか?
はい、そこに矩形は無いものとしたいです。
Bの期待する出力は、二つの矩形が中央の線分(1px)で区切られているという考えです。

>また、入力Dに対し、
な、なるほど。これも盲点でした。
おっしゃるとおり、その出力も正しいです。

ご教授いただいたアルゴリズム1~3(4)に対し、理解を深めたいと思います。
大変申し訳ないのですが、しばらくお時間をください。

アバター
みけCAT
記事: 6216
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: (C++)直線に囲まれた矩形の座標を知りたい

#18

投稿記事 by みけCAT » 5年前

Ketty さんが書きました:>上の入力Bでは(50,100)-(51,100)がつながっていませんが、この説明だとこれは矩形ではないのではないでしょうか?
はい、そこに矩形は無いものとしたいです。
Bの期待する出力は、二つの矩形が中央の線分(1px)で区切られているという考えです。
申し訳ありませんが、よくわかりません。
「中央の線分(1px)」とはなんですか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6216
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: (C++)直線に囲まれた矩形の座標を知りたい

#19

投稿記事 by みけCAT » 5年前

入力

コード:

12
150 100 150 150
150 150 100 150
100 150 100 200
100 200 150 200
150 200 150 250
150 250 200 250
200 250 200 200
200 200 250 200
250 200 250 150
250 150 200 150
200 150 200 100
200 100 150 100
に対する出力はどうなりますか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
Ketty
記事: 101
登録日時: 5年前

Re: (C++)直線に囲まれた矩形の座標を知りたい

#20

投稿記事 by Ketty » 5年前

>みけCAT さん

>「中央の線分(1px)」とはなんですか?
失礼しました。50px目と51px目のすき間のことを指したつもりですが、
私の表現が間違えているのだと思いました。

言いたいこととしては、Bの出力の期待値としては、
みけCATさんにご提示いただいた図で言いますと、
赤色と緑色の間の1pxの隙間は矩形として扱いたくないということです。

また、No.19でご提示いただいた件につきまして、回答させていただきます。
領域と領域の区切り方によってはもっと多くのパターンをつくれるはずですが、
区切れる数としては3つしかない見込みですので、3パターンを提示させていただきます。
(添付の図と合わせてご覧ください)

パターン1

コード:

100 150 150 200 ・・・赤色の部分
150 100 200 150 ・・・黄色の部分
200 150 250 200 ・・・水色の部分
150 200 200 250 ・・・緑色の部分
150 150 200 200 ・・・紫色の部分
パターン2

コード:

100 150 200 200 ・・・赤色の部分
150 100 200 150 ・・・黄色の部分
200 150 250 200 ・・・水色の部分
150 200 200 250 ・・・緑色の部分
パターン3

コード:

100 150 250 200 ・・・赤色の部分
150 100 200 150 ・・・黄色の部分
150 200 200 250 ・・・緑色の部分
添付ファイル
パターン例.png
No.19の出力パターン例です
パターン例.png (15.38 KiB) 閲覧数: 2092 回

アバター
みけCAT
記事: 6216
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: (C++)直線に囲まれた矩形の座標を知りたい

#21

投稿記事 by みけCAT » 5年前

もう一度確認しますが、
Ketty さんが書きました: 下図のように、いろんな線分(斜めは無し)があって、
4辺がとぎれることなくそろっている矩形(赤い部分)を知りたい、というものです。
赤い部分を表すために必要な座標を知りたいのです。
という条件に対し、Bは1辺が途切れているので矩形ではない(矩形は0個)のではないか、ということです。
もし入力Bに対しこの出力が欲しいのであれば、No: 16のアルゴリズムは間違いになると思います。

また、入力F

コード:

5
10 10 100 10
100 10 100 100
10 10 10 100
10 100 49 100
51 100 100 100
に対する出力はどうなりますか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
usao
記事: 1552
登録日時: 6年前

Re: (C++)直線に囲まれた矩形の座標を知りたい

#22

投稿記事 by usao » 5年前

オフトピック
だめだ,BもDも意味がわからん……

B:3辺しかない領域×2個が矩形として扱われるというルールが不明
D:2つの矩形が重なる領域を持つ場合に何がおこるのかが不明(緑とか赤に分割される特殊ルールが謎過ぎる)

アバター
みけCAT
記事: 6216
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: (C++)直線に囲まれた矩形の座標を知りたい

#23

投稿記事 by みけCAT » 5年前

No:19 のデータ(これを入力Eとします)に対する出力から考えると、使う矩形の数は最小でなくてもいいということですね?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
Ketty
記事: 101
登録日時: 5年前

Re: (C++)直線に囲まれた矩形の座標を知りたい

#24

投稿記事 by Ketty » 5年前

>みけCATさん、usaoさん
大変失礼しました!私が間違っていました。
Bは、矩形なしです!

(存在しない線分を頭の中で無意識に補完してしまったまま、気づかずに回答し続けておりました(><)!!!!)
もうなんとお詫びすればよいやら・・・きっとこれがみなさんを混乱させてしまった最大の原因だと思います。
申し訳ありませんでした。

>みけCATさん
>No:19 のデータ(これを入力Eとします)に対する出力から考えると、使う矩形の数は最小でなくてもいいということですね?
はい、そうです。最小でなくてもかまわないです。

また、Fの出力も同様で、
矩形なしです。
(さらなる間違いをおかさぬように、こちらも図を作り、添付させていただきました)
添付ファイル
F.png
Fは矩形なしです(Bも矩形なしでした)
F.png (8.77 KiB) 閲覧数: 2070 回

アバター
みけCAT
記事: 6216
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: (C++)直線に囲まれた矩形の座標を知りたい

#25

投稿記事 by みけCAT » 5年前

わかりました。
No: 16の方針で具体的なことを考えてみます。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
Ketty
記事: 101
登録日時: 5年前

Re: (C++)直線に囲まれた矩形の座標を知りたい

#26

投稿記事 by Ketty » 5年前

>みけCATさん
はい、重ね重ねありがとうございます。
私も先のアルゴリズムの理解とともに、別のやり方も模索してみます。

アバター
みけCAT
記事: 6216
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: (C++)直線に囲まれた矩形の座標を知りたい

#27

投稿記事 by みけCAT » 5年前

No: 16の4として、「左上から順番に見ていき、矩形で埋めるべき場所だったら、
できるだけ広い幅で、その幅でできるだけ大きい高さで矩形を置く」という貪欲法を採用し、実装してみました。
► スポイラーを表示
添付ファイルには、
  • このプログラム
  • ランダムテストケースジェネレータ
  • サンプル入力ファイル
  • ビジュアライザ
が入っています。
添付ファイル
get_kukei.zip
実装したファイル
(80.69 KiB) ダウンロード数: 21 回
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
Ketty
記事: 101
登録日時: 5年前

Re: (C++)直線に囲まれた矩形の座標を知りたい

#28

投稿記事 by Ketty » 5年前

>みけCAT さん
サンプルソースを作ってくださって、ありがとうございます。
ダウンロードさせていただきました。

恐れ入りますが、まだご提示くださったアルゴリズムの理解もできておりませんので、
いましばらくお時間くださいm(__)m

ちなみに、私が今考えているアルゴリズムは、以下のとおりで、
ロジックの実現可能性と、出力の妥当性の検証をかねてプログラムを作っている最中です。

1.交点を含むすべての座標と、そこから延びる全ての線分を求める
2.すべての座標について、ひとつずつ、以下の手順に従ってルート探索する
  2-1.座標Aをスタート地点とする
  2-2.座標Aから延びる線分A-1をたよりに次に進む座標B~を求める
   ※すでにたどった座標にもどらないようにする(後戻りしない)
   ※途中で行き止まりになった場合は、線分A-2をたよりに・・・を繰り返す
  2-3.上記を繰り返し、座標Aまで戻ってこれたら、この座標と中継した座標を記憶して終わり
   ※つまり、この座標を起点にして、線分に囲まれた領域を作ることができるはず

3.2の結果から、線分に囲まれた領域を全て求める
4.3の領域から、重複する矩形、またはこの領域内の矩形を除去する

完成したらこれもここにアップさせていただきます。
(効率的とは言えないかもしれませんが)

アバター
usao
記事: 1552
登録日時: 6年前

Re: (C++)直線に囲まれた矩形の座標を知りたい

#29

投稿記事 by usao » 5年前

(お二人の間では共通認識が得られているようですので,わざわざ口出す必要性もないとは思うのですが…)

矩形が分割されるルールがきちんと説明されていないような気がします.
例えば,例Aでは単一の矩形を正解とされていますが,これを適当に4つとか5つとかに細切れにした結果
(細切れにされたものは全て矩形形状であって,これらを全て合わせると正解とされている1つの矩形になる場合)
は,正解なのでしょうか?
(→ダメだとしたら,「切っていい場合」と「切り方のルール」が存在するハズ.)
オフトピック
もし,適当に縦横に領域を切りまくってもOKという話であるならば,
与えられた線分群を全て直線(長さ無限)に置き換えて,
場をサイズ不規則なグリッド状に分割して考えてしまえば,効率は最悪ですが,アルゴリズムは簡単ですよね.

アバター
Ketty
記事: 101
登録日時: 5年前

Re: (C++)直線に囲まれた矩形の座標を知りたい

#30

投稿記事 by Ketty » 5年前

>usao さん
ご指摘くださりありがとうございますm(__)m
おっしゃるとおりですね。

結論から申しますと、入力の線分から求められる矩形領域について、何個分割してもよいし、分割しなくてもよいです。
ルールとしては、
矩形とする領域の起点(左上)と対角点(右下)は、必ず、入力の線分の始点または終点または線分同士の交点となる、です。
(それ以外の座標に点を置いてはならない)

ですので、例Aについては、赤の矩形と緑の矩形、または、赤と緑がくっついたひとつの大きな矩形としてもよいです。
(例Aでは、多くても赤と緑の2つまでしか分割できないです)

他にも私の至らない記述があるかもしれません。
お気づきになられましたらバシバシご指摘ください。

閉鎖

“C言語何でも質問掲示板” へ戻る