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

# ポイントクラス
class Point:
    def __init__(self, index, pos):
        self.index = index
        self.pos = hou.Vector3(pos)

# Douglas Peuckerのポリラインリダクション
def douglas_peucker(points, epsilon):

    if len(points) < 3:
        return points

    start, end = points[0], points[-1]
    max_distance = 0.0
    index = 0

    # 最大距離とそのインデックスを計算
    for i in range(1, len(points) - 1):
        distance = point_line_distance(points[i], start, end)
        if distance > max_distance:
            max_distance = distance
            index = i

    # 許容距離を超える場合は再帰的に処理
    if max_distance > epsilon:
        left = douglas_peucker(points[:index + 1], epsilon)
        right = douglas_peucker(points[index:], epsilon)
        
        return left[:-1] + right
    else:
        return [start, end]

# 線分と点の最短距離
def point_line_distance(point, start, end):
    if start.pos == end.pos:
        return (point.pos - start.pos).length()

    line_vec = (end.pos - start.pos).normalized()
    point_vec = point.pos - start.pos
    d = line_vec.dot(point_vec)
    projection = start.pos + line_vec * d
    dist = (point.pos - projection).length()
    
    return dist

# Pointオブジェクトのリスト
points = []
index = 0
for pt in geo.points():
    points.append(Point(index, pt.position()))
    index += 1

# 簡略化されたポリラインを取得
simplified_points = douglas_peucker(points, epsilon)

# ポイントインデックスをリストにまとめる
result = []
for i in range(len(simplified_points)):
    result.append(simplified_points[i].index)

# Detailに情報を保存
geo.addArrayAttrib(hou.attribType.Global, 'result', hou.attribData.Int, 1)
geo.setGlobalAttribValue('result', result)

この後にPoint Wrangleをつないで不要なポイントを削除する。

// Run Over: Points
int pts[] = detail(0, "result");

if(len(pts) > 0 && find(pts, @ptnum) < 0)
    removepoint(0, @ptnum);