几何算法

❶ 计算几何的全部算法

1. 矢量减法

设二维矢量 P = （x1,y1） ，Q = (x2,y2)
则矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 )
显然有性质 P - Q = - ( Q - P )
如不加说明，下面所有的点都看作矢量，两点的减法就是矢量相减；

2.矢量叉积

设矢量P = （x1,y1） ，Q = (x2,y2)
则矢量叉积定义为： P × Q = x1*y2 - x2*y1 得到的是一个标量
显然有性质 P × Q = - ( Q × P ) P × ( - Q ) = - ( P × Q )
如不加说明，下面所有的点都看作矢量，点的乘法看作矢量叉积；

叉乘的重要性质：

> 若 P × Q > 0 , 则P 在Q的顺时针方向
> 若 P × Q < 0 , 则P 在Q的逆时针方向
> 若 P × Q = 0 , 则P 与Q共线，但可能同向也可能反向

3.判断点在线段上

设点为Q，线段为P1P2 ，判断点Q在该线段上的依据是：

( Q - P1 ) × ( P2 - P1 ) = 0 且 Q 在以 P1，P2为对角顶点的矩形内

4.判断两线段是否相交

我们分两步确定两条线段是否相交：

(1)． 快速排斥试验

设以线段 P1P2 为对角线的矩形为R， 设以线段 Q1Q2 为对角线的矩形为T，如果
R和T不相交，显然两线段不会相交；

(2)． 跨立试验

如果两线段相交，则两线段必然相互跨立对方，如图1所示。在图1中，P1P2跨立
Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即
( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0
上式可改写成
( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0
当( 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 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) ≥ 0

至此已经完全解决判断线段是否相交的问题。

5.判断线段和直线是否相交

如果线段 P1P2和直线Q1Q2相交，则P1P2跨立Q1Q2，即：

( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) ≥ 0

6.判断矩形是否包含点

只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。

6.判断线段、折线、多边形是否在矩形中

因为矩形是个凸集，所以只要判断所有端点是否都在矩形中就可以了。

7.判断矩形是否在矩形中

只要比较左右边界和上下边界就可以了。

8.判断圆是否在矩形中

圆在矩形中的充要条件是：圆心在矩形中且圆的半径小于等于圆心到矩形四边的距
离的最小值。

9.判断点是否在多边形中

以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多
边形外，考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的
时候，进入到了多边形的内部，遇到第二个交点的时候，离开了多边形，……所
以很容易看出当L和多边形的交点数目C是奇数的时候，P在多边形内，是偶数的话
P在多边形外。

但是有些特殊情况要加以考虑。如果L和多边形的顶点相交，有些情况下交点只能
计算一个，有些情况下交点不应被计算（自己画个图就明白了）；如果L和多边形
的一条边重合，这条边应该被忽略不计。为了统一起见，我们在计算射线L和多边
形的交点的时候，1。对于多边形的水平边不作考虑；2。对于多边形的顶点和L相
交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则计数，否则忽略；
3。对于P在多边形边上的情形，直接可判断P属于多边行。由此得出算法的伪代码
如下：

1. count ← 0;
2. 以P为端点，作从右向左的射线L;
3. for 多边形的每条边s
4. do if P在边s上
5. then return true;
6. if s不是水平的
7. then if s的一个端点在L上且该端点是s两端点中纵坐标较大的端点
9. then count ← count+1
10. else if s和L相交
11. then count ← count+1;
12. if count mod 2 = 1
13. then return true
14. else return false;

其中做射线L的方法是：设P'的纵坐标和P相同，横坐标为正无穷大（很大的一个正
数），则P和P'就确定了射线L。这个算法的复杂度为O(n)。

10.判断线段是否在多边形内

线段在多边形内的一个必要条件是线段的两个端点都在多边形内；

如果线段和多边形的某条边内交（两线段内交是指两线段相交且交点不在两线段的
端点），因为多边形的边的左右两侧分属多边形内外不同部分，所以线段一定会有
一部分在多边形外。于是我们得到线段在多边形内的第二个必要条件：线段和多边
形的所有边都不内交；

线段和多边形交于线段的两端点并不会影响线段是否在多边形内；但是如果多边形
的某个顶点和线段相交，还必须判断两相邻交点之间的线段是否包含与多边形内部。
因此我们可以先求出所有和线段相交的多边形的顶点，然后按照X-Y坐标排序，这样
相邻的两个点就是在线段上相邻的两交点，如果任意相邻两点的中点也在多边形内，
则该线段一定在多边形内。证明如下：

命题1：

如果线段和多边形的两相邻交点P1 ，P2的中点P' 也在多边形内，则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在多边形内且对于i =1, 2,……, n-1，Pi ,Pi+1
的中点也在多边形内。

在实际编程中，没有必要计算所有的交点，首先应判断线段和多边形的边是否内交
，倘若线段和多边形的某条边内交则线段一定在多边形外；如果线段和多边形的每
一条边都不内交，则线段和多边形的交点一定是线段的端点或者多边形的顶点，只
要判断点是否在线段上就可以了。

至此我们得出算法如下：

1. if 线端PQ的端点不都在多边形内
2. then return false;
3. 点集pointSet初始化为空;
4. for 多边形的每条边s
5. do if 线段的某个端点在s上
6. then 将该端点加入pointSet;
7. else if s的某个端点在线段PQ上
8. then 将该端点加入pointSet;
9. else if s和线段PQ相交 // 这时候可以肯定是内交
10. then return false;
11. 将pointSet中的点按照X-Y坐标排序，X坐标小的排在前面，
对于X坐标相同的点，Y坐标小的排在前面；
12. for pointSet中每两个相邻点 pointSet[i] , pointSet[ i+1]
13. do if pointSet[i] , pointSet[ i+1] 的中点不在多边形中
14. then return false;
15. return true;

这个算法的复杂度也是O(n)。其中的排序因为交点数目肯定远小于多边形的顶点数
目n，所以最多是常数级的复杂度，几乎可以忽略不计。

11.判断折线在多边形内

只要判断折线的每条线段是否都在多边形内即可。设折线有m条线段，多边形有n个
顶点，则复杂度为O(m*n)。

12.判断多边形是否在多边形内

只要判断多边形的每条边是否都在多边形内即可。判断一个有m个顶点的多边形是
否在一个有n个顶点的多边形内复杂度为O(m*n)。

13.判断矩形是否在多边形内

将矩形转化为多边形，然后再判断是否在多边形内。

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

只要计算圆心到多边形的每条边的最短距离，如果该距离大于等于圆半径则该圆在
多边形内。计算圆心到多边形每条边最短距离的算法在后文阐述。

15.判断点是否在圆内

计算圆心到该点的距离，如果小于等于半径则该点在圆内。

16.判断线段、折线、矩形、多边形是否在圆内

因为圆是凸集，所以只要判断是否每个顶点都在圆内即可。

17.判断圆是否在圆内

设两圆为O1,O2，半径分别为r1, r2，要判断O2是否在O1内。先比较r1，r2的大小
，如果r1<r2则O2不可能在O1内；否则如果两圆心的距离大于r1 - r2 ，则O2不在
O1内；否则O2在O1内。

18.计算点到线段的最近点

如果该线段平行于X轴（Y轴），则过点point作该线段所在直线的垂线，垂足很容
易求得，然后计算出垂足，如果垂足在线段上则返回垂足，否则返回离垂足近的端
点；

如果该线段不平行于X轴也不平行于Y轴，则斜率存在且不为0。设线段的两端点为
pt1和pt2，斜率为：
k = ( pt2.y - pt1. y ) / (pt2.x - pt1.x );
该直线方程为：
y = k* ( x - pt1.x) + pt1.y
其垂线的斜率为 - 1 / k，
垂线方程为：
y = (-1/k) * (x - point.x) + point.y
联立两直线方程解得：
x = ( k^2 * pt1.x + k * (point.y - pt1.y ) + point.x ) / ( k^2 + 1)
y = k * ( x - pt1.x) + pt1.y;

然后再判断垂足是否在线段上，如果在线段上则返回垂足；如果不在则计算两端点
到垂足的距离，选择距离垂足较近的端点返回。

19.计算点到折线、矩形、多边形的最近点

只要分别计算点到每条线段的最近点，记录最近距离，取其中最近距离最小的点即
可。

20.计算点到圆的最近距离

如果该点在圆心，则返回UNDEFINED
连接点P和圆心O，如果PO平行于X轴，则根据P在O的左边还是右边计算出最近点的
横坐标为centerPoint.x - radius 或 centerPoint.x + radius， 如图4 (a)所示；
如果PO平行于Y轴，则根据P在O的上边还是下边计算出最近点的纵坐标为
centerPoint.y + radius 或 centerPoint.y - radius， 如图4 (b)所示。

如果PO不平行于X轴和Y轴，则PO的斜率存在且不为0，如图4(c)所示。这时直线PO
斜率为
k = （ P.y - O.y ）/ ( P.x - O.x )
直线PO的方程为：
y = k * ( x - P.x) + P.y
设圆方程为:
(x - O.x ) ^2 + ( y - O.y ) ^2 = r ^2，
联立两方程组可以解出直线PO和圆的交点，取其中离P点较近的交点即可。

21.计算两条共线的线段的交点

对于两条共线的线段，它们之间的位置关系有图5所示的几种情况。
图5(a)中两条线段没有交点；图5 (b) 和 (d) 中两条线段有无穷焦点；图5 (c)
中两条线段有一个交点。设line1是两条线段中较长的一条，line2是较短的一条，
如果line1包含了line2的两个端点，则是图5(d)的情况，两线段有无穷交点；如
果line1只包含line2的一个端点，那么如果line1的某个端点等于被line1包含的
line2的那个端点，则是图5(c)的情况，这时两线段只有一个交点，否则就是
图5(c)的情况，两线段也是有无穷的交点；如果line1不包含line2的任何端点，
则是图5(a)的情况，这时两线段没有交点。

22.计算线段或直线与线段的交点

设一条线段为L0 = P1P2，另一条线段或直线为L1 = Q1Q2 ，要计算的就是L0和L1
的交点。

1.首先判断L0和L1是否相交（方法已在前文讨论过），如果不相交则没有交点，
否则说明L0和L1一定有交点，下面就将L0和L1都看作直线来考虑。

2.如果P1和P2横坐标相同，即L0平行于Y轴
a)若L1也平行于Y轴，
i.若P1的纵坐标和Q1的纵坐标相同，说明L0和L1共线，假如L1是直线的话他们有
无穷的交点，假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们
的交点（该方法在前文已讨论过）；
ii.否则说明L0和L1平行，他们没有交点；
b)若L1不平行于Y轴，则交点横坐标为P1的横坐标，代入到L1的直线方程中可以计
算出交点纵坐标；
3.如果P1和P2横坐标不同，但是Q1和Q2横坐标相同，即L1平行于Y轴，则交点横
坐标为Q1的横坐标，代入到L0的直线方程中可以计算出交点纵坐标；
4.如果P1和P2纵坐标相同，即L0平行于X轴
a)若L1也平行于X轴，
i.若P1的横坐标和Q1的横坐标相同，说明L0和L1共线，假如L1是直线的话他们
有无穷的交点，假如L1是线段的话可用"计算两条共线线段的交点"的算法求
他们的交点（该方法在前文已讨论过）；
ii.否则说明L0和L1平行，他们没有交点；

b)若L1不平行于X轴，则交点纵坐标为P1的纵坐标，代入到L1的直线方程中可以计
算出交点横坐标；
5.如果P1和P2纵坐标不同，但是Q1和Q2纵坐标相同，即L1平行于X轴，则交点纵坐标
为Q1的纵坐标，代入到L0的直线方程中可以计算出交点横坐标；
6.剩下的情况就是L1和L0的斜率均存在且不为0的情况
a)计算出L0的斜率K0，L1的斜率K1 ；
b)如果K1 = K2
i.如果Q1在L0上，则说明L0和L1共线，假如L1是直线的话有无穷交点，假如L1
是线段的话可用"计算两条共线线段的交点"的算法求他们的交点（该方法在
前文已讨论过）；
ii.如果Q1不在L0上，则说明L0和L1平行，他们没有交点。
c)联立两直线的方程组可以解出交点来

说明：这个算法并不复杂，但是要分情况讨论清楚，尤其是当两条线段共线的情况
需要单独考虑，所以在前文将求两条共线线段的算法单独写出来。另外，一开始就
先利用矢量叉乘判断线段与线段（或直线）是否相交，如果结果是相交，那么在后
面就可以将线段全部看作直线来考虑。

23.求线段或直线与折线、矩形、多边形的交点

分别求与每条边的交点即可。

24.求线段或直线与圆的交点

设圆心为O，圆半径为r，直线（或线段）L上的两点为P1,P2。
1.如果L是线段且P1，P2都包含在圆O内，则没有交点；否则进行下一步
2.如果L平行于Y轴，
a)计算圆心到L的距离dis
b)如果dis > r 则L和圆没有交点；
c)利用勾股定理，可以求出两交点坐标，如图6(a)所示；但要注意考虑L和圆的相
切情况
3.如果L平行于X轴，做法与L平行于Y轴的情况类似；
4.如果L既不平行X轴也不平行Y轴，可以求出L的斜率K，然后列出L的点斜式方程
，和圆方程联立即可求解出L和圆的两个交点；
5.如果L是线段，对于2，3，4中求出的交点还要分别判断是否属于该线段的范围内。

❷ 几何咋算

在初中数学的学习中，几何一直是大多数学生的难题，那么学习几何到底有没有捷径呢？我们又应该怎样来学习几何呢？

步骤/方法

1

（一）对基础知识的把握一定要牢固，在这个基础上我们才能谈如何学好的新问题。例如我们在证实相似的时候，假如利用两边对应成比例及其夹角相等的方法时，必须注重所找的角是两边的夹角，而不能是其它角。在回答圆的对称轴时不能说是它的直径，而必须说是直径所在的直线。像这样的细节我们必须在平时就要引起足够的重视并且牢固把握，只有这样才是学好几何的基础。

2

（二）善于归纳总结，熟悉常见的特征图形。举个例子，已知A，B，C三点共线，分别以AB，BC为边向外作等边△ABD和等边△BCE，假如再没有其他附加条件，那么你能从这个图形中找到哪些结论？
假如我们通过很多习题能够总结出：一般情况下题目中假如有两个有公共顶点的等边三角形就必然会出现一对旋转式的全等三角形的结论，这样我们很轻易得出△ABE≌△DBC，在这对全等三角形的基础上我们还会得出△EMB≌△CNB，△MBN是等边三角形，MN∥AC等主要结论，这些结论也会成为解决其它新问题的桥梁。在几何的学习中这样典型的图形很多，要善于总结。

3

（三）熟悉解题的常见着眼点，常用辅助线作法，把大新问题细化成各个小新问题，从而各个击破，解决新问题。在我们对一个新问题还没有切实的解决方法时，要善于捕捉可能会帮助你解决新问题的着眼点。例如，在一个非直角三角形中出现了非凡的角，那你应该马上想到作垂直构造直角三角形。因为非凡角只有在非凡形中才会发挥功能。再比如，在圆中出现了直径，马上就应该想到连出90°的圆周角。碰到梯形的计算或者证实新问题时，首先我们心里必须清楚碰到梯形新问题都有哪些辅助线可作，然后再具体新问题具体分析。举个例子说，假如题目中说到梯形的腰的中点，你想到了什么？你必须想到以下几条，第一你必须想到梯形的中位线定理。第二你必须想到可以过一腰的中点平移另一腰。第三你必须想到可以连接一个顶点和腰的中点然后延长去构造全等三角形。只有这几种可能用到的辅助线烂熟于心，我们才能很好的解决新问题。其实很多时候我们只要抓住这些常见的着眼点，试着去作了，那么新问题也就迎刃而解了。另外只要我们想到了，一定要肯于去尝试，只有你去做了才可能成功。

4

（四）考虑新问题全面也是学好几何至关重要的一点。在几何的学习中，经常会碰到分两种或多种情况来解的新问题，那么我们怎么能更好的解决这部分新问题呢？这要靠平时的点滴积累，对比较常见的分情况考虑的新问题要熟悉。例如说到等腰三角形的角要考虑是顶角还是底角，说到等腰三角形的边要考虑是底还是腰，说到过一点作直线和圆相交，要考虑点和圆有三种位置关系，所以要画出三种图形。这样的情况在几何的学习中是非经常见的，在这里不一一列举，但大家在做题时一定要注重考虑到是否要分情况考虑。很多时候是你平常注重积累了，你心里有了这个新问题，你作题时才会自然而然的想到。
总之，学好几何必须在牢固把握基础知识的基础上注重平时的点滴积累，善于归纳总结，熟悉解题的常见着眼点，当然做到这些必须要有一定数量的习题积累，我们并不提倡题海战术，但做适量的习题还是必要的，只有量的积累才能达到质的飞跃。

以上来自网络经验

❸ 几何体求算法

你的图1是切线，但是图2为最短距离。到底问什么呀？
你问的是切点吗？只有切线才可以叫切点的，但是切线不是A到圆O上最短的点。已知直线过A(X1，Y1),设直线为：y-y1=k（x-x1），圆心到这个点的距离为r，可解出切线的方程，可解得切点坐标。
还是问A到圆O上最短的点。如果是问最短的点的话，直线AO，A点已知，O点已知，可以得到AO的方程；圆O，方程为（x-m）^+(y-n)^=R^,这个方程同时成立可以得到两个解，一个为最近距离一个为最远距离。

❹ 几何图形计算公式

编辑本段二、我们所熟悉的几何图形的公式：

正方形
a-----边长
C＝4a
S＝a^2
长方形
a和b-----边长
C＝2(a+b)
S＝ab
三角形
a,b,c-----三边长
h-----a边上的高
s-----周长的一半
A,B,C-----内角
其中s＝(a+b+c)/2
S＝ah/2
＝ab/2·
sinC
＝[s(s-a)(s-b)(s-c)]1/2
＝a2sin
BsinC/(2sinA)
四边形
d,D-----对角线长
α-----对角线夹角
S＝dD/2·sinα
平行四边形
a,b-----边长
h-----a边的高
α-----两边夹角
S＝ah
＝absinα
菱形
a-----边长
α-----夹角
D-----长对角线长
d-----短对角线长
S＝Dd/2
＝a2sinα
梯形
a和b-----上、下底长
h-----高
m-----中位线长
S＝(a+b)h/2
＝mh
圆
r-----半径
d-----直径
C＝πd＝2πr
S＝πr2
＝πd2/4
扇形
r-----扇形半径
a-----圆心角度数
C＝2r＋2πr×(a/360)
S＝πr2×(a/360)
弓形
l-----弧长
b-----弦长
h-----矢高
r-----半径
α-----圆心角的度数
S＝r2/2·(πα/180-sinα)
＝r2arccos[(r-h)/r]
-
(r-h)(2rh-h2)1/2
＝παr2/360
-
b/2·[r2-(b/2)2]1/2
＝r(l-b)/2
+
bh/2
≈2bh/3
圆环
R-----外圆半径
r-----内圆半径
D-----外圆直径
d-----内圆直径
S＝π(R2-r2)
＝π(D2-d2)/4
几何还有立体几何：
立方体
a-----棱长
C=12a
S=a×a×a
长方体
a-----长
b-----宽
c-----高
C=(a+b+c)×3
S=(a×b）+（a×c）+（b×c）
圆柱
圆台
棱柱
棱台
圆锥
棱锥等

❺ 几何应算

不懂，有计算几何:
计算几何

computational geometry

研究几何模型和数据处理的学科，探讨几何形体的计算机表示。分析和综合，研究如何灵活、有效的建立几何形体的数学模型以及在计算机中更好地存储和管理这些模型数据.

由函数逼近论、微分几何、代数几何、计算数学等形成的边缘学科，研究几何外形信息的计算机表示、分析和综合。它是计算机辅助几何设计（即CAGD）的数学基础。计算机辅助设计的研究工作始于1955年 ，20世纪60年代进入实用阶段，到70年代已广泛应用于造船、航空、汽车及众多工业产品的外形设计和制造领域。进行此项工作的设计者首先要把一般的曲线或曲面表示在计算机上，然后对这些曲线或曲面的几何性质进行分析，比如看曲线上有无拐点、奇点、曲面的凹凸性等等，最后采用有效的数值计算方法，经过程序运算或人机对话等形式控制或修改这些曲线或曲面，使之符合产品设计的要求。

法国雷诺汽车公司工程师P.E.贝济埃 ，从 1962 年开始研究并首次完成一项曲线曲面设计系统 ，得到了成功的应用。继贝济埃曲线曲面之后，又有两个图形系统问世，它们是B样条曲线曲面和孔斯曲面。计算几何现主要研究和应用的仍然是以上3种图形系统。

❻ 几何是如何计算的

矢量相加或者相减

❼ 算法几何讲什么

算法几何的就是他的一个算法的能力，这就是三角函数概念，还有他那个含义和内涵。

❽ 数学几何计算

综述：R=10.8052

梯形的高：55×cos(114.6°-90°)=50.008

直角三角形的竖直角边：

50.008-2R

a=R÷tan((180-114.6)÷2)

＝1.55766R

b=53×cos(71.1)

＝17.1676

c=R÷tan((180-71.1)÷2)

＝0.7146R

直角三角形的横直角边：

100-a-b-c

＝82.8324-2.27226R

直角三角形的斜边：6R

勾股定理：（6R)²=(50.008-2R)²+(82.8324-2.27226R)²，

解方程得：R=10.8052

几何简介

几何是研究空间结构及性质的一门学科。它是数学中最基本的研究内容之一，与分析、代数等等具有同样重要的地位，并且关系极为密切。几何学发展历史悠长，内容丰富。

它和代数、分析、数论等等关系极其密切。几何思想是数学中最重要的一类思想。暂时的数学各分支发展都有几何化趋向，即用几何观点及思想方法去探讨各数学理论。常见定理有勾股定理，欧拉定理，斯图尔特定理等。

❾ 几何平均的算法

负数照代进去咯，算出一个负值，明显不能代表实际情况，没有统计意义

CAGR=(1+20%)*(1+30%)*(1+50%)*(1+25%)*(1-15%)*(1+5%)^(1/6)-1

很明显算平均增长率用CAGR比几何平均合适，具有统计意义，按照六年来的增长率，用CAGR可以估计下一年产值.