gyorgy fekete 和 alex szalay
約翰霍普金絲大學

jim gray
microsoft（聯系作者）

適用于
microsoft sql server 2005

摘要：本文說明了如何使用 c# 和表值函數將空間搜索函數（“鄰近點的點”和“多邊形內的點”）添加到 microsoft sql server 2005。使用此庫可以在不編寫任何特殊代碼的情況下向應用程序中添加空間搜索。此庫實現了來自約翰霍普金絲大學的公共域 c# 分層三角網格 (htm) 算法。該 c# 庫使用一組標量值函數和表值函數連接到 sql server 2005。這些函數起空間索引的作用。

您可以下載本文檔的 microsoft word 版本。

本頁內容
 簡介
 表值函數：主要概念
 使用表值函數添加空間索引
 數據集
 典型查詢
 結束語
 附錄 a：參考資料
 附錄 b：基本 htm 例程

簡介
空間數據搜索常用于商業和科學應用程序。結合在針對天文領域構建 skyserver (http://skyserver.sdss.org/)方面的努力，我們開發了一種空間搜索系統。skyserver 是一個幾千 gb 大小的數據庫，其中收錄了大約 3 億個天體對象。天文學家需要對該數據庫進行的許多查詢都會涉及到空間搜索。典型的查詢包括：“鄰近此點的對象有哪些”、“此區域內包含哪些對象”以及“哪些區域與此區域有重疊”？

在本文中，我們向天文學家的赤經/赤緯 (ra/dec) 天球（天空）網格添加了緯度/經度 (lat/lon) 地球網格。這兩種網格大致相同，但并非精確對應，傳統順序 lat-lon 與 dec-ra 相對應。這一順序上的顛倒迫使我們必須明確坐標系。我們將格林尼治子午線-赤道大地坐標系稱為 latlon 坐標系。該庫支持三種坐標系：

• 格林尼治緯度-經度，稱為 latlon。
 
• 天文赤經-赤緯，稱為 j2000。
 
• 笛卡爾 (x, y, z)，稱為笛卡爾。 
 

天文學家使用弧度分作為標準的距離度量。由于一海里為一弧度分，因此距離轉換非常簡單。其他許多概念也極為相似。為了說明這些問題，本文將演示如何使用此空間庫針對兩個 usgs 數據集構建空間索引，這兩個數據集是：美國城市和美國流量計。本文使用這些索引和一些空間函數提供了若干示例，來說明如何搜索鄰近某一點的城市、如何查找鄰近某一城市的流量計以及如何查找某個州（多邊形區域）內的流量計或城市。

我們認為此方法具有通用性?？梢韵驇缀跛袘贸绦蛑刑砑涌臻g數據核心架構和空間數據函數以便進行空間查詢。這些概念也適用于其他的多維索引方案。例如，這些技術可用于搜索顏色空間或其他任何低維度度量空間。

返回頁首
表值函數：主要概念
關系代數的主要概念是，每個關系運算符均使用一個或多個關系，并生成一個輸出關系。sql 是對這一概念的語法修飾，使您可以定義關系（數據定義語言）和用選擇-插入-更新-刪除語法來操作關系。

定義自己的標量函數使您可以對關系數據庫進行擴展：您可以發送郵件，可以執行命令腳本，還可以計算非標準標量和聚合值，例如 tax() 或 median()。

但是，如果您可以創建表，則可以成為關系引擎的一部分：既是關系表的生成者，也是其使用者。這就是 oledb 的概念，此概念允許任何數據源生成數據流。這也是 sql server 2000 表值函數蘊含的概念。

在 transact-sql 中實現表值函數很簡單：

create function t_sql_tvfpoints()
returns @points table (x float, y float)
as begin
insert @points values(1,2);
insert @points values(3,4);
return;
end

如果可以完全在 transact-sql 中執行函數，這樣做就可以了。但是，在 sql server 2000 中，要在 transact-sql 外部實現 oledb 數據源或表值函數確實非常困難。

而 sql server 2005 集成了公共語言運行庫，可以容易地創建表值函數。您可以創建列表、數組或任意 ienumerable 對象（可以對其進行 foreach 操作的任意對象），然后將其轉換為表。

[sqlfunction(tabledefinition   = "x float, y float" ,
fillrowmethodname = "fillpair")]
public static ienumerable cspoints( )
   {
int[,] points = { { 1, 2 }, { 3, 4 } };
return (ienumerable) points;
   }

在 visual studio 中編譯這段代碼，然后單擊 deploy（部署）。表值函數將被安裝到數據庫中。

返回頁首
使用表值函數添加空間索引
對于索引，人們存在許多困惑。事實上，索引非常簡單：它們只是帶有一些特殊屬性的表：

• sql server 僅有一種關聯（按值）索引：b 樹。b 樹可以具有多字段鍵，但最常選擇的是第一個字段。
 
• 從概念上說，b 樹索引是由 b 樹鍵字段、基表鍵字段以及您要添加到索引的任何包含字段所組成的表。
 
• b 樹索引將根據索引鍵（例如郵政編碼或客戶 id）來排序，以便按該鍵進行查找或順序掃描會很快。
 
• 索引通常比基表小，只包含最重要的屬性，以便與檢查整個表相比，在索引中進行查找所涉及的字節數小得多。通常情況下，索引非常小，以致能完全裝在主內存中，從而省去更多的磁盤存取。
 
• 當您執行索引查找時，可能僅僅是搜索索引（基表的垂直部分），也可能是先搜索索引，再利用基表主鍵將符合要求的索引逐行加入基表中（書簽查找）。 
 

中心思想是，空間索引可為您提供一小部分數據。索引會告訴您查找的位置，并通常附帶一些有用的搜索信息（專家將其稱為包含列或覆蓋列）。索引的選擇性表明了初始縮減的程度（圖 1 所示的粗略子集）。找到相應的子集后，將仔細檢查該子集的每個成員并舍棄假正值。圖 1 中的菱形框指明了該過程。好的索引只含有少量的假正值。在整篇文章中，我們都將使用圖 1 中的說法（粗略子集和仔細檢查）。

圖 1

b 樹和表值函數可以如下組合，以使您可以構建自己的空間索引來生成粗略子集：

您無法始終讓每個鍵與其所有相關項鄰近，因為鍵是在一個維度中排序的，而相關項是在二維或更高維數的空間中與其鄰近。但是可以盡量這樣做。假正值與正確答案的比率衡量了您所采取的方式的好壞。

標準方法是，找到某一條空間填充曲線，并使鍵空間沿該曲線穿過。例如，使用標準墨卡托地圖，可以將西北中的每個人分配給西北鍵范圍，將東南中的每個人分配給東南鍵范圍。圖 2 顯示了第二種順序空間填充曲線，它橫穿所有這些象限，按順序分配鍵。西北-西南象限中的每個人都具有鍵前綴 nwsw。如果您的區域與圖 2 中所示的圓圈類似，就可以知道您的鍵范圍

   key between 'nwsw' and 'nwse'

圖 2

此搜索空間占整個表的八分之一，并且含有大約 75% 的假正值（由圓圈外但位于兩個方框內的區域表示）。改進不大，但傳達了一種概念。更好的索引要使用更精細的單元格分區。如果單元格足夠精細，則聚合區域中的假正值就會非常少。要詳細查看空間填充曲線和空間分區樹，您可以參閱 hanan samet [samet] 的書籍。

現在，我們要定義一種空間填充曲線：分層三角網格 (htm)，它特別適用于球面。地球是圓的，天球也是圓的，因此，這種球面系統對于地理學家和天文學家來說非常方便。我們可以對任何度量空間做一些類似的事情?？臻g填充曲線提供了一些鍵來作為空間索引的基礎。那么，如果某人具有所需的區域時，我們的表值函數將為其提供一組適當的鍵范圍供查找（圖 1 中的粗略篩選）。這些鍵范圍將覆蓋帶有球面三角形的區域（稱為 trixel），這與圖 2 中覆蓋圓圈的兩個方框非常相似。搜索函數只需查看這些 trixel 的鍵范圍內的所有對象，以確定它們是否符合要求（圖 1 中的仔細檢查）。

我們可以用一個具體的例子進行說明，假設有一個對象表

create table object (objid bigint primary key,lat   float, -- latitudelon   float, -- longitudehtmid bigint) -- the htm key

和一個距離函數 dbo.fdistancelatlon(lat1, lon1, lat2, lon2)，該函數可計算出兩點之間的海里（弧度分）數。進一步假設以下表值函數給出了位于某個 lat-lon 點的定長半徑范圍內的 htmid 點的鍵范圍列表。

define function fhtmcovercirclelatlon(@lat float, @lon float, @radius float)returns @trixeltable table(htmidstart bigint, htmidend bigint)

然后，以下查詢會查找舊金山 (lat,lon) = (37.8,-122.4) 周圍 40 海里范圍內的點。

select o.objid, dbo.fdistancelatlon(o.lat,o.lon, 37.8, -122.4)from fhtmcovercirclelatlon(37.8, -122.4, 40) as trixeltable join object o on o.htmid between trixeltable.htmidstart        -- coarse testand trixeltable.htmidend      where dbo.fdistancelatlon(lat,lon,37.8, -122.4) < 40   -- careful test

現在，我們必須定義 htm 鍵生成函數、距離函數和 htm 覆蓋函數。下一步我們將以兩組美國地質空間數據集為例執行這些操作。如果您不相信其中包含的對象達數十億，請訪問 http://skyserver.sdss.org/ 并瀏覽一下該網站。該網站使用相同的代碼來對幾千 gb 的天文數據庫進行空間查找。

本文主要講述如何使用 sql 表值函數和像 htm 這樣的空間填充曲線來構建空間索引。同樣地，我們將 htm 代碼本身當作一種在別處 [szalay] 存檔的黑色方框，我們只關注如何使其在 sql 應用程序內適合我們的需要。

返回頁首

數據集

美國地質勘探局 (usgs) 收集并發布了美國的相關數據。圖 3 顯示了由 usgs 維護的 18000 臺用于測量河流水流量和級別的流量計。usgs 還發布了 23000 個地點的地名及其人口的列表。

圖 3

usgs 居民點（23000 個城市）

usgs 在 1993 年發布了地點名稱及其某些屬性的列表。usgs 網站上有一些更新的列表，但由于它們是按州來分段的，因此很難獲得一個全國范圍的列表。舊的列表足以能夠演示空間索引。數據格式如下：

create table place(placename   varchar(100) not null, -- city namestate       char(2)      not null, -- 2 char state codepopulation  int          not null, -- number of residents (1990)households  int          not null, -- number of homes (1990)landarea    int          not null, -- area in sqare kmwaterarea   int          not null, -- water area within land arealat         float        not null, -- latitude in decimal degreeslon         float        not null, -- longitude decimal degreeshtmid       bigint       not null primary key --spatial index key)

為了加快名稱查找，我們添加了一個名稱索引，但數據是按空間鍵聚集在一起的。鄰近的對象共同位于聚集 b 樹中，并因此位于相同或相鄰的磁盤頁上。

create index place_name on place(placename)

可以從 usgs 網站下載除 htmid 數據以外的其他所有數據。可以用 sql server 2005 數據導入向導來導入數據（我們已在示例數據庫中進行了此操作）。htmid 字段是根據 latlon 按以下方法計算出的：

update place set htmid = dbo.fhtmlatlon(lat, lon)

usgs 流量計（17000 臺儀器）

usgs 自 1854 起一直在維護河流流量記錄。到 2000 年 1 月 1 日，他們已累積了超過 43 萬年的測量數據。大約有六千個活動的測量站處于活動狀態，而有大約四千個處于聯機狀態。http://waterdata.usgs.gov/nwis/rt 中對這些流量計進行了詳細介紹。有個 noaa 站點以非常便利的方式顯示了來自幾百個最普遍的測量站的數據：http://weather.gov/rivers_tab.php。

我們的數據庫只包含美國大陸的測量站（見圖 3）。關島、阿拉斯加、夏威夷、波多黎各和維京群島也有測量站，但不包含在此數據庫內。流量計測量站表為：

create table station (stationname   varchar(100) not null,     -- usgs station namestate         char(2)      not null,     -- state locationlat           float        not null,     -- latitude in decimallon           float        not null,     -- longitude in decimaldrainagearea  float        not null,     -- drainage area (km2)firstyear     int          not null,     -- first year operation yearsrecorded int          not null,     -- record years (at y2k)isactive      bit          not null,     -- was it active at y2k?isrealtime    bit          not null,     -- on internet at y2k?stationnumber int          not null,     -- usgs station numberhtmid         bigint       not null,     -- htm spatial key-- (based on lat/lon)primary key(htmid, stationnumber) )  

如上所述，htmid 字段是根據 latlon 按以下方法計算出的：

update station set htmid = dbo.fhtmlatlon(lat, lon)

由于一個位置有多達 18 個測量站，因此主鍵必須包括測量站編號以便區分它們。但是，在 b 樹中，htm 鍵將所有鄰近的測量站聚集在一起。為了加快查找，我們添加了測量站編號和名稱索引：

create index station_name   on station(stationname)create index station_number on station(stationnumber)

空間索引表

現在，我們就可以創建自己的空間索引了。我們本可以將字段添加到基表，但要使存儲過程對多個不同的表均有效，我們發現，只需將所有對象加入到一個空間索引中即可。您可以選擇 (type,htmid) 作為鍵來隔離不同類型的對象；我們選擇了 (htmid, key) 作為鍵，以便將所有類型（城市和流量計）的鄰近對象聚集在一起。該空間索引為：

create table spatialindex (htmid   bigint   not null , -- htm spatial key (based on lat/lon)lat     float    not null , -- latitude in decimallon     float    not null , -- longitude in decimalx       float    not null , -- cartesian coordinates,y       float    not null , -- derived from lat-lonz       float    not null , --,type    char(1)  not null , -- place (p) or gauge (g)objid   bigint   not null , -- object id in tableprimary key (htmid, objid) )

此主題后面將對笛卡爾坐標進行說明。至于現在，我們只需要知道，fhtmcenterpoint(htmid) 函數將返回該 htm 三角形中心點的笛卡爾 (x,y,z) 單位向量。這就是該 htm 的極限點，因為此中心被細分為無窮個小的 trixel。

spatialindex 表將根據 place 和 station 表的數據來填充，如下所示：

insert spatialindexselect   p.htmid, lat, lon, xyz.x, xyz.y, xyz.z, 'p' as type, p. htmid as objidfrom   place p cross apply fhtmlatlontoxyz(p.lat, p.lon)xyzinsert spatialindexselect s.htmid, lat, lon, xyz.x, xyz.y, xyz.z, 's' as type, s.stationnumber as objidfrom   station s cross apply fhtmlatlontoxyz(s.lat, s.lon) xyz

為了清理數據庫，應執行以下命令：

dbcc indexdefrag    (spatial  , station, 1)dbcc indexdefrag    (spatial  , station, station_name)dbcc indexdefrag    (spatial  , station, station_number)dbcc indexdefrag    (spatial  , place,   1)dbcc indexdefrag    (spatial  , place,   place_name)dbcc indexdefrag    (spatial  , spatialindex, 1)  dbcc shrinkdatabase (spatial  , 1  ) - 1 percent spare space

題外話：笛卡爾坐標

您可以選擇跳過此部分。此部分對于使用該庫并不是必需的。htm 代碼必須依靠一種技巧來避開球面幾何問題：它從球面的二維表面移到了三維空間。這就使得“在多邊形內”和“在點附近”查詢的檢查進行得非常快。

球面上的每個 lat/lon 點都可以表示為三維空間中的一個單位向量 v = (x,y,z)。北極和南極（90° 和 -90°）的單位向量分別為 v = (0,0,1) 和 v = (0,0,-1)。z 代表旋轉軸，xz 平面代表本初（格林尼治）子午線，其經度為 0° 或 180°。正式的定義為：

x = cos(lat)cos(lon)y =cos(lat)sin(lon)z = sin(lat)

這些笛卡爾坐標的使用方法如下：給定單位球面上的兩點 p1=(x1,y1,z1) 和 p2 = (x2,y2,z2)，則它們的點乘積 p1&p2 = x1*x2+y1*y2+z1*z2 就是這兩點所代表的單位向量之間的角度的余弦值。它是一個距離度量。圖 4 顯示了笛卡爾坐標如何使得對“多邊形內的點”和“鄰近點的點”的檢查快速進行。每個 lat/lon 點均具有一個對應的 (x,y,z) 單位向量。

圖 4

如果我們要查找 p1 點周圍 45 海里（弧度分）范圍內的點，則它與 p1 點最多成 45/60 度。這些點與 p1 的點乘積將小于 d=acos(radians(45/60)。該“鄰近”檢查即變為 { p2 | p2&p1 < d}，它將很快進行。在圖 5 中，每個大圓圈或小圓圈都是一個平面與該圓圈的交集，如果某一點與平面法向量的點乘積小于 cos(?¨)（其中 2?¨ 是該圓圈的弧度角直徑），則該點就在圓圈內部。

圖 5

笛卡爾坐標還可以使得對“多邊形內的點”的檢查快速進行。所有的多邊形都具有大圓邊或小圓邊。這些邊沿著與球面交叉的某個平面分布。因此，可以通過與該平面垂直的單位向量 v 及其位移來定義這些邊。例如，赤道就是向量 v = (0,0,1)，且位移為零。緯度 60° 由向量 v = (0,0,1) 及位移 0.5 來定義，而圍繞巴爾的摩市的 60° 緯度圈由向量 v = (0.179195, -0.752798, 0.633392) 及 0.5 個位移來定義。對于地點 p2，如果 p2&v < 0.5，則該地點就位于巴爾的摩市 60° 緯度圈內。同樣，可以通過計算出三個這種點乘積來確定某個點位于 htm 三角形內部還是外部。這是 htm 代碼如此有效和快捷的主要原因之一。

我們實現了若干輔助過程來進行從 latlon 到笛卡爾坐標的轉換。

本文稍后將用到這些函數，它們存檔在 api spec and intellisense [fekete] 中。

在此，該庫的默認設置為 21 級深度的 htm 鍵（第一級將球面分成八個表面區域，隨后每一級將球面三角形分成四個子三角形）。從表 1 中可看出，21 級深度的 trixel 相當小。最多可以將代碼修改為 31 級深度，這是因為不能超出 64 位表示法所占用的位數。

在表 1 中，每個 htm 級別都會細分球面。對于每個級別，此表均以度數、弧度分、弧度秒和米四種單位的平方形式表示了面積。trixel 列顯示了一些特征大?。耗J的 21 級深度的 trixel 大約為 0.3 平方弧度秒。usgs 數據在每 12 級深度的 trixel 具有大約半個對象。

返回頁首

典型查詢

現在，您應當可以執行一些查詢了。

查詢 1：查找鄰近點的點：查找鄰近某一地點的城鎮

最常見的查詢是查找鄰近某個特定地點或點的所有地點。考慮以下查詢，“查找馬里蘭州巴爾的摩市周圍 100 海里內的所有城鎮”。通過下面的方法來得到覆蓋巴爾的摩市周圍 100 海里（100 弧度分）范圍的 htm 三角形

select * -- find a htm cover 100 nm around baltimorefrom fhtmcovercirclelatlon(39.3, -76.6, 100)  

它將返回表 2 中所示的 trixel 表。即，fhtmcovercirclelatlon() 函數將返回“覆蓋”該圓圈（在本例中，是單個 trixel）的一組 htm 三角形。該圓圈內所有對象的 htm 鍵也位于這些三角形中之一內。現在，我們需要檢查所有這些三角形并舍棄假正值（圖 1 中的仔細檢查）。我們將按照與巴爾的摩市的距離對答案集進行排序，因此，如果我們需要找出最近的地點，只需選擇 top 1 where distance > 0 即可（我們要從中排除巴爾的摩市本身）。

declare @lat float, @lon floatselect @lat = lat, @lon = lon from place where place.placename = 'baltimore' and state = 'md' select objid, dbo.fdistancelatlon(@lat,@lon, lat, lon) as distancefrom spatialindex join fhtmcovercirclelatlon(@lat, @lon, 100)  on htmid between htmidstart and htmidend           -- coarse testand type = 'p'and dbo.fdistancelatlon(@lat,@lon, lat, lon) < 100 -- careful testorder by distance asc

表 2. 巴爾的摩市 htm 覆蓋緯度圈

此覆蓋聯接將返回 2928 行（粗略檢查）；其中 1122 行在 100 航空英里以內（仔細檢查）。它給出了 61% 的假正值：全部操作在 9 毫秒內完成。

由于這些是常見的任務，因此具有針對它們的標準函數：

fhtmnearbylatlon(type, lat, lon, radius)fhtmnearestlatlon(type, lat, lon)

這樣，上述查詢就變為

select objid, distance from fhtmnearestlatlon('p', 39.3, -76.61)   

查詢 2：查找某個方框內的地點

在顯示正方形的地圖或窗口時，應用程序通常需要查找某個正方形視區內的所有對象?？屏_拉多州幾乎完全是正方形的，它的西北角點為 (41°n-109°3'w)，西南角點為 (37°n-102° 3'e)。該州的中心點為 (39°n, -105°33'e)，因此可以用以該點為中心的圓圈覆蓋該正方形。

declare @radius floatset @radius = dbo.fdistancelatlon(41,-109.55,37,-102.05)/2select * from station where stationnumber in (select objid from fhtmcovercirclelatlon(39, -105.55, @radius) join spatialindex on htmid between htmidstart and htmidendand lat between 37 and 41and lon between -109.05 and -102.048and type = 's')option (force order)

本例在大約 46 毫秒內返回了 1030 個流量計?？屏_拉多州的其他五個流量計正好在其邊界上，散布于距離南緯 37°緯度圈不超過一海里的范圍內。如果將南緯從 37° 調整到 36.98°，則其他這五個測量站就會出現。（gis 系統和天文應用程序通常需要某一區域周圍具有緩沖區。此 htm 代碼包含對緩沖區的支持，在實際的應用程序經常會用到緩沖區。請查看參考資料 [szalay] 以了解具體操作方式。）此覆蓋圓圈返回了 36 個三角形。與 spatialindex 表的聯接返回了 1975 個流量計。其中包含 47% 的假正值。下一節將演示如何通過使用 htm 區域指定多邊形覆蓋而非圓圈覆蓋對此進行改進。

force order 子句比較麻煩：如果缺少該子句，查詢的運行時間會長十倍，因為優化器會將空間索引作為外部表進行嵌套循環聯接。如果這些表更大（包含數百萬行），優化程序有可能會采取其他計劃，但我們不能指望它。優化程序不可能無需提示就能針對上一部分中的所有查詢選擇正確的計劃。

查詢 3：查找某個多邊形內的地點

htm 代碼允許我們將此區域指定為圓圈、矩形、凸球面或這些區域的組合。特別地，htm 庫允許使用下面的線性語法來指定區域：

circlespec  := 'circle latlon '      lat lon radius  |  'circle j2000 '       ra  dec radius|  'circle [cartesian ]' x y z   radius  rectspec    := 'rect latlon '        { lat lon }2|  'rect j2000 '         { ra  dec }2|  'rect [cartesian ]'   { x y z   }2hullspec    := 'chull latlon '       { lon lat }3+|  'chull j2000 '        { ra dec  }3+|  'chull [cartesian ]'  { x y z   }3+convexspec  := 'convex ' [ 'cartesian '] { x y z d }*areaspec    := rectspec | circlespec | hullspec | convexspec regionspec  := 'region ' {areaspec}* | areaspec 

下面給出了區域指定示例：

'circle latlon 39.3 -76.61 100''circle cartesian 0.1792 -0.7528 0.6334 100'

'rect latlon 37 -109.55  41 -102.05'

'chull latlon 37 -109.55 41 -109.55 41 -102.051 37 -102.05'

'convex   -0.17886 -0.63204 -0.75401 0.00000          -0.97797  0.20865 -0.00015 0.00000           0.16409  0.57987  0.79801 0.00000           0.94235 -0.33463  0.00000 0.00000'

'region convex 0.7 0.7 0.0 -0.5 circle latlon 18.2 -22.4 1.75'

可以這些區域描述中的任意一個應用于 fhtmcoverregion() 例程，以返回一個 trixel 表，用來描述覆蓋該區域的一組 trixel（三角形區域）。用于此科羅拉多州查詢的較簡單的代碼為：

select s.* from (select objid from fhtmcoverregion('rect latlon 37 -109.55  41 -102.05') loop join spatialindexon htmid between htmidstart and htmidendand lat between 37 and 41and lon between -109.05 and -102.048and type = 's') as g join station s on g.objid = s.stationnumberoption (force order)

有必要使用這種不尋常的查詢格式來準確告訴優化器聯接的執行順序（以使“強制順序”選項正確運行）。很難以這種方式修改優化器，直到表值函數具有統計信息為止，估計它們會非常耗費資源。您必須強制使它們進入內部循環聯接。

此查詢將返回 1030 個流量計，而有 1365 個來自覆蓋范圍的候選項，因此包含 25% 的假正值。請注意，矩形覆蓋優于圓形覆蓋，因為后者包含 61% 的假正值。對于非矩形形狀的州，可以使用多邊形語法，但本文僅講述表值函數，而不講述 htm 算法。您可以在項目中以及項目的相關文檔中查看 htm 代碼。

可以轉換為凸球面進行類似的查詢。

select s.* from (select objid from fhtmcoverregion('chull latlon 37 -109.55 41 -109.55 41 -102.05 37 -102.05') loop join spatialindexon htmid between htmidstart and htmidendand lat between 37 and 41and lon between -109.05 and -102.048and type = 's') as g join station s on g.objid = s.stationnumberoption (force order) 

此查詢將返回 1030 個流量計，而有 1193 個來自覆蓋范圍的候選項，因此包含 14% 的假正值。在本例中，凸球面覆蓋比同等的矩形覆蓋更好。

查詢 4：高級主題：復雜區域

前面的示例給出了用于區域的語法，并對“鄰近點的點”和“矩形內的點”搜索進行了論述。區域可能會十分復雜。它們是多個凸形區域的布爾組合。我們無法在此詳細解釋區域的概念，但伴隨項目中的 htm 庫包含對區域進行布爾組合、簡化區域、計算區域頂點和計算區域面積的邏輯，還包含許多其他特性。[fekete]、[gray] 和 [szalay] 中介紹了這些概念。

為了初步理解這些概念，我們以猶他州為例。它的邊界可用兩個矩形來近似地定義：

declare @utahregion varchar(max)set @utahregion = 'region '  + 'rect latlon 37 -114.0475  41 -109.0475 ' -- main part+ 'rect latlon 41 -114.0475  42 -111.01  '  -- ogden and salt lake.

現在，我們可以用以下查詢來查找猶他州中的所有流量計：

select s.* from (select objid from fhtmcoverregion(@utahregion) loop join spatialindexon htmid between htmidstart and htmidendand (((     lat between 37        and      41)  -- careful testand (lon between -114.0475 and -109.04)) -- are we inside or ((   lat between 41        and      42)  -- one of the twoand (lon between -114.0475 and -111.01)) -- boxes?          )and type = 's' ) as g   join station s on g.objid = s.stationnumber  option (force order) 

覆蓋返回了 38 個 trixel。聯接返回了 775 個測量站。仔細檢查找到了猶他州中的 670 個測量站，另外有懷俄名州的兩個測量站正好位于接壤處（14% 的假正值）。

大多數州需要使用復雜得多的區域。例如，近似地將加利福尼亞州的邊界連起來的區域為：

declare @californiaregion varchar(max)set @californiaregion = 'region '+ 'rect latlon 39    -125 '    -- nortwest corner+   '42    -120 '    -- center of lake tahoe + 'chull latlon 39    -124 '    -- pt. arena+ '39    -120 '    -- lake tahoe.+ '35    -114.6 '  -- start colorado river+ '34.3  -114.1 '  -- lake havasu+ '32.74 -114.5 '  -- yuma+ '32.53 -117.1 '  -- san diego+ '33.2  -119.5 '  -- san nicholas is+ '34    -120.5 '  -- san miguel is.+ '34.57 -120.65 ' -- pt. arguelo+ '36.3  -121.9 '  -- pt. sur + '36.6  -122.0 '  -- monterey+ '38    -123.03 ' -- pt. rayesselect stationnumberfrom fhtmcoverregion(@californiaregion) loop join spatialindexon htmid between htmidstart and htmidend/* and <careful test> */and type = 's'    join station s on objid = s.stationnumber option (force order)

覆蓋返回了 108 個 trixel，一共包含 2132 個測量站。其中，1928 個位于加利福尼亞州內，因此假正值比率大約為 5%。但是仔細檢查并非小事。

針對地點而非測量站進行的相同查詢（包括仔細檢查）類似于以下代碼：

select * from place where htmid in (select distinct si.objidfrom fhtmcoverregion(@californiaregion)  loop join spatialindex sion si.htmid between htmidstart and htmidend and si.type = 'p'join place p on si.objid = p.htmidcross join fhtmregiontotable(@californiaregion) polygroup by si.objid, poly.convexid having min(si.x*poly.x + si.y*poly.y + si.z*poly.z - poly.d) >= 0      )    option (force order) 

此查詢使用加利福尼亞州的凸形半空間表示法和 [gray] 中介紹的技術來快速檢查某個點是否位于加利福尼亞州凸球面內。它返回了 885 個地點，其中 7 個位于與加利福尼亞州毗鄰的亞利桑那州（多邊形近似于加利福尼亞州的邊界）。它在 1ghz 的處理器上運行了 0.249 秒。如果不用 option(force order) 子句，其運行速度將變慢，需要花費 247 秒。

由于此要求十分常見，而且代碼極具技巧性，因此我們添加了 fhtmregionobjects(region,type) 過程，用來從空間索引中返回對象 id。由于此過程封裝了前面所示的兩個技巧性代碼，因此這兩個針對加利福尼亞州的查詢變為了：

select *                 -- get all the california river stationsfrom stationwhere stationnumber in   -- that are inside the region(select objid from fhtmregionobjects(@californiaregion,'s'))  select *                 -- get all the california citiesfrom placewhere htmid in           -- that are inside the region(select objid from fhtmregionobjects(@californiaregion,'p'))

針對科羅拉多州和猶他州的查詢也可以使用此例程來簡化。

返回頁首

結束語

在此所述的 htm 空間索引庫本身是有趣而又有用的?；谇蛎鏋椤岸噙呅蝺鹊狞c”查詢索引數據是一種便利的方法。但是，該庫還作為一個示例很好地說明了如何通過添加以諸如 c#、c++、visual basic 或 java 之類的語言進行實際計算的類庫來擴充 sql server 和其他數據庫系統。實現功能強大的表值函數和標量函數并將這些查詢及其永久數據集成到數據庫中的能力是一種非常強大的擴充機制，它將在保證對象關系數據庫的基礎上傳遞。這僅僅是個開頭。在接下來的十年中，編程語言和數據庫查詢語言有可能獲得更好的數據集成方式。這對于應用程序開發人員來說將是一件好事。

詳細信息請參見：

http://msdn.microsoft.com/sql/

項目編輯：susanne bonney

返回頁首

附錄 a：參考資料

返回頁首

附錄 b：基本 htm 例程

本節將介紹 htm 例程。附帶文檔 [szalay] 中含有用于每個例程的手冊頁，并且這些例程本身帶有批注以支持 intellisense。

在下面，lat 和 lon 以十進制度數表示（南部和西部緯度為負），距離以海里（弧度分）表示。

htm 庫版本：fhtmversion() 將返回版本字符串

例程將返回一個 nvarchar(max) 字符串來給出 htm 庫版本。

使用示例：

   print dbo.fhtmversion()

返回的內容類似以下結果：

   'c# htm.dll v.1.0.0 1 august 2005'

生成 htm 鍵：fhtmlatlon (lat, lon) 將返回 htmid

例程將返回該 latlon 點的 21 級深度的 htm id。

使用示例：

   update place set htmid = dbo.fhtmlatlon(lat,lon)

還有 fhtmxyz() 和 fhtmeq() 函數可供天文學家使用。

latlon 到 xyz：fhtmlatlontoxyz (lat,lon) 將返回點 (x, y, z)

例程將返回該 lat lon 點的笛卡爾坐標。

使用示例（這是標識函數）：

select latlon.lat, latlon.lon-360    from fhtmlatlontoxyz(37.4,-122.4) as xyz cross apply fhtmxyztolatlon(xyz.x, xyz.y, xyz.z) as latlon

還有 fhtmeqtoxyz() 函數可供天文學家使用。

xyz 到 latlon：fhtmxyztolatlon (x,y,z) 將返回點 (lat, lon)

例程將返回該 lat lon 點的笛卡爾坐標。

使用示例（這是標識函數）：

select latlon.lat, latlon.lon-360    from fhtmlatlontoxyz(37.4,-122.4) as xyz cross apply fhtmxyztolatlon(xyz.x, xyz.y, xyz.z) as latlon

還有 fhtmxyztoeq() 函數可供天文學家使用。

查看 htm 鍵：fhtmtostring (htmid) 將返回 htm 字符串

如果給定了 htmid，則例程將返回一個 nvarchar(32)，其形式為 [n|s]t1t2t3...tn，其中每個三角數字 ti 均為 {0,1,2,3} 格式，用以說明三角網格中該深度的 htm trixel。

使用示例：

print 'sql server development is at: ' + dbo.fhtmtostring(dbo.fhtmlatlon(47.646,-122.123))

返回結果：'n132130231002222332302'。

還有 fhtmxyz() 和 fhtmeq() 函數可供天文學家使用。

htm trixel 中心點：fhtmtocenterpoint(htmid) 將返回點 (x, y, z)

返回由 htmid 指定的 htm trixel 的笛卡爾中心點。

使用示例：

select * from fhtmtocenterpoint(dbo.fhtmlatlon(47.646,-122.123)) 

htm trixel 角點：fhtmtocornerpoints(htmid) 將返回點 (x, y, z)

返回由 htmid 指定的 htm trixel 的三個笛卡爾角點。

使用示例：

select * from fhtmtocornerpoints(dbo.fhtmlatlon(47.646,-122.123)) 

計算距離：fdistancelatlon(lat1, lon1, lat2, lon2) 將返回距離

以海里（弧度分）為單位計算兩點之間的距離。

使用示例：

declare @lat float, @lon floatselect @lat = lat, @lon = lon from  place where placename = 'baltimore' and state = 'md' select placename, dbo.fdistancelatlon(@lat,@lon, lat,  lon) as distancefrom place

還有 fdistancexyz() 和 fdistanceeq() 函數可供天文學家使用。

下面的例程可返回一個用作空間索引的表。所返回空間索引表的數據定義為：

spatialindextable table (htmid   bigint   not null , -- htm spatial key (based on lat/lon)lat     float    not null , -- latitude in decimallon     float    not null , -- longitude in decimalx       float    not null , -- cartesian coordinates,y       float    not null , -- derived from lat-lonz       float    not null , --,type    char(1)  not null , -- place (p) or gauge (g)objid   bigint   not null , -- object id in tabledistance float   not null , -- distance in arc minutes to objectprimary key (htmid, objid) )

查找鄰近的對象：fhtmnearbylatlon(type, lat, lon, radius) 將返回空間索引表

返回半徑范圍內特定類型的對象列表及它們到給定點的距離。該列表將按對象的位置由近到遠排列。

使用示例：

   select distance, place.*from fhtmnearbylatlon('p', 39.3, -76.6, 10) i join place on i.objid = place.htmidorder by distance

還有 fhtmgetnearbyeq() 和 fhtmgetnearbyxyz() 函數可供天文學家使用。

查找最近的對象：fhtmnearestlatlon(type, lat, lon) 將返回空間索引表

返回包含距離該點最近的特定類型對象的列表。

使用示例：

   select distance, place.*from fhtmnearestlatlon('p', 39.3, -76.6) i join place on i.objid = place.htmid

還有 fhtmgetnearbyeq() 和 fhtmgetnearbyxyz() 函數可供天文學家使用。

下面的例程將返回一個表，用以說明覆蓋所需區域的一組 trixel（him 三角形）的 htmidstart 和 htmidend。表的定義為：

trixeltable table (htmidstart   bigint not null , -- min htmid in trixelhtmidend     bigint not null   -- max htmid in trixel         )

圓圈區域 htm 覆蓋：fhtmcovercirclelatlon(lat, lon, radius) 將返回 trixel 表

返回覆蓋指定圓圈的 trixel 表。

使用示例：

declare @answer nvarchar(max)declare @lat float, @lon floatselect @lat = lat, @lon = lon from place where place.placename = 'baltimore' and state = 'md' set @answer = ' using fhtmcovercirclelatlon() it finds:      'select @answer = @answer  + cast(p.placename as varchar(max)) + ', ' + str( dbo.fdistancelatlon(@lat,@lon, i.lat, i.lon) ,4,2) + '  arc minutes distant.' from spatialindex i join fhtmcovercirclelatlon(@lat, @lon, 5)  on htmid between htmidstart and htmidend -- coarse testand type = 'p'                           -- it is a placeand dbo.fdistancelatlon(@lat,@lon, lat, lon) between 0.1 and 5  -- careful testjoin place p on i.objid = p.htmidorder by dbo.fdistancelatlon(@lat,@lon, i.lat, i.lon) ascprint 'the city within 5 arc minutes of baltimore is: ' + 'lansdowne-baltimore highlands, 4.37 arc minutes away'

還有 fhtmcovercircleeq() 函數可供天文學家使用。

htm 覆蓋的常規區域指定：fhtmcoverregion(region) 將返回 trixel 表

返回覆蓋指定區域的 trixel 表（本主題前面對區域進行了介紹）。

select s.* from  (select objid from fhtmcoverregion('rect latlon 37 -109.55  41 -102.05') loop join spatialindexon htmid between htmidstart and htmidendand lat between 37 and 41and lon between -109.05 and -102.048and type = 's') as g join station s on g.objid = s.stationnumberoption (force order)

常規區域指定：fhtmregiontonormalformstring(region) 將返回區域字符串

返回格式為 region {convex {x y z d}* }* 的字符串，其中已從每個凸形刪除多余的半空間；如 [fekete] 中所述，凸形已被簡化。

print dbo.fhtmtonormalform('rect latlon 37 -109.55  41 -102.05')

下面的例程將返回一個表，用以說明覆蓋所需區域的一組 trixel（him 三角形）的 htmidstart 和 htmidend。表的定義為：

regiontable (convexid     bigint not null , -- id of the convex, 0,1,...halfspaceid bigint not null     -- id of the halfspace -- within convex, 0,1,2,x           float  not null     -- cartesian coordinates ofy           float  not null     -- unit-normal-vector of z           float  not null     -- halfspace planed           float  not null     -- displacement of halfspace )                               -- along unit vector [-1..1]

將區域字符串轉換為表：fhtmregiontotable(region) 將返回區域表

返回一個表，用以將區域作為凸形組合來說明，其中每個凸形均為 x，y，z，d 半空間的交集。如 [fekete] 中所述，凸形已被簡化。本文第 4 節介紹了此函數的用法。

select *from dbo.fhtmtonormalform('rect latlon 37 -109.55  41 -102.05')

查找區域內的點：fhtmregionobjects(region, type) 將返回對象表

返回一個表，其中包含空間索引中具有指定類型且位于區域內的對象的對象 id。

select *            -- find colorado places.from places join where htmid inselect objid from dbo. fhtmregionobjects('rect latlon 37 -109.55  41 -102.05','p')

常規區域診斷：fhtmregionerror(region ) 將返回消息

如果區域定義有效，則返回“ok”；否則，返回描述區域定義問題的診斷信息，并且后跟區域的語法定義。

print dbo.fhtmregionerror ('rect latlon 37 -109.55 41 -102.05')