16 pgRouting in Debian6 7 - ルートの検索3 Shooting-Star

6.3. Shooting-Star
Shooting-Star アルゴリズムは、最新の pgRouting 最短経路アルゴリズムです。
その特徴は、リンクからリンクへルートを決めることで、Dijikstra や A-Star アルゴリズムのように vertex から vertex ではありません。
これは、例えばリンク間の関係を定義することを可能にし、「パラレルリンク」のようなほかの vertex が基本となるアルゴリズムの問題を解決し、同じ source と target で、違う costs を持ってます。

Prerequisites は、既に設定済みです。

Shooting-Star algorithm introduces two new attributes
Shooting-Star の新しい２つの属性の紹介

rule:
カンマで区切られたエッジ ID の文字列で、制限を転回するルールが記述されています。（もしこれらのエッジに沿うなら、to_cost カラムに置かれている cost によって現在のエッジに通すことができます。）

to-_cost:
制限された通路の cost。（交通信号の場合のエッジ cost による転回制限または同等の場合は、とても高い。

6.3.1. Core
Shooting Star クエリーの例：

routing2=# SELECT * FROM shortest_path_shooting_star('
SELECT gid as id, source::integer, target::integer, length::double precision as cost, x1, y1, x2, y2, rule, to_cost FROM ways',10, 1, false, false);

 vertex_id | edge_id |        cost        
-----------+---------+--------------------
         8 |      10 |  0.267958532298737
        16 |      28 | 0.0770723510944786
        18 |      29 |     0.062939722076
        20 |      30 | 0.0402954467053289
        22 |      31 | 0.0190948665928645
        24 |     109 |  0.116227259387871
       136 |     110 |  0.174299630853856
         1 |     111 | 0.0382842275772729
       139 |     112 |  0.286175933407192
       141 |     113 | 0.0520291616070434
       145 |     565 |  0.289789710373784
       900 |  380609 |   0.76797799806671
       187 |  380608 |  0.735939901886778
       303 |     215 |  0.226197723036394
        27 |      36 |  0.634325320625154
        28 |       1 |   2.26935080251169
(16 行)

~
(stdin):q


6.3.2. Wrapper
Wrapper 関数は、遷移や境界線 box 制限などで core 関数を拡張します。

routing2=# SELECT gid, AsText(the_geom) AS the_geom FROM shootingstar_sp('ways', 10, 1, 0.1, 'length',true, true);

   gid  |                             the_geom                                                                             
--------+----------------------------------------------------------------------------------------
     10 | MULTILINESTRING((139.7576138 35.6405785,139.757642 35.6429882))
     28 | MULTILINESTRING((139.757642 35.6429882,139.7567891 35.6429914))
     29 | MULTILINESTRING((139.7567891 35.6429914,139.7560926 35.642988))
     30 | MULTILINESTRING((139.7560926 35.642988,139.7556467 35.6429917))
     31 | MULTILINESTRING((139.7556467 35.6429917,139.7554354 35.6429934))
    109 | MULTILINESTRING((139.7554354 35.6429934,139.7549489 35.6420258))
    110 | MULTILINESTRING((139.7549489 35.6420258,139.7542037 35.64058))
    111 | MULTILINESTRING((139.7542037 35.64058,139.7540437 35.6402612))
    112 | MULTILINESTRING((139.7540437 35.6402612,139.7535339 35.6392546,139.7528491 35.6378777))
    113 | MULTILINESTRING((139.7528491 35.6378777,139.7526395 35.6374419))
(stdin):q