没有合适的资源?快使用搜索试试~ 我知道了~
首页常考GIS算法思路及代码实现
资源详情
资源评论
资源推荐
一、着色问题
有形如下列图形的地图,图中每一块区域代表一个省份,现请你用红(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<Point_T> pts = new List<Point_T>();
List<Point_T> npts = new List<Point_T>();
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<Point_T> pts,List<Point_T> npts, double
precision)
{
List<Point_T> lpts = new List<Point_T>();
List<Point_T> rpts = new List<Point_T>();
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 <tag; i++)
{
lpts.Add(pts[i]);
}
for (int i = tag - 1; i < pts.Count; i++)
{
rpts.Add(pts[i]);
}
DouglasPuker(lpts, npts, precision);
DouglasPuker(rpts, npts, precision);
}
}
三、多边形面积计算
为了计算方便,选择原点(0,0),因此,单个三角形的面积为:
整个多边形的面积为:
1.已知一个多边形,其数据结构为一个点数组
2.取任意一点,可取特殊点(0,0),遍历多边形数据,每次取出两个相邻点,使用叉积法计
算带符号的三角形面积
3.最后将各个三角形面积求和。
double PolygonArea(s,n)
{
double area=0;
for(int i=0;i<n-1;i++)
{
area+=s[i]叉积 s[i+1];
}
area+=s[n-1]叉积 s[0];
return area;
}
public double PolygonArea(Ring_T ring)
{
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
六、矢量到栅格
/*栅格数据结构*/
P1
P2
P3
P4
P5
L1
L2
L3
L4
L5
L6
L7
L8
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.端点的栅格化
剩余20页未读,继续阅读
任性的小矿矿
- 粉丝: 0
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0