一種複雜矢量多邊形圖形空間疊置分析製圖方法

2023-05-13 02:21:31

專利名稱：一種複雜矢量多邊形圖形空間疊置分析製圖方法
技術領域：
本發明涉及一種複雜矢量多邊形圖形空間疊置分析製圖方法，其核心技術是基於矢量多邊形圖形與精度遊程編碼圖形混合疊置處理的方法，屬於地理信息系統中的空間分析製圖和空間數據挖掘等技術領域。
背景技術：
矢量多邊形圖形空間疊置分析是對兩個包含空間要素拓撲關係的不規則面元集合實施的空間疊合操作，它將兩幅單要素麵狀圖層進行疊置產生一個新的要素圖層，新的要素圖層綜合了兩幅原地層要素具有的屬性，並建立了新的要素圖層單元與兩個疊置圖層單元之間的隸屬關係。矢量多邊形圖形空間疊置分析不僅生成了新圖形及其空間關係，而且還將輸入的多個數據層的屬性聯繫起來產生了新的屬性關係。從原理上說，矢量多邊形圖形空間疊置分析是對面狀分布的多層空間要素按一定的數學模型進行計算分析，其中涉及到邏輯交、邏輯並、邏輯差等運算。·矢量多邊形圖形空間疊置分析可以形象的理解為對一幅按某種要素分級或分類所做的空間分割圖形，再按另一種要素分級或分類做新的一輪空間分割。通過矢量多邊形圖形拓撲疊置分析可以對多幅圖層要素地圖進行綜合，獲得在幾何面積上更為細碎而在要素指標更為多元的詳細分類圖層，提供各個原始圖層無法單獨明確界定的有價值的空間信息。兩幅矢量多邊形圖形的疊置分析是多邊形圖形空間疊置分析製圖的基本操作，多次調用該操作可以實現多幅矢量多邊形圖形的疊置分析製圖。通常，實現矢量多邊形空間疊置分析製圖主要通過相互疊置圖形間多邊形圖形鏈段的求交、分解、重組和拓撲關係重建等幾個步驟，但是隨著地理信息分析技術應用的深入，分析區域的擴大和高精度分析需求的激增，面臨的問題將日趨複雜，現有方法通常難以承受形態複雜和具有海量圖斑單元矢量多邊形圖形間拓撲疊置分析製圖所消耗的計算資源，其處理效率瓶頸凸顯，分析可靠性受至IJ挑戰，迫切需要高效、簡便、可靠和實用的新技術出現。據申請人了解，目前已有的方法大致可分為直接方法和間接方法兩類一是直接方法即純碎的矢量求交方法，需要對疊置圖形的所有多邊形圖形鏈段進行相交判別，對相交鏈段進行交點計算和分解，最後重建拓撲關係。為了檢出兩幅多邊形圖形間可能相交的鏈段，過濾空間相離的鏈段，減少不必要的求交計算，出現了外包矩形檢測法、矢量柵格方法、柵格輔助法等，這些方法在一定程度上提高了分析製圖的效率，但對較大幅面的複雜圖形而言，算法增加的額外空間與時間開銷依然過大，仍然可能超出可接受的範圍，制約了方法的實用性；二是間接方法，即先將參與疊置的多邊形圖形轉換為一定精度的柵格圖形，再對柵格圖形進行疊置，最後將疊置後的柵格圖形轉換為矢量多邊形圖形，並建立相應的拓撲關係。由於矢量多邊形圖形與柵格圖形之間的轉換是一種精度損耗的圖形格式變換，疊置分析獲得的矢量多邊形圖形的精度取決於採用的柵格精度，而高精度柵格分析通常會急劇增加存貯空間，其格式雙向轉換及疊置處理時間也會大幅提升，可行性降低。因此，間接方法及算法的空間和時間複雜度同時受到圖形複雜程度和柵格精度的雙重製約，其實用性受到影響，難以成為性能穩定和高效的空間疊置分析方法。

發明內容
本發明的目的在於提出一種面向複雜圖形、可靠和高效的矢量多邊形圖形空間疊置分析製圖方法。具體而言，針對上述現有技術存在的問題，提出一種簡化兩幅矢量多邊形圖形疊置過程中鏈段求交分解和成果矢量多邊形圖形拓撲關係構建的方法，即基於矢量多邊形圖形與精度遊程編碼圖形混合疊置的複雜矢量多邊形圖形空間疊置分析製圖方法，從而提高矢量多邊形圖形空間疊置分析製圖技術的魯棒性和實用性。本發明設計了用於混合疊置處理的精度遊程編碼，其存儲格式有別於常規柵格遊程編碼，它按預定的縱向精度間隔將矢量多邊形圖形劃分為一系列相同高度的水平條帶，每個條帶對應一個遊程記錄表，其中有序排列的一組遊程記錄對應條帶中的各個區段，每個遊程記錄相應區段的起始位置(多邊形圖形鏈段與該條帶中間掃描線交點)的Z坐標和區段所處(交點右側)的多邊形編碼。由於按預定縱向精度間隔劃分的條帶上的遊程以表示區段起始位置精確的z坐標數值取代了常規遊程的柵格數，因此可使精度遊程編碼存儲的圖形無精度損失。 精度遊程編碼記錄數據結構
Struct RLEncoding {
double X;//鏈段與掃描線交點x坐標
int rightpoly;//交點右側多邊形編碼
}
假設參與疊置的兩幅矢量多邊形圖形分別為圖A和圖B，疊置獲得的矢量多邊形圖形為圖C，本發明可實現五種空間疊置模式，分別是Α Β、Α(；Β、(AEB) gA, (Α Β)卬、A_B，即圖A與圖B並、圖A與圖B交、圖A域內的Α Β、圖B域內的Α Β、圖A與圖B差。本發明參與疊置分析的矢量多邊形圖形的組成多邊形面元具有預定的編碼標識——多邊形編碼，疊置成果矢量多邊形圖形的組成多邊形面元也具有唯一的編碼標識——多邊形編碼，且具有簡略的空間關係表達形式，採用無冗餘的空間數據存儲方式，相鄰多邊形的共同邊界鏈段只存儲一次，其數據結構主要包括多邊形圖形鏈段索引記錄表、鏈段坐標數據表和多邊形屬性表(DBF數據格式)，鏈段索引在記錄鏈段坐標存儲位置和存儲長度的同時，也記錄了鏈段兩側的多邊形編碼，以表示與相鄰多邊形的空間關係。Struct LinkIndex { //多邊型鏈段索引表記錄結構
long Link_id;//鏈段標識碼
long LeftPolycode;//左側多邊形編碼(左區碼)
long RightPolycode; //右側多邊形編碼(右區碼) long Coordadd;//坐標起始位置
long CoordCount;//鏈段坐標個數
}
歸納起來，為了達到以上目的，本發明提出的複雜矢量多邊形圖形空間疊置分析製圖方法包括以下基本步驟
步驟I、圖形轉換——分別將兩幅矢量多邊形圖形(A、B)轉換成相應的精度遊程編碼圖形(參見圖4-c和圖4-d的AK、BK)，所述精度遊程編碼由遊程表示區段起始位置的X坐標和區段所處多邊形的編碼構成；
步驟2、交叉混合疊置處理——分別以轉換得到的兩幅精度遊程編碼圖形中的一幅為背景底圖，以交叉方式對另一幅矢量多邊形圖形鏈段進行上覆遍歷疊置、跨多邊形檢測和分解，分別得到對應兩幅疊置矢量多邊形圖形的兩組分解和未分解鏈段(參見圖4-g和圖4-h)；
步驟3、篩選構圖鏈段——按照預定疊置模式對疊置產生的兩組分解和未分解鏈段進行篩選，篩選出符合疊置模式的合格鏈段作為疊置成果矢量多邊形圖形的組成鏈段(參見圖I);
步驟4、構建含有確定空間關係的疊置成果矢量多邊形圖形——按預定規則對疊置成 果矢量多邊形圖形的組成鏈段進行左右多邊形區域編碼，構建疊置成果矢量多邊形圖形組成鏈段與其兩側多邊形面元的空間拓撲關係，以及疊置成果矢量多邊形圖形面元與所述兩幅矢量多邊形圖形面元的隸屬關係，構成含有空間關係的疊置成果矢量多邊形圖形(參見圖 4-i)。簡言之，本發明先對矢量多邊形圖形A和B進行數據格式轉換處理，分別獲得相應的兩幅精度遊程編碼圖形K和Bk ;將矢量多邊形圖形A與圖B的精度遊程編碼圖形Bk進行空間疊置操作，再將矢量多邊形圖形B與圖A的精度遊程編碼圖形Ak進行空間疊置操作；兩次疊置獲得的鏈段經過疊置模式篩選和空間關係構建後，最終構成成果矢量多邊形圖形C0本發明針對複雜矢量多邊形圖形空間疊置分析製圖中鏈段求交分解和疊置成果圖形拓撲關係構建等困難問題，提出將參與疊置的兩幅矢量多邊形圖形分別與對方圖形的精度遊程編碼圖形混合疊置處理的方法。通過基於精度遊程編碼圖形的點面包含分析，對跨越多邊形的矢量鏈段進行交點計算和分解處理，避免了兩幅複雜矢量多邊形圖形直接疊置所帶來的大量鏈段相交判斷和可能出現的誤判及遺漏，同時上述處理過程為成果矢量多邊形圖形空間關係的構建帶來方便，非常有利於有效建立新的拓撲關係。從分析製圖的可操作性角度來看，將矢量多邊形之間複雜的空間拓撲疊置問題簡化為矢量多邊形圖形與精度遊程編碼圖形間的疊置問題，可以在保證疊置精度的前提下使疊置成果矢量多邊形圖形的鏈段生成及其拓撲關係構建變得直觀、可靠和易於實現，提高了矢量多邊形圖形空間疊置分析製圖技術的可操作性、魯棒性和實用性。


下面結合附圖對本發明作進一步的說明。圖I為本發明的5種模式的矢量多邊形圖形空間疊置示意圖。圖2為本發明一個實施例的流程圖。圖3為圖2實施例中矢量多邊形圖形與精度遊程編碼圖形疊置時鏈段求交與分解處理流程圖。圖4為本發明一個實施例具有相同矩形輪廓兩幅矢量多邊形圖形空間疊置示意圖。圖中黑點為鏈段結點，菱形點為探測節點，白點為跨界交點(新結點)。
具體實施方式
實施例一
本實施例的複雜多邊形空間疊置分析製圖方法實現步驟如下(參見圖2)
步驟I、圖形轉換——分別對參加疊置的兩幅矢量多邊形圖形A和B進行轉換處理，生成它們相應的精度遊程編碼圖形K和Βκ，以備混合疊置分析時使用。具體轉換步驟如下第i-ι步、以預定的縱向精度間隔在疊置分析製圖矩形範圍內布設水平掃描線，為每條水平掃描線設置一個記錄多邊形圖形鏈段穿越次數計數器；遍歷矢量多邊形圖形A的各條鏈段，將所述鏈段穿越各掃描線的次數分別記錄到對應的計數器中；
第1-2步、根據穿越次數計數器的計數結果建立分別對應每條掃描線的遊程編碼表(該編碼表的存儲空間根據計數器的計數結果確定)，所述遊程編碼表用於逐一記錄各條多邊形圖形鏈段穿越掃描線時交點的X坐標及其右側多邊形的編碼；
第1-3步、再次遍歷矢量多邊形圖形A的所有鏈段，計算所述鏈段穿越掃描線時交點的X坐標，連同交點右側的多邊形編碼逐一存儲到對應的遊程編碼表中(當鏈段由下向上穿越·掃描線時，交點右側的多邊形編碼為鏈段的右區碼，當鏈段由上向下穿越掃描線時，右側的多邊形編碼為鏈段的左區碼)；
第1-4步、以精度遊程編碼表中記錄的X坐標為關鍵字，分別對各條掃描線的精度遊程編碼表做遞增排序，獲得矢量多邊形圖形A的精度遊程編碼圖形Ak ；
第1-5步、對另一矢量多邊形圖形B重複上述4個步驟的處理過程，得到相應的精度遊程編碼圖形Βκ。(參見圖4-c和圖4-d，其中虛線為遊程條帶間的界線，掃描線則處於相鄰虛線之間的中線上)。步驟2、交叉混合疊置處理(參見圖3)—分別以轉換得到的兩幅精度遊程編碼圖形中的其中一幅為背景底圖，按交叉方式對另一幅待疊置的矢量多邊形圖形的鏈段進行上覆遍歷疊置、跨多邊形檢測和分解，分別得到對應兩幅疊置矢量多邊形圖形的兩組分解和未分解鏈段(參見圖4-g和圖4-h)。具體按以下各步對待疊置矢量多邊形圖形與精度遊程編碼圖形混合疊置處理
第2-1步、以精度遊程編碼圖BBk為背景底圖，按順序對矢量多邊形圖形A的每條鏈段進行跨B圖多邊形探測。以預定探測步長依次判斷當前處理鏈段中的相鄰探測節點落入背景底圖的多邊形區域是否發生改變(採用點面包含分析)，當判斷到的相鄰兩個探測點落入背景底圖不同多邊形區域時，則在這兩個相鄰探測點的連線上採用折半逼近法計算跨越點坐標，並在跨越點(即交點)處分解該鏈段，對多次跨越背景底圖不同多邊形的鏈段則實施多次分解，對從未跨越底圖不同多邊形的鏈段不進行分解(參見圖3以及圖4-e和圖4-g)；第2-2步、以精度遊程編碼圖形K為背景底圖，按順序對矢量多邊形圖形B的每條鏈段進行跨A圖多邊形探測。以預定探測步長依次判斷當前處理鏈段中的相鄰探測節點落入背景底圖的多邊形區域是否發生改變，當判斷到的相鄰兩個探測點落入背景底圖不同多邊形區域時，則在這兩個相鄰探測點的連線上採用折半逼近法計算跨越點坐標，並在跨越點處分解該鏈段，對多次跨越背景底圖不同多邊形的鏈段則實施多次分解，對從未跨越背景底圖不同多邊形的鏈段不進行分解(參見圖4-f和圖4-h)。以上混合疊置處理中上覆矢量多邊形圖形鏈段探測點落入背景底圖多邊形區域的點面包含判斷方法為根據探測點的y坐標直接定位到背景底圖相應掃描線的精度遊程編碼表，再根據探測點的X坐標對該精度遊程編碼表進行折半查找，檢索到探測點所處的遊程區段，從而獲得探測點在背景底圖中所處的多邊形區域及其編碼。多邊形圖形鏈段跨越背景底圖多邊形區域的跨越點(交點)坐標折半逼近計算方法為根據跨越點兩側相鄰探測點坐標計算中點坐標，以中點坐標代替與其落入背景底圖同樣多邊形區域的相鄰探測點坐標，使兩個相鄰探測點逼近跨越點，重複上述逼近過程直到兩個相鄰探測點充分接近(距離小於預定精度)時，它們的中點坐標即為跨越點坐標。例如，圖4-e中探測點r和《落入背景底圖的不同多邊形區域，以它們作為最初的相鄰探測點，採用折半逼近計算方法即可計算出處於它們連線上的跨越點。需要說明的是，如果待疊置矢量多邊形圖形A和B的外輪廓邊界完全一致(如圖4-a和圖4-b)，混合疊置處理時，矢量多邊形圖形A的所有鏈段參加疊置(如圖4-e)，而矢量多邊形圖形B只有內部鏈段參加疊置(如圖4-f )，此時對矢量多邊形圖形A的外輪廓鏈段(左多邊形編碼或右多邊形編碼為O的鏈段)上的探測點採用鄰近原則判別其落入B圖中的多邊形區域。例如，圖4-e中矢量多邊形圖形A矩形外輪廓右側鏈段上的探測點可能落入所在Bk遊程條帶的最後區段(區段編碼為0)，此時取鄰近的非O遊程區段即左側的遊程 區段作為其落入區段。步驟3、篩選構圖鏈段——按預先設定的疊置模式將組成疊置成果矢量多邊形圖形的相關鏈段篩選出來，即按照預定疊置模式對疊置產生的兩組分解和未分解鏈段進行篩選，篩選出符合疊置模式的合格鏈段作為疊置成果矢量多邊形圖形的組成鏈段(參見圖I);本發明支持的五種空間疊置模式分別是Α Β、Α(；Β、(AEB)gA, (AEB)gB,A-B,即圖A與圖B並、圖A與圖B交、圖A域內的Α Β、B圖域內的Α Β、A圖與B圖差(參見圖I)。按各種疊置模式篩選疊置產生鏈段的處理分別為
第3-1步、預定疊置模式為並模式——此模式對圖A與圖B疊置產生的所有多邊形均予以保留，兩次混合疊置產生的所有分解和未分解鏈段均選為合格鏈段，作為疊置成果矢量多邊形圖形C的組成鏈段(參見圖Ι-c)；
第3-2步、預定疊置模式為交模式——此模式對矢量多邊形圖形A與精度遊程編碼圖形Bk疊置產生的分解鏈段或未分解鏈段，若其落入矢量多邊形圖形B輪廓範圍以內，則選為合格鏈段，作為疊置成果矢量多邊形圖形C的組成鏈段，否則丟棄。同樣，對矢量多邊形圖形B與精度遊程編碼圖形Ak疊置產生的分解鏈段或未分解鏈段，若其落入矢量多邊形圖形A輪廓範圍以內，則選為合格鏈段，作為疊置成果矢量多邊形圖形C的組成鏈段，否則丟棄(參見圖1-d)。第3-3步、預定疊置模式為矢量多邊形圖形A域內的並模式——矢量多邊形圖形A與精度遊程編碼圖形Bk疊置產生的分解鏈段或未分解鏈段均選為合格鏈段，作為疊置成果矢量多邊形圖形C的組成鏈段；對矢量多邊形圖形B與精度遊程編碼圖形K疊置獲得的分解鏈段或未分解鏈段，若其落入矢量多邊形圖形A輪廓範圍以內，則篩選為合格鏈段，作為疊置成果矢量多邊形圖形C的組成鏈段，否則丟棄(參見圖1-h)。第3-4步、預定疊置模式為矢量多邊形圖形B域內的並模式——矢量多邊形圖形B與精度遊程編碼圖形Ak疊置產生的分解鏈段或未分解鏈段均選為合格鏈段，作為疊置成果矢量多邊形圖形C的組成鏈段；對矢量多邊形圖形A與精度遊程編碼圖形Bk疊置獲得的分解鏈段或未分解鏈段，若其落入矢量多邊形圖形B輪廓範圍以內，則選為合格鏈段，作為疊置成果矢量多邊形圖形C的組成鏈段，否則丟棄(參見圖1-i)。
第3-5步、預定疊置模式為差模式——對矢量多邊形圖形A與精度遊程編碼圖形Bk疊置產生的分解鏈段或未分解鏈段，若其落入矢量多邊形圖形B輪廓範圍以外，則選為合格鏈段，作為疊置成果矢量多邊形圖形C的組成鏈段，若其落入矢量多邊形圖形B輪廓範圍以內，則丟棄；對矢量多邊形圖形B與精度遊程編碼圖形K疊置產生的分解鏈段或未分解鏈段，若其來自矢量多邊形圖形B的輪廓鏈段且落入矢量多邊形圖形A輪廓範圍以內，則選為合格鏈段，作為疊置成果矢量多邊形圖形C的組成鏈段，若其來自矢量多邊形圖形B內部鏈段，則丟棄(參見圖l_e)。簡言之，即對疊置產生的新鏈段——包括分解和未分解鏈段，進行符合疊置模式的篩選，以篩選出的鏈段集合構成疊置成果矢量多邊形圖形。並模式下的疊置結果為矢量多邊形圖形A、B兩圖疊置產生的所有多邊形集合，交模式下的疊置結果為矢量多邊形圖形A、B兩圖公共範圍以內疊置產生的多邊形集合，圖A域內的並模式疊置結果是對上述並模式疊置結果按圖A輪廓範圍進行拾取，圖B域內的並模式疊置結果是對並模式疊置結果按圖B輪廓範圍進行拾取，差模式下的疊置結果為圖A輪廓範圍以內且圖B輪廓範圍以外疊置產生多邊形集合。 步驟4、構建含有確定空間關係的疊置成果矢量多邊形圖形——對疊置成果矢量多邊形圖形的組成鏈段進行拓撲關係編碼，通過對疊置成果矢量多邊形圖形面元的初始編碼，建立成果矢量多邊形圖形組成鏈段與其兩側多邊形面元的空間拓撲關係，以及成果矢量多邊形圖形面元與兩個疊置多邊形圖形面元的隸屬關係，構成含有確定空間關係的疊置成果矢量多邊形圖形(參見圖4-i)。具體而言，以如下公式得出疊置成果矢量多邊形圖形C的多邊形初始編碼，從而正確構建疊置成果矢量多邊形圖形C的鏈段與其兩側相鄰多邊形的拓撲關係
Code3= Code/( +1)+Code2(I)
式中=Code3為疊置成果矢量多邊形圖形C中多邊形的初始編碼，Code1為其所處矢量多邊形圖形A中多邊形的編碼，Code2為其所處矢量多邊形圖形B中多邊形的編碼，m為矢量多邊形圖形B包含的多邊形數目
初始編碼的公式基於以下分析得出設矢量多邊形圖形A包含的多邊形數目為/7，矢量多邊形圖形B包含的多邊形數目為心並約定一幅矢量多邊形圖形輪廓以外區域為O區，理論上圖A與圖B疊置可能產生的不同疊置多邊形數目最大為(/7+1V ( +l),由於事先無法獲知哪些多邊形面元會在疊置分析製圖中出現，因此必須為所有可能產生的多邊形編碼。例如圖4-b中待疊置矢量多邊形圖形B的多邊形數目為3，圖4-i中疊置成果矢量多邊形圖形C的初始編碼多邊形7是矢量多邊形圖形A的多邊形I與矢量多邊形圖形B的多邊形3疊合而成，滿足7=Γ 4+3，疊置成果矢量多邊形圖形C的初始編碼多邊形14是矢量多邊形圖形A的多邊形3與矢量多邊形圖形B的多邊形2疊合而成的，滿足14=34+2。採用公式(I)對兩次交叉混合疊置獲得的每條疊置成果矢量多邊形圖形C的組成鏈段進行左右多邊形編碼。假設來自圖A的一條疊置產生鏈段的原始左右多邊形編碼分別為Ieftcode和該鏈段在圖B中所處多邊形的編碼為則該條新鏈段在圖C中的左右多邊形編碼分別採用以下公式計算
鏈段左多邊形編碼二Ieftcode' (jn+l) +polycode(2)
鏈段右多邊形編碼=ijn+l) +polycode(3)假設來自圖B的一條疊置產生鏈段的原始左右多邊形編碼分別是而和rigAicoofe,該鏈段在圖A中所處多邊形的編碼為/7o7_m ￡/e,則該條鏈段在圖C中的左右多邊形編碼分別採用以下公式計算
鏈段左多邊形編碼(jn+l) +leftcode(4)
鏈段右多邊形編碼=Ζ ο7_7 θ￡/ / (jn+l) +rightcode(5)
例如圖4-e中來自矢量多邊形圖形A的鏈段/ττ左右多邊形編碼分別為I和2，它在與精度遊程編碼圖形Bk疊置過程中被分解為/77和qr兩條鏈段，其中鏈段/77落在圖B的多邊形I中，其左右多邊形初始編碼分別為14+1=5和2' 4+1=9，鏈段#落在圖B的多邊形3中，其左右多邊形初始編碼分別為14+3=7和24+3=11 (參見圖4-i)。考慮到實際兩幅矢量多邊形圖形疊置所產生的多邊形數目要小於理論上的最大可能數目，有的初始編碼多邊形在疊置成果矢量多邊形圖形C中並不存在。此時需要對圖C 中實際存在的多邊形進行連續編碼處理，即對圖C中所有鏈段的左右多邊形編碼進行相應更新，具體方法如下
第4-1步、遍歷疊置成果矢量多邊形圖形C的所有鏈段，通過對所述鏈段左右多邊形編碼的統計和增序排列，獲得所述疊置成果矢量多邊形圖形C中實際存在的初始編碼多邊形，建立初始編碼多邊形與連續編碼多邊形對照表(結合圖4-i和4-j參見表I的1、2兩列)；
第4-2步、根據所述對照表中疊置成果矢量多邊形圖形C的各個多邊形的初始編碼，按照公式(6)計算其隸屬的矢量多邊形圖形A多邊形編碼，按照公式(7)計算其隸屬的矢量多邊形圖形B多邊形編碼，從而獲得疊置成果矢量多邊形圖形C的多邊形面元與矢量多邊形圖形A的多邊形面元和矢量多邊形圖形B的多邊形面元的隸屬關系列表(結合圖4-i和4-j參見表I的3、4兩列)；
隸屬圖A多邊形編碼=圖C多邊形初始編碼/ (m+1) (6)
隸屬圖B多邊形編碼=圖C多邊形初始編碼％(m+l) (7)
公式(7)中符號％為取餘數運算符，m的含義同前。第4-3步、根據初始編碼多邊形與連續編碼多邊形對照表將疊置成果矢量多邊形圖形C的所有鏈段的左右多邊形編碼由初始編碼更新轉變為連續編碼(結合圖4-i和4-j參見表2)
表I初始編碼多邊形與連續編碼多邊形對照表
權利要求
1.一種複雜矢量多邊形圖形空間疊置分析製圖方法，其特徵在於包括以下步驟 步驟I、圖形轉換一分別將兩幅矢量多邊形圖形轉換成相應的精度遊程編碼圖形，所述精度遊程編碼由遊程表示區段起始位置的X坐標和區段所處多邊形的編碼構成； 步驟2、交叉混合疊置處理——分別以轉換得到的兩幅精度遊程編碼圖形中的一幅為背景底圖，以交叉方式對另一幅矢量多邊形圖形鏈段進行上覆遍歷疊置、跨多邊形檢測和分解，分別得到對應兩幅疊置矢量多邊形圖形的兩組分解和未分解鏈段； 步驟3、篩選構圖鏈段——按照預定疊置模式對疊置產生的兩組分解和未分解鏈段進行篩選，篩選出符合疊置模式的合格鏈段作為疊置成果矢量多邊形圖形的組成鏈段； 步驟4、構建含有確定空間關係的疊置成果矢量多邊形圖形——按預定規則對疊置成果矢量多邊形圖形的組成鏈段進行左右多邊形區域編碼，構建疊置成果矢量多邊形圖形組 成鏈段與其兩側多邊形面元的空間拓撲關係，以及疊置成果矢量多邊形圖形面元與所述兩幅矢量多邊形圖形面元的隸屬關係，構成含有空間關係的疊置成果矢量多邊形圖形。
2.根據權利要求I所述的複雜矢量多邊形圖形空間疊置分析製圖方法，其特徵在於所述步驟I的具體步驟如下 第i-ι步、以預定的縱向精度間隔在疊置分析製圖矩形範圍內布設水平掃描線，為每條水平掃描線設置一個記錄多邊形圖形鏈段穿越次數計數器；遍歷矢量多邊形圖形的各條鏈段，將所述鏈段穿越各掃描線的次數分別記錄到對應的計數器中； 第1-2步、根據穿越次數計數器的計數結果建立分別對應每條掃描線的遊程編碼表，所述遊程編碼表用於逐一記錄各條多邊形圖形鏈段穿越掃描線時交點的X坐標及右側多邊形的編碼； 第1-3步、再次遍歷所述矢量多邊形的所有多邊形圖形鏈段，計算各條多邊形圖形鏈段穿越掃描線時交點的X坐標，連同交點右側的多邊形編碼逐一存儲到對應的遊程編碼表中； 第1-4步、以精度遊程編碼表中記錄的X坐標為關鍵字，分別對各條掃描線的精度遊程編碼表做遞增排序，獲得對應所述矢量多邊形圖形的精度遊程編碼圖形。
3.根據權利要求2所述的複雜矢量多邊形圖形空間疊置分析製圖方法，其特徵在於所述步驟2進行上覆多邊形鏈段跨背景底圖多邊形探測時，以預定探測步長依次判斷當前處理鏈段中的相鄰探測節點落入背景底圖的多邊形區域是否發生改變，當判斷到的相鄰兩個探測點落入背景底圖不同多邊形區域時，則在這兩個相鄰探測點的連線上採用折半逼近法計算跨越點坐標，並在跨越點處分解該鏈段，對多次跨越背景底圖不同多邊形的鏈段則實施多次分解，對從未跨越背景底圖不同多邊形的鏈段不進行分解。
4.根據權利要求3所述的複雜矢量多邊形圖形空間疊置分析製圖方法，其特徵在於所述步驟3的預定疊置模式包括所述兩幅矢量多邊形圖形的並模式、所述兩幅矢量多邊形圖形的交模式、所述兩幅矢量多邊形圖形之一域內的並模式、以及所述兩幅矢量多邊形圖形的差模式。
5.根據權利要求4所述的複雜矢量多邊形圖形空間疊置分析製圖方法，其特徵在於所述步驟4中的預定規則對疊置成果矢量多邊形圖形的組成鏈段進行左右多邊形區域編碼的依據為以如下公式得出疊置成果矢量多邊形圖形的多邊形初始編碼Code3= Code/ (jn+l) +Code2式中=Code3為疊置成果矢量多邊形圖形中多邊形的初始編碼 Code1為其所處矢量多邊形圖形之一中多邊形的編碼 Code2為其所處矢量多邊形圖形另一中多邊形的編碼 m為其所處矢量多邊形圖形另一包含的多邊形數目。
6.根據權利要求5所述的複雜矢量多邊形圖形空間疊置分析製圖方法，其特徵在於所述步驟4還包括以下具體步驟 第4-1步、遍歷疊置成果矢量多邊形圖形的所有鏈段，通過對所述鏈段左右多邊形編碼的統計和增序排列，獲得所述疊置成果矢量多邊形圖形中實際存在的初始編碼多邊形，建立初始編碼多邊形與連續編碼多邊形對照表； 第4-2步、根據所述對照表中疊置成果矢量多邊形圖形存在的各個多邊形的初始編碼，按照以下(a)式計算其隸屬的矢量多邊形圖形之一的多邊形編碼，按照以下(b)式計算其隸屬的矢量多邊形圖形另一的多邊形編碼，獲得疊置成果矢量多邊形圖形與兩幅多邊形與矢量多邊形圖形的多邊形關系列表； 隸屬矢量多邊形圖形之一的多邊形編碼= 疊置成果矢量多邊形圖形的多邊形初始編碼/(m+1) (a) 隸屬矢量多邊形圖形另一的多邊形編碼= 疊置成果矢量多邊形圖形的多邊形初始編碼％(m+l) (b) 式中％為取餘數運算符 第4-3步、根據初始編碼多邊形與連續編碼多邊形對照表將疊置成果矢量多邊形圖形所有鏈段的左右多邊形編碼由初始編碼更新轉變為連續編碼。
全文摘要
本發明涉及一種複雜矢量多邊形圖形空間疊置分析製圖方法，屬於地理信息系統中的空間分析製圖和空間數據挖掘技術領域。該方法的步驟包括將兩幅矢量多邊形圖形轉換成精度遊程編碼圖形；分別以其中一幅精度遊程編碼圖形為背景底圖，以交叉方式對另一幅矢量多邊形圖形鏈段進行上覆遍歷疊置、跨多邊形檢測和分解，得到分解和未分解鏈段；篩選出符合疊置模式的合格鏈段作為疊置成果矢量多邊形圖形的組成鏈段；構建含有確定空間關係的疊置成果矢量多邊形圖形。本發明避免了矢量多邊形圖形之間直接疊置帶來的大量鏈段相交判斷和可能出現的誤判及遺漏，為有效建立新的拓撲關係創造了條件，提高了矢量多邊形圖形空間疊置分析製圖技術的可操作性、魯棒性和實用性。
文檔編號G06F17/50GK102902837SQ20121026071
公開日2013年1月30日 申請日期2012年7月25日 優先權日2012年7月25日
發明者謝順平, 王結臣, 都金康, 趙書河 申請人:南京大學