以垂足判斷點(diǎn)與多邊形的關(guān)系

趙 晉 睿

(河北九華勘查測(cè)繪有限責(zé)任公司，河北 保定 071000)

以垂足判斷點(diǎn)與多邊形的關(guān)系

趙 晉 睿

(河北九華勘查測(cè)繪有限責(zé)任公司，河北 保定 071000)

介紹了判斷點(diǎn)與平面多邊形關(guān)系的新方法，通過點(diǎn)向多邊形的每條邊做垂線，比較垂足在邊上的垂線長(zhǎng)度，尋找與點(diǎn)最近的邊，再以此“有向邊”與點(diǎn)的關(guān)系判斷點(diǎn)與多邊形(面)的關(guān)系，以供類似研究參考。

多邊形，插入點(diǎn)，關(guān)系

在平時(shí)工作中，經(jīng)常會(huì)遇到以下一些情況：檢查居民到房屋注記是否匹配、齊全；檢查宗地屬性點(diǎn)是否在宗地內(nèi)；檢查圖斑號(hào)是否在圖斑內(nèi)等等。尤其在地類調(diào)查中，各種形狀的多邊形經(jīng)常使得圖斑號(hào)注記錯(cuò)漏，檢查起來極其繁瑣。其實(shí)這些可以歸為點(diǎn)(插入點(diǎn))與閉合多邊形(多段線)的關(guān)系。

點(diǎn)在多邊形內(nèi)外關(guān)系的判斷是關(guān)于多邊形的一種基本算法，在計(jì)算機(jī)圖形學(xué)中應(yīng)用廣泛。判斷的經(jīng)典方法主要有射線法、標(biāo)號(hào)法和360°內(nèi)角和等，前兩種方法實(shí)現(xiàn)起來比較復(fù)雜，而且在臨界情況下可靠性不好，后一種方法比較普遍。本文介紹一種新的判斷方法，即通過最靠近點(diǎn)的邊來判斷點(diǎn)與多邊形的關(guān)系。

1 圖形分析

點(diǎn)與多邊形的關(guān)系如圖1所示。通過判斷點(diǎn)與多邊形節(jié)點(diǎn)坐標(biāo)極限值(X方向與Y方向的最大值和最小值)，可以明確圖1a)和圖1b)的情況；當(dāng)點(diǎn)在多邊形內(nèi)時(shí)，必然至少在2條邊上有垂足，則通過記錄點(diǎn)與邊垂足的個(gè)數(shù)，可以明確圖1c)和圖1d)的情況；圖1f)圖形比較經(jīng)典容易判斷；圖1e)圖形屬于半包圍形狀，以上幾種方法均不能采用。由圖1e)可知，通過點(diǎn)向每邊做垂線可以建立點(diǎn)與多邊形的關(guān)系，結(jié)合多邊形的方向可以判斷內(nèi)外關(guān)系，但是在所有的有向邊中，只有最靠近此點(diǎn)的邊即垂線最短的邊，才能代表多邊形進(jìn)行判斷，其他有向邊均存在判斷誤差。當(dāng)多邊形的方向?yàn)轫槙r(shí)針時(shí)，點(diǎn)在最近有向邊右側(cè)為內(nèi)，左側(cè)為外；反之，右側(cè)為外，左側(cè)為內(nèi)。

2 編程思路

編程采用CAD自帶VBA工具。實(shí)現(xiàn)功能：當(dāng)注記在多邊形內(nèi)，刪除注記與多邊形，保留不匹配或多余的對(duì)象。

首先在點(diǎn)(注記的插入點(diǎn))集合中遍歷點(diǎn)對(duì)象，然后遍歷多邊形(多段線)集合中的多邊形對(duì)象，判斷其與點(diǎn)的關(guān)系。判斷前，應(yīng)對(duì)多邊形對(duì)象進(jìn)行基本的自查，如是否閉合和重合節(jié)點(diǎn)；符合要求后，求多邊形在X方向和Y方向的最大值與最小值，并以此初步判斷點(diǎn)是否在多邊形外；接下來的主程序包括一些極限情況；當(dāng)多邊形與此點(diǎn)均不匹配時(shí)，開始下一個(gè)多邊形，若所有多邊形都不匹配則開始遍歷下一個(gè)點(diǎn)；若確定點(diǎn)在多邊形內(nèi)，則刪除兩個(gè)匹配對(duì)象，開始下一點(diǎn)，直至所有對(duì)象遍歷完。

本程序的核心是點(diǎn)與有向線段關(guān)系的判斷，在確定多邊形方向、求垂線長(zhǎng)度和最終判斷時(shí)都會(huì)多次調(diào)用此子程序。

3 程序編譯

設(shè)C為點(diǎn)，AB線段以A為起點(diǎn)，B為終點(diǎn)，則點(diǎn)與有向線段關(guān)系如圖2所示。當(dāng)C點(diǎn)在AB之間時(shí)，兩者關(guān)系命名為“AB”；當(dāng)C點(diǎn)在線段延長(zhǎng)線上時(shí)，以端點(diǎn)命名，有“A”或“B”兩種情況；當(dāng)C點(diǎn)不在線上時(shí)，分左右兩大類情況，由C點(diǎn)向AB做垂線，當(dāng)垂足在AB之間時(shí)，兩者的關(guān)系為“L”或“R”；當(dāng)垂足在延長(zhǎng)線上時(shí)，在“L”或“R”后加端點(diǎn)名表示，有“LA”“LB”“RA”和“RB”四種情況。

1)點(diǎn)與有向線段的判斷。子程序命名為pointanddirectline(以下簡(jiǎn)稱PDL)，返回值類型為字符串。通過AC和AB方位角及距離判斷C點(diǎn)與有向線段AB(A為起點(diǎn)，B為終點(diǎn))的關(guān)系。經(jīng)過分析，當(dāng)AB和AC方位角相等時(shí)，通過計(jì)算AB和AC的距離可以確定C點(diǎn)在AB之間(PDL=“AB”)或C點(diǎn)在B點(diǎn)一側(cè)的延長(zhǎng)線上(PDL=“B”)；當(dāng)AB和AC方位角相差180°時(shí)，C點(diǎn)在A點(diǎn)一側(cè)的延長(zhǎng)線上(PDL=“A”)，以上為極限情況。當(dāng)αAB(有向線段方位角)在[0，π]區(qū)間時(shí)，若αAB>αAC或(αAB+π)<αAC時(shí)，C點(diǎn)在AB的左側(cè)；若αAB<αAC并且(αAB+π)>αAC時(shí)，C點(diǎn)在AB的右側(cè)。當(dāng)αAB(有向線段方位角)在(π，2π)區(qū)間時(shí)，若αAB>αAC且(αAB-π)<αAC時(shí)，C點(diǎn)在AB的左側(cè)；若αAB<αAC或(αAB-π)>αAC時(shí)，C點(diǎn)在AB的右側(cè)。確定C點(diǎn)在AB左側(cè)或右側(cè)后，通過有向線段BC與有向線段BA之間的夾角判斷C點(diǎn)在AB線段上的垂足的位置，以此確定最后的返回值。當(dāng)αAB和αAC之間的夾角不大于π/2同時(shí)αBC和αBA之間的夾角不大于π/2時(shí)，C點(diǎn)在AB線段的垂足在AB之間(PDL=“L”或PDL=“R”)；當(dāng)αAB和αAC之間的夾角大于π/2且小于π時(shí)，C點(diǎn)在AB線段的垂足在A點(diǎn)一側(cè)的延長(zhǎng)線上(PDL=“LA”或PDL=“RA”)；當(dāng)αBC和αBA之間的夾角大于π/2且小于π時(shí)，C點(diǎn)在AB線段的垂足在B點(diǎn)一側(cè)的延長(zhǎng)線上(PDL=“LB”或PDL=“RB”)。

2)多邊形方向的判斷。子程序命名為POLYDIR，返回值為字符串，通過判斷多邊形連續(xù)3個(gè)點(diǎn)的關(guān)系得出多邊形方向。以前兩個(gè)點(diǎn)作為有向線段，調(diào)用PDL子程序判斷第3點(diǎn)與其的關(guān)系。當(dāng)?shù)?點(diǎn)在右時(shí)，計(jì)數(shù)器K1加1；當(dāng)?shù)?點(diǎn)在左時(shí)，計(jì)數(shù)器K2加1。當(dāng)多邊形節(jié)點(diǎn)坐標(biāo)3個(gè)一組全部遍歷完后，比較K1與K2的值，當(dāng)K1>K2時(shí)，多邊形為順時(shí)針，記為“true”；反之為逆時(shí)針，記為“false”。

3)其他子程序介紹。在程序運(yùn)行中，還需要調(diào)用的子程序有：a.判斷并刪除重合節(jié)點(diǎn)，命名為chickoverlap，返回值為數(shù)組；b.求多段線節(jié)點(diǎn)坐標(biāo)極限值，命名為polymaxmin，返回值為4元素?cái)?shù)組，分別代表X方向與Y方向的最大值和最小值；c.求平面垂線長(zhǎng)度，命名為PMplumbline，返回值為實(shí)數(shù)；d.調(diào)用的常用子程序還有：方位角計(jì)算和夾角計(jì)算。

4)主程序。根據(jù)各種圖形判斷對(duì)象的不同，建立不同條件的選擇集。在cass地形圖中，將圖層為“JMD”的多段線對(duì)象作為選擇集，將圖層為“ZJ”的文字對(duì)象作為點(diǎn)選擇集，提取插入點(diǎn)為點(diǎn)坐標(biāo)；在地籍圖中，將圖層為“JZX”的多段線對(duì)象作為選擇集，將圖層為“ZD”的點(diǎn)對(duì)象作為選擇集。將點(diǎn)選擇集中的坐標(biāo)分別賦值于xC和yC，將多邊形選擇集中的對(duì)象obj_poly的節(jié)點(diǎn)坐標(biāo)數(shù)組賦值給動(dòng)態(tài)數(shù)組coord，然后進(jìn)行各項(xiàng)判斷。各變量分別代表：strp代表多段線的方向；i記錄多段線節(jié)點(diǎn)坐標(biāo)數(shù)組下標(biāo)；l1為點(diǎn)到邊垂線長(zhǎng)度；l2記錄最短垂線，jj記錄最短垂線對(duì)應(yīng)邊端點(diǎn)坐標(biāo)的數(shù)組元素下標(biāo)；j記錄垂足個(gè)數(shù)；str值為最近邊與點(diǎn)的關(guān)系。

主程序的編寫過程如圖3所示。

4 程序運(yùn)行及改進(jìn)

在一幅1∶2 000土地利用現(xiàn)狀圖中，有多段線對(duì)象217個(gè)和地類注記220個(gè)。運(yùn)行此程序檢查后，有多余多段線3條，其中2條未封閉，2條無注記；查出6個(gè)多余注記，其中1個(gè)注記在多段線上；用時(shí)小于10 s。

為方便改正，通過添加語句，將未封閉多段線以綠線表示；當(dāng)節(jié)點(diǎn)重合時(shí)，以此節(jié)點(diǎn)為圓心做紅色圓圈為標(biāo)識(shí)；點(diǎn)在多段線上時(shí)，以此點(diǎn)為圓心做綠色圓圈為標(biāo)識(shí)；這樣使得各種錯(cuò)誤更加明顯，修改具有針對(duì)性。

5 需要注意的問題

本程序在調(diào)試過程中，出現(xiàn)了一些問題，主要有以下幾點(diǎn)：

1)在運(yùn)行程序前，需要將弧線剔除。

2)因重合節(jié)點(diǎn)影響垂足個(gè)數(shù)，所以必須將重合節(jié)點(diǎn)從數(shù)組中剔除，尤其注意首尾兩點(diǎn)的重合情況。

3)由于數(shù)據(jù)精度問題，必須以format函數(shù)強(qiáng)制角度比較結(jié)果的小數(shù)位數(shù)，否則三點(diǎn)共線等極限條件極難成立，經(jīng)過分析保留6位小數(shù)即可達(dá)到秒級(jí)精度。

4)需要考慮多段線的類型，確定遍歷節(jié)點(diǎn)坐標(biāo)值的步長(zhǎng)。

5)由于多段線首尾相接，應(yīng)將第一點(diǎn)坐標(biāo)值作為新增坐標(biāo)添加到節(jié)點(diǎn)坐標(biāo)數(shù)組中，增加兩個(gè)元素重新定義，保證各項(xiàng)判斷的完整性。

6)因程序中需要使用方位角，故采用測(cè)量坐標(biāo)系。

7)對(duì)小宗完全嵌套于大宗的情況無法判斷。

6 結(jié)語

顯然，通過垂足把點(diǎn)與多邊形聯(lián)系起來，并判斷二者關(guān)系的算法是可行的。解決點(diǎn)與多邊形匹配的問題，也可以采用拓?fù)涞姆椒ǎ孕枰簧俚牟僮鞑襟E，相比而言程序更快捷。本程序能準(zhǔn)確檢查出一些極限情況并加以標(biāo)識(shí)，與單純的角度計(jì)算相比，可拓展的空間更多一些；引用的多個(gè)子程序，都廣泛應(yīng)用于其他方面的計(jì)算和判斷，應(yīng)用更加靈活。

[1] CJJ 8—99，城市測(cè)量規(guī)范[S].

[2] 徐忠陽.全站儀原理與應(yīng)用[M].北京：解放軍出版社，2003.

[3] GB 50026—2007，工程測(cè)量規(guī)范[S].

[4] GB/T 18314—2009，全球定位系統(tǒng)(GPS)測(cè)量規(guī)范[S].

Judgement on the relationship of point and polygon with pedal

Zhao Jinrui

(HebeiJiuhuaSurvey&MappingCo.,Ltd,Baoding071000,China)

The paper introduces new judgement method of point and polygon, makes vertical lines through polygon, compares the vertical line length on the pedal edge, seeks the latest edge with the point, and judges the relationship of point and polygon(surface) with the relationship of “directed edge” and the point, with a view to provide some guidance for similar research.

polygon, insertion point, relationship

2015-06-09

趙晉睿(1981- )，男，工程師

1009-6825(2015)23-0201-02

TU198

A