概述
多段線切割多邊形米苹,直觀上來說首先就是求多段線與多邊形之間的交點儒搭,然后利用這些交點與多邊形頂點構(gòu)成多邊形,這樣一個多邊形就被切割成多個多邊形怀薛。如下圖所示:
多段線與多邊形
切割后的多邊形
主要過程
以下圖所示的分割為例尾序,做簡短說明:
示例
難點
- 如何連接交點與頂點钓丰?如上圖所示,切割的多邊形為AB21每币,D34携丁,E56,12C3456F兰怠;當(dāng)我們求出交點之后梦鉴,如何組織交點與頂點的連接很重要,一個解決方法是將多邊形的邊界與多段線組成有向邊揭保,依據(jù)他們的方向來進(jìn)行組織連接肥橙;
- 剔除不合理的多邊形?很明顯,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*