多段線切割多邊形

概述

多段線切割多邊形米苹,直觀上來說首先就是求多段線與多邊形之間的交點儒搭,然后利用這些交點與多邊形頂點構(gòu)成多邊形,這樣一個多邊形就被切割成多個多邊形怀薛。如下圖所示:


多段線與多邊形
切割后的多邊形

主要過程

以下圖所示的分割為例尾序,做簡短說明:


示例

難點

  1. 如何連接交點與頂點钓丰?如上圖所示,切割的多邊形為AB21每币,D34携丁,E56,12C3456F兰怠;當(dāng)我們求出交點之后梦鉴,如何組織交點與頂點的連接很重要,一個解決方法是將多邊形的邊界與多段線組成有向邊揭保,依據(jù)他們的方向來進(jìn)行組織連接肥橙;
  2. 剔除不合理的多邊形?很明顯,C23這個多變形不符合要求秸侣,因為它位于多邊形的外側(cè)存筏,這個要去除掉;

過程

對于上述難點味榛,本文主要是利用geos中構(gòu)建多邊形的方法來解決椭坚,尤其是難點1,具體的原理可參考直線切割凹多邊形
1.獲取帶分割的幾何圖形搏色,注意該幾何圖形是線形的善茎,主要包括待切割的閉合環(huán)(如多邊形的邊界)以及分割線;

geos::geom::Geometry *tempG = _geos_geometry->getBoundary();
geos::geom::Geometry *tempG1 = tempG->Union(_asGeos(splitline));

2.構(gòu)建多邊形频轿,在geos主要是Polygonizer類垂涯,獲取所有分割的多邊形,當(dāng)然也包括類似C23這樣不合理的多邊形航邢,下一步是剔除這些多邊形集币;

geos::operation::polygonize::Polygonizer pz;
pz.add(tempG1);
std::vector< geos::geom::Polygon*> *result_geom = pz.getPolygons();

3.剔除不合理多邊形,理論上來說翠忠,切割出來的多變?nèi)绻辉级噙呅伟涂梢员A簦{(diào)用geos中的Cover或Contains等拓?fù)溆嬎惚憧梢云蛘ィ窃趯嶋H操作過程中有兩個問題:
(1)拓?fù)溆嬎悴徽_秽之,每次返回值都是false,猜測可能是精度問題当娱,因為如果坐標(biāo)都是整型,可以返回正確結(jié)果;
(2)效率不高考榨,相對于contain和within,建議在geos中優(yōu)先使用cover或coverby跨细。具體可參考九交模型
所以選取一個折中方案,如下所示:

//過濾掉不在多邊形內(nèi)部的切割面;
//不能直接用包含和覆蓋直接判斷河质,存在精度問題;
//利用切割面與原始多邊形相交后的多邊形面積與切割面的面積之比判斷;
//比值在0.99~1.01之間;

4.最后得到的就是一個vector集合冀惭,數(shù)據(jù)類型是geos::geom::Polygon*

相關(guān)鏈接

GEOS庫一些自己的見解和注意點
GEOS庫學(xué)習(xí)之三:空間關(guān)系、DE-9IM和謂詞

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末掀鹅,一起剝皮案震驚了整個濱河市散休,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌乐尊,老刑警劉巖戚丸,帶你破解...
    沈念sama閱讀 222,946評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異扔嵌,居然都是意外死亡限府,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評論 3 399
  • 文/潘曉璐 我一進(jìn)店門痢缎,熙熙樓的掌柜王于貴愁眉苦臉地迎上來胁勺,“玉大人,你說我怎么就攤上這事独旷∈鹚耄” “怎么了?”我有些...
    開封第一講書人閱讀 169,716評論 0 364
  • 文/不壞的土叔 我叫張陵势告,是天一觀的道長蛇捌。 經(jīng)常有香客問我,道長咱台,這世上最難降的妖魔是什么络拌? 我笑而不...
    開封第一講書人閱讀 60,222評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮回溺,結(jié)果婚禮上春贸,老公的妹妹穿的比我還像新娘。我一直安慰自己遗遵,他們只是感情好萍恕,可當(dāng)我...
    茶點故事閱讀 69,223評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著车要,像睡著了一般允粤。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,807評論 1 314
  • 那天类垫,我揣著相機(jī)與錄音司光,去河邊找鬼。 笑死悉患,一個胖子當(dāng)著我的面吹牛残家,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播售躁,決...
    沈念sama閱讀 41,235評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼坞淮,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了陪捷?” 一聲冷哼從身側(cè)響起回窘,我...
    開封第一講書人閱讀 40,189評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎揩局,沒想到半個月后毫玖,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,712評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡凌盯,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,775評論 3 343
  • 正文 我和宋清朗相戀三年付枫,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片驰怎。...
    茶點故事閱讀 40,926評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡阐滩,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出县忌,到底是詐尸還是另有隱情掂榔,我是刑警寧澤,帶...
    沈念sama閱讀 36,580評論 5 351
  • 正文 年R本政府宣布症杏,位于F島的核電站装获,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏厉颤。R本人自食惡果不足惜穴豫,卻給世界環(huán)境...
    茶點故事閱讀 42,259評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望逼友。 院中可真熱鬧精肃,春花似錦、人聲如沸帜乞。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,750評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽黎烈。三九已至习柠,卻和暖如春匀谣,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背津畸。 一陣腳步聲響...
    開封第一講書人閱讀 33,867評論 1 274
  • 我被黑心中介騙來泰國打工振定, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人肉拓。 一個月前我還...
    沈念sama閱讀 49,368評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像梳庆,于是被迫代替她去往敵國和親暖途。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,930評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 前言 多邊形偏移 (polygon offset) 算法可能我們印象不深膏执,不過用過 autoCAD 的同學(xué)應(yīng)該有印...
    zyl06閱讀 11,443評論 19 14
  • 引言 自從今年春天選修了計算機(jī)圖形學(xué)課程驻售,這朵烏云就在頭頂盤旋不散。始終弄不明白計算機(jī)圖形學(xué)到底在研究什么更米,所謂的...
    金戈大王閱讀 60,943評論 35 61
  • 1. 矢量減法 設(shè)二維矢量 P = (x1,y1) 欺栗,Q = (x2,y2) 則矢量減法定義為: P - Q = ...
    潭潭_180閱讀 2,253評論 0 1
  • 最近做的一個小算法,使用平行線填充一個多邊形區(qū)域征峦。用過 AutoCAD 的同學(xué)應(yīng)該知道迟几,可以選定一個區(qū)域,指定平行...
    zyl06閱讀 4,434評論 0 2
  • 雖然已經(jīng)一年多沒有維護(hù)gbox這個圖形庫項目了栏笆,最近確實時間不夠用类腮。。蛉加。 今年的重點是把xmake徹底正好蚜枢,至少在...
    waruqi閱讀 1,447評論 0 50