首页 / 算法 / GIS算法基础——左转算法拓扑生成
GIS算法基础——左转算法拓扑生成
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了GIS算法基础——左转算法拓扑生成，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含11467字，纯文字阅读大概需要17分钟。
内容图文
GIS算法基础——左转算法拓扑生成
基于JavaScript的左转算法拓扑生成
本博文用以梳理课堂及自学内容，转载请标明出处。
本人应用JS中的Canvas对算法结果进行可视化验证，在算法说明及实现中绘制验证部分省略
拓扑相关基本概念：拓扑空间关系是一种对空间结构进行明确定义的数学方法。
?具有拓扑关系的矢量数据结构就是拓扑数据结构。
?拓扑数据结构描述了基本空间目标点、线、面之间的关联、邻接和包含关系
?拓扑空间关系信息是空间分析的基础之一
拓扑生成算法的技术路线
数据预处理–弧段处理，使整幅图形中的所有弧段，除在端点处相交外，没有其他交点，即没有相交或自相交的弧段–结点匹配，建立结点、弧段关系拓扑构建–建立多边形，以左转算法或右转算法跟踪，生成多边形，建立多边形与弧段的拓扑关系–建立多边形与多边形的拓扑关系
弧段预处理
拓扑关系自动建立的第一步就是处理弧段，使得弧段不存在自相交和相交现象，其过程分为三步：
–直线段相交的判断方法
–自相交弧段处理
–弧段相交打断处理
左转算法流程
从组成多边形边界的某一条弧段开始；如果该弧段与ｘ轴正向夹角为最大，则从该弧段的同一结点出发的其他弧段中，方向角最小的弧段是该多边形的后续弧段；如果该弧段的方向角最小或介于同一结点的其他弧段方向角之间，则最小夹角偏差所对应的弧段为多边形的后续弧段
(1)顺序取一个结点作为起始结点，取完为止；取过该结点的方位角最小的未使用过的或仅使用过一次，且使用过的方向与本次相反的弧段作为起始弧段。(2)取这条弧段的另一个结点，找这个结点关联的弧段集合中的本条弧段的下一条弧段，如果本条弧段是最后一条弧段，则取弧段集合的第一条弧段，作为下一条弧段。
(3)判断是否回到起点，如果是则形成了一个多边形，记录下它，并且根据弧段的方向，设置组成该多边形的左右多边形信息。否则转(2)。
(4)取起始点上开始的，刚才所形成多边形的最后一条边作为新的起始弧段，转(2)；若这条弧段已经使用过两次，即形成了两个多边形，转(1)。
构建结点、弧段、多边形类
// 结点类
1. class Nodep extends Point{//结点类继承点类
2. constructor(id,x,y){
3. super(x,y);
4. this.id = id;
5. this.linkarc = new Array();
6. }
7.
8. SortArc(){//将与该结点相关的弧段按方位角排序
9. for(let i = 0;i < this.linkarc.length;i++){
10. this.linkarc[i].GetAzimuth(this);
11. }
12. this.linkarc.sort(Utils.CompareProp('azimuth'));
13. }
14.
15. GetNearArc(aarc){//获取该弧的左转的下一条弧（需使用SortArc排过序）
16. this.SortArc();
17. let i = 0;
18. while(this.linkarc[i] != aarc) ++i;
19. return this.linkarc[(i+1)%this.linkarc.length];
20. }
21.
22. GetuseableArc(){//选择没有被遍历过或被遍历方向与当前不同的弧段
23. this.SortArc();
24. let i = 0;
25. for(i;i<this.linkarc.length;i++){
26. if(this.linkarc[i].ifergodic!=2){
27. return this.linkarc[i];
28. }
29. }
30. return 0;
31. }
32. }
//弧段类
1. class Arc{
2. constructor(id,points){
3. this.id = id;
4. this.points = points;
5. this.sp = null;//起始结点
6. this.ep = null;//终止结点
7. this.lpg = null;//左多边形
8. this.rpg = null;//右多边形
9. this.azimuth = 0;//方位角
10. this.ifergodic = 0;//用于判断这条边方向的使用次数
11. }
12.
13. Getspep(){//用于在构建多边形中动态获取起点终点
14. this.sp = this.points[0];
15. this.ep = this.points[this.points.length-1];
16. }
17.
18. Reverse(){//将点倒置使得正常多边形的边均为顺时针
19. this.points.reverse();
20. this.Getspep();
21. }
22.
23. GetAzimuth(anode){//获取弧段上一个结点的方位角
24. if(this.points[0]==anode){
25. this.azimuth = Utils.GetAzimuth(this.points[0],this.points[1]);
26. }
27. else{
28. this.azimuth = Utils.GetAzimuth(this.points[this.points.length-1],this.points[this.points.length-2]);
29. }
30. }
31.
32. GetDirection(anode){//判断这条弧段的遍历方向，如果方向与点相反则逆置points
33. if(anode == this.points[0]){
34. this.Getspep();
35. }
36. else if(anode == this.points[this.points.length-1]){
37. this.Reverse();
38. }
39. else console.log("点匹配失败获取方向出现问题");
40. }
41.
42. GetanotherNode(node){//获得弧上的另一个结点
43. if(this.sp == node) return this.ep;
44. return this.sp;
45. }
46. }
//多边形类
1. class Polygon{
2. constructor(id,arcs){
3. this.id = id;
4. this.arcs = arcs;
5. this.points = new Array();
6. this.part = new Array();//岛
7. this.centerpoint = this.GetCp();
8. this.bbox;
9. }
10.
11. GetCp(){//获取多边形中心点
12. let sumx = 0, sumy = 0, sump =0;
13. for(let i = 0;i<this.arcs.length;i++){
14. let pointlist = this.arcs[i].points;
15. sump+=pointlist.length;
16. for(let j = 0;j<pointlist.length;j++){
17. sumx += pointlist[j].x;
18. sumy += pointlist[j].y;
19. }
20. }
21. let centerP = new Point(sumx/sump,sumy/sump);
22. return centerP;
23. }
24.
25. JudgePart(){//岛只有一个节点的情况判断删除多余重复弧段
26. if(this.arcs[0]==this.arcs[1]){
27. this.arcs.splice(1,1);
28. }
29. }
30.
31. GetPoints(){
32. let i = 0;
33. this.JudgePart();
34. for(i ; i < this.arcs.length;i++){
35. let arc = this.arcs[i];
36. if(arc.ifergodic==1){
37. for(let m = 0;m<arc.points.length-1;++m){
38. this.points.push(arc.points[m]);
39. }
40. }
41. else if(arc.ifergodic==2){
42. for(let j = arc.points.length-1;j>0;--j){
43. this.points.push(arc.points[j]);
44. }
45. }
46. else console.log("赋予多边形点信息出错");
47. }
48. this.points.push(this.points[0]);
49. }
50.
51. ArcSide(){//给多边形内的弧段赋予多边形拓扑信息
52. for(let arc of this.arcs){
53. if(arc.ifergodic == 1) arc.rpg = this;
54. else if(arc.ifergodic == 2) arc.lpg = this;
55. else console.log("左转出现错误");
56. }
57. }
58.
59. Area(){
60. let asum = 0;
61. for(let i = 0;i<this.points.length-1;i++){
62. let apoint = this.points[i];
63. asum+=(this.points[i+1].x*apoint.y-apoint.x*this.points[i+1].y);
64. }
65. return asum/2;
66. }
67.
68. PolygonBBox(){
69. let ltp = new Point(this.points[0].x,this.points[0].y);//左上
70. let rbp = new Point(this.points[0].x,this.points[0].y);//右下
71. for(let point of this.points){
72. ltp.x = (ltp.x<point.x)?ltp.x:point.x;
73. ltp.y = (ltp.y>point.y)?ltp.y:point.y;
74. rbp.x = (rbp.x>point.x)?rbp.x:point.x;
75. rbp.y = (rbp.y<point.y)?rbp.y:point.y;
76. }
77. this.bbox = new BBox(new Array(ltp,rbp));
78. }
79. }
左转算法部分
//左转算法
1. static SubTurnLeft(stnode,starc){//左转构造多边形递归部分
2. starc.ifergodic++;
3. let curnode = starc.GetanotherNode(stnode);
4. let polyarcs = new Array();
5. polyarcs.push(starc);
6. let curarc = curnode.GetNearArc(starc);
7.
8. while(curnode!=stnode){//当没有回到起始边的时候循环找下一条边
9. if(curarc.ifergodic==0){//没有遍历过的边先确定方向
10. curarc.GetDirection(curnode);
11. curnode = curarc.ep;
12. }
13. else if(curarc.ifergodic==1) curnode = curarc.sp;//确定了方向的边则一定是选取起始点
14. else console.log("左转选取下一条边出现问题");
15. curarc.ifergodic++;
16. polyarcs.push(curarc);
17. curarc = curnode.GetNearArc(curarc);
18. }
19. let apolygon = new Polygon(polyid,polyarcs);
20. ++polyid;
21.
22. apolygon.ArcSide();//左右多边形
23. apolygon.GetPoints();//按顺序连接点
24. this.JudgeHole(apolygon,polygons,holes);//通过面积判断将多边形分别放入多边形以及岛列表中
25. starc = apolygon.arcs[apolygon.arcs.length-1];//多边形最后一条边作为起始进行递归
26. //TODO:似乎有更好的逻辑？？？尝试过之后会有bug
27.
28. if(starc.ifergodic!=2) this.SubTurnLeft(stnode,starc);
29. else return;
30. }
31.
32. static Turnleft(nodelist){//左转构建多边形主体以及岛的list
33. for(let node of nodelist){
34. node.SortArc();
35. for(let arc of node.linkarc){//选取可以开始遍历构造多边形的边
36. if(arc.ifergodic==0){//第一次遍历则为其赋予方向
37. arc.GetDirection(node);
38. this.SubTurnLeft(node,arc);
39. break;
40. }
41. else if(arc.ifergodic==1){//第二次遍历判断本次遍历方向与第一次是否相同
42. if(arc.sp==node) continue;//通过判断第一次遍历的方向起始点判断方向
43. else{
44. this.SubTurnLeft(node,arc);
45. break;
46. }
47. }
48. else if(arc.ifergodic==2) continue;//遍历过两次的边跳过
49. }
50. }
51. }
匹配多边形岛
1. static PairHoles(polygons,holes){
2. let flag = 0;
3. for(let apoly of polygons){
4. let apolyarea = apoly.Area();
5. apoly.PolygonBBox();
6. let polybbox = apoly.bbox;
7. for(let ahole of holes){
8. let holearea = ahole.Area();
9. if(holearea+apolyarea<0) continue;//第一层判断面积
10.
11. ahole.PolygonBBox();
12. let holebbox = ahole.bbox;
13.
14. if(polybbox.Compare(holebbox)) continue;//第二层判断包围盒
15.
16. for(let apoint of ahole.points){//第三层逐个点判断是否在内部
17. if(Utils.ptInPolyByCorner(apoint,apoly)==0){
18. flag = 0;
19. console.log(apoint);
20. break;
21. }
22. flag = 1;
23. }
24. if(flag){
25. apoly.part.push(ahole);
26. }
27. }
28. }
29. }
可视化效果
利用Canvas将生成的多边形随机填充为不同的颜色，多边形岛统一不填充（但是他们并非为空而也是多边形）
总结
左转算法逻辑清晰，多读几遍算法过程描述就能理解其逻辑，但是将此逻辑转化为编程语言并不容易，特别是在需要从基础的类开始构建的情况下。
在我进行的过程中，按照自己的思路写了一遍发现总是会有bug，在debug改代码进行了很长时间依然没有效果的情况下，我果断选择全部重写，事实证明是有效的。对于JS这门语言，在很多书中以及博主的教学中，都提及其动态性等导致自己的程序很难debug成功，而花费的时间精力不如从头来过，并且这样能解决大多数的问题。我是真实体验过了。
内容总结
以上是互联网集市为您收集整理的GIS算法基础——左转算法拓扑生成全部内容，希望文章能够帮你解决GIS算法基础——左转算法拓扑生成所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。