区間の集合から任意の値が含まれる区間のみを高速に探索するためのクラス [詳細]

#include <interval_tree.h>

データ構造
class	node
	Interval-treeのノードを表すクラス（interval_treeクラスの内部でのみ使用） [詳細]

Public 型
typedef S	section_type
	区間を表す型
typedef S::min_max_type	min_max_type
	区間の両端の値を表す型
typedef S::tag_type	tag_type
	区間のタグ情報をを表す型
typedef V	value_type
	区間の探索の際に入力される値を表す型

Public メソッド
void	find (const value_type &val, std::vector< tag_type > &tags)
	入力された値が含まれる区間の探索
bool	construct (const std::vector< section_type > &secs)
	Interval-treeの構築
void	destruct ()
	Interval-treeの破棄
	interval_tree ()
	デフォルトコンストラクタ
	interval_tree (const std::vector< section_type > &secs)
	コンストラクタ（Interval-treeの構築）
	interval_tree (const interval_tree< section_type, value_type > &it)
	コピーコンストラクタ
	~interval_tree ()
	デストラクタ
interval_tree &	operator= (const interval_tree< section_type, value_type > &it)
	代入演算子

説明

template<typename S, typename V>
class interval_tree< S, V >

区間の集合から任意の値が含まれる区間のみを高速に探索するためのクラス

区間の集合から2分木を構築し、通常O(n)かかる探索時間をO(log n)に削減する．線分や面分の重なり判定などに有効．

注意: mist::tagged_section< M, T >型のstd::vetorを入力とする．; mist::tagged_section< M, T >::tag_type型のstd::vetorを探索結果の出力とする．

引数

S	… 区間のデータ型（ mist::tagged_section< M, T >型）
V	… 区間の探索の際に入力する任意の値のデータ型（ double や float など，mist::rgb< M, T >::min_max_typeと同じか、あるいはより精度の高い型）

 使用例
// 区間の集合の用意
typedef mist::tagged_section< int, size_t > section_type;
std::vector< section_type > secs; // int型の最大値，最小値にはさまれた区間の集合，各区間にはsize_t型のタグが付けられる．
secs.push_back( section_type( -1, 5, 0 ) );　// タグ0が付いた区間[ -1, 5 )を集合に追加．
/* 
    区間の集合へ追加処理
*/
// Interval-treeの構築
typedef mist::interval_tree< section_type, double > i_tree_type;
mist::i_tree_type i_tree( secs );
// 任意の値が含まれる区間のタグの集合を高速に探索
std::vector< section_type::tag_type > tags;
i_tree.find( 0.0, tags ); // 0.0 が含まれる区間のタグの集合を得る
// 探索結果の表示
for( size_t i = 0 ; i < tags.size( ) ; i ++ )
{
    std::cout << secs[ tags[ i ] ] << std::endl;
}

コンストラクタとデストラクタ

template<typename S, typename V>

interval_tree< S, V >::interval_tree ( const std::vector< section_type > & secs )

inline

コンストラクタ（Interval-treeの構築）

引数

[in] secs … 区間集合

template<typename S, typename V>

interval_tree< S, V >::interval_tree ( const interval_tree< section_type, value_type > & it )

inline

コピーコンストラクタ

引数

[in] it … interval_treeオブジェクト

関数

template<typename S, typename V>

bool interval_tree< S, V >::construct ( const std::vector< section_type > & secs )

inline

Interval-treeの構築

引数

[in] secs … 区間の集合

戻り値: 木が正しく構築された場合に真を返す

参照元 interval_tree< section_type, float_type >::interval_tree().

template<typename S, typename V>

void interval_tree< S, V >::find	(	const value_type &	val,
		std::vector< tag_type > &	tags
	)

inline

入力された値が含まれる区間の探索

引数

[in]	val	… 入力（この値を間に含む区間を探索）
[out]	tags	… 探索された区間のタグ情報の集合

template<typename S, typename V>

interval_tree& interval_tree< S, V >::operator= ( const interval_tree< section_type, value_type > & it )

inline

代入演算子

引数

[in] it … interval_treeオブジェクト

このクラスの説明は次のファイルから生成されました:

interval_tree.h

データ構造

Public 型

Public メソッド

説明

template<typename S, typename V> class interval_tree< S, V >

コンストラクタとデストラクタ

関数

template<typename S, typename V>
class interval_tree< S, V >