计算几何算法实现（C语言实现）

计算几何几何函数库

-------------------------------------------------------------------------------------------------------------------------------

导引

1. 常量定义和包含文件

2. 基本数据结构

3. 精度控制

6. 求一点饶某点旋转后的坐标

7. 求矢量夹角

㈡ 线段及直线的基本运算

1. 点与线段的关系

2. 求点到线段所在直线垂线的垂足

3. 点到线段的最近点

4. 点到线段所在直线的距离

5. 点到折线集的最近距离

6. 判断圆是否在多边形内

7. 求矢量夹角余弦

㈢ 多边形常用算法模块

1. 判断多边形是否简单多边形

2. 检查多边形顶点的凸凹性

3. 判断多边形是否凸多边形

4. 求多边形面积

5. 判断多边形顶点的排列方向

7. 射线法判断点是否在多边形内

8. 判断点是否在凸多边形内

9. 寻找点集的 graham 算法

10.寻找点集凸包的卷包裹法

const int MAXV = 300;

{

// 直线的解析方程 a*x+b*y+c=0 为统一表示，约定 a>= 0

{

{

}

//浮点误差的处理

{

if(fabs(d)<EP)

}

}

bool equal_point(POINT p1,POINT p2)

{

}

/*(sp-op)*(ep-op)的叉积

r=multiply(sp,ep,op),得到(sp-op)*(ep-op)的叉积

r<0: sp 在矢量 op ep 的逆时针方向 */

{

}

/*矢量(p1-op)和(p2-op)的点积

r=dotmultiply(p1,p2,op),得到矢量(p1-op)和(p2-op)的点积如果两个矢量都非零矢量

}

bool online(LINESEG l,POINT p)

}