MapPlanner/README.html at master · akinori-ito/MapPlanner · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
<html>
  <head>
    <meta content="text/html; charset=UTF-8" http-equiv="content-type">
    <title>MapPlanner</title>
  </head>
  <body>
    <h1>MapPlanner</h1>
    <h2>はじめに</h2>
    <p>MapPlannerは、マップ画像から2点間の最短経路を計算するC++のデモプログラムである。実質的には、マップを表現するMapPlaneクラス、
      最短経路を探索するPathFinderクラスの2つからなる。また、PPM形式の画像の読み書きを実装したPPMクラスがおまけとして付いてくる。</p>
    <h2>前提とアルゴリズム</h2>
    <p>マップは基本的に2次元画像であり、各ピクセルは0～255の値を持つ。白い（値が大きい）ピクセルは移動可能であることを示し、黒い（値が小さい）ピクセ
      ルは移動不可能であることを示す。下の画像はマップの例であり、黒いピクセルはLRFで観測した障害物、白いピクセルはLRFで観測した障害物のない領域、灰
      色は未観測領域を示す。</p>
    <img style="width: 340px; height: 398px;" alt="map" src="README.files/map.png"><br>
    <br>
    最初にここから移動可能領域を計算する。ピクセルの輝度に関して閾値を与え、閾値より大きい（すなわち、白い）ピクセルを「移動可能」、小さいピクセルを「移動不
    可能」と判定する。また、障害物から一定の距離範囲内にはロボットが接近できないので、移動不可能ピクセルから一定の範囲内も実質的な移動不可能領域と判定しなけ
    ればならない。そのようにして処理したマップは次のようになる。<br>
    <img style="width: 340px; height: 400px;" alt="map" src="README.files/dark.png"><br>
    <br>
    次に、移動可能領域を2点選んで、その間の最短経路を計算する。経路計算は、すべてのピクセルをグラフのノードとするグラフ最短経路探索を用いている。計算には
    A*アルゴリズムを使っており、ポテンシャルは考慮しないので、基本的に移動可能領域の縁に沿う経路を選択する。ただし、ピクセル間の移動の際は、あるピクセルの
    8近傍のどれかに移動する経路を選ぶため、全体として斜めの直線経路を選ぶことができず、縦・横および斜め45度の経路を組み合わせたような経路が選ばれる。<br>
    <img alt="最短経路" src="README.files/Result.png"><br>
    <br>
    <h2>クラスの利用方法</h2>
    <h3>MapPlaneクラス</h3>
    マップを表現するクラスである。<br>
    <h4>メンバ変数（publicなもののみ）</h4>
    <table border="1" width="100%">
      <tbody>
        <tr>
          <td>int width</td>
          <td>マップの幅。単位はピクセル。</td>
        </tr>
        <tr>
          <td style="width: 151.417px;">int height</td>
          <td style="width: 597.583px;">マップの高さ。単位はピクセル。</td>
        </tr>
        <tr>
          <td>int threshold</td>
          <td>各ピクセルを「移動可能」「移動不可能」に分けたときの閾値。閾値が設定されていない場合には-1になる。マップ作成時には閾値は設定されて
            おらず、mask_brigher(), mask_darker()メソッドを呼んだ時点で閾値が設定される。</td>
        </tr>
      </tbody>
    </table>
    <h4>コンストラクタとファクトリメソッド</h4>
    <table border="1" width="100%">
      <tbody>
        <tr>
          <td style="width: 261.5px;">MapPlane(int w, int h)</td>
          <td style="width: 487.5px;">幅w、高さhのマップを生成する。ピクセルの値は初期化されない。</td>
        </tr>
        <tr>
          <td>MapPlane(MapPlane&amp; map)</td>
          <td>既存のマップをコピーして新たなマップを生成する。</td>
        </tr>
        <tr>
          <td>MapPlane(MapPlane* map)</td>
          <td>既存のマップをコピーして新たなマップを生成する。</td>
        </tr>
        <tr>
          <td>MapPlane(PPM&amp; ppm)</td>
          <td>PPM形式画像からマップを生成する。カラー画像の場合には、Rプレーンだけからピクセル値を取得する。</td>
        </tr>
      </tbody>
    </table>
    <h4>メソッド</h4>
    <br>
    <table border="1" width="100%">
      <tbody>
        <tr>
          <td>uint8_t get(int x, int y)</td>
          <td>(x,y)のピクセル値を取得する。(x,y)がマップの範囲外であった場合には例外を投げる。</td>
        </tr>
        <tr>
          <td>void set(int x, int y, uint8_t value)</td>
          <td>(x,y)のピクセル値を value にする。(x,y)がマップの範囲外であった場合には例外を投げる。</td>
        </tr>
        <tr>
          <td>bool is_bright(int x, int y, uint8_t value)</td>
          <td>(x,y)のピクセル値がvalue より明るいかどうかを判定する。明るい場合はtrueを返す。</td>
        </tr>
        <tr>
          <td style="width: 372.5px;">bool is_bright(int x, int y)</td>
          <td style="width: 376.5px;">(x,y)のピクセル値が設定してある閾値（メンバ変数threshold）より明るいか
            どうかを判定する。明るい場合はtrueを返す。</td>
        </tr>
        <tr>
          <td>MapPlane* mask_brighter(int length, uint8_t threshold)</td>
          <td>元のマップに対して、明るい点の周辺length×lengthの正方形領域を「明るい」点に設定した新たなマップを返す。ここで指定した閾
            値が、新たなマップの変数thresholdに設定される。</td>
        </tr>
        <tr>
          <td>MapPlane* mask_darker(int length, uint8_t threshold)</td>
          <td>元のマップに対して、暗い点の周辺length×lengthの正方形領域を「暗い」点に設定した新たなマップを返す。ここで指定した閾値
            が、新たなマップの変数thresholdに設定される。</td>
        </tr>
        <tr>
          <td>PPM* toPPM()</td>
          <td>マップをPPM形式画像に変換し、その画像を返す。</td>
        </tr>
      </tbody>
    </table>
    <h3>PathFinderクラス</h3>
    マップの経路探索をするためのクラスである。必要なマップを生成した後、PathFinderのインスタンスを生成して、find()メソッドを呼ぶことで経路が
    探索される。<br>
    <br>
    <h4>コンストラクタとファクトリメソッド</h4>
    <table border="1" width="100%">
      <tbody>
        <tr>
          <td style="width: 250.7px;">PathFinder(MapPlane* map)</td>
          <td style="width: 498.3px;">マップからPathFinderインスタンスを生成する。</td>
        </tr>
      </tbody>
    </table>
    <h4>メソッド</h4>
    <table border="1" width="100%">
      <tbody>
        <tr>
          <td style="width: 235.133px;">std::vector&lt;PathFinder::Position&gt;&amp;
            find(int x1, int y1, int x2, int y2)</td>
          <td style="width: 513.867px;">(x1, y1)から(x2,
            y2)への最短経路を計算する。計算された最短経路は、PathFinder::Position型のvectorとして帰ってくる。
            PathFinder::Position型
            は、xとyの2つのメンバ変数を持つ単純な構造体である。始点または終点の座標が移動可能（明るいピクセル）でなかった場合には例外を投げる。ま
            た、始点と終点がそれぞれ属する領域が連結でない（経路がない）場合にも例外を投げる。 </td>
        </tr>
       <tr>
          <td style="width: 235.133px;">std::vector&lt;PathFinder::Position&gt;&amp;
            makeLines(std::vector&lt;PathFinder::Position&gt;&amp; path)</td>
          <td style="width: 513.867px;">find()が返す経路は１ピクセルごとの座標列であるが、makeLines()はその座標列を引数とし、できるだけ数の少ない直線列にまとめたうえ、直線の端点列を返す。
          </td>
        </tr>
      </tbody>
    </table>
    <h3> PPMクラス</h3>
    PPM (Portable Pixmap)形式の非圧縮画像を扱うクラス。PPM形式と類似した画像形式の解説及びツールについては、<a href="http://netpbm.sourceforge.net/">Netpbm
      のページ</a>を参照のこと。PPM形式を扱うことのできるツールとしては、Netpbmのツールのほか、<a href="https://www.imagemagick.org/script/index.php">ImageMagick</a>で
    も対応している。<br>
    <h4>メンバ変数</h4>
    <table border="1" width="100%">
      <tbody>
        <tr>
          <td style="width: 243.617px;">static const PPM::pixel BLACK, RED,
            GREEN, YELLOW, BLUE, MAGENTA, CYAN, WHITE</td>
          <td style="width: 505.383px;">それぞれの色のピクセルを表現する定数。</td>
        </tr>
      </tbody>
    </table>
    <h4>コンストラクタとファクトリメソッド</h4>
    <table border="1" width="100%">
      <tbody>
        <tr>
          <td>PPM(int width, int height)</td>
          <td>幅と高さを指定してPPM画像を生成する。</td>
        </tr>
        <tr>
          <td>PPM(PPM&amp; ppm)</td>
          <td>他のPPM画像からPPM画像を生成する。</td>
        </tr>
        <tr>
          <td style="width: 282.9px;">PPM* create(const char *filename)</td>
          <td style="width: 466.1px;">ファイルからPPM画像を読み込む。ファイルが存在しない場合、ファイル形式が異常な場合
            な どの場合は例外を投げる。</td>
        </tr>
      </tbody>
    </table>
    <h4>メソッド</h4>
    <table border="1" width="100%">
      <tbody>
        <tr>
          <td>int Width()</td>
          <td>画像の幅をピクセル単位で返す。</td>
        </tr>
        <tr>
          <td>int Height()</td>
          <td>画像の高さをピクセル単位で返す。</td>
        </tr>
        <tr>
          <td style="width: 245.683px;">pixel&amp; point(int x, int y)</td>
          <td style="width: 503.317px;">(x,y)のピクセルへの参照を返す。</td>
        </tr>
        <tr>
          <td>void write(const char *filename)</td>
          <td>ファイルにPPM画像を書きだす。</td>
        </tr>
        <tr>
          <td>void drawLine(int x1, int y1, int x2, int y2, pixel pix)</td>
          <td>(x1,y1)から(x2,y2)までの直線上のピクセル値をpixにセットする。</td>
      </tbody>
    </table>
    <br>
    <h3>PPM::pixelクラス </h3>
    ピクセルを表現するクラス。<br>
    <h4>メンバ変数</h4>
    <table border="1" width="100%">
      <tbody>
        <tr>
          <td style="width: 130.433px;">uint8_t pix[3]</td>
          <td style="width: 618.567px;">R, G, B各色の値を保持する。</td>
        </tr>
      </tbody>
    </table>
    <br>
    <br>
    <br>
    <br>
    <br>
  </body>
</html>