ボロノイ図と放物線

id:yellow_73:20080208#p2 の続きでFortune'sについてのメモ。前回の記述に対するスターありがとうございます。ただ、本当に実装するかどうかは未定です。
水平線を引き、サイトPnごとに、下に凸の放物線Knを描きます。この放物線は、水平線を準線、サイトを焦点とします。
水平線以上の領域にあるサイトの位置は全て知っていて、水平線より下は、どうなっているか知らない、とします。

1. Knは、水平線の位置によって変化します。
2. Kn上の任意の点について、Pnからの距離と、水平線からの距離と、が同じになります。
3. 頂点の検出はKn曲線上について検討します。
   1. Knより下になる領域の点は、その点を中心にしてPnを通る円を描くと、水平線を横切ります。もしかしたら水平線より下の領域にあるサイトが引っかかってくるかも知れません。
   2. ボロノイ図の頂点かどうか確定できる領域は、Knのいずれか(Kiとします)について、Ki以上になる領域です。
4. ボロノイ図の辺は二点が同じ距離になるところで、頂点は、三点以上が同じ距離になるところです。
   1. 二つの放物線Ki,Kjの交点Cijは、PiとCijとの距離=Cijと水平線との距離, PjとCijとの距離=Cijと水平線との距離, となりますので、PiとCijの距離=PjとCijの距離となります。
   2. 同じようにKi,Kj,Kkの公転Cijkは、Pi,Pj,Pkから等距離にあることになります。