ページ 11

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

Posted: 2014年2月14日(金) 17:32
by みけCAT
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
に対する正しい出力を教えていただけますか?

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

Posted: 2014年2月14日(金) 17:53
by usao
>矩形とする領域の起点(左上)と対角点(右下)は、必ず、入力の線分の始点または終点または線分同士の交点となる、です。
>(それ以外の座標に点を置いてはならない)

例えば,
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の方はすぐには母集団から取り除けない.まだ他の矩形と重なっているかもしれないので.)

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

Posted: 2014年2月14日(金) 18:34
by Ketty
>みけCATさん
申し訳ありません。
usaoさんがご指摘くださっている内容通りなのですが、私の記述に誤りがありました。
度重なる誤記、謝罪いたします。

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

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

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

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

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

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

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

>今までの例を見た感じだと,こんなことなのかなー? というのを書いてみます.
ありがとうございます。
まだ細かい部分まで読解できておりませんが、おそらくご提示いただいた内容で、
私の希望する出力は実現できると思われます。

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

Posted: 2014年2月14日(金) 22:06
by みけCAT
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個ずつ使用して矩形を塗っていきます。
一番下の色まで使ってしまった場合、一番上の色に戻ってまた順番に塗っていきます。

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

Posted: 2014年2月15日(土) 18:22
by Ketty
>みけ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さんのやり方ですと、非常に高速でしたので、
これを使わせていただこうと思います。

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

Posted: 2014年2月17日(月) 22:42
by Ketty
>みけCAT さん
現在、みけCATさんが考案してくださったアルゴリズムを理解しようとしているのですが、
以下、私の理解がおよびませんので、お手数ですがご教授願えないでしょうか?

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

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

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

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

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

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

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

Posted: 2014年2月19日(水) 23:24
by Ketty
>みけCATさん

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

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

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

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

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

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

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

Posted: 2014年2月19日(水) 23:41
by みけCAT
Ketty さんが書きました:なるほど、座標圧縮というのは、内部のオブジェクト同士の比率をたもったまま、全体の空間自体を縮小するイメージなのですね。
その結果、等倍で探索するよりも処理が高速になると。
惜しいです。
「比率」ではなく「位置関係」をたもちます。

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

Posted: 2014年2月20日(木) 23:40
by Ketty
>みけCATさん
ご指摘くださりありがとうございます。
なるほど・・・オブジェクト同士の「位置関係」をたもつ、ですか。

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

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

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

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

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

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

今回の用途だと、「迷路(のようなもの)」の道がどこでつながっていて、どこで切れているかだけ分かればよく、
間の空間の大きさの情報は(座標を変換するテーブルのみを持っていれば)必要ないので、
「比率」は保たず、「順序関係」を保つ変換をして考えてもいい、ということになります。

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

Posted: 2014年2月22日(土) 22:59
by Ketty
>みけCATさん
ご解説をしてくださりありがとうございます。

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

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

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

Posted: 2014年2月23日(日) 13:22
by みけCAT
Ketty さんが書きました:トピックと関係ないですが、
2014/02/22時点で、みけCATさんのWebサイトが閲覧できなくなっておりますです(o _o)更新中かな。
サーバーの調子がかなり悪いようなので、実験場として使用していた別のサーバーにコンテンツを移動しました。
http://mikecat.dip.jp/