散亂數據（Scattered data）指的是在二維平面域或三維空間中隨機分布的抽樣數據點。散亂數據主要來源於3個方面：一是物理量的測量數據；二是科學實驗所得的數據；三是科學計算或工程計算的結果數據。
基本介紹
- 中文名：散亂數據
- 外文名：Scattered data
- 涉及學科：信息科學
- 套用：自動化
- 空間：二維平面域或三維空間
- 實質：抽樣數據點
術語簡介,基本定義,最佳化準則,處理流程,方法描述,
術語簡介
散亂數據指的是在二維平面域或三維空間中隨機分布的抽樣數據點。
散亂數據的可視化就是對散亂數據進行插值或擬合，形成曲線或曲面並用圖形或圖像表示出來的技術。
散亂數據主要來源於3個方面：一是物理量的測量數據；二是科學實驗所得的數據；三是科學計算或工程計算的結果數據。
散亂數據點的曲面重建一直以來是函式逼近論的一個重要研究內容近幾年來，隨著計算機輔助設計與圖形學的發展，散亂數據的曲面重建技術得到了廣泛的研究和套用，如基於測距技術的幾何模型自動生成、醫學成像數據的可視化等該技術的發展有力地促進了造型和可視化等技術的高速發展。
散亂數據擬合或插值是指用一個光滑的曲面來逼近或通過這一系列無規則的抽樣數據點。
基本定義
域分割
(tessellation)給定平面上n個不相重的散亂點，對於每個散亂點構造一個域，使該域內的任一點離此散亂點的距離比離其他散亂點更近，這種域分割稱為Dirichlet Tessellation,又稱Voronoi圖。由這個定義可知，域邊界是連線兩相鄰散亂點的直線的垂直平分線。
Delaunay三角化
具有公共域邊界的散亂點對相連形成的三角化稱Delaunay三角化，見圖1。
圖1 Dirichlet Tessellation(粗線)和Delaunay三角剖分(細線)
鄰接點
具有公共邊界的域為鄰接域，兩個域的生成點為鄰接點。
最佳化準則
對散亂點進行三角剖分的方法很多，其最佳化準則有五，即Thiessen區域準則、最小內角最大準則、圓準則、ABN準則及PLC準則。
(1) Thiessen區域準則(Thiessen regioncriterion) Thiessen區域指域分割後形成的多邊形區域，如果兩個區域具有非零長度的公共線段，則稱這兩個區域的生成點為Thiessen強鄰接點(strong Thiessen neigh-hours) ；如果它們的公共部分僅導一個點，則稱為Thiessen弱鄰接點(weak Thiessenneighbours)。一個嚴格凸的四邊形至多有一對相對頂點是Thiessen強鄰接點。Thiessen區域準則指對一個嚴格凸的四邊形三角化時，將Thiessen強鄰接點相連，若兩對相對頂點都是Thiessen弱鄰接點，則任選一對相連，這祥構造的三角化是最優的，見圖2。
圖2 Thiessen區域準則
(2)最小內角最大準則(max-min angle criterion)對一個嚴格凸的四邊形三角化時，有兩種選擇。最小內角最大準則就是要保證對角線連線後所形成的兩個三角形中的最小內角最大，此三角化為最優，見圖3。
圖3最小內角最大準則
(3)圓準則((circle criterion )設K是經過嚴格凸四邊形中三個項點的圓，如果第四個頂點落在圓內，則將第四個頂點與其相對的頂點相連，否則將另兩個頂點相連，見圖4。
圖4圈準則
Sibson證明了這三個準則的等價性，並指出符合這三個準則的三角化只有一個，即DeIsunay三角化.
(4)ABN準則(angles between normals)設T是散亂點集
的三角化。定義每一條內邊c的權值為與之相鄰的兩個三角面法矢量的夾角。若兩三角面處於同一平面上，則
對一個嚴格凸的四邊形三角化時，有兩種選擇。設這兩種對角線連線分別為e和e' , ABN準則就是要選擇。c(e)和c (e')中值較小的一種三角化。
(5)PLC準則(piecewise linear analog of curvature)設T是散亂點集的三角化。
是交於Pi點按逆時針方向排列的三角面，nj是各三角面的單位法矢量。則Pi點的權值函式定義為該點處n與nj夾角的平方和，PLC準則就是要保證三角化結果使得
最小。
處理流程
該方法處理流程為(圖5):
(1)將散亂數據進行三角剖分;
(2)進行空間三角最佳化;
(3)在每個三角形上建立五次C三角插值曲面;
(4)用平行截面截取三角曲面得到相應的截面線;
( 5)對截面線數據進行去重點、光順、勻化等處理，生成四邊形格線形狀的規則數。
( 5)對截面線數據進行去重點、光順、勻化等處理，生成四邊形。
圖5散亂數據規則化數據處理流程
方法描述
該方法的關鍵是建立散亂數據的插值曲面。散亂數據的插值方法已有很多，最常用的是局部的三角曲面插值方法。這種方法首先要在空間上形成三角形格線，然後在每個三角形上構造三角曲面片，它在三角形的三個頂點及其它有關點上滿足插值條件，各曲面片之間為光滑拼接不難看出，三角插值曲面構造的基礎是三角格線剖。
三角剖分
三角剖分將直接影響到三角插值曲面形態的好壞採用不同的三角剖分方法所得到的三角剖分結果相距很遠，導致建立在三角剖分上的三角插值曲面形態也相差很大。因此要選擇適當的三角剖分方法。
在三維散亂數據的曲面插值中，三角剖分是最基本也是最困難的問題之戈在實際套用中，按照三維散亂數據的基本分布特點可以把它們的三角剖分分成3個具有一定代表性的問題來討論。
(1)將三維散亂數據{(xi,yi,zi)，i = 1, 2, 3,... ,N}投影到某一平面，例如X一Y平面，把一個三維三角剖分問題轉化成平面上不規則點{(xi,yi,zi)，i = 1, 2, 3,... ,N}的三角圖1散亂數據規則化數據處理流程剖分問題，從而採用比較最佳化的平面三角剖分算法。
(2)當三維散亂數據與一些較規則的曲面沙口柱面球環等)相對應時，可採用一種對三維散亂數據進行直接三角剖分的算法。
(3)與多值曲面相對應的三維散亂數據的三角剖分問題，目前研究得很i}一種解決方法是將三維散亂數據分片，把分片數據投影到相應的平面上，先用平面上不規則點的三角剖分算法處理，然後將每片的三角剖分結果合併，再重新最佳化。
測量造型中的散亂測量數據絕大多數都屬於第一類情況。因此將三維散亂測量數據投影到某一平面，把三維散亂數據三角剖分問題轉化為平面散亂數據的三角剖分問題，然後由平面上的三角剖分格線得到空間三角剖分格線(點連線關係不變)。
從目前研究成果來看，平面散亂數據的三角剖分方法大都是對平面上散亂數據點的凸包進行三角剖分。對於非凸多邊形域，則是將其轉化為若干個凸域，分別對凸域內的散亂數據點進行Delaunary三角化，最後將各三角剖分結果合併，該方法存在以下缺點:
- (1)三角剖分結果不唯一，即選取不同的轉化方法，可得到不同的三角剖分結果。
- (2)各凸域合併處的三角化結果不夠理想，需要進行再最佳化
- (3)程式比較複雜
這裡，採用一種基於軌跡生成和邊界裁剪等技術以實現平面上任意邊界內部散亂數據的自動三角剖分方法：該方法具有5個特點：
- (1)三角剖分結果好。
- (2)剖分速度快。
- (3)適用面廣。
- (4)運行穩定可靠。
- (5)程式簡單。
空間三角最佳化
在曲面插值中，曲面的形態是否滿足要求是很重要的。對三維散亂點的三角插值曲面是以空間三角格線剖分為基礎的。因此，空間三角剖分對最終的插值曲面有明顯的影響事實上，空間三角剖分本身就是對給定的空間數據
的線性插值。
一般來講，從三角格線的形狀就可以大體上看出插值曲面的變化趨勢。那么基於上面的任意邊界內部散亂數據的三角剖分方法所得到的平面三角剖分，其對應的空間形狀很可能是“坑坑窪窪”的，如果依此構造空間C插值曲面，得到的曲面將會凹凸不平。
因此，還必須進行空間三角最佳化，根據三角剖分的空間形狀考慮三角剖分的好和壞，使空間三角格線具有良好的形態，即：
(1)曲面的起伏應儘量的少，也即有儘量少的凹凸變化次數或區域
(2)曲面變化均勻，出現儘量少的劇烈變化的區域。
建立五次已插值曲面
三角剖分經過空間最佳化後，在此基礎上建立的插值曲面具有比較好的形態根據測量造型的需要，採用局部的五次多項式C'插值曲面方法該方法具有一些特點:
- 簡單速度快。
- 曲面片之間是c連續的。
- 曲面片數較少。
- 便於求截面線。
生成規則數據
在三角剖分上完成c三角曲面插值之後，用一組平行截面截取三角曲面，得到一組平行截面線。當平行截面之間的距離越小時，所得的數據越密。在實用中可根據實物模型的特點，在數據變化劇烈的地方，截面取密一些，數據點變化平坦的地方，截面取稀一些，以節省計算時間。得到了每條截面線上若干個離散點後，還必須去掉重點，進行光順和勻化等處理，以得到比較好的規則的四邊形格線數據。
