[問題] concave polygon

[nbalife (來福)]

我在二維空間中有許多資料散布點  x和y  以及速度(u,v)

我想要用這些取樣點對整個空間做內插

我是用三角型的內插

triscatteredinterp (griddata的結果好像是一樣的?)

matlab都會用convhull的概念  對凸多邊形進行內插

但其實我的取樣點應該是concave polygon

目前我的做法是這樣

先不管上述情況  先內插出整個空間的u和v

然後把所有的delaunay檢查一遍把不合理的三角型去掉

接著把坐標不在所有三角形中的點的 u v 令為nan

可是這樣一來程式執行的速度太慢了  已經跑了兩個小時還沒完....

感覺很沒效率  想問問看有沒有更好的想法

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.230.188
推 sunev:用for就沒救了
→ nbalife:我的確是用for....
推 sunev:我看到 "把所有的xxxx檢查一遍" 就知道了...:P
→ nbalife:因為我無法建立concave polygon的邊界
→ nbalife:所以只能一個一個三角形看
推 sunev:所以你想做這件事?
→ sunev:http://0rz.tw/LhdT1 ?
→ nbalife:是有點像  但是他的形狀比較簡單 頂點數很好決定
→ nbalife:我的點是散佈的  我目前是把任一邊長太大的三角形刪去
→ YoursEver:constrained Delaunay triangulation?
→ YoursEver:如果是CDT的話,你該作的事情是先把boundary定義好,
→ YoursEver:接下來再去run CDT.
→ YoursEver:如果是想先作delaunay再去刪除不合理的三角型,那麼,
→ YoursEver:"重新補三角型"會比你現在作"檢查"這件事更要命.
→ YoursEver:再來,如果是想靠simplex來作interpolation,這部分應該是
→ YoursEver:和三角型是否過於狹長無關.