ボロノイ図とは

ボロノイ図は、

ある平面内の点を、

ある特定の点群の中からどれに最も近いかによって

分割してできる図のことを指します。

(下図はボロノイ図の例)

f:id:meison_amsl:20160727203826p:plain

ボロノイ図を作るための

特定の点群を母点といい、

ボロノイ図の境界は、

それぞれ隣接する母点の垂直二等分線で構成されます。

このボロノイ図は、

最適配置問題や、

最近傍点探索などに使われることが多いようです。

後述の通り、ロボティクスにも使われています。

ロボティクスにおけるボロノイ図

ロボティクスの分野では、

ボロノイ図はパスプラニングの分野で利用されることが多いです。

myenigma.hatenablog.com

Robot Path Planning Using Generalized Voronoi Diagrams.

障害物の情報を点群にし、

その点群情報からボロノイ図を作ることにより、

ボロノイ図は障害物を回避するコースの候補になります。

あとはこのボロノイ図のノードを探索することで、

ある地点からある地点までの、

障害物にぶつからないパスを生成をすることができるのです。

下記の図は、

ボロノイ図によるパス生成のサンプルになります。

path.jpg (JPEG 画像, 424x287 px)

Pythonサンプルコード

Pythonでボロノイ図を作りたい場合は

scipyのVoronoiモジュールを使うと便利です。

例えば下記のPythonコードのように、

2xNのリストで点群リストを作り、

Voronoiモジュールに読み込ませると、

#!/usr/bin/env python
# -*- coding:utf-8 -*-
import numpy as np
import matplotlib.pyplot as plt
import pandas
from scipy.spatial import Voronoi, voronoi_plot_2d

npoint=10
maxvalue=10
points =np.array([[np.random.rand()*maxvalue,np.random.rand()*maxvalue] for i in range(npoint)])

vor = Voronoi(points)
voronoi_plot_2d(vor)
plt.show()