Polylineのリダクション（Douglas-Peuckerアルゴリズム）

カーブを単純化するアルゴリズムです。

処理の流れ
コード

処理の流れ

１：始点と終点をプロット対象とする。

２：プロット対象をラインで結び、その間の各点との距離を調べる

３：許容距離以上で一番遠いポイントを選び、新たにプロット対象とする

４：２～３の処理を再帰的に繰り返す

最初の状態。許容距離を決めます。

始点Aと終点Hをラインで結ぶ。間のポイントで許容距離以上で一番遠いポイントはCとなる。ここでA、H、Cは確定する。

AとCをラインで結び、同じように間のポイントで一番遠いものを探す。Bが一番遠いポイントになるが、許容距離以下なので除外する。今度はCとHをラインで結び、間のポイントで一番遠いポイントを探す。Gが許容距離以上なので確定する。

CとGをラインで結び、間のポイントがEが確定する。GとHの間にはポイントがないのスキップ。

CとEを結び、間のポイントDは許容距離以下なので除外。EとGの間にあるFも許容距離以下なので除外する。

こうして、A-C-E-G-Hを結んだカーブが残る。

コード

必ずSort SOPを直前に挟み、頂点の並びを整えておく。

再帰処理を使うため、Pythonでコードを書いた。変数epsilonに許容範囲を入力することで機能する。

node = hou.pwd()
geo = node.geometry()

# 許容距離ε
epsilon = 0.5

pos = []
for pt in geo.points():
    pos.append(pt.position())
    
# Douglas-Peucker関数、返り値は間引かれた座標リスト
def rdp(pos, epsilon):
    start = pos[0]
    end = pos[-1]
    
    # 一番大きな垂線を探し、インデックスと距離を調べる（内積を使って垂線との交点座標を求めている）
    max = 0
    index = -1
    ab = end - start
    ab = ab.normalized()
    for i in range(1, len(pos)-1):
        ap = pos[i] - start
        d = ab.dot(ap)
        cross = start + ab * d
        dist = (pos[i] - cross).length()
        
        if dist > max:
            max = dist
            index = i
    
    # 再帰処理
    result = []
    if max > epsilon:
        # 始点からインデックスまで（左側）
        L = rdp(pos[:index+1], epsilon)
        # インデックスから終点まで（右側）
        R = rdp(pos[index:], epsilon)
        # 重複していなければリストに追加
        result += [list(i) for i in L if list(i) not in result]
        result += [list(i) for i in R if list(i) not in result]
    else:
        # 許容距離を越えていなければ始点と終点をリストに追加
        result += [start, end]
        
    return result 
    
list = rdp(pos, epsilon)

# ポリラインを新しく生成する
geo.clear()

poly = geo.createPolygon(is_closed=False)
for i in range(len(list)):
    point = geo.createPoint()
    point.setPosition(list[i])
    poly.addVertex(point)

このPython SOPをポリラインにつなげれば間引かれたカーブが生成される。