计算机图形学中计算几何算法

《计算机图形学中计算几何算法》由会员分享，可在线阅读，更多相关《计算机图形学中计算几何算法（4页珍藏版）》请在金锄头文库上搜索。

1、计算机图形学中计算几何算法计算机图形学中计算几何算法/*计算几何(本文档源文件格式为.cpp,上传百度时被迫改有.txt)目录 点的基本运算 1. 平面上两点之间距离 1 2. 判断两点是否重合 1 3. 矢量叉乘 1 4. 矢量点乘 2 5. 判断点是否在线段上 2 6. 求一点饶某点旋转后的坐标 2 7. 求矢量夹角 2 线段及直线的基本运算 1. 点与线段的关系 3 2. 求点到线段所在直线垂线的垂足 4 3. 点到线段的最近点 4 4. 点到线段所在直线的距离 4 5. 点到折线集的最近距离 4 6. 判断圆是否在多边形内 5 7. 求矢量夹角余弦 5 8. 求线段之间的夹角 5 9.

2、 判断线段是否相交 6 10.判断线段是否相交但不交在端点处 6 11.求线段所在直线的方程 6 12.求直线的斜率 7 13.求直线的倾斜角 7 14.求点关于某直线的对称点 7 15.判断两条直线是否相交及求直线交点 7 16.判断线段是否相交，如果相交返回交点 7 多边形常用算法模块 1. 判断多边形是否简单多边形 8 2. 检查多边形顶点的凸凹性 9 3. 判断多边形是否凸多边形 9 4. 求多边形面积 9 5. 判断多边形顶点的排列方向，方法一 10 6. 判断多边形顶点的排列方向，方法二 10 7. 射线法判断点是否在多边形内 10 8. 判断点是否在凸多边形内 11 9. 寻找点

3、集的 graham 算法 12 10.寻找点集凸包的卷包裹法 13 11.判断线段是否在多边形内 14 12.求简单多边形的重心 15 13.求凸多边形的重心 17 14.求肯定在给定多边形内的一个点 17 15.求从多边形外一点出发到该多边形的切线 18 16.判断多边形的核是否存在 19 圆的基本运算 1 .点是否在圆内 20 2 .求不共线的三点所确定的圆 21 矩形的基本运算 1.已知矩形三点坐标，求第 4 点坐标 22 常用算法的描述 22 补充 1两圆关系： 24 2判断圆是否在矩形内： 24 3点到平面的距离： 25 4点是否在直线同侧： 25 5镜面反射线： 25 6矩形包含：

4、 26 7两圆交点： 27 8两圆公共面积： 28 9. 圆和直线关系： 29 10. 内切圆： 30 11. 求切点： 31 12. 线段的左右旋： 31 13公式： 32 */* 需要包含的头文件 */ #include /* 常用的常量定义 */ const doubleINF= 1E200 const doubleEP= 1E-10 const intMAXV= 300 const doublePI= 3.14159265 /* 基本几何结构 */ struct POINT double x; double y; POINT(double a=0, double b=0) x=a; y=b; /constructor