下载后可任意编辑计算几何算法概览一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要讨论解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。二、目录 本文整理的计算几何基本概念和常用算法包括如下内容： 矢量的概念矢量加减法 AcGeVector2d/AcGeVector3d + - += -=等运算符重载 或者setToSum 矢量叉积 AcGeVetor3d crossProduct 折线段的拐向推断 由矢量叉积的性质推出 推断点是否在线段上 isOn 推断两线段是否相交 AcgeLineSeg2d intersectWith 推断线段和直线是否相交 AcgeLine2d AcgeLineSeg2d intersectWith 推断矩形是否包含点 推断线段、折线、多边形是否在矩形中 推断矩形是否在矩形中 推断圆是否在矩形中 推断点是否在多边形中 推断线段是否在多边形内 推断折线是否在多边形内 推断多边形是否在多边形内 推断矩形是否在多边形内 推断圆是否在多边形内 推断点是否在圆内 推断线段、折线、矩形、多边形是否在圆内下载后可任意编辑 推断圆是否在圆内 计算点到线段的最近点line.closestPointTo(point); 计算点到折线、矩形、多边形的最近点 计算点到圆的最近距离及交点坐标 计算两条共线的线段的交点 计算线段或直线与线段的交点 求线段或直线与折线、矩形、多边形的交点 求线段或直线与圆的交点 凸包的概念 凸包的求法三、算法介绍 矢量的概念： 假如一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。假如有向线段 p1p2 的起点 p1 在坐标原点，我们可以把它称为矢量(vector)p2。 矢量加减法： 设二维矢量 P = ( x1, y1 )，Q = ( x2 , y2 )，则矢量加法定义为： P + Q = ( x1 + x2 , y1 + y2 )，同样的，矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 )。显然有性质 P + Q = Q + P，P - Q = - ( Q - P )。 矢量叉积： 计算矢量叉积是与直线和线段相关算法的核心部分。设矢量 P = ( x1, y1 )，Q = ( x2, y2 )，则矢量叉积定...
