一種基於掃描線算法的動態容差設置方法

2023-10-18 19:44:29 1

專利名稱：：一種基於掃描線算法的動態容差設置方法
技術領域：
：本發明涉及應用於地理信息系統中的掃描線算法，特別地，涉及到一種基於掃描線算法的動態容差設置方法。
背景技術：
：地理信息系統(GIS)是一種特定的十分重要的空間信息系統。它是在計算機硬、軟體系統支持下，對整個或部分地球表層(包括大氣層)空間中的有關地理分布數據進行採集、儲存、管理、運算、分析、顯示和描述的技術系統。地理信息系統的核心是處理空間地理數據，包括點面疊加、線面疊加和面面疊加，所有的疊加分析都是基於關聯線段簇以及線段交點的處理。掃描線算法是經典的輸出線段交點的算法。此算法是由Bentley和Ottmann提出的，其最原始的目的是對給定一系列線段，求出所有這些線段的交點並輸出。其輸入是一系列線段，輸出是這些線段之間的交點。在掃描線算法的計算過程中，正確地求取線段的交點是非常重要的。然而實際計算中線段的坐標常常是用浮點數來表示的。浮點數的表示存在誤差，並且在浮點計算過程中，誤差會傳遞。因此每次計算過當前點的線段時，若不考慮誤差，或者採用了錯誤的誤差估計方法，有可能出現錯誤。現有技術中，或者僅是從理論上研究掃描線算法，認為所有數據均是精確的，忽略誤差問題；或者是簡單設置一個靜態數值作為容差。然而，掃描線算法在實際應用中，不能迴避誤差的存在；並且在地理信息系統中應用時，可能碰到不同坐標系的地理數據，而這些數據的數值範圍相差懸殊，例如以經綿度為單位的話，其數值大小小於1000;以千米為單位時，其數值大小可能在幾萬；以米為單位，其數值大小可能為幾百萬。因此靜態設置容差不能保證掃描線算法判斷事件點是否在線段上的正確性。
發明內容該發明目的是解決求取掃描線算法中浮點數值計算的容差問題，特別是解決在浮點計算存在誤差的前提下，用掃描線算法處理不同數量級的數據時的動態容差計算問題，從而正確判斷事件點是否在線段上，保證掃描線算法的正確性，即能正確求得所有交點，進一步地，保證了疊加分析的正確實現，使得地理信息系統可以提供更準確的地理信息。為實現上述目的，根據本發明的一個方面，提供了一種基於掃描線算法的動態容差設置方法，其包含如下步驟根據線段交點計算過程中的函數，利用公式i計算交點坐標的絕對誤差；根據確定點是否在線段上過程中的函數，利用公式i和交點坐標的絕對誤差計算容差；5(/(W.x))=/(|^))2+……+(|^(x))2公式i其中/表示關於變量^X2…、的函數，^y(^JC2,…X"))表示函數/的絕對誤差；把此容差設置為判斷點是否在線段上的容差。根據本發明的另一方面，提供了一種確定線段交點的方法，其包含如下步驟1)接收線段，得到事件點結構；2)從事件點結構中取得最小的事件點，對與此點關聯線段進行處理並更新事件點結構；3)事件點結構為空時，輸出交點集合；其中步驟2)包含計算線段交點，確定點是否在線段上，根據公式i計算容差，並把此容差設置為判斷點是否在線段上的容差。本發明效果在於能夠確定浮點數運算後的容差，進一步的，是在表示點坐標和線段等的浮點數值的運算存在誤差的前提下，正確判斷事件點是否在線段上，保證掃描線算法的正確性，即能正確求得所有交點，進一步地，保證了疊加分析的正確實現，使得地理信息系統可以提供更準確的地理信息。以下，結合附圖來詳細說明本發明的實施例，其中圖l是實際計算交點與理論交點偏移示意圖。圖2是掃描線算法流程圖。具體實施例方式關於誤差分析的方法，實際的科學計算的情況是錯綜複雜的，每次計算會產生新的捨入誤差並傳播前面各步已有的誤差，而運算次數又往往非常之多，常以數千萬計，誤差的累積過程是時增時減的，簡單的按單調增長估計是不可取的，因為那樣得到的誤差界會遠遠超出實際情況，甚至會完全掩蓋有用的結果。在實際應用中，由於多次運算中有捨入相抵，故實際誤差應當小得多。多次運算的誤差傳遞是相互獨立的，並且不可能同時取得極值，應該採用一種樂觀的方式來進行誤差分析。根據正態分布的"3a原則"，n次運算的累積誤差以99.97%的概率保證s其中S是測量或計算的誤差界，^是每次測量的誤差。此公式表明誤差產生與傳遞無關。在物理或者化學實驗分析中，測量誤差是許許多多微小的偶然因素共同作用的結果，必然服從正態分布。由這些服從正態分布的並且相互獨立的測量誤差參與計算而造成的誤差分析常採用如下高斯誤差傳遞公式《x土力-^^2(x)+^(力；心(—)=^-^-,少7一般地，5(/(Xl，X2,...、))=(!^(^))2+……+(^^(X))2。因為浮點數的精度都是有限的，所以掃描線算法中用浮點數表示點坐標和線段，在計算過程中會不可避免地產生誤差。浮點計算經過多次運算後，由初始均勻分布的捨入誤差造成累積誤差必然服從正態分布(O,CT)。雖然初始誤差分布為均勻分布，但是經過幾步的計算之後，必然近似服從正態分布。因此把在物理化學測量或者計算中常用的高斯誤差傳遞公式運用到浮點計算的誤差分析中來。6掃描線算法的流程如圖2所示，詳細描述如下首先初始化以所有線^:端點初始化事件點結構Q並排序；初始化當前激活線段束R為空集合；當前所有線段有序集合為S;當前輸出交點集合I為空集合。判斷Q是否是空，如果是空集合，則計算結束，I即為計算而得的交點的集合；否則循環以下操作直至Q是空集合。從Q中取得最小的事件點P，並將其從Q中刪除。查找R中以p為終點的線段，刪除線段；根據容差查找R中經過p且p不是線段端點的線段，則此點是正常相交的交點，輸出此點到I;並且，將這些線段的順序反置；從S中選取從此點起始的線段，從S中刪除，加入到R中去。以上三個操作每查找到一個線段後，計算查找到的線段與其相鄰線段可能存在的交點，如果存在則把交點添加到Q中去。針對算法進行分析可得計算可能存在的交點時就產生誤差，即求得的交點並不恰好是兩線段的理論交點，而是有微小的偏移，如圖1所示。而查找R中經過p且p不是線段端點的線段時也會繼續產生誤差，且需要判斷這個誤差結果是否小於容差，從而正確判斷點p是否在線段上。掃描線算法中判斷當前事件點是否在線段上一般用下述公式來實現。det=(point.x-head.x)*(tail.y-pointy)-(point.y-head.y)*(tail.x-point.x)其中point是當前點，head和tail分別是當前線段的兩端點，x、y分別表示點的橫、縱坐標值。當det等於0時，點point在線段上；否則，點point不在線段上。在此需要考慮誤差。若簡單地判斷det--O，因為浮點計算的誤差問題，必然不能正確得到過某點的線段；若設定一個靜態值，又因浮點計算的誤差與數值的大小相關，則這個靜態值對某些數據可能正確，對其他數據可能不正確。本發明提供了一種動態設置容差的掃描線算法，根據要求交點的線段的外包來確定數值的大體範圍，根據計算可能存在的交點步驟，計算此過程產生的交點坐標的絕對誤差；再根據查找R中經過p且p不是線段端點的線段步驟，也即確定點p是否在線段上的步驟，以及已經得到的交點絕對誤差進一步計算此過程產生的誤差，即容差；在掃描線算法進行過程中，根據此容差確定過事件點p的線段。以上分析對自然分布的數據均成立。以外包即包含圖層的最小外接矩形的長寬是106數量級、一般的相對坐標值即某一局部範圍內點的坐標差值在x或者y坐標方向上是105數量級的數據為例，具體描述本發明。計算可能存在的交點，並計算此過程所產生的誤差的具體過程如下，其中兩線段分別以head0和tail0,headl和taill為起點和終點，所求交點為inter;x和y分別表示橫、縱坐標；A代表相對誤差；5代表絕對誤差分別計算起點和終點的坐標差值doublezx=tail0.x-head0.x;doublezy=tailO.y-head0.y;doubleox=taill.x-headl.x;doubleoy=tail1.y-head1.y;doubleozx=headO.x-headl.x;doubleozy=headO.y-headl.y;以上六組運算中各個參數的坐標值都是精確的，則兩個精確的數值的減法運算，其結果只有捨入誤差。雙精度浮點數的相對捨入誤差為△=1.11x10—16。捨入誤差與計算過程無關，是得到的計算結果需要捨入以在計算機中表示出來而引起的誤差。doubledenominator=zx*oy-zy*ox;此運算有三次誤差傳遞，兩次乘法，一次減法；乘法傳遞相對誤差，為V^xl.llx10—16=1.57xl(T16,捨入誤差為1.11x10—16。此相對誤差指由於計算造成的傳遞誤差，其與捨入誤差是相互獨立的。因此，△Ox*o力=A(2y*ox)=>/l.572+l.ll2x1(T16=2x10-16。根據數據的特點，zx、zy、ox、oy、ozx、ozy等是小於105數量級數據。3(zx*oy)=5(zy*ox)=2x10_16x1010=2x10—6。5(denominator)=x2x10-6=2.8x10-6。根據對1X數量級的數據，其積約為10(2X—"數量級的統計規律，得到denominator為109數量級的數據。A(denominator)=2.8xl0—6+10—9=2.8x10—15〉>1.1lx10—16的捨入誤差，因此從這一步開始不再考慮捨入誤差。doublenumeratorO=ox*ozy-oy*ozx;numerator0與以上denominator的i吳差分鬥斤相同。doubleUa=numeratorO/denominator;傳遞相對誤差A(Ua)=V^x2.8x1(T15=3.9xl(T15。i殳置inter點的坐標為(headO.x+Ua*zx,headO.y+Ua*zy),對此坐標值，其絕對誤差是^:3.9xlO-"xl0^3.9xl(T10。查找R中經過p且p不是線段端點的線段，也就是判斷p點是否在線段上，通過判斷線段的端點和p點所構成的三角形的面積是否為O的操作完成，如果面積為0則點在線段上。此計算過程不考慮捨入誤差，因為此處的點p是上述計算的可能存在的交點，其誤差已經遠遠大於浮點表示的捨入誤差。本計算的具體過程如下，其中，head和tail對應線段的兩個端點，x和y分別表示橫、縱坐標doublexl=p.x-head.x;doubleyl=p.y-head.y;doublex2=tail.x-p.x;doubley2=tail.y隱p.y;在此head,tail的數據均非中間結果，都是初始的輸入數據，沒有誤差，則根據求得的交點的誤差，上面各個差值的絕對誤差為3.9x10—1Q。doubledet=xl*y2-x2*yl;此運算有三次誤差傳遞，兩次乘法，一次減法，只考慮傳遞誤差△(xl)=A(_yl)=A(x2)=A(>2)=3.9x1(T10+105=3.9x1(T15。所以誤差^:^V^x3.9x10—"xl(^xV^二7.8x10—5,則此值即為根據本發明思想，依據數據計算的動態容差。判斷det的絕對值是否小於誤差3=7.8x10—5，如果小於則點在線段上，否則，線段不過該點。以上是對106數量級數據的誤差分析。在整個分析過程中，有一些假設，即外包的數量級下，都是一些自然的數據，即坐標的數量級小於外包的數量級。對任意外包為(1X)數量級的數據，帶入到上述分析過程，可得其容差計算公式為'.7.8xl0(2〃17),其中X為數量級。此容差僅僅適用於用上述方法計算交點、並判斷點是否過線段的思路。根據本發明思想，針對不同的計算流程，有不同的誤差容差計算公式。在真實地理數據的測試中，用此公式計算得到的容差保證了算法的正確性，實驗數據如下表所示9表l測試以上述代碼分析的外包為106的數據結果tableseeoriginaldocumentpage10本發明計算而得的容差為7.8x10—5,上表真實地理數據的測試說明了用本發明計算的動態容差以極大概率地大於計算過程中產生的誤差，表明本方法能保證算法的正確性。本發明對於數值採用浮點數表示並且需要判斷數值是否完全相等的問題提供了一種解決思路。應該注意到並理解，在不脫離後附的權利要求所要求的本發明的精神和範圍的情況下，能夠對上述詳細描述的本發明做出各種修改和改進。因此，要求保護的技術方案的範圍不受所給出的任何特定示範教導的限制。權利要求1.一種基於掃描線算法的動態容差設置方法，其包含如下步驟根據線段交點計算過程中的函數，利用公式1計算交點坐標的絕對誤差；根據確定點是否在線段上的過程中的函數，利用公式1和所述交點坐標的絕對誤差計算容差；公式1其中f表示關於變量x1，x2，…xn的函數，δ(f(x1，x2，…xn))表示函數f的誤差；將所述容差設置為判斷點是否在線段上的容差。2.根據權利要求1所述的方法，其特徵在於，對於/^x士y，3.根據權利要求1所述的方法，其特徵在於，對於/^;cxy，4.根據權利要求l所述的方法，其特徵在於，對於/=王，少少25.—種確定掃描線交點的方法，其包含如下步驟1)接收線段，得到事件點結構；2)從所述事件點結構中取得最小的事件點，對與此點關聯線段進行處理，更新所述事件點結構；3)所述事件點結構為空時，輸出交點集合；其中步驟2)包含根據線段交點計算過程中的函數，利用公式1計算交點坐標的絕對誤差；根據確定點是否在線段上過程中的函數，利用公式1和所述交點坐標的絕對誤差計算容差；將所述容差設置為判斷點是否在線段上的容差。6.根據權利要求5所述的方法，其特徵在於，所述與此點關聯線段包含終止於此點的線段、經過此點的線段或者始於此點的線段。7.根據權利要求5所述的方法，其特徵在於，對於/=^±;;,8.根據權利要求5所述的方法，其特徵在於，對於/^xx少，9.根據權利要求5所述的方法，其特徵在於，對於/=土，全文摘要本發明提供一種掃描線算法，包括步驟根據計算容差的公式和計算線段交點的過程，計算交點坐標的絕對誤差；根據計算容差公式、交點坐標的絕對誤差和確定點是否在線段上的計算過程，計算判斷點是否在線段上的容差；根據此容差確定事件點是否在線段上。本發明能夠確定浮點數運算後的容差，進一步的，是在表示點坐標和線段等的浮點數值的運算存在誤差的前提下，正確判斷事件點是否在線段上，從而保證掃描線算法正確性。文檔編號G06F17/10GK101458678SQ20071017958公開日2009年6月17日申請日期2007年12月14日優先權日2007年12月14日發明者方金雲,朱效民,程振林,林齊申請人:中國科學院計算技術研究所