[發(fā)明專利]基于節(jié)點匹配對的直線段與直線段的自動分割方法

在審

• 申請?zhí)枺?/td>: 201710904539.3
• 申請日: 2017-09-29
• 公開（公告）號: CN107833234A
• 公開（公告）日: 2018-03-23
• 發(fā)明（設(shè)計）人: 虞昌彬;夏俊;趙志剛;賀彪;李霖;董玉鵬
• 申請（專利權(quán)）人: 浙江大學寧波理工學院
• 主分類號: G06T7/162
• 分類號: G06T7/162;G06T11/20
• 代理公司: 寧波市鄞州甬致專利代理事務(wù)所(普通合伙)33228
• 代理人: 李迎春

技術(shù)領(lǐng)域

本發(fā)明涉及地理信息科學領(lǐng)域，尤其涉及一種基于節(jié)點匹配對的直線段與直線段的自動分割方法。

背景技術(shù)

線段與線段的分割(或稱為線段與線段的裁剪)是地理信息科學與計算機科學中的經(jīng)典問題，其在許多領(lǐng)域有所應(yīng)用，包括在道路網(wǎng)中道路與道路的自動打斷、基于物空間的三維實體群的線消隱處理、二維宗地的自動構(gòu)建、多邊形的封套構(gòu)建、多邊形合并、多邊形裁剪等(Shamos，M.I.et al.(1976).Geometric Intersection Problems[C].Foundations of Computer Science，Syposium on，IEEE:208-215；Bently，J.L.et al.(2006).Algorithms for Reporting and Counting Geometric Intersections[J].IEEE Transactions on Computers，28(9):643-647；Edelsbrunner，H.et al.(1981).On the Intersection of Orthogonal Objects[J].Information Processing Letters，13(4-5):177-181；Nievergelt，J.et al.(1981).Plane-sweep Algorithms for Intersecting Geometric Figures[J].Communications of the ACM，25(25):739-747；Andrews，D.S.et al.(1994).Further Comparison of Algorithms for Geometric Intersection Problems[J].Proceedings of International Symposium on Spatial Data Handling；Martin Held.(1997).ERIT_A Collection of Efficient and Reliable Intersection Tests[J].Journal of Graphics Tools，2(4):25-44.)。針對直線段與直線段的求交，歸納而言可以分為三個層次：

第一個層次是“算得對(即結(jié)果對，英文上稱為effective)”，

第二個層次是“算得準(即計算準，英文上稱為efficient)”，

第三個層次是“算得快(即速度快，英文上稱為quick)”。

針對第一個層次“算得對(即結(jié)果對)”，著重于各類拓撲關(guān)系下線段之間裁剪操作的正確處理，這是本發(fā)明的研究重點；針對第二個層次“算得準(即計算準)”，著重于在直線段之間相交判斷中實交情況下(即跨越cross時)新交點坐標的精確計算(甚至包含小數(shù)位數(shù)的精確計算)以及其他情況下交點坐標的準確定位，這同樣是本發(fā)明的研究重點；針對第三個層次“算得快(即速度快)”，著重于直線段之間裁剪操作在軟件與硬件條件下的加速處理，軟件方面典型如采用最小外接矩形(也稱最小包圍盒，即Minimum Bounding Box)來初步篩選可能發(fā)生相交關(guān)系的候選直線段集合從而初步減少計算量，硬件方面典型如將線段裁切算法固化于硬件設(shè)備之中，這不是本發(fā)明的研究重點，在這里略過。

以下內(nèi)容將圍繞第一層次“算的對(即結(jié)果對)”和“算的準(即計算準)”展開，相關(guān)研究成果眾多，最常見的主要涉及判斷線段與線段是否存在相交情況、若相交則線段與線段存在的相交拓撲種類、線段與線段確定實交時新交點坐標的精確計算等。