凸包に挑んでみる2

昨日のイマイチな処理、使用すべきベクトルが間違っていたと言うお粗末な結末。
ある程度修正したので、利用価値があるものかどうか不明ながら公開。

#FusionAPI_python ConvexHull2D
#Author-kantoku
#Description-新たなｽｹｯﾁを作成し、ランダムに2Dな点を作成し、凸包する

import adsk.core, adsk.fusion, traceback
import random

def run(context):
    ui = None
    
    #作成するランダムな点の数
    pointcount = 100

    try:
        #準備
        app = adsk.core.Application.get()
        ui = app.userInterface
        des = app.activeProduct
        root = des.rootComponent
        
        #ｽｹｯﾁと点の作成
        skt = root.sketches.add(root.xYConstructionPlane)
        InitRandomPoint(skt, -10.0, 10.0, pointcount)
        
        #時間測定開始
        import time
        t = time.time()
        print('-- start --')
        
        #凸包
        ConvexHullEdges = ExeConvexHull(skt.sketchPoints)
        [print("({:.3f},{:.3f})-({:.3f},{:.3f})"
            .format(b[0].x *10 ,b[0].y*10,b[1].x *10 ,b[1].y*10)) for b in ConvexHullEdges]
        
        [CreateSketchLine(skt,Vec2dtoPnt3d(v1) ,Vec2dtoPnt3d(v2)) for v1,v2 in ConvexHullEdges]
        
        #終了
        t = time.time()- t
        ui.messageBox(' Points Count:{}\n ConvexHull Edges Count:{}\n time:{:.2f}s'
            .format(pointcount,len(ConvexHullEdges),t))
        
    except:
        if ui:
            ui.messageBox('ｴﾗｰ:\n{}'.format(traceback.format_exc()))

#凸包処理
def ExeConvexHull(points):
    #ｽｹｯﾁ点群をVector2D化
    vecs = [adsk.core.Vector2D.create(p.geometry.x, p.geometry.y)
            for p in points]
                
    #X方向のMinMax取得
    vec_min = min(vecs,key=lambda v:v.x)
    vec_max = max(vecs,key=lambda v:v.x)
    
    #半分づつ処理
    boundarys = []
    boundarys = GetConvexList(vec_min,vec_max,vecs,boundarys)
    boundarys = GetConvexList(vec_max,vec_min,vecs,boundarys)
    
    return boundarys

#凸包となる点リスト作成　-　再帰やめたい
def GetConvexList(v1, v2, vecs, boundarys):
    #始点終点あｈ除外
    if v1 in vecs:
        vecs.remove(v1)
    if v2 in vecs:
        vecs.remove(v2)
    
    #v1, v2の直交ベクトル
    vec1_2 = v2.copy()
    vec1_2.subtract(v1)
    vec_crs = adsk.core.Vector2D.create(vec1_2.y * -1, vec1_2.x)
    
    #v1, v2の外側検索
    check_lst = []
    for v in vecs:
        vv = v.copy()
        vv.subtract(v1)
        if vec_crs.dotProduct(vv) < 0:
            check_lst.append((v,vec1_2.angleTo(vv)))

    if len(check_lst) < 1:
        #v1, v2の組み合わせでOK
        boundarys.append((v1, v2))
        return boundarys
    
    #一番外の点検索
    max_pnt,ang = max(check_lst,key=lambda p:p[1])
    
    vecs = [v for (v,a) in check_lst]
    boundarys = GetConvexList(v1,max_pnt,vecs,boundarys)
    boundarys = GetConvexList(max_pnt,v2,vecs,boundarys)
    
    return boundarys

#Point2D又はVecter2DからZ0のPoint3Dを作成
def Vec2dtoPnt3d(v):
    pnt = adsk.core.Point3D.create(v.x,v.y,0)
    return pnt

#2点間戦分
def CreateSketchLine(skt,p1,p2):
    lines = skt.sketchCurves.sketchLines
    line = lines.addByTwoPoints(p1,p2)

#ランダムな点の作成
def InitRandomPoint(skt, low, upp, count):
    pnts = [adsk.core.Point3D.create(
            random.uniform(low,upp),random.uniform(low,upp),0) 
            for dmy in range(count)]
        
    skt_Pnts = skt.sketchPoints
    [skt_Pnts.add(pnt) for pnt in pnts]
    return

凸包となる点を検索するアルゴリズムは、こちらの "ギフト包装法" では無く
https://ja.wikipedia.org/wiki/%E3%82%AE%E3%83%95%E3%83%88%E5%8C%85%E8%A3%85%E6%B3%95

こちらで説明されている "Quickhull" にしたつもりです。(直感的に速そうだったので)
http://asura.iaigiri.com/OpenGL/gl50.html

Fusion360のｽｹｯﾁは2Dでは無く3Dの為、どうしようかと悩みました。
処理上、内外積を使う必要があり、内積はまぁ構わないのですが
外積は次元によって答えが変わってきます。（2Dと3Dしか知らないですが･･･）
結局、効率無視で2Dとして処理し、最後に3Dの線（ｽｹｯﾁの線）を作成しました。

Fusion360のAPIは、Vector3DとVector2Dの両方用意されているのですが、
Vector3Dには外積(crossProductﾒｿｯﾄﾞ)が用意されているのに
Help

Vector2Dには無いんです･･･。何でだろう？
Help

ついでに愚痴なのですが、Vector3D(2Dも同様)のﾒｿｯﾄﾞが破壊的か？非破壊的か？が、
かなり迷いました。
・破壊的 - ﾍﾞｸﾄﾙそのものが変化してしまうもの
　add(和),subtract(差),normalize(単位化),scaleBy(ｽｹｰﾙ),transformBy(変換)
・非破壊的 - 戻り値で新たなﾍﾞｸﾄﾙが返ってくるもの
　copy(複製 ←深いよ),crossProduct(外積)
こうして見ると外積だけか･･･個人的には全て非破壊的にして欲しい。

C#ATIA

↑ﾀｲﾄﾙ詐欺　主にFusion360API　偶にCATIA V5 VBA(絶賛ネタ切れ中)

凸包に挑んでみる2