shortest path

人材獲得作戦・４　試験問題ほかに出てる問題、pythonで書いてみました。

１時間ちょいかかりました。30分とか速いな....

Blender - シーンの自動生成(3)

前回は大まかに踊り場を作るところまでやりましたが、今回はさらに以下の変更を加えました。

• (1)踊り場の形状をタンジェントとか使って厳密に計算した


• (2)道路同士をなめらかに繋ぐようにした

と、さらっと書きましたが、実装は結構面倒でした。

(1)は、各頂点について、上から見た時の辺の角度（9時の方向を -PI として反時計回りに大きくなる）で辺をソートして、隣り合う辺から生成される道路同士の交点を計算した後に、各辺について左右の交点のうち手前の方に合わせて逆側の点を作って、これらの凸包を踊り場にする...という感じのことをやっています。

(2)は、水平面との角度が踊り場の 0 から坂の角度になるまで、坂と踊り場の間にちょっと傾いたポリゴンを作っていきます。ポリゴンを入れるたびに坂の角度がちょっとずつ急になるのに気付かずハマリ。


拡大図。



あと、よく考えたら道路がない部分に地面を作らないと。道路が全部平らなら地面ポリゴンを１枚置けばいいですが、傾斜があるのでうまいこと地面を生成しないといけないかもです。方針としては、元のグラフ構造からループ部分を検出してポリゴンを作る感じでしょうか。。あと、立体交差のときは地面いらないとか考えないといけなさそうです。む〜ん。

2D Convex hull algorithm

Convex hull (凸包)を計算する Python コード

与えられた点をピンだと思って、最も左のピンから糸を上に引っ張って、次々と時計回りに巻いていく感じです。最初の点まで帰ってきたら終了です。この方式は、Gift wrapping algorithmと呼ばれているそうです。

リスト処理関数(map, reduce, filter)を使って意外と簡潔に書けたつもりですが、改行が入っちゃうとそんなに短く見えないですね。あと math.atan2 便利。

入力となる点集合は list of (x, y) の形ですが、v[0] で x, v[1] で y にアクセスできればよいので list of Blender.Mathutils.Vector でもよいです。

def convex_hull(vs):
    def limit(max_rad, v): return max_rad < v and v - 2 * math.pi or v
    def rad(v): return math.atan2(v[1], v[0])
    def sub(a, b): return (a[0]-b[0], a[1]-b[1])
    
    node = (reduce(lambda a, b: a[0] < b[0] and a or b, vs), math.pi / 2)
    ch = [node[0]]
    for i in range(len(vs)):
        node = reduce(lambda a, b: a[1] > b[1] and a or b, map(lambda x: (x, limit(node[1], rad(sub(x, node[0])))), filter(lambda x: node[0] != x, vs)))
        if ch[0] == node[0]: break
        ch.append(node[0])
    return ch

# Test code
def convex_hull_test():
    vs = [ (0, 0), (0, 1), (1, 1), (1, 0) ]
    for i in range(10): vs.append((random.uniform(0.3,0.6), random.uniform(0.3,0.6)))
    print "convex hull:", convex_hull(vs)

Blender - シーンの自動生成(2)

あけましておめでとうございますトラ。

道路同士をシームレスに繋げる

Blender - シーンの自動生成の TODO のうち、道路同士をシームレスに繋げるというのをやりました。（今回は実家のウィンドウズマシンで作業しました。）



最終版ではないかもしれませんが、こんな感じのメッシュが出来ていればさしあたってＯＫかな、というところです。


方法

これは意外と面倒で、単に道路の長さを調整するのではなく、踊り場を新たに作らないとうまくいきません。以下、図で説明します。Blender で作れよという感じですが。

(1) とりあえず線を太くして道路ポリゴンにしたもの。



(2) こんな風にすれば、シームレスに繋がりそうですが...



(3) 坂がある場合、上から見るとシームレスですが、坂の傾きがあるのでひび割れができてしまいます。これを無理やり合わせると、坂がねじれてしまって良くないです。



(4) こんな感じで踊り場を作ると、よい具合になります。坂の傾きは、踊り場の分、若干きつめになります。



いろいろなパターンに対応するために、実際の踊り場の形はいくつかの点の凸包(Convex hull)にしています。

点集合から Convex hull を求める洗練された python ルーチンはウェブにいくつもありますが、ちょっと（簡潔に）書いてみたかったのでこれもオレオレ版を書きました。これについては後ほど記事を書くかもしれません。


擬似コード


各頂点 A について
それにつながる各頂点 B について
A を道路の幅分ずらした点 FL, FR を計算
FL, FR をそれぞれちょっと B 側にずらした点 BL, BR を計算
A から出ている辺の数が 2 以上なら
点 FL, FR, BL, BR の集合の convex hull を計算
上記からなるポリゴンをつくる（三角形をいくつかつくる）
各辺について
2 つの頂点それぞれの BL, BR 点を元に四角形ポリゴンをつくる
重複する点を削除(Blender の "Remove doubles" 機能)