梯形图及点定位.PDF

梯形图及点定位 目录 实验内容 1 数据结构 2 二维点 2 线段 2 辅助矩形 2 梯形 2 有向无环图节点 3 有哪些信誉好的足球投注网站结构 3 梯形图及点定位算法类 3 算法说明 4 随机线段生成算法 4 梯形图和查找结构构造算法 5 算法思路 5 算法流程图 6 相交梯形的查找与退化情况的处理 9 点定位算法 9 程序结构 10 文件说明 10 类和结构体说明 10 实验结果 11 随机生成线段 11 构建梯形图和查找结构 12 点定位 14 实验分析 16 实验内容 对于平面上一组互不相交的线段，构造梯形图以及对应的一个查找结构。梯形图组 织为梯形结构集合形式，查找结构为有向无环图形式。 这里的点定位查找定义为：在输入的线段集中，找出与发自查询点、垂直向上的射 线相交的第一条线段，并返回其编号。 约定： 1. 射线为闭，即包含起点本身； 2. 输入线段均为左闭右开，即包含左端点但不含右端点； 3. 假象为通过逆时针地轻微转动坐标轴，消除垂直线段——亦即，垂直线段下闭上 开； 4. 共左端点的线段，以右端点的纵坐标为序； 5. 若射线不与任何线段相交，则返回“inf”标识 数据结构 二维点 class TMPoint2D{ public: double x, y; // 表示点对应的x坐标和y坐标 } 线段 class TMSegment{ public: TMPoint2D start; // 线段的起始点 TMPoint2D end; // 线段的终止点 } 辅助矩形 class TMRectangle { public: double left; // 矩形左侧边x坐标 double right; // 矩形右侧边x坐标 double bottom; // 矩形底边y坐标 double top; // 矩形顶边y坐标 } 梯形 class TMTrapezoidal{ public: /*梯形自身的拓扑信息*/ size_t up; //作为梯形上边的线段 size_t bottom; //作为梯形下边的线段 TMPoint2D leftp; //生成左边射线的某端点 TMPoint2D rightp; //生成右边射线的某端点 double leftUpY; //梯形左边上端点的Y坐标 double leftBottomY; //梯形左边下端点的Y坐标 double rightUpY; //梯形右边上端点的Y坐标 double rightBottomY; //提醒右边下端点的Y坐标 /*梯形与邻居的邻接关系*/ TMTrapezoidal* rightUpNeigh; //梯形的右上方邻居，与当前 梯形共享同一个up线段