MATLAB Function Reference

delaunay

Delaunay 三角測量(triangulation)

Syntax

TRI = delaunay(x,y)
TRI = delaunay(x,y,'sorted')

Definition

給定一個資料點的集合，Delaunay 三角測量(triangulation) 是連接每個點到其自然鄰點(natural neighbors)的線段集合。Delaunay triangulation 與 Voronoi diagram 有關聯 -- 圈起一個 Delaunay 三角形的圓之圓心會在 Voronoi 多邊形的頂點上。

Description

TRI = delaunay(x,y) 傳回一個三角形的集合，使得在任何一個圈起三角形的圓裡面沒有其他資料點。 每個 m-by-3 矩陣 TRI 的橫列定義每個三角形和它所包含點在向量 x 和 y 的索引值。

為了避免在一直線上資料點造成的衰減，delaunay 增加一些隨機的模糊點(fuzz)到資料中。預設選取 4*sqrt(eps) 為標準模糊偏差量(fuzz standard deviation)來維持資料七位的準確度。

tri = delaunay(x,y,fuzz) 使用特定值做標準模糊偏差量(fuzz standard deviation)。有可能沒有 fuzz 的值會產生正確的三角測量。在這個不太可能的情形下，你需要對你的資料做前處理來避免資料點在同一直線或是幾乎在同一直線上。

TRI = delaunay(x,y,'sorted') 假設點 x 和 y 先對 y 排序，然後才對 x 排序，且重複的點已經被排除。

Remarks

Delaunay 三角測量(triangulation) 和下列方法一起使用：griddata (插入散佈的資料)，convhull, voronoi (計算 voronoi 圖)，它本身對散佈的資料產生三角格很有用。

函數 dsearch 和 tsearch 分別搜尋三角測量來找最鄰近的鄰點和圈起三角形。

Note    delaunay 以 qhull 為基礎 [1]。 更多有關 qhull 的資訊，請見 http://www.geom.umn.edu/software/qhull/。版權的資訊，請見 http://www.geom.umn.edu/software/download/COPYING.html。

Examples

這段程式對十個隨機產生的點畫出 Delaunay 三角測量(triangulation)。

rand('state',0);
x = rand(1,10); 
y = rand(1,10); 
TRI = delaunay(x,y);
subplot(1,2,1),...
trimesh(TRI,x,y,zeros(size(x))); view(2),...
axis([0 1 0 1]); hold on; 
plot(x,y,'o');
set(gca,'box','on');

同樣的點，與 Voronoi diagram 做比較：

[vx, vy] = voronoi(x,y,TRI);
subplot(1,2,2),...
plot(x,y,'r+',vx,vy,'b-'),...
axis([0 1 0 1])

See Also

convhull, delaunay3, delaunayn, dsearch, griddata, trimesh, trisurf, tsearch, voronoi, voronoin

References

[1]  National Science and Technology Research Center for Computation and Visualization of Geometric Structures (The Geometry Center), University of Minnesota. 1993.

del2

delaunay3