アルゴリズムクイックリファレンス 第2版

316

■

9

章 計算幾何学

例

9-7

 ボロノイ図で新たな円イベントの生成

def generateCircleEvent(self, node):

"""

3

連続節点の真ん中の、この新しい節点では、円イベントの可能性がある。

その場合には、新しい円イベントを将来の処理のために優先度付きキューに追加する。

"""

#

左右に存在するはずの隣接節点を見つける

leftA = node.getLeftAncestor()

if leftA is None:

return

left = leftA.getLargestLeftDescendant()

#

右隣を見つける

rightA = node.getRightAncestor()

if rightA is None:

return

right = rightA.getSmall

estRightDescendant()

#

サニティーチェック。一致しないはず。

if left.site == right.site:

return

# 2

辺が交差を持たないなら、何もしない

p = leftA.edge.intersect(rightA.edge)

if p is None:

return

radius = ((p.x-left.site.x)**2 + (p.y-left.site.y)**2)**0.5

#

外接円の底の点を選ぶ

circleEvent = Event(Point((p.x, p.y-radius)))

if circleEvent.p.y ...