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

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

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

#1

投稿記事 by Ketty » 10年前

こんにちは。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
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

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

#2

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

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

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

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

#3

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

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


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

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

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

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

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

#4

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

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

コード:

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

入力
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 » 10年前

>みけ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
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

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

#6

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

入力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 » 10年前

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

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

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

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

#8

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

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

静観します。

Ketty

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

#9

投稿記事 by Ketty » 10年前

>みけ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
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

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

#10

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

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

Ketty

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

#11

投稿記事 by Ketty » 10年前

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

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

アバター
usao
記事: 1887
登録日時: 11年前

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

#12

投稿記事 by usao » 10年前

「囲まれた矩形」とは何なのか…
説明だけ読むと 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
記事: 102
登録日時: 10年前

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

#13

投稿記事 by Ketty » 10年前

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

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

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

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

アバター
Ketty
記事: 102
登録日時: 10年前

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

#14

投稿記事 by Ketty » 10年前

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

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

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

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

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

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

#15

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

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) 閲覧数: 14412 回
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

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

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

#16

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

アルゴリズムとしては、

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

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

アバター
Ketty
記事: 102
登録日時: 10年前

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

#17

投稿記事 by Ketty » 10年前

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

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

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

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

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

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

#18

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

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

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

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

#19

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

入力

コード:

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
記事: 102
登録日時: 10年前

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

#20

投稿記事 by Ketty » 10年前

>みけ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) 閲覧数: 14371 回

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

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

#21

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

もう一度確認しますが、
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
記事: 1887
登録日時: 11年前

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

#22

投稿記事 by usao » 10年前

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

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

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

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

#23

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

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

アバター
Ketty
記事: 102
登録日時: 10年前

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

#24

投稿記事 by Ketty » 10年前

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

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

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

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

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

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

#25

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

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

アバター
Ketty
記事: 102
登録日時: 10年前

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

#26

投稿記事 by Ketty » 10年前

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

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

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

#27

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

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

アバター
Ketty
記事: 102
登録日時: 10年前

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

#28

投稿記事 by Ketty » 10年前

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

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

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

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

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

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

アバター
usao
記事: 1887
登録日時: 11年前

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

#29

投稿記事 by usao » 10年前

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

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

アバター
Ketty
記事: 102
登録日時: 10年前

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

#30

投稿記事 by Ketty » 10年前

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

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

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

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

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

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

#31

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

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

ですので、例Aについては、赤の矩形と緑の矩形、または、赤と緑がくっついたひとつの大きな矩形としてもよいです。
(例Aでは、多くても赤と緑の2つまでしか分割できないです)
申し訳ありません。
私のプログラムは、このルールに当てはめると、例えば

コード:

8
50 100 100 100
100 100 100 50
100 50 150 50
150 50 150 100
150 100 200 100
200 100 200 150
200 150 50 150
50 150 50 100
という入力(入力Gとする)に対し、間違った出力を返します。

また、このルールにおいて、入力H

コード:

8
50 50 50 100
50 100 100 100
100 100 100 150
100 150 50 150
50 150 50 200
50 200 150 200
150 200 150 50
150 50 50 50
に対する正しい出力を教えていただけますか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
usao
記事: 1887
登録日時: 11年前

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

#32

投稿記事 by usao » 10年前

>矩形とする領域の起点(左上)と対角点(右下)は、必ず、入力の線分の始点または終点または線分同士の交点となる、です。
>(それ以外の座標に点を置いてはならない)

例えば,
No10で添付されている画像での Dの出力例2 の赤い矩形を見ると
左上の座標は縦の線分の途中にあって,この条件を満たしていないように見えますが,どうなのでしょう?

また,矩形の4つの角のうち,残りの2点(右上と左下)に関してはこのルールから逃れられるということなのでしょうか?
(おそらくそういう意味ではないのだと思いますが)
オフトピック
別に重箱の隅をつつきたいわけではないのですが,
ここらへんのところがアバウトなままだと困るんじゃないかな,と.
今までの例を見た感じだと,こんなことなのかなー? というのを書いてみます.

(1)まずは,入力線分群によって4辺が完全に作られる矩形群を得る.全て得る.
(2) (1)の結果では,重なっているやつがいるのが問題になるので,それを以下の手順でなんとかする.

(2-1)重なっている2つの矩形A,Bについて,とりあえず一方の側(ここではAとする)はそのまま回答として採択する.
(2-2)他方の側Bについて,採択された側Aの矩形の頂点のうちBの内部に位置する頂点群を求め,
  それら頂点群から水平および垂直方向に(Aの外側に向かう方向に)Bの辺にぶつかる位置まで線を引っ張る.
  Bの領域は,Aの辺群と,この操作によって新たにひかれた線群とによって,複数のサブ矩形領域に分けられることになる.
(2-3)分けられたサブ領域のうち,Aに含まれるものは不要(既に回答Aに含まれている)なので除外する.
(2-4)残ったサブ領域群をBの代わりの回答とする.
  ただし,サブ領域群のいくつかを連結した結果も矩形となるのであれば,
  連結されたサブ領域群の代わりに,連結結果矩形の側を回答として用いても良い.

ただし,実際には,(1)の時点で 3つ以上の複数の矩形が重なってたりするかもしれないので,
(2-1)~(2-4)の結果をすぐに「回答」とするのではなくて,
元の母集団(矩形集合)に書き戻し,これ((2-1)~(2-4))を,重なっている矩形が存在しなくなるまでやる必要があるんだと思う.
(Bは,(2-4)の回答矩形群で置き換えてもいいけど,Aの方はすぐには母集団から取り除けない.まだ他の矩形と重なっているかもしれないので.)

アバター
Ketty
記事: 102
登録日時: 10年前

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

#33

投稿記事 by Ketty » 10年前

>みけCATさん
申し訳ありません。
usaoさんがご指摘くださっている内容通りなのですが、私の記述に誤りがありました。
度重なる誤記、謝罪いたします。

「または線分同士の交点となる」ではなく、ただしくは、「または"直線"同士の交点となる」です。
線分を伸ばしたものとの交点も、矩形の座標としてありです。

Hの解答例をあげさせていただきます。

また、大変お手数おかけすることとは思いますが、
差支えなければ、ダウンロードさせていただいたサンプルソースの使い方をご教授願えますでしょうか?
(私の使い方や認識に誤りがあるかもしれませんので、その場合はご指摘いただけると助かります。)

visualiser.htmlについてなのですが、
1)入力(線分)のtextareaに入力したあと、表示ボタンをクリックすると、
  その上部に線分がグラフィカルに表示されるのですが、
  出力(矩形)のtextareaには何も表示されないのですが、どのような操作をすればよいのでしょうか?
 
2)矩形を塗るのに使用する色のtextareaはどのように使うのでしょうか?
  選択した色で上部のグラフィカル領域の矩形の面積が塗りつぶされるのかなと思ってるのですが、
  その選択の方法が分かりません。
  rgb(255,0,0)のような文字列をクリックしても反応がなく、矩形は白いままなので悩んでおります。

※ブラウザは、ChromeとIE10の両方で試しました。

>usaoさん
ご指摘くださり、ありがとうございます。
上記に私の誤記について書きましたのでよろしければご確認ください。

>ここらへんのところがアバウトなままだと困るんじゃないかな,と.
はい、正しい仕様を自分で説明できないと困りますので、ご指摘は大変ありがたいです。

>今までの例を見た感じだと,こんなことなのかなー? というのを書いてみます.
ありがとうございます。
まだ細かい部分まで読解できておりませんが、おそらくご提示いただいた内容で、
私の希望する出力は実現できると思われます。
添付ファイル
Hの解答例.png
Hの解答例.png (1.53 KiB) 閲覧数: 13470 回

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

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

#34

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

Ketty さんが書きました:「または線分同士の交点となる」ではなく、ただしくは、「または"直線"同士の交点となる」です。
線分を伸ばしたものとの交点も、矩形の座標としてありです。
わかりました。それでしたら、入力Gに対する自分のプログラムの出力

コード:

3
100 50 150 150
50 100 100 150
150 100 200 150
も条件を満たしそうですね。
Ketty さんが書きました:visualiser.htmlについてなのですが、
1)入力(線分)のtextareaに入力したあと、表示ボタンをクリックすると、
  その上部に線分がグラフィカルに表示されるのですが、
  出力(矩形)のtextareaには何も表示されないのですが、どのような操作をすればよいのでしょうか?
visualiser.html自体には矩形分割の計算機能はありません。

ビジュアライザの使い方
1. 「入力(線分)」の入力欄にNo: 4の形式の入力データを貼り付ける
2. 「出力(矩形)」の入力欄にNo: 4の形式の出力データを貼り付ける
3. 必要に応じて「設定」の「拡大率」を調整する
4. 「表示」ボタンを押すと、上に線分と矩形が表示される
5. ブラウザが対応していれば、画像を右クリックして「名前をつけて画像を保存」(または、それに相当する操作)で保存できる
Ketty さんが書きました:2)矩形を塗るのに使用する色のtextareaはどのように使うのでしょうか?
  選択した色で上部のグラフィカル領域の矩形の面積が塗りつぶされるのかなと思ってるのですが、
  その選択の方法が分かりません。
  rgb(255,0,0)のような文字列をクリックしても反応がなく、矩形は白いままなので悩んでおります。
HTML5のcanvasのコンテキストのfillStyleに代入する文字列をそのまま1行ごとに指定します。
出力データで指定された順番に、ここで指定した色を上から1個ずつ使用して矩形を塗っていきます。
一番下の色まで使ってしまった場合、一番上の色に戻ってまた順番に塗っていきます。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
Ketty
記事: 102
登録日時: 10年前

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

#35

投稿記事 by Ketty » 10年前

>みけCAT さん
ヴィジュアライザーの使い方をご教授くださりありがとうございました。
なるほど、これはとても便利ですね。重ね重ねありがとうございます。

また、遅ればせながら、
作ってくださった矩形算出プログラムが正しく動作することを確認いたしました。
私の期待する出力のとおりでしたので、その旨ご報告させていただきます。

みけCATさんの作ってくださったプログラムをそのまま、
No.1で投稿した私のDXライブラリ用のプロジェクトに移植しましたので、一応ここにあげさせていただきます。
(中身はまるまるみけCATさんの実装なので、わざわざあげる意味はないのかもしれませんが、誰かの役に立つかも)

コード:

#pragma warning(disable:4996)	// 警告を消します
#pragma warning(disable:4146)	// 警告を消します
#include "DxLib.h"
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <sstream>

using namespace std ;

//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 各種構造体
//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 線分と矩形を表す構造体
struct LINE {
	int pos1X,pos1Y,pos2X,pos2Y;
	LINE(): pos1X(0),pos1Y(0),pos2X(0),pos2Y(0) {}
	LINE(int sx,int sy,int dx,int dy): pos1X(sx),pos1Y(sy),pos2X(dx),pos2Y(dy) {}
};

struct SQUARE {
	int pos1X,pos1Y,pos2X,pos2Y;
	SQUARE(): pos1X(0),pos1Y(0),pos2X(0),pos2Y(0) {}
	SQUARE(int sx,int sy,int dx,int dy): pos1X(sx),pos1Y(sy),pos2X(dx),pos2Y(dy) {}
};

// 座標を表す構造体
struct POSITION {
	int x,y;
	POSITION(): x(0),y(0) {}
	POSITION(int ix,int iy): x(ix),y(iy) {}
};

//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 各種クラス
//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 擬似的な二次元配列を動的に確保するためのクラス
template<class T>
class virtual_2d_array {
	T* buffer;
	size_t x_size,y_size;
	public:
		virtual_2d_array() {
			buffer=new T[1];
			x_size=y_size=1;
		}
		~virtual_2d_array() {delete[] buffer;}
		// 要素数を[y][x]に指定する
		void resize(size_t y,size_t x) {
			delete[] buffer;
			buffer=new T[x*y];
			x_size=x;
			y_size=y;
		}
		virtual_2d_array(size_t y,size_t x) {
			buffer=new T[1];
			resize(y,x);
		}
		T* operator[](size_t idx) {return buffer+x_size*idx;}
		const T* operator[](size_t idx) const {return buffer+x_size*idx;}
		// 配列の要素全体を指定した値で埋める
		void fill_all(const T& value) {
			fill(buffer,buffer+x_size*y_size,value);
		}
};

// 二次元BITのクラス
class bit_2d {
	virtual_2d_array<int> bit2d_table;
	size_t bit_max_x,bit_max_y;

	void internal_add(int* array, size_t pos, int value) {
		pos++;
		while(pos<=bit_max_x) {
			array[pos-1]+=value;
			pos+=pos & (-pos);
		}
	}

	int internal_sum(const int* array, size_t pos) const {
		int sum=0;
		pos++;
		while(pos>0) {
			sum+=array[pos-1];
			pos-=pos & (-pos);
		}
		return sum;
	}

	public:
		// 初期化する
		void clear() {
			bit2d_table.fill_all(0);
		}
		// 要素数を設定する
		void resize(size_t y_size,size_t x_size) {
			bit2d_table.resize(y_size,x_size);
			bit_max_x=x_size;
			bit_max_y=y_size;
		}
		bit_2d(): bit_max_x(0),bit_max_y(0) {}
		bit_2d(size_t y_size,size_t x_size) {
			resize(y_size,x_size);
		}

		// (x,y)にvalueを加える
		void add(size_t x,size_t y,int value) {
			y++;
			while(y<=bit_max_y) {
				internal_add(bit2d_table[y-1],x,value);
				y+=y & (-y);
			}
		}

		// [0,x]×[0,y]の和を求める
		int sum(size_t x,size_t y) const {
			int sum=0;
			y++;
			while(y>0) {
				sum+=internal_sum(bit2d_table[y-1],x);
				y-=y & (-y);
			}
			return sum;
		}

		// [sx,dx)×[sy,dy)にvalueを塗る(いもす法相当)
		void add2(int sx,int sy,int dx,int dy,int value) {
			if(sx<0)sx=0;
			if(sy<0)sy=0;
			if(sx>=(int)bit_max_x || sy>=(int)bit_max_y)return;
			add(sx,sy,value);
			if(dx<(int)bit_max_x)add(dx,sy,-value);
			if(dy<(int)bit_max_y)add(sx,dy,-value);
			if(dx<(int)bit_max_x && dy<(int)bit_max_y)add(dx,dy,value);
		}

		// [sx,dx)×[sy,dy)の和を求める
		int sum2(int sx,int sy,int dx,int dy) const {
			int ret=0;
			dx--;dy--;
			if(dx<0 || dy<0)return 0;
			if(dx>=(int)bit_max_x)dx=bit_max_x-1;
			if(dy>=(int)bit_max_y)dy=bit_max_y-1;
			ret=sum(dx,dy);
			if(sx>0)ret-=sum(sx-1,dy);
			if(sy>0)ret-=sum(dx,sy-1);
			if(sx>0 && sy>0)ret+=sum(sx-1,sy-1);
			return ret;
		}
};

// 座標圧縮を行うクラス
class coord_compresser {
	int* coords;
	size_t coords_num;
	size_t buffer_num;
	public:
		// 座標を指定し、圧縮する
		void set_coords(const int* coord_array,size_t n) {
			if(n>buffer_num) {
				if(coords!=NULL)delete[] coords;
				coords=new int[n];
				buffer_num=n;
			}
			copy(coord_array,coord_array+n,coords);
			sort(coords,coords+n);
			coords_num=(int)(unique(coords,coords+n)-coords);
		}
		coord_compresser(): coords(NULL),coords_num(0),buffer_num(0) {}
		coord_compresser(const int* coord_array,size_t n) {
			coords=NULL;
			coords_num=0;
			buffer_num=-1;
			set_coords(coord_array,n);
		}
		~coord_compresser() {delete[] coords;}
		// 指定されたインデックスの座標を取得する
		int operator[](size_t idx) const {return coords[idx];}
		// 圧縮後の座標の数を取得する
		size_t size() const {return coords_num;}
		// 確保されたバッファのサイズを取得する
		size_t capacity() const {return buffer_num;}
		// 指定した座標の圧縮後のインデックスを取得する
		int indexOf(int coord) const {
			return (int)(lower_bound(coords,coords+coords_num,coord)-coords);
		}
};

// 線分で囲まれている場所を覆う矩形を見つける処理本体を行うクラス
class square_finder {
	// 何回も計算する時にいちいち再確保しなくていいように、メモリを使いまわすためメンバ変数で持つ
	virtual_2d_array<int> grid;
	coord_compresser coord_x,coord_y;
	bit_2d bit;
	int *coord_x_buf,*coord_y_buf;
	size_t buffer_size;
	public:
		square_finder(): coord_x_buf(NULL),coord_y_buf(NULL),buffer_size(0) {}
		~square_finder() {
			if(coord_x_buf!=NULL)delete[] coord_x_buf;
			if(coord_y_buf!=NULL)delete[] coord_y_buf;
		}
		// メモリの確保を行う
		void reserve(size_t size) {
			if(size>buffer_size) {
				if(coord_x_buf!=NULL)delete[] coord_x_buf;
				if(coord_y_buf!=NULL)delete[] coord_y_buf;
				buffer_size=size;
				coord_x_buf=new int[buffer_size*2];
				coord_y_buf=new int[buffer_size*2]; 
				grid.resize(buffer_size*4+1,buffer_size*4+1);
				bit.resize(buffer_size*2,buffer_size*2);
			}
		}
		vector<SQUARE*> get_squares(const vector<LINE*>& line);
};

//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 各種関数
//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 線分で囲まれている部分を適当な矩形に分割する
// 線分の数をNとして、O(N^2 log N)だと思う
std::vector<SQUARE*> square_finder::get_squares(const std::vector<LINE*>& line) {
	// 線分が無いなら、自明に矩形は存在しない
	if(line.empty())return std::vector<SQUARE*>();
	// 必要ならバッファの再確保を行う
	reserve(line.size());
	size_t n=line.size();
	// 座標圧縮の準備
	for(size_t i=0;i<n;i++) {
		if(line[i]->pos1X!=line[i]->pos2X && line[i]->pos1Y!=line[i]->pos2Y) {
			// 入力が無効(線分がナナメ)
			return std::vector<SQUARE*>();
		}
		coord_x_buf[i*2]=line[i]->pos1X;
		coord_x_buf[i*2+1]=line[i]->pos2X;
		coord_y_buf[i*2]=line[i]->pos1Y;
		coord_y_buf[i*2+1]=line[i]->pos2Y;
	}
	// 座標圧縮
	coord_x.set_coords(coord_x_buf,n*2);
	coord_y.set_coords(coord_y_buf,n*2);
	size_t x_size=coord_x.size();
	size_t y_size=coord_y.size();
	size_t grid_x_size=x_size*2+1;
	size_t grid_y_size=y_size*2+1;
	// いもす法でグリッド上に線分を描く
	grid.fill_all(0);
	// 線分を置く
	for(size_t i=0;i<n;i++) {
		LINE& l=*line[i];
		int sx=coord_x.indexOf(min(l.pos1X,l.pos2X))*2+1;
		int sy=coord_y.indexOf(min(l.pos1Y,l.pos2Y))*2+1;
		int dx=coord_x.indexOf(max(l.pos1X,l.pos2X))*2+1;
		int dy=coord_y.indexOf(max(l.pos1Y,l.pos2Y))*2+1;
		grid[sy][sx]++;
		grid[sy][dx+1]--;
		grid[dy+1][sx]--;
		grid[dy+1][dx+1]++;
	}
	// 累積和を取る
	for(size_t y=0;y<grid_y_size;y++) {
		for(size_t x=1;x<grid_x_size;x++)grid[y][x]+=grid[y][x-1];
	}
	for(size_t x=0;x<grid_x_size;x++) {
		for(size_t y=1;y<grid_y_size;y++)grid[y][x]+=grid[y-1][x];
	}
	// 幅優先探索で矩形ではない場所に印をつける
	std::queue<POSITION> search_queue;
	search_queue.push(POSITION(0,0));
	grid[0][0]=1;
	while(!search_queue.empty()) {
		static const int dx[4]={1,0,-1,0};
		static const int dy[4]={0,1,0,-1};
		POSITION now_coord=search_queue.front();
		search_queue.pop();
		for(int i=0;i<4;i++) {
			int nx=now_coord.x+dx[i];
			int ny=now_coord.y+dy[i];
			if(0<=nx && nx<(int)grid_x_size && 0<=ny && ny<(int)grid_y_size && grid[ny][nx]==0) {
				grid[ny][nx]=1;
				search_queue.push(POSITION(nx,ny));
			}
		}
	}
	// 印が付いていない場所について、二次元BITに値を足していく
	bit.clear();
	for(size_t y=0;y<y_size;y++) {
		for(size_t x=0;x<x_size;x++) {
			if(grid[y*2+2][x*2+2]==0)bit.add(x,y,1);
		}
	}
	// 二次元BITを用いて矩形を検出し、リストに挿入した後消す
	// 左上から右に順にスキャンし、貪欲に矩形を埋めていく
	std::vector<SQUARE*> squares;
	for(size_t y=0;y<y_size;y++) {
		for(size_t x=0;x<x_size;x++) {
			if(bit.sum2(x,y,x+1,y+1)==1) {
				size_t left,right;
				// x方向の二分探索
				left=x;right=x_size-1;
				while(left<=right) {
					size_t mid=(left+right)/2;
					if(bit.sum2(x,y,mid+1,y+1)==(int)(mid-x+1)) {
						left=mid+1;
					} else {
						right=mid-1;
					}
				}
				size_t dx=left-1;
				// y方向の二分探索
				left=y;right=y_size-1;
				while(left<=right) {
					size_t mid=(left+right)/2;
					if(bit.sum2(x,y,dx+1,mid+1)==(int)((dx-x+1)*(mid-y+1))) {
						left=mid+1;
					} else {
						right=mid-1;
					}
				}
				size_t dy=left-1;
				// 矩形を登録する
				squares.push_back(new SQUARE(coord_x[x],coord_y[y],coord_x[dx+1],coord_y[dy+1]));
				// BITから今登録した矩形に該当する部分を消す
				for(size_t y2=y;y2<=dy;y2++) {
					for(size_t x2=x;x2<=dx;x2++)bit.add(x2,y2,-1);
				}
			}
		}
	}
	return squares;
}
// int型を文字列に変換する関数
string IntToString( const int & number )
{
	stringstream ss ;
	ss << number ;
	
	return ss.str() ;
}
//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 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としておきます
	// 矩形を複数保持する配列
	std::vector<SQUARE*> squares(0) ;	// とりあえずサイズ0としておきます
	// 矩形を見つける処理本体クラス
	square_finder sf ;

	//+++++++++++++++++++++++++++++++++++++++++++++++++++
	// 線分を思いつくまま追加します
	// ※以下は、実験用に固定で追加しますが、
	//  本来は、長さ、本数、追加順が不定です
	//  斜めの線は無い、ということだけ決まっています
	//+++++++++++++++++++++++++++++++++++++++++++++++++++
	//// 線分を追加
	lines.push_back( new LINE( 100, 100, 300, 100 ) ) ;
	lines.push_back( new LINE( 300, 300, 300, 100 ) ) ;
	lines.push_back( new LINE( 100, 300, 300, 300 ) ) ;
	lines.push_back( new LINE( 100, 300, 100, 100 ) ) ;

	//+++++++++++++++++++++++++++++++++++++++++++++++++++
	// 矩形を算出する処理
	//+++++++++++++++++++++++++++++++++++++++++++++++++++
	int startTime = GetNowCount() ;

	squares = sf.get_squares( lines );
	int endTime = GetNowCount() ;

	//+++++++++++++++++++++++++++++++++++++++++++++++++++
	// 画面表示する処理
	//+++++++++++++++++++++++++++++++++++++++++++++++++++
	// 矩形を表示する
	for( int i=0, n=squares.size() ; i<n ; ++i )
	{
		DrawBox( squares[i]->pos1X, squares[i]->pos1Y, squares[i]->pos2X, squares[i]->pos2Y, GetColor( 255, 0, 0 ), TRUE ) ;
	}

	// 線分を表示する
	for( int i=0, n=lines.size() ; i<n ; ++i )
	{
		DrawLine( lines[i]->pos1X, lines[i]->pos1Y, lines[i]->pos2X, lines[i]->pos2Y, GetColor( 255, 255, 255 ) ) ;
	}

	// 処理時間を描画する
	string mes = "処理時間=" + IntToString( ( endTime - startTime ) / 1000 ) + "秒" ;
	DrawString( 0, 0, mes.c_str(), GetColor( 255, 255, 255 ) ) ;

	// メモリを解放する
	for( vector<LINE*>::iterator it=lines.begin();it!=lines.end();it++)
	{
		delete[] *it;
	}
	for( vector<SQUARE*>::iterator it=squares.begin();it!=squares.end();it++)
	{
		delete[] *it;
	}

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

	// DXライブラリ使用の終了処理
	DxLib_End() ;
	// ソフトの終了
	return 0 ;
}
※組み込む際に、「error C2371: 'COORD' : 再定義されています。異なる基本型です。」というエラーが出ましたので、
構造体COORDの名前をPOSITIONという別の名前に置換しております。

また、No.28に書かせていたいた、私のアルゴリズムですが、
>2.すべての座標について、ひとつずつ、以下の手順に従ってルート探索する
この部分で非常に処理コストがかかってしまうことが分かり、断念しました。
(私の環境でですが20本程度の線分で40秒以上かかってしまいました)

それに比べ、みけCATさんのやり方ですと、非常に高速でしたので、
これを使わせていただこうと思います。

アバター
Ketty
記事: 102
登録日時: 10年前

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

#36

投稿記事 by Ketty » 10年前

>みけCAT さん
現在、みけCATさんが考案してくださったアルゴリズムを理解しようとしているのですが、
以下、私の理解がおよびませんので、お手数ですがご教授願えないでしょうか?

>1. 線分を座標圧縮する(座標の値が0~1000くらいなら必要ない)
座標圧縮という言葉を今回初めて知りましたので、ネットで調べてみました。
(Google検索で3~4件程度しかヒットできず、その実態がなんなのか理解に苦しんでいるのですが、何やらプログラミング技術者のアルゴリズム試験かなにかで有名な設問であるかのような印象をうけました。)

お聞きしたいこととして、座標圧縮とは何なのでしょうか?
現在の私の認識では、「座標圧縮=座標を、処理の都合のために昇順(または降順)にソートすること」 と考えております。
みけCATさんが作ってくださったソースを見てそう解釈したのですが、私が不勉強なため、
誤って解析している場合がありますので、ご指摘くだされば幸いです。

また、「座標の値が0~1000くらいなら必要ない」というのは、
0~1000くらいなら、ソートしてもしなくても、今回は全体の処理速度的に大差がない、
あるいはソートするコストに対して、全体の処理コストへの見返りが少ない、という認識でよろしいでしょうか?

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

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

#37

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

Ketty さんが書きました:お聞きしたいこととして、座標圧縮とは何なのでしょうか?
座標圧縮とは、空間(1次元かもしれないし、2次元かもしれないし、より高次元かもしれない)上に
オブジェクト(区間、線分、矩形など)がいくつかあり、
座標の幅は大きい(-10^9~10^9など)がオブジェクトの数は少ない(数100~10000程度)時に有効なテクニックです。

オブジェクトに関連する座標(始点や終点など)の位置関係(大小)を保ったまま間隔を狭くすることにより、
座標の幅をオブジェクトの数の定数倍にでき、空間に対する走査がしやすくなります。
適当な例を考えてみると、実質的に意味のない空白が消え、考えないといけない面積が小さくなることがわかります。
zahyoassyuku_exsample.png
座標圧縮の例
zahyoassyuku_exsample.png (2.41 KiB) 閲覧数: 13394 回
座標をソートするのは、元の座標に対する圧縮後の座標を素早く求めるためです。
Ketty さんが書きました:また、「座標の値が0~1000くらいなら必要ない」というのは、
0~1000くらいなら、ソートしてもしなくても、今回は全体の処理速度的に大差がない、
あるいはソートするコストに対して、全体の処理コストへの見返りが少ない、という認識でよろしいでしょうか?
座標の値が0~1000くらいの整数である場合、
今回のアルゴリズムで使用する幅優先探索の対象の面積はだいたい1,000,000になり、1秒程度で処理できるということがわかります。
累積和はO(x座標の最大値×y座標の最大値)、
矩形を見つける処理もO(x座標の最大値×y座標の最大値×log(x座標の最大値)×log(y座標の最大値))
くらいなので、座標の最大値が1000くらいなら座標圧縮をしなくても実用的な速度で解が求まるということがわかります。
「必要ない」であって、「やっても意味がない」「やらないべき」ではないことに注意してください。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
Ketty
記事: 102
登録日時: 10年前

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

#38

投稿記事 by Ketty » 10年前

>みけCATさん

ご教授くださりありがとうございます。
なるほど、座標圧縮というのは、内部のオブジェクト同士の比率をたもったまま、全体の空間自体を縮小するイメージなのですね。
その結果、等倍で探索するよりも処理が高速になると。

おかげさまで、理解できました。
とても分かりやすいご説明を図まで用意して教えてくださり、ありがとうございました。

>「必要ない」であって、「やっても意味がない」「やらないべき」ではないことに注意してください。
座標圧縮した上での処理速度は、実際に入力される線分の大きさや座標の分布に依存するので、
果たして座標圧縮する甲斐があるかないかは、座標圧縮してみないことにはわからないということですね。
ご忠告くださりありがとうございます。

みけCATさんのご提示くださったアルゴリズムの理解ができましたので、
あとは(これまたみけCATさんがご提示くださった)プログラムを見ながら、コーディングのテクニック的な部分を学ばせていただくだけですので、
このスレッドは解決とさせていただきます。

この度は、私の不注意と不勉強から皆様を混乱させてしまいすみませんでした。
また、それでも最初から最後までお付き合いくださったみけCATさんと、
私のミスを適切にご指摘をしてくださったusaoさんに感謝いたします。
どうもありがとうございました。

今回の質問は、私にとって大変勉強になりました。
この場をお借りして、このスレッドをご覧いただいた皆様にもお礼申し上げます。

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

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

#39

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

Ketty さんが書きました:なるほど、座標圧縮というのは、内部のオブジェクト同士の比率をたもったまま、全体の空間自体を縮小するイメージなのですね。
その結果、等倍で探索するよりも処理が高速になると。
惜しいです。
「比率」ではなく「位置関係」をたもちます。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
Ketty
記事: 102
登録日時: 10年前

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

#40

投稿記事 by Ketty » 10年前

>みけCATさん
ご指摘くださりありがとうございます。
なるほど・・・オブジェクト同士の「位置関係」をたもつ、ですか。

トピックを解決済みにしてしまったので、いまさらに確認させていただくのは大変恐縮なのですが、
以下の私の認識があっておりますでしょうか?
お手すきの際でけっこうですので、ご覧になられたらご回答くださると幸いです。

>「比率」ではなく「位置関係」をたもちます。
この、みけCATさんのご指摘の意図としては、
比率という表現だと、位置関係まで指し示せていないから、私が使う言葉を間違えているよ、ということですね。

頭の中では、
線分Aは線分Bより右にあるとか下にあるとかは、(きっと)不変であるという(私の勝手な)思い込みで、
線分の長さがそれぞれ同じ倍率で小さくなる・・・とイメージしてしまっておりましたので、
比率をたもつ、と表現してしまいました。
ご指摘くださらなければ、この思い込みのことも気づけなかったと思いますorz

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

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

#41

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

Ketty さんが書きました:>「比率」ではなく「位置関係」をたもちます。
この、みけCATさんのご指摘の意図としては、
比率という表現だと、位置関係まで指し示せていないから、私が使う言葉を間違えているよ、ということですね。
違います。逆です。
「位置関係」というより「順序関係」と言ったほうが良かったですね。

例えば、元の座標がA=10,B=300,C=100000だったとすると、(自分の思っている意味では)
これをA'=1,B'=30,C'=10000にするのが「比率」を保った変換、
A'=1,B'=2,C'=3にするのが「比率」は保っていないけれど「順序関係」は保っている変換です。

今回の用途だと、「迷路(のようなもの)」の道がどこでつながっていて、どこで切れているかだけ分かればよく、
間の空間の大きさの情報は(座標を変換するテーブルのみを持っていれば)必要ないので、
「比率」は保たず、「順序関係」を保つ変換をして考えてもいい、ということになります。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
Ketty
記事: 102
登録日時: 10年前

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

#42

投稿記事 by Ketty » 10年前

>みけCATさん
ご解説をしてくださりありがとうございます。

>「比率」は保たず、「順序関係」を保つ変換をして考えてもいい、ということになります。
なるほど・・・!! ようやく理解できました。
とても分かりやすかったです。貴重なお時間を割いてご説明くださりありがとうございました。

トピックと関係ないですが、
2014/02/22時点で、みけCATさんのWebサイトが閲覧できなくなっておりますです(o _o)更新中かな。

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

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

#43

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

Ketty さんが書きました:トピックと関係ないですが、
2014/02/22時点で、みけCATさんのWebサイトが閲覧できなくなっておりますです(o _o)更新中かな。
サーバーの調子がかなり悪いようなので、実験場として使用していた別のサーバーにコンテンツを移動しました。
http://mikecat.dip.jp/
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

閉鎖

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