常考GIS算法思路及代码实现.pdf-资料库

一、着色问题有形如下列图形的地图，图中每一块区域代表一个省份，现请你用红（1）、兰（2）、黄（3）、绿（4）四种颜色给这些省份填上颜色，要求每一省份用一种颜色，且任意两个相邻省份的颜色不能相同，请给出一种符合条件的填色方案。将实际地图用无向图的形式给出，每个省份代表图上的一个顶点，边代表两个省份是相邻的。算法思想：从编号 1 的省开始，按 4 种颜色的排列顺序，首先选择第一种颜色，然后检查是否矛盾，即相邻的区域中是否已有该颜色，若不矛盾，则涂色，若矛盾，则选择下一个颜色，再判断，当 4 种颜色都不可能时，则需回溯。当第一个省的颜色确定之后，依次对第二个省、第三个省……进行处理，当所有省都涂上颜色之后，得到一种解法。 color:array[1..maxn] of integer; 其中，color[k]：表示第 k 个省所填的颜色 {还未全部填色} {是否所有省份都已经填色} 四色着色算法（递归）： procedure search(k: integer); {递归搜索第 m 个省份} begin if k > n then begin write(color[1]); { 已全部填色，输出结果，终止程序} for j := 2 to n do write(' ', color[j]); writeln; halt end else for j := 1 to 4 do begin {依次用四种颜色对当前省份填色} if (k <= n) and pd(k) then {没有冲突} begin color[k] := j; {记录当前省份颜色} search(k + 1); {递归检查下一个省份} end; end; end; 二、道格拉斯-普克法

算法原理：将一条曲线首、末点连一条直线，求出其余各点到该直线的距离，选其最大者与规定的临界值相比较，若大于临界值，则离该直线距离最大的点保留，否则，将所有的点全部舍去。算法步骤： 1.确定首末两点直线方程 2.求其余点到首末两点直线的距离 3.求最大距离值 4.比较最大距离与距离限差(阈值)的大小 5.If 最大距离小于等于阈值，去除中间所有点，留下首尾两点； If 最大距离大于阈值，以该点分割曲线段，首点和该点构成直线返回第一步，再以该点和尾点构成直线段返回第一步。道格拉斯-普克法算法： public Path_T Douglas(Path_T path, double precision) { Path_T newpa = new Path_T(); List pts = new List(); List npts = new List(); foreach (Line_T li in path) { pts.Add(li.Frompt); } pts.Add(path.Tpoint); DouglasPuker(pts, npts, precision); for (int i = 0; i < npts.Count-1; i++) { Line_T cl = new Line_T(npts[i], npts[i + 1]); newpa.Add(cl); } return newpa; } public void DouglasPuker(List pts,List npts, double precision) { List lpts = new List(); List rpts = new List(); int tag = 0; Line_T lineft = new Line_T(pts[0], pts[pts.Count - 1]); double maxdis = 0; for (int i = 1; i < pts.Count - 1; i++) { double distance = PointToLine(pts[i], lineft); if (distance >= maxdis) { maxdis = distance; tag = i; }

} if (maxdis < precision) { npts.Add(pts[0]); return; } else { for (int i = 0; i

{ double area = 0; foreach (Line_T li in ring.Path) { area += li.Frompt.X * li.Topt.Y - li.Frompt.Y * li.Topt.X; } area = Math.Abs(area / 2); return area; } 四、拓扑关系自动生成 1.弧段处理：将图形中的线段在相交处打断，组织成弧段，建立弧段—结点拓扑关系表 2.结点匹配：建立结点—弧段拓扑关系表 3.组织多边形：以顺时针方向跟踪组织多边形，建立多边形—弧段拓扑关系表 4.组织复杂多边形：建立多边形与多边形的包含关系五、多边形的自动生成（面域的组织）： 1.顺时针方向构多边形：指的是多边形按顺时针方向组织，也就是多边形在弧段的右侧。 2.最靠右边的弧段：是指从弧段的一个端点出发，在这条弧段的方向上最右边的一条弧段。（如何求最右边的弧段？通过计算与一个结点关联的弧段间的角度，然后对其排序）已知条件：结点数据+弧段数据+结点—弧段拓扑表+弧段—结点拓扑表求：面域—弧段拓扑表算法过程： 1、顺序取一个结点为起始结点，取完为止；取过该结点的任一条弧段作为起始弧段。 2、取这条弧段的另一结点，找这个结点上靠这条弧段最右边的弧段，作为下一条弧段 3、是否回到起点：是，已形成多边形，记录之，并转 4；否，转 2； 4、取起点上开始的，刚才所形成多边形的最后一条边作为新的起始弧段，转 2；若这条弧段已用过两次，即已成为两个多边形的边，则转 1； 1、P1 开始，起始弧段为 L1,L1 最右边的弧段为 L6,L6 最右边的弧段为 L5,所以 A1:L1,L6,L5 2、P1 开始，起始弧段为 A1 的最后一条弧段 L5，L5 最右边的弧段为 L8，L8 最右边的弧段为 L4,所以：A2:L5,L8,L4 3、P1 开始，起始弧段为 A2 的最后一条弧段 L4，L4 最右边的弧段为 L3,L3 最右边的弧为 L2，L2 最右边的弧为 L1，所以 A3:L4,L3,L2,L1 4、由于 P1 的弧段都被使用 2 次，所以从下个结点 P2 开始，判断一条弧段要不要，就要看这条弧段是不是被使用过两次；由此可构建 A4,A5 六、矢量到栅格 /*栅格数据结构*/ P1P2P3P4P5L1L2L3L4L5L6L7L8

public class Raster_T { private int rows; // 栅格网的行数 private int cols; // 栅格网的列数 private double pixelSize; //栅格网像素的大小 private Point_T originPoint; // 栅格网的原点｝ public class PixelPosition_T { private int col; //列号 private int row; //行号 private int code; //栅格数据｝ 1.确定栅格矩阵(行列数\分辨率)；在转换之前需要确定栅格单元的大小，栅格单元的大小又称为栅格图像的分辨率，直接决定了栅格数据的精度。行列数的确定: I=(Ymax-Ymin)/dy J=(Xmax-Xmin)/dx dx=(Xmax-Xmin)/J dy=(Ymax-Ymin)/I 2.点的转换(点的栅格化) public PixelPosition_T RasterationPoint(Point_T pt, Raster_T ras)//栅格化点 { int row=(int)((pt.Y-ras.Originpt.Y)/ras.Pixelsize); int col = (int)((pt.X - ras.Originpt.X) / ras.Pixelsize); PixelPosition_T pp = new PixelPosition_T(row,col); return pp; } 3.线的转换(线的栅格化) 八方向栅格化算法过程： A．端点的栅格化

B．判断端点之间 x 方向还是 y 方向栅格差值大，选择大的一个方向 C．依次求出每个栅格的垂直于该方向的中心线 D．求出中心线与该线段的交点 /*八方向栅格化*/ public List RasterationLine(Line_T line, Raster_T ras) { List linepixel = new List(); PixelPosition_T fpp = RasterationPoint(line.Frompt, ras); linepixel.Add(fpp); PixelPosition_T tpp = RasterationPoint(line.Topt, ras); int count=Math.Max(Math.Abs(fpp.Row-tpp.Row),Math.Abs(fpp.Col-tpp.Col)); for (int i = 1; i <= count; i++) { //求出当前线 Point_T fp,tp; if (Math.Abs(fpp.Row - tpp.Row) <= Math.Abs(fpp.Col - tpp.Col)) { double x; if(tpp.Col-fpp.Col>=0) { x= (fpp.Col + i - 0.5) * ras.Pixelsize + ras.Originpt.X; } else { x=(fpp.Col - i - 0.5) * ras.Pixelsize + ras.Originpt.X; } fp = new Point_T(x, ras.Originpt.Y); tp = new Point_T(x, ras.Originpt.Y + ras.Pixelsize * ras.Rows); } else { double y; if (tpp.Row - fpp.Row >= 0) { y = (fpp.Row + i - 0.5) * ras.Pixelsize + ras.Originpt.Y; } else { y = (fpp.Row - i - 0.5) * ras.Pixelsize + ras.Originpt.Y; } fp = new Point_T(ras.Originpt.X, y); tp = new Point_T(ras.Originpt.X+ ras.Pixelsize * ras.Cols, y); } Line_T cline = new Line_T(fp,tp);

Point_T pt = IntersectPoint(cline, line); PixelPosition_T cpp=RasterationPoint(pt,ras); linepixel.Add(cpp); } linepixel.Add(tpp); return linepixel; } 全路径栅格化： Bresenham 法： 4.多边形的变换(面的变换) 边界线的转化与线的栅格化方法相同，接下来就是属性的填充。填充的方法很多，关键问题是正确判断哪些栅格单元位于多边形之内，哪些位于多边形之外。为此，多边性必须严格封闭，没有缝隙。方法有：内部点扩散法、射线算法、平行线扫描法与铅垂线跌落法、边界代数充填算法、边界点跟踪算法 ①x-扫描线算法基本思想：引一条扫描线，判断它与多边形边的交点，判断位于多边形内的直线段并绘制。算法步骤：确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大 y 值（ymin 和 ymax）。从 y=ymin 到 y=ymax，每次用一条扫描线进行填充。对一条扫描线填充的过程可分为四个步骤： 1.求交：扫描线与多边形两两顶点组成的边一次求交，得到的交点存放在一维数组中。在对直线求交的过程中，就对异常情况做处理，使得得到的交点是合理可以被直接处理的交点。 2.排序：对存放在数组中的点按 x 坐标值大小排序；

3.交点配对：根据排好序的交点，按顺序依次取出 2 个交点配对，构成一条水平直线段； 4.区间填色：对该水平直线段进行线的栅格化。 /*多边形栅格化算法*/ public List RasterationPolygon(Map_T map, Raster_T ras) { List pypixel=new List(); foreach (Geometry_T geo in map.Geofeatures) { if (geo.GetType() == typeof(Ring_T)) { Ring_T ri = (Ring_T)geo; List pypts = new List(); foreach (Line_T li in ri.Path) { pypts.Add(li.Frompt); } CompareY comy=new CompareY(); CompareX comx = new CompareX(); pypts.Sort(comy);//计算最大最小 y 值，并将此两点栅格化 PixelPosition_T ppmax = RasterationPoint(pypts[pypts.Count - 1], ras); PixelPosition_T ppmin = RasterationPoint(pypts[0], ras); //循环遍历，使用递进一个单位栅格中心线 for (int i = 0; i <=(ppmax.Row - ppmin.Row); i++) { double y = (ppmin.Row + i + 0.5) * ras.Pixelsize + ras.Originpt.Y; Point_T pt1 = new Point_T(ras.Originpt.X,y); Point_T pt2=new Point_T(ras.Originpt.X+ras.Cols*ras.Pixelsize,y); Line_T cline = new Line_T(pt1,pt2); List interpts = new List();//依次和多边形的边求交点 foreach (Line_T li in ri.Path) { if (cline.Frompt.Y < Math.Max(li.Frompt.Y, li.Topt.Y) && cline.Frompt.Y > Math.Min(li.Frompt.Y, li.Topt.Y)) { Point_T interpt = IntersectPoint(cline, li);//求交点 interpts.Add(interpt); } } interpts.Sort(comx);//对交点按照 x 值排序 for (int j = 0; j < interpts.Count - 1; j = j + 2) //交点两两配对成水平直线 { Line_T pline = new Line_T(interpts[j], interpts[j + 1]);

资料库

常考GIS算法思路及代码实现.pdf

相关推荐

考试认证

热门标签

最新资料