計算幾何学

ボロノイ図って、なんとなくならどんなものかはわかってきたのですが、ボロノイ図をプログラムで表現するときには、どのようになるのか？どのように作れば良いのか？どのように利用すればよいのかわかりません。

私が利用したいのは三次元ボロノイ図なので、平面によって分離される半空間になると思うのですが、ある三次元の点が与えられたとき、その点がどのボロノイセルに含まれるのかを調べる方法は、その半空間の中にあるのか外にあるのかを判定しながら調べていくのが良さそうだと思います。

...これって結局、BSPツリーなんじゃないのかなぁと思ってみたりして

ボロノイ図をデータ化するメリットがあまり感じないんだよな

データの絞込みに使うものなんじゃなくって、何かをするために(例えばスフィアツリーを中間軸法で作るために)、ボロノイ頂点そのものを計算したいってだけなのかな？