目录序前言第1章算法设计和分析1．1概述1．2算法设计原则1．3算法复杂性的度量1．3．1时间复杂性1．3．2空间复杂性1．4最优算法1．5算法的评价1．5．1如何估计算法运行时间1．5．2最坏情况和平均情况的分析1．5．3平摊分析1．5．4输入大小和问题实例思考题第2章GIS算法的计算几何基础2．1维数扩展的9交集模型2．1．1概述2．1．2模型介绍2．1．3空间关系的判定2．2矢量的概念2．2．1矢量加减法2．2．2矢量叉积2．3折线段的拐向判断2．4判断点是否在线段上2．5判断两线段是否相交2．6判断矩形是否包含点2．7判断线段、折线、多边形是否在矩形中2．8判断矩形是否在矩形中2．9判断圆是否在矩形中2．10判断点是否在多边形内2．10．1射线法2．10．2转角法2．11判断线段是否在多边形内2．12判断折线是否在多边形内2．13判断多边形是否在多边形内2．14判断矩形是否在多边形内2．15判断圆是否在多边形内2．16判断点是否在圆内2．17判断线段、折线、矩形、多边形是否在圆内2．18判断圆是否在圆内2．19计算两条共线的线段的交点2．20计算线段或直线与线段的交点2．21求线段或直线与圆的交点2．22中心点的计算2．23过点作垂线2．24作平行线2．25过点作平行线2．26线段延长2．27三点画圆2．28线段打断2．29前方交会2．30距离交会2．31极坐标作点思考题第3章空间数据的变换算法3．1平面坐标变换3．1．1平面直角坐标系的建立3．1．2平面坐标变换矩阵3．1．3平移变换3．1．4比例变换3．1．5对称变换3．1．6旋转变换3．1．7错切变换3．1．8复合变换3．1．9相对(xf，yf)点的比例变换3．1．10相对(xf，yf)点的旋转变换3．1．11几点说明3．2球面坐标变换3．2．1球面坐标系的建立3．2．2确定新极Q地理坐标中φ0、λ03．3仿射变换3．4地图投影变换3．4．1概述3．4．2地球椭球体的相关公式3．4．3兰勃特投影3．4．4墨卡托投影3．4．5高斯一克吕格投影3．4．6通用横轴墨卡托投影思考题第4章空间数据转换算法4．1矢量数据向栅格数据转换4．1．1矢量点的栅格化4．1．2矢量线的栅格化4．1．3矢量面的栅格化4．2栅格数据向矢量数据转换4．2．1栅格点坐标与矢量点坐标的关系4．2．2栅格数据矢量化的基本步骤4．2．3线状栅格数据的细化4．2．4多边形栅格转矢量的双边界搜索算法4．2．5多边形栅格转矢量的单边界搜索算法思考题第5章空间数据组织算法5．1矢量数据的压缩5．1．1间隔取点法5．1．2垂距法和偏角法5．1．3道格拉斯一普克法5．1．4光栏法5．1．5曲线压缩算法的比较5．1．...
