(C++)直線に囲まれた矩形の座標を知りたい
Posted: 2014年2月09日(日) 15:40
こんにちは。Kettyです。
以前、C++(stl)の正規表現について質問させていただき、お世話になりました。
ご協力くださったh2so5さんとみけCATさん、その節はありがとうございました。
今回の質問は、以下のとおりで、C++とDXライブラリを使っております。
私がやりたいことは、任意の始点、終点を持つ直線が、任意の本数だけある場合、
これらに囲まれた矩形の座標を求めたいというものです。
※ここで扱う直線は以下のとおりです。
ななめの線は無いこと(すべて、X軸方向(またはY軸方向)に水平(または垂直))
長さが0のものは無いこと
始点および終点に負値はないこと
始点および終点はいずれも整数であること(小数点なし)
現状としては、
各直線の始点と終点は、構造体で管理して、
この構造体自体をstl::vectorで管理しています。
また、矩形の座標も、起点と対角点を構造体で管理したいと考えており、
プログラム内でどうにかして、直線の座標をもとに、これらに囲まれた全ての矩形の座標を知りたいのですが、
このときのアルゴリズムが思いつかないので、お聞きしたいのです。
考え方やヒントでもかまわないのですが、ご教授ください。
以下に現在制作中のソースコードを挙げておきます。
以前、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() ;
}