概要

障害物を回避しながら start から goal まで移動する経路を作成します。

経路の生成手順

円で与えられた障害物を回避する経路を生成します。

障害物がない場合や、start から goal までの直線上に障害物がない場合には、start から goal までの直線を経路として返します。

start から goal までの直線上に円が存在する場合は、その円を迂回する経路を返します。

このとき返される経路は、

の３つの要素で構成されます。
また、円を迂回する経路は時計回り、反時計回りの２通りのうち start から goal まで距離が短い方を選択します。

迂回する経路が複数の円で構成される場合、より外側の円を迂回する経路を生成する。
より外側の円を迂回すべきかは、生成した経路が他の円と交差するかで判定できます。

もし、複数の円によって goal までの経路が存在しない場合、goal までの直線で、最も近い円弧上まで移動する経路を返します。