autocadARX程序设计几何算法配置环境常用函数命令添加等 .docx

《autocadARX程序设计几何算法配置环境常用函数命令添加等 .docx》由会员分享，可在线阅读，更多相关《autocadARX程序设计几何算法配置环境常用函数命令添加等 .docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结封面可编辑资料 - - - 欢迎下载精品名师归纳总结作者： PanHongliang仅供个人学习运算几何算法概览一、引言运算机的显现使得很多原本特殊繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很简洁的问题却需要拿出一套并不简洁的通用解决方案，比如几何问题。作为运算机科学的一个可编辑资料 - - - 欢迎下载精品名师归纳总结分支，运算几何主要争辩解决几何问题的算法。在现代工程和数学领域，运算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着特殊重要的应用。在本文中，我们将对运算几何常用的基本算法做一个全面的介绍，期望对您明白并应用运算几何的学问解决问题起到

2、帮忙。二、目录本文整理的运算几何基本概念和常用算法包括如下内容： 矢量的概念矢量加减法 AcGeVector2d/AcGeVector3d+-+=-=等运算符重载或者 setToSum矢量叉积 AcGeVetor3d crossProduct折线段的拐向判定 由矢量叉积的性质推出判定点是否在线段上isOn判定两线段是否相交AcgeLineSeg2d intersectWith判定线段和直线是否相交AcgeLine2d AcgeLineSeg2d intersectWith判定矩形是否包含点判定线段、折线、多边形是否在矩形中判定矩形是否在矩形中判定圆是否在矩形中判定点是否在多边形中 判定线段是否

3、在多边形内判定折线是否在多边形内判定多边形是否在多边形内判定矩形是否在多边形内 判定圆是否在多边形内判定点是否在圆内判定线段、折线、矩形、多边形是否在圆内可编辑资料 - - - 欢迎下载精品名师归纳总结判定圆是否在圆内运算点到线段的最近点line.closestPointTopoint运算点到折线、矩形、多边形的最近点运算点到圆的最近距离及交点坐标运算两条共线的线段的交点运算线段或直线与线段的交点求线段或直线与折线、矩形、多边形的交点求线段或直线与圆的交点凸包的概念凸包的求法。三、算法介绍矢量的概念：假如一条线段的端点是有次序之分的，我们把这种线段成为有向线段directed segment。

4、假如有向线段 p1p2 的起点 p1 在坐标原点，我们可以把它称为矢量vectorp2。矢量加减法：设二维矢量 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 ，就矢量叉积定义为由0,0 、 p1 、p2 和 p1+p2所组成的平行四边形的带符号的面积，即： P

5、Q = x1*y2 - x2*y1，其结果是一个标量。明显有性质P Q = - QP 和 P -Q = - PQ 。一般在不加说明的情形下，本文下述算法中全部的点都看作矢量，两点的加减法就是矢量相加减，而点的乘法就看作矢量叉积。叉积的一个特殊重要性质是可以通过它的符号判定两矢量相互之间的顺逆时针关系： 如 P Q 0 ,就 P 在 Q 的顺时针方向。如 P Q 0,就p0p1 在 p1点拐向右侧后得到p1p2 。如 p2 - p0p1 - p0 0,就p0p1 在 p1点拐向左侧后得到p1p2 。如 p2 - p0p1 - p0 = 0,就 p0 、p1 、p2 三点共线。具体情形可参照下图：

6、判定点是否在线段上：设点为 Q，线段为 P1P2 ，判定点 Q 在该线段上的依据是： Q - P1 P2 - P1 = 0且Q 在以 P1， P2 为对角顶点的矩形内。前者保证Q 点在直线 P1P2 上，后者是保证Q 点不在线段 P1P2 的延长线或反向延长线上，对于这一步骤的判定可以用以下过程实现：ON-SEGMENTpi,pj,pkif minxi,xj = xk = maxxi,xj and minyi,yj = yk = maxyi,yj then return true 。else return false。特殊要留意的是，由于需要考虑水平线段和垂直线段两种特殊情形，minxi,xj

7、=xk=maxxi,xj和 minyi,yj=yk=maxyi,yj两个条件必需同时中意才能返回真值。判定两线段是否相交：我们分两步确定两条线段是否相交：(1) 快速排斥试验设以线段 P1P2 为对角线的矩形为R，设以线段 Q1Q2 为对角线的矩形为T，假如 R和 T 不相交，明显两线段不会相交。(2) 跨立试验假如两线段相交，就两线段必定相互跨立对方。如P1P2 跨立 Q1Q2 ，就矢量 P1 -Q1 和 P2 - Q1 位于矢量 Q2 - Q1 的两侧，即 P1 - Q1 Q2 - Q1 * P2 - Q1 可编辑资料 - - - 欢迎下载精品名师归纳总结 Q2 - Q1 0。当可编辑资料

8、 - - - 欢迎下载精品名师归纳总结 P1 - Q1 Q2 - Q1 = 0时，说明 P1 - Q1 和 Q2 - Q1 共线，但是由于已经通过快可编辑资料 - - - 欢迎下载精品名师归纳总结速排斥试验，所以P1 确定在线段 Q1Q2 上。同理， Q2 - Q1 P2 - Q1 = 0说明 P2 确定在线段 Q1Q2 上。所以判定 P1P2 跨立 Q1Q2 的依据是： P1 - Q1 Q2 - Q1 * Q2 - Q1 可编辑资料 - - - 欢迎下载精品名师归纳总结 P2 - Q1 = 0。同理判定 Q1Q2 跨立 P1P2 的依据是： Q1 - P1 P1 Q2 - P1 = 0。具体

9、情形如下图所示： P2- P1 * P2 -可编辑资料 - - - 欢迎下载精品名师归纳总结在相同的原理下，对此算法的具体的实现细节可能会与此有所不同，除了这种过程外，大家也可以参考算法导论上的实现。判定线段和直线是否相交：有了上面的基础，这个算法就很简洁了。假如线段P1P2 和直线 Q1Q2 相交，就 P1P2 跨立可编辑资料 - - - 欢迎下载精品名师归纳总结Q1Q2 ，即： P1 - Q1 Q2 - Q1 * Q2 - Q1 P2 - Q1 = 0。可编辑资料 - - - 欢迎下载精品名师归纳总结判定矩形是否包含点：只要判定该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。判定线段

10、、折线、多边形是否在矩形中：由于矩形是个凸集，所以只要判定全部端点是否都在矩形中就可以了。判定矩形是否在矩形中：只要比较左右边界和上下边界就可以了。判定圆是否在矩形中：很简洁证明，圆在矩形中的充要条件是：圆心在矩形中且圆的半径小于等于圆心到矩形四边的距离的最小值。判定点是否在多边形中：判定点 P 是否在多边形中是运算几何中一个特殊基本但是特殊重要的算法。以点P 为端点，向左方作射线L，由于多边形是有界的，所以射线L 的左端确定在多边形外，考虑沿着L 从无穷远处开头自左向右移动，遇到和多边形的第一个交点的时候，进入到了多边形的内部，遇到其次个交点的时候，离开了多边形，所以很简洁看出当L 和多边形

11、的交点数目C 是奇数的时候， P 在多边形内，是偶数的话P 在多边形外。但是有些特殊情形要加以考虑。如图下图abcd所示。在图 a 中， L 和多边形的顶点相交，这时候交点只能运算一个。在图b 中， L 和多边形顶点的交点不应被运算。在图c 和d 中， L 和多边形的一条边重合，这条边应当被忽视不计。假如L 和多边形的一条边重合，这条边应当被忽视不计。可编辑资料 - - - 欢迎下载精品名师归纳总结为了统一起见，我们在运算射线L 和多边形的交点的时候，1。对于多边形的水平边不作考虑。 2。对于多边形的顶点和L 相交的情形，假如该顶点是其所属的边上纵坐标较大的顶点，就计数，否就忽视。3 。对于

12、P 在多边形边上的情形，直接可判定P属于多边行。由此得出算法的伪代码如下：count 0 。以 P为端点，作从右向左的射线L。for 多边形的每条边sdo if P 在边 s 上then return true 。if s 不是水平的then if s 的一个端点在 L 上if 该端点是 s 两端点中纵坐标较大的端点then count count+1else if s 和 L 相交then count count+1 。if count mod 2 = 1then return true 。else return false 。其中做射线L 的方法是：设 P的纵坐标和 P 相同，横坐标为正无

13、穷大（很大的一个正数），就P 和 P就确定了射线 L。判定点是否在多边形中的这个算法的时间复杂度为On 。另外仍有一种算法是用带符号的三角形面积之和与多边形面积进行比较，这种算法由于使用浮点数运算所以会带来确定误差，不举荐大家使用。判定线段是否在多边形内：可编辑资料 - - - 欢迎下载精品名师归纳总结线段在多边形内的一个必要条件是线段的两个端点都在多边形内，但由于多边形可能为凹，所以这不能成为判定的充分条件。假如线段和多边形的某条边内交（两线段内交是指两线段相交且交点不在两线段的端点），由于多边形的边的左右两侧分属多边形内外不同部分，所以线段确定会有一部分在多边形外 见图 a。于是我们得到线

14、段在多边形内的其次个必要条件：线段和多边形的全部边都不内交。线段和多边形交于线段的两端点并不会影响线段是否在多边形内。但是假如多边形的某个顶点和线段相交，仍必需判定两相邻交点之间的线段是否包含于多边形内部（反例见图b 。因此我们可以先求出全部和线段相交的多边形的顶点，然后依据X-Y 坐标排序 X 坐标小的排在前面，对于X 坐标相同的点， Y 坐标小的排在前面，这种排序准就也是为了保证水平和垂直情况的判定正确 ，这样相邻的两个点就是在线段上相邻的两交点，假如任意相邻两点的中点也在多边形内，就该线段确定在多边形内。证明如下：命题 1：假如线段和多边形的两相邻交点P1 ， P2 的中点 P 也在多边

15、形内，就P1, P2 之间的全部点都在多边形内。证明：假设 P1,P2 之间含有不在多边形内的点，不妨设该点为Q，在 P1, P 之间，由于多边形是闭合曲线，所以其内外部之间有界，而P1 属于多边行内部， Q 属于多边性外部， P属于多边性内部， P1-Q-P 完全连续，所以P1Q 和 QP确定跨过多边形的边界，因此在P1,P之间至少仍有两个该线段和多边形的交点，这和P1P2 是相邻两交点冲突，故命题成立。证毕。由命题 1 直接可得出推论： 推论 2：设多边形和线段 PQ 的交点依次为 P1,P2, Pn，其中 Pi 和 Pi+1 是相邻两交点，线段PQ 在多边形内的充要条件是： P， Q 在

16、多边形内且对于 i =1, 2, -1 ，, nPi ,Pi+1 的中点也在多边形内。在实际编程中，没有必要运算全部的交点，第一应判定线段和多边形的边是否内交，假如线段和多边形的某条边内交就线段确定在多边形外。假如线段和多边形的每一条边都不内交，可编辑资料 - - - 欢迎下载精品名师归纳总结就线段和多边形的交点确定是线段的端点或者多边形的顶点，只要判定点是否在线段上就可以了。至此我们得出算法如下：if 线端 PQ 的端点不都在多边形内then return false 。点集 pointSet 初始化为空。for 多边形的每条边sdo if 线段的某个端点在s 上then 将该端点加入 po

17、intSet 。else if s 的某个端点在线段PQ 上then 将该端点加入 pointSet 。else if s 和线段 PQ 相交 / 这时候已经可以确定是内交了then return false 。将 pointSet 中的点依据X-Y 坐标排序。for pointSet 中每两个相邻点pointSeti , pointSet i+1 do if pointSeti , pointSet i+1的中点不在多边形中then return false 。return true 。这个过程中的排序由于交点数目确定远小于多边形的顶点数目n ，所以最多是常数级的复杂度，几乎可以忽视不计。因

18、此算法的时间复杂度也是On 。判定折线是否在多边形内：只要判定折线的每条线段是否都在多边形内即可。设折线有m 条线段，多边形有n 个顶点，就该算法的时间复杂度为Om*n 。判定多边形是否在多边形内：只要判定多边形的每条边是否都在多边形内即可。判定一个有m 个顶点的多边形是否在一个有 n 个顶点的多边形内复杂度为Om*n 。可编辑资料 - - - 欢迎下载精品名师归纳总结判定矩形是否在多边形内：将矩形转化为多边形，然后再判定是否在多边形内。判定圆是否在多边形内：只要运算圆心到多边形的每条边的最短距离，假如该距离大于等于圆半径就该圆在多边形内。运算圆心到多边形每条边最短距离的算法在后文阐述。判定点

19、是否在圆内：运算圆心到该点的距离，假如小于等于半径就该点在圆内。判定线段、折线、矩形、多边形是否在圆内：由于圆是凸集，所以只要判定是否每个顶点都在圆内即可。判定圆是否在圆内：设两圆为 O1,O2 ，半径分别为 r1, r2 ，要判定 O2 是否在 O1 内。先比较 r1 ， r2 的大小，假如 r1 r就 L 和圆没有交点。c) 利用勾股定理，可以求出两交点坐标，但要留意考虑L 和圆的相切情形。3. 假如 L 平行于 X 轴，做法与 L 平行于 Y 轴的情形类似。4. 假如 L 既不平行 X 轴也不平行 Y 轴，可以求出 L 的斜率 K，然后列出L 的点斜式方程，和圆方程联马上可求解出L 和圆

20、的两个交点。5. 假如 L 是线段，对于 2， 3 ， 4 中求出的交点仍要分别判定是否属于该线段的范畴内。凸包的概念：点集 Q 的凸包 convex hull是指一个最小凸多边形，中意Q 中的点或者在多边形边上或者在其内。下图中由红色线段表示的多边形就是点集Q=p0,p1,.p12的凸包。凸包的求法：现在已经证明白凸包算法的时间复杂度下界是On*logn,但是当凸包的顶点数h 也被考虑进去的话， Krikpatrick和 Seidel 的剪枝搜寻算法可以达到On*logh，在渐进意义下达到最优。最常用的凸包算法是Graham 扫描法和 Jarvis 步进法。本文只简洁介绍一下Graham 扫

21、描法，其正确性的证明和Jarvis 步进法的过程大家可以参考算法导论。对于一个有三个或以上点的点集Q， Graham 扫描法的过程如下： 令 p0 为 Q 中 Y-X 坐标排序下最小的点设 为对其余点按以p0 为中心的极角逆时针排序所得的点集（假如有多个点有相同的极角，除了距p0 最远的点外全部移除压 p0 进栈 S压 p1 进栈 S压 p2 进栈 S for i 3 to mdo while 由 S 的栈顶元素的下一个元素、S 的栈顶元素以及pi 构成的折线段不拐向左侧对 S弹栈可编辑资料 - - - 欢迎下载精品名师归纳总结压 pi 进栈 S return S。此过程执行后，栈S 由底至顶

22、的元素就是Q 的凸包顶点按逆时针排列的点序列。需要留意的是，我们对点按极角逆时针排序时，并不需要真正求出极角，只需要求出任意两点的次序就可以了。而这个步骤可以用前述的矢量叉积性质实现。四、结语尽管人类对几何学的争辩从古代起便没有中断过，但是具体到借助运算机来解决几何问题的争辩，仍只是停留在一个初级阶段，无论从应用领域仍是进展前景来看，运算几何学都值得我们认真学习、加以运用，期望这篇文章能带你走进这个丰富多彩的世界 。版权申明本文部分内容，包括文字、图片、以及设计等在网上搜集整理。版权为潘宏亮个人全部This article includes some parts, including text

23、, pictures, and design. Copyright is Pan Hongliangs personal ownership.用户可将本文的内容或服务用于个人学习、争辩或观看，以及其他非商业性或非盈利性用途，但同时应遵守著作权法及其他相关法律的规定，不得侵害本网站及相关权益人的合法权益。除此以 外，将本文任何内容或服务用于其他用途时，须征得本人及相关权益人的书面许可，并支付酬劳。Users may use the contents or services of this article for personal study, research or appreciation,

24、and other non-commercial or non-profit purposes, but at the可编辑资料 - - - 欢迎下载精品名师归纳总结same time, they shall abide by the provisions of copyright law and other relevant laws, and shall not infringe upon the legitimate rights of this website and its relevant obligees. In addition, when any content or ser

25、vice of this article is used for other purposes, written permission and remuneration shall be obtained from the person concerned and the relevant obligee.转载或引用本文内容必需是以新闻性或资料性公共免费信息为使用目的的合理、善意引用，不得对本文内容原意进行曲解、修 改，并自负版权等法律责任。Reproduction or quotation of the content of this article must be reasonable and good-faith citation for the use of news or informative public free information. It shall not misinterpret or modify the original intention of the content of this article, and shall bear legal liability such as copyright.可编辑资料 - - - 欢迎下载