読者です 読者をやめる 読者になる 読者になる

MyEnigma

とあるエンジニアのブログです。#Robotics #Programing #C++ #Python #MATLAB #Vim #Mathematics #Book #Movie #Traveling #Mac #iPhone

ボロノイ図の概要とPythonサンプルコード

なわばりの数理モデル -ボロノイ図からの数理工学入門-

なわばりの数理モデル -ボロノイ図からの数理工学入門-

目次

ボロノイ図とは

ボロノイ図は、

ある平面内の点を、

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

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

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

f:id:meison_amsl:20160727203826p:plain

 

ボロノイ図を作るための

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

ボロノイ図の境界は、

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

 

このボロノイ図は、

最適配置問題や、

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

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

 

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

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

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

myenigma.hatenablog.com

myenigma.hatenablog.com

 

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

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

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

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

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

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

 

下記の図は、

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

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()

 

下記のように、

簡単にボロノイ図を作ることができます。

f:id:meison_amsl:20160727203826p:plain

 

Voronoiオブジェクトのメンバーは

ボロノイ図の各要素になっています。

  • points: 入力点 2xN

  • vertices: ボロノイ図の頂点 2xN

   

参考資料

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

なわばりの数理モデル -ボロノイ図からの数理工学入門-

なわばりの数理モデル -ボロノイ図からの数理工学入門-