ボロノイ図
[幾何計算]

説明

２次元ボロノイ図を「逐次四分添加法」によって作成します。 最悪の処理速度のオーダーはＯ( n^2 )ですが、平均的にはＯ( n )であることが知られており、 分割統治法(処理速度オーダーはＯ( n log n ))より実用的です。

与えられた点集合の各点(以下「母点」といいます)に対して１つの領域が対応しており、その領域に おいては対応する母点が全母点の中で一番近い点になっているような平面の分割図のことをボロノイ図 と言います。(下図を参照してください)。

fie_cg_voronoi.png
点集合の「各点間の近さを表わす地図」のようなものと考えられます。 図の各辺は両隣の母点の垂直２等分線になっています。 細胞が最初は点とみなせて同じ速度で成長する場合に収束状態で出来る図がこのボロノイ図であり、 実際に各領域は「ボロノイ細胞」とも呼ばれます。 また、ボロノイ図のことを「ボロノイ勢力図」等とも呼び、工学はもとより、生物学、考古学、社会学等幅広い分野に応用されています。

参考文献:
用語説明 
	「母点」、「頂点」、「辺」
		それぞれ、ボロノイ母点、ボロノイ頂点、ボロノイ辺、のこととします。
	「辺リスト」
		ボロノイ辺リストのことです。
		例えば、ある母点の周囲辺を記録するためにこの辺リストを用います。
		ボロノイ辺構造体は複数の母点・頂点に共有されるため、このような辺リストを各母点・頂点に与えます。
		各辺リストは辺情報の実体のある辺構造体へのポインタを持つことで情報の取得を可能にしています。
		辺リスト自体は辺の接続関係(グラフ構造)を表わすためだけに用いられています。
		なお、辺構造体も動的に管理されるため、全体として双方向循環リストを構成しているが、
		混同しないように注意してください(この「辺リスト」も双方向循環リスト構造をなしています)。
	「入力母点」
		入力点のことです。
		これらはボロノイ図ではボロノイ母点と呼ばれます。
	「ボロノイ図の有効領域」
		矩形型領域で指定されています。
		入力母点はこの有効領域の内部になくてはなりません。
		また、構成されるボロノイ図はこの有効領域において正しい情報を与えることが保証されます。
	「最近母点」
		ある点に対して一番近い母点のことです。
	「隣接母点」
		ある点の属するボロノイ領域の母点と、その領域に隣接する領域の母点のことです。
	「便宜付加母点」
		ボロノイ図構成時に無限ボロノイ領域を扱うことを回避するために、有効領域の外側に
		便宜的に付加される点のことです。
		正三角形の頂点上に３点が付加されます。
	「探索出発母点」
		母点を逐次添加していく際に、既に添加した母点の中で最近母点を探索しなければなりません。
		その際の探索の初期母点を探索出発母点といいます。
		最近母点を探索する際には探索出発母点の隣接母点と添加する母点との距離を調べていき、
		より近い母点があればそこに移って同様のことを行なう、という処理を繰り返します。


データ構造

struct  F_CG_VE_INFO
 ボロノイ図 辺情報構造体 [詳細]
struct  F_CG_VG_INFO
 ボロノイ図母点情報構造体 [詳細]

列挙型

enum  f_cg_vrni_egde_type {
  F_CG_SEGMENT_TYPE = 0, F_CG_ST_PNT_RAY = 1,
  F_CG_ED_PNT_RAY = 2, F_CG_LINE_TYPE = 3
}
 ボロノイ辺の種類 [詳細]
enum  f_cg_vrni_region_bound { F_CG_BND_RGN = 0, F_CG_UNBND_RGN = 1 }
 ボロノイ領域の境界 [詳細]

関数

FHANDLE FVALGAPI fnFIE_cg_voronoi_open (const PNT_T *pnts, INT num, INT sx, INT sy, INT ex, INT ey)
 ２次元ボロノイ図のオープン
INT FVALGAPI fnFIE_cg_voronoi_nearest_gnrt (FHANDLE hvrni, PNT_T pnt, INT *near_gnrt_no)
 最も近い入力点（母点）の探索
INT FVALGAPI fnFIE_cg_voronoi_get_gnrt_info (FHANDLE hvrni, INT gnrt_no, F_CG_VG_INFO **info)
 ２次元ボロノイ図の各母点に関する情報の取得

列挙型

enum f_cg_vrni_egde_type

ボロノイ辺の種類

ボロノイ辺の種類を表します。 通常、ボロノイ辺が F_CG_LINE_TYPE となることはありません。 F_CG_SEGMENT_TYPE 、 F_CG_ST_PNT_RAY 、 F_CG_ED_PNT_RAY のいづれかとなります。

列挙型の値:
F_CG_SEGMENT_TYPE  線分であるボロノイ辺(始点、終点共に有効領域内に含まれる)
F_CG_ST_PNT_RAY  始点を持つ半直線であるボロノイ辺(始点のみが有効領域内に含まれる)
F_CG_ED_PNT_RAY  終点を持つ半直線であるボロノイ辺(終点のみが有効領域内に含まれる)
F_CG_LINE_TYPE  直線であるボロノイ辺(始点、終点共に有効領域内に含まれない)

enum f_cg_vrni_region_bound

ボロノイ領域の境界

ボロノイ領域の境界を表します。

列挙型の値:
F_CG_BND_RGN  有限領域であるボロノイ領域
F_CG_UNBND_RGN  無限領域であるボロノイ領域

関数

FHANDLE FVALGAPI fnFIE_cg_voronoi_open ( const PNT_T *  pnts,
INT  num,
INT  sx,
INT  sy,
INT  ex,
INT  ey 
)

２次元ボロノイ図のオープン

入力された２次元点データから、逐次四分添加法を使用してボロノイ図オブジェクトを作成します。

与えられる入力母点は「順序データ」である必要はありませんが、重複点がないことを仮定しています。 これに従わない入力に関しては結果を保証しません。

パラメータ sx , sy , ex , ey はボロノイ図の有効領域です。 この有効領域内においてボロノイ図の結果が保証されます。 したがって、この有効領域の外部での結果は本来得られるはずのボロノイ図とは異なる 平面グラフが構成されている場合があります。 有効領域は、以下の条件を満たしてください。

  • ex >= sx
  • ey >= sy
なお、入力母点数は１以上を入力してください。

本関数で生成したオブジェクトは不要になったら fnFIE_free_object() にて解放してください。

引数:
[in] pnts 入力母点群
[in] num 入力母点数( pnts の要素数)
[in] sx ボロノイ図有効領域左上Ｘ座標
[in] sy ボロノイ図有効領域左上Ｙ座標
[in] ex ボロノイ図有効領域右下Ｘ座標
[in] ey ボロノイ図有効領域右下Ｙ座標
戻り値:
正常に終了した場合は、デスクリプタを返します。 メモリ確保に失敗や不正なパラメータが与えられた場合、 ライセンスエラー、または未初期化エラーが発生した場合など、異常終了した場合はNULLを返します。

INT FVALGAPI fnFIE_cg_voronoi_nearest_gnrt ( FHANDLE  hvrni,
PNT_T  pnt,
INT *  near_gnrt_no 
)

最も近い入力点（母点）の探索

入力された点データの中から調査点に一番近い点を探します。 本関数は、ボロノイ図が正常に作成されていることを前提にして、最も近い点の高速な探索を行ないます。 回答は戻り値として調査点に最も近い母点の番号が返されます。 この番号は入力された入力母点群の配列での要素番号です。

調査点はボロノイ図構成時に指定した有効領域内になければいけません。 回答が複数ある場合でも、そのうちの１つのみを回答として出力します。

引数:
[in] hvrni ２次元ボロノイ図のハンドル
[in] pnt 調査点
[out] near_gnrt_no 最近母点の番号
戻り値:
F_ERR_NONE 正常終了
F_ERR_INVALID_OBJECT 不正なオブジェクトが渡された
  • オブジェクトがボロノイ図ではない
  • オープンが完了していないか
  • ボロノイ図が作成されていないか
F_ERR_INVALID_PARAM 不正なパラメータが渡された
  • 調査点がボロノイ図の有効範囲に入っていない
  • near_gnrt_no にヌルポインタが渡された
F_ERR_NO_LICENCE ライセンスエラー、または未初期化エラー

INT FVALGAPI fnFIE_cg_voronoi_get_gnrt_info ( FHANDLE  hvrni,
INT  gnrt_no,
F_CG_VG_INFO **  info 
)

２次元ボロノイ図の各母点に関する情報の取得

ボロノイ図に関して、指定された母点(＝入力母点群)の領域の情報を取得します。 回答データは本ライブラリを再度コールするかボロノイ図をクローズするまで保持されます。

なお、調査母点番号の上限は入力母点数未満の値を入力してください。 下限は０以上の値を入力してください。

母点情報構造体 info は fnFIE_cg_voronoi_open() にて確保されているため、呼び出し側が確保する必要はありません。 この配列は fnFIE_free_object() により２次元ボロノイ図のハンドルが解放される時に、同時に解放されます。 ユーザー側で個別に解放はしないでください。

引数:
[in] hvrni ２次元ボロノイ図のハンドル
[in] gnrt_no 調査母点番号
[out] info 母点情報構造体
戻り値:
F_ERR_NONE 正常終了
F_ERR_INVALID_OBJECT 不正なオブジェクトが渡された
  • オブジェクトがボロノイ図ではない
  • オープンが完了していないか
  • ボロノイ図が作成されていないか
F_ERR_INVALID_PARAM 不正なパラメータが渡された
  • 調査点がボロノイ図の有効範囲に入っていない
  • info にヌルポインタが渡された
  • *info がNULLで初期化されていない
F_ERR_NO_LICENCE ライセンスエラー、または未初期化エラー

Documentation copyright © 2009-2024 FAST Corporation.
Generated on Fri Aug 9 16:38:47 2024 for FIEライブラリ by doxygen 1.5.6-FASTSP-p2