矩界算法

⑴ 大数据最常用的算法有哪些

奥地利符号计算研究所(Research Institute for Symbolic Computation，简称RISC)的Christoph Koutschan博士在自己的页面上发布了一篇文章，提到他做了一个调查，参与者大多数是计算机科学家，他请这些科学家投票选出最重要的算法，以下是这次调查的结果，按照英文名称字母顺序排序。

大数据等最核心的关键技术：32个算法

1、A* 搜索算法——图形搜索算法，从给定起点到给定终点计算出路径。其中使用了一种启发式的估算，为每个节点估算通过该节点的最佳路径，并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此，A*搜索算法是最佳优先搜索的范例。

2、集束搜索(又名定向搜索，Beam Search)——最佳优先搜索算法的优化。使用启发式函数评估它检查的每个节点的能力。不过，集束搜索只能在每个深度中发现最前面的m个最符合条件的节点，m是固定数字——集束的宽度。

3、二分查找(Binary Search)——在线性数组中找特定值的算法，每个步骤去掉一半不符合要求的数据。

4、分支界定算法(Branch and Bound)——在多种最优化问题中寻找特定最优化解决方案的算法，特别是针对离散、组合的最优化。

5、Buchberger算法——一种数学算法，可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。

6、数据压缩——采取特定编码方案，使用更少的字节数(或是其他信息承载单元)对信息编码的过程，又叫来源编码。

7、Diffie-Hellman密钥交换算法——一种加密协议，允许双方在事先不了解对方的情况下，在不安全的通信信道中，共同建立共享密钥。该密钥以后可与一个对称密码一起，加密后续通讯。

8、Dijkstra算法——针对没有负值权重边的有向图，计算其中的单一起点最短算法。

9、离散微分算法(Discrete differentiation)。

10、动态规划算法(Dynamic Programming)——展示互相覆盖的子问题和最优子架构算法

11、欧几里得算法(Euclidean algorithm)——计算两个整数的最大公约数。最古老的算法之一，出现在公元前300前欧几里得的《几何原本》。

12、期望-最大算法(Expectation-maximization algorithm，又名EM-Training)——在统计计算中，期望-最大算法在概率模型中寻找可能性最大的参数估算值，其中模型依赖于未发现的潜在变量。EM在两个步骤中交替计算，第一步是计算期望，利用对隐藏变量的现有估计值，计算其最大可能估计值;第二步是最大化，最大化在第一步上求得的最大可能值来计算参数的值。

13、快速傅里叶变换(Fast Fourier transform，FFT)——计算离散的傅里叶变换(DFT)及其反转。该算法应用范围很广，从数字信号处理到解决偏微分方程，到快速计算大整数乘积。

14、梯度下降(Gradient descent)——一种数学上的最优化算法。

15、哈希算法(Hashing)。

16、堆排序(Heaps)。

17、Karatsuba乘法——需要完成上千位整数的乘法的系统中使用，比如计算机代数系统和大数程序库，如果使用长乘法，速度太慢。该算法发现于1962年。

18、LLL算法(Lenstra-Lenstra-Lovasz lattice rection)——以格规约(lattice)基数为输入，输出短正交向量基数。LLL算法在以下公共密钥加密方法中有大量使用：背包加密系统(knapsack)、有特定设置的RSA加密等等。

19、最大流量算法(Maximum flow)——该算法试图从一个流量网络中找到最大的流。它优势被定义为找到这样一个流的值。最大流问题可以看作更复杂的网络流问题的特定情况。最大流与网络中的界面有关，这就是最大流-最小截定理(Max-flow min-cut theorem)。Ford-Fulkerson 能找到一个流网络中的最大流。

20、合并排序(Merge Sort)。

21、牛顿法(Newton’s method)——求非线性方程(组)零点的一种重要的迭代法。

22、Q-learning学习算法——这是一种通过学习动作值函数(action-value function)完成的强化学习算法，函数采取在给定状态的给定动作，并计算出期望的效用价值，在此后遵循固定的策略。Q-leanring的优势是，在不需要环境模型的情况下，可以对比可采纳行动的期望效用。

23、两次筛法(Quadratic Sieve)——现代整数因子分解算法，在实践中，是目前已知第二快的此类算法(仅次于数域筛法Number Field Sieve)。对于110位以下的十位整数，它仍是最快的，而且都认为它比数域筛法更简单。

24、RANSAC——是“RANdom SAmple Consensus”的缩写。该算法根据一系列观察得到的数据，数据中包含异常值，估算一个数学模型的参数值。其基本假设是：数据包含非异化值，也就是能够通过某些模型参数解释的值，异化值就是那些不符合模型的数据点。

25、RSA——公钥加密算法。首个适用于以签名作为加密的算法。RSA在电商行业中仍大规模使用，大家也相信它有足够安全长度的公钥。

26、Sch?nhage-Strassen算法——在数学中，Sch?nhage-Strassen算法是用来完成大整数的乘法的快速渐近算法。其算法复杂度为：O(N log(N) log(log(N)))，该算法使用了傅里叶变换。

27、单纯型算法(Simplex Algorithm)——在数学的优化理论中，单纯型算法是常用的技术，用来找到线性规划问题的数值解。线性规划问题包括在一组实变量上的一系列线性不等式组，以及一个等待最大化(或最小化)的固定线性函数。

28、奇异值分解(Singular value decomposition，简称SVD)——在线性代数中，SVD是重要的实数或复数矩阵的分解方法，在信号处理和统计中有多种应用，比如计算矩阵的伪逆矩阵(以求解最小二乘法问题)、解决超定线性系统(overdetermined linear systems)、矩阵逼近、数值天气预报等等。

29、求解线性方程组(Solving a system of linear equations)——线性方程组是数学中最古老的问题，它们有很多应用，比如在数字信号处理、线性规划中的估算和预测、数值分析中的非线性问题逼近等等。求解线性方程组，可以使用高斯—约当消去法(Gauss-Jordan elimination)，或是柯列斯基分解( Cholesky decomposition)。

30、Strukturtensor算法——应用于模式识别领域，为所有像素找出一种计算方法，看看该像素是否处于同质区域( homogenous region)，看看它是否属于边缘，还是是一个顶点。

31、合并查找算法(Union-find)——给定一组元素，该算法常常用来把这些元素分为多个分离的、彼此不重合的组。不相交集(disjoint-set)的数据结构可以跟踪这样的切分方法。合并查找算法可以在此种数据结构上完成两个有用的操作：

查找：判断某特定元素属于哪个组。

合并：联合或合并两个组为一个组。

32、维特比算法(Viterbi algorithm)——寻找隐藏状态最有可能序列的动态规划算法，这种序列被称为维特比路径，其结果是一系列可以观察到的事件，特别是在隐藏的Markov模型中。

以上就是Christoph博士对于最重要的算法的调查结果。你们熟悉哪些算法?又有哪些算法是你们经常使用的?

⑵ 19年3月二级C--数据结构与算法

1.假设线性表的长度为n，则最坏情况下:

冒泡排序: 需要经过n/2遍的从前往后扫描和n/2遍从后往前扫描，需要比较的次数为n(n-1)/2。总的时间复杂度为O(n的平方)。

快速排序: 比较次数也是n(n-1)/2。总的时间复杂度为O(n的平方)。

直接插入排序: 所需要比较的次数为n(n-1)/2。总的时间复杂度为O(n的平方)。

希尔排序所需要比较的次数为O(n的1.5次方)。(时间复杂度小于以上三种)

堆排序: 最坏情况下，其时间复杂度为O(nlogn)。(小于O(n的平方))。

2.根据数据结构中各元素之间前后关系的复杂程度，一般数据结构分为两大类: 线性结构和非线性结构。

如果一个非空的数据结构满足下列两个条件，①有且只有一个根结点 ②每个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，又称线性表。

3.算法时间复杂度与空间复杂度没有关系。

4.所谓算法的时间复杂度，是指执行算法所需要的计算工作量。

为了能够比较客观的反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所用的计算机程序设计语言，以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。

5.同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。

算法分析的目的在于选择合适算法和改进算法。

6.堆排序在平均情况下的时间复杂度与最坏情况下的时间复杂度都是O(nlogn)。

7.二叉链表: 以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和第一个孩子下的一个兄弟结点。

  循环链表是链式存储结构，循环队列是线性存储结构。( 【×】循环链表是循环队列的链式存储结构)

  双向链表也叫双链表，是链表的一种，它的每个数据结点都有两个指针，分别指向直接后继和直接前驱，所以从双链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。

8.数据的逻辑结构由两个要素: 一是数据元素的集合，通常记为D。二是D上的关系，它反映了D中各元素之间的前后件关系，通常记为R。

即一个数据结构可以表示成B=(D,R)，其中B表示数据结构，为了反映D中各元素之间的前后件关系，一般用二元组来表示。例如，假如a与b是D中的两个数据，则二元组表示a是b的前件，b是a的后件。

  线性结构用图形表示更加直观。例如: R=｛(5,1)，(7,9)，(1,7)，(9,3)｝，结构为: 5→1→7→9→3

9.快速排序法是一种互换类的排序方法，但由于比冒泡排序的速度快，因此称为快速排序。

其基本思想是从线性表中选择一个元素设为t，将线性表后面小于t的元素移到前面，而前面大于t的元素移到后面，结果就将线性表分成了两部分，t插入到分界线的位置处，这个过程称为线性表的分割。

  简单插入排序法，是指将无序序列中的各元素依次插入到已经有序的线性表中。

  冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换，逐步将线性表变为有序。

  后两种元素的移动过程中不会产生新的逆序。

10.程序可作为算法的一种描述。

11.为了降低算法的空间复杂度，要求算法尽量采用原地工作，所谓的原地工作是指执行算法时所使用的额外空间固定。

  一个算法的空间复杂度一般是指执行这个算法所需要的内存空间，一个算法所占用的存储空间包括程序所占的空间，输入的初始数据所占的空间以及算法执行过程中所需要的额外空间。

12.能从任意一个结点开始没有重复的扫描到所有结点的数据结构是循环链表。

13.循环队列是队列的一种存储结构

14.算法的设计要求包括效率与低存储量，即要考虑算法的时间复杂度与空间复杂度。

  算法的复杂度包括时间复杂度和空间复杂度。

  时间复杂度: 是指执行算法所需要的计算工作量。

  空间复杂度: 一般是指执行这个算法所需要的内存空间。

15.栈是一种特殊的线性表。链式结构把每一个存储结点分为数据域与指针域，带链的栈可以通过指针域的变化改变原有的栈的组织数据原则; 而顺序栈的栈底指针不变，栈顶指针改变。

16.堆排序在最坏的情况下需要比较nlogn次。

  快速排序，在最坏情况下需要比较n(n-1)/2次。

  顺序查找，在最坏情况下需要比较n次。

  最坏情况下，二分查找需要log2n(小于n-1)

  在长度为n的顺序表中寻找最大项/最小项时，比较次数最少为1，最多为n-1。

17.如果一个非空的数据结构满足下列两个条件，①有且只有一个根节点 ②每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称为非线性结构。

18.带链栈空的条件是 top=bottom=NULL

19.满二叉树也是完全二叉树，完全二叉树不一定是满二叉树。对于满二叉树和完全二叉树来说，可以按照程序进行顺序存储，不仅节省了空间，又能方便地确定每一个结点的父结点等于左右子结点的位置，但顺序存储结构对于一般的二叉树不适用。

20.带链栈队头指针与队尾指针相同，且不为空时，队列元素个数为1; 若为空时，队列元素个数为0。

带链栈的栈底指针是随栈的操作而动态变化的。

21.二叉树的链式存储结构，也称为二叉链表。在二叉树中，由于每一个元素可以有两个后件，因此用于存储二叉树的存储结点的指针域有两个，所以二叉链表属于非线性结构。

22.线性表由一组元素数据元素构成，各元素的数据类型必须相同，矩阵是一个比较复杂的线性表，线性表除了插入和删除运算之外，还可以查找，排序，分解，合并等。数组是长度固定的线性表。

23.冒泡排序中，在互换两个相邻元素时，只能消除一个逆序; 快速排序及希尔排序中，一次交换可以消除多个逆序。

24.二分法检索的效率比较高，设线性表有n个元素，则最多的比较次数为log2n，最少检索次数为1。

25.循环链表的结构具有以下两个特点。一，在循环链表中，增加了一个表头结点，其数据域为任意或者根据需要来设置指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。二、循环链表中最后一个节点的指针域不是空，而是指向表头结点，即在循环链表中所有的结点指针构成一个环状链。

26.二叉树的存储结构是非线性结构，而完全二叉树是特殊形态的二叉树。采用顺序存储的完全二叉树属于非线性结构。

27.时间复杂度和计算机运行速度以及存储空间无关。

算法的空间复杂度和存储结构无关。

数据处理效率与数据的存储结构有关。

28.线性表，向量，栈，队列都属于线性结构的顺序存储。

29.循环队列是队列的存储结构。

  循环链表是另一种形式的念式存储结构。

  (✘循环链表是循环队列的链式存储结构。✘)

30.完全二叉树的总结点为奇数时，叶子结点是总结点加一再除以二。

31.在实际处理中，可以用一位数组来存储堆序列中的元素，也可以用完全二叉树来直观的表示堆的结构。在用完全二叉树表示堆时，树中所有非叶子结点值均不小于其左，右子树的根结点值，因为堆顶元素必须为序列的n个元素的最大项，因此其中序并不是有序序列。

  多重链表指表中每个结点由两个或两个以上的指针域的链表。如果一个非空的数据结构满足下列两个条件，①有且只有一个根结点，②每个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构，所以多重链表不一定是非线性结构。

  在计算机中二叉树通常采用链式存储结构，对于满二叉树和完全二叉树来说，可以按层次进行顺序存储。

  排序二叉树的中序遍历序列是有序序列。

32.对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。

33.在线性表中寻找最大项时，平均情况下和最坏情况下比较次数都是n-1。

34.在长度为n的顺序表中查找一 个元素， 假没需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相

同的。则在平均情况下需要比较的次数大约为_

A.3n/4    B.n    C.n/2  D.n/4

本题的考查知识点是顺序表的存储结构。

因为需要查找的元素有一半机会在表中，所以二分之一的情况下平均比较次数为n/2，另二分之一的情况下平均比较次数为n。总的平均比较次数为(n/2+n) /2-3n/4。

故本题答案为A。

35.设数据结构B=(D, R)，其中

D={a,b,c,d，e，f}

R={(a，b)，(b，c)，(c，d)，(d，e)，(e，f)，(f,a)}该数据结构为

A.线性结构    B.循环队列

C.循环链表    D.非线性结构

本题的考查知识点是数据结构。

如果一个非控的数据结构满足下列两个条件: 1) 有且只有一个根节点; 2) 每一一个结点最多有一一个前件，也最多有一一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。

数据结构B=(D, R)中， 每一个结点均有一个前件，不符合“有且只有一个根节点”的条件，所以为非线性结构。故本题答案选D。

36.某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。 该队列中的元素个数为_

A.1    B.0    C.1或0    D.不确定

本题的考查知识点是带链队列。

在初始状态为front=rear=NULL的带链队列入队时，如果插入的结点既是队首结点又是队尾结点，则rear和front同时指向这个结点;否则在循环队列的队尾加入一一个新元素，rear指向新增结点的数据域，rear+1, front不变。 退队时，在循环队列的排头位置退出一个元素并赋给指定的变量，front指向第二个结点的数据域，front+1, rear不变。当front=rear=10时， front和rear同时指向这个唯一 元素，所以该队列中的元素个数为1。

故本题答案为A。

37.若二叉树没有叶子结点，则为空二叉树。

38.某带链栈的初始状态为top=bottom=NULL, 经过一系列正 常的入栈与退栈操作后，top=10, bottom=20。 该栈中的元素个数为_____。

A.不确定    B. 10    C.1    D.0

本题考查的知识点是栈。

带链的栈是具有栈属性的链表，线性链表的存储单元是不连续的，为把存储空间中一-些离散的空闲存 储结点利用起来，把所有空闲的结点组织成一个带链的栈，称为可利用栈。

线性链表执行删除操作运算时， 被删除的结点可以”回收到可利用栈，对应于可利用栈的入栈运算;线性链表执行插入运算时，需要一个新的结点，可以在可利用栈中取栈顶结点，对应于可利用栈的退栈运算。

可利用栈的入栈运算和退栈运算只需要改动top指针即可。因为是不连续的存储空间，所以top指针将不会有规律地连续变化，因此无法据此判断栈中的元素个数。

所以本题答案为A。

⑶ 在图像处理中有哪些算法

1、图像变换：

由于图像阵列很大，直接在空间域中进行处理，涉及计算量很大。采用各种图像变换的方法，如傅立叶变换、沃尔什变换、离散余弦变换等间接处理技术，将空间域的处理转换为变换域处理，可减少计算量，获得更有效的处理。它在图像处理中也有着广泛而有效的应用。

2、图像编码压缩：

图像编码压缩技术可减少描述图像的数据量，以便节省图像传输、处理时间和减少所占用的存储器容量。

压缩可以在不失真的前提下获得，也可以在允许的失真条件下进行。

编码是压缩技术中最重要的方法，它在图像处理技术中是发展最早且比较成熟的技术。

3、图像增强和复原：

图像增强和复原的目的是为了提高图像的质量，如去除噪声，提高图像的清晰度等。

图像增强不考虑图像降质的原因，突出图像中所感兴趣的部分。如强化图像高频分量，可使图像中物体轮廓清晰，细节明显；如强化低频分量可减少图像中噪声影响。

4、图像分割：

图像分割是数字图像处理中的关键技术之一。

图像分割是将图像中有意义的特征部分提取出来，其有意义的特征有图像中的边缘、区域等，这是进一步进行图像识别、分析和理解的基础。

5、图像描述：

图像描述是图像识别和理解的必要前提。

一般图像的描述方法采用二维形状描述，它有边界描述和区域描述两类方法。对于特殊的纹理图像可采用二维纹理特征描述。

6、图像分类：

图像分类属于模式识别的范畴，其主要内容是图像经过某些预处理（增强、复原、压缩）后，进行图像分割和特征提取，从而进行判决分类。

图像分类常采用经典的模式识别方法，有统计模式分类和句法模式分类。

(3)矩界算法扩展阅读：

图像处理主要应用在摄影及印刷、卫星图像处理、医学图像处理、面孔识别、特征识别、显微图像处理和汽车障碍识别等。

数字图像处理技术源于20世纪20年代，当时通过海底电缆从英国伦敦到美国纽约传输了一幅照片，采用了数字压缩技术。

数字图像处理技术可以帮助人们更客观、准确地认识世界，人的视觉系统可以帮助人类从外界获取3/4以上的信息，而图像、图形又是所有视觉信息的载体，尽管人眼的鉴别力很高，可以识别上千种颜色，

但很多情况下，图像对于人眼来说是模糊的甚至是不可见的，通过图象增强技术，可以使模糊甚至不可见的图像变得清晰明亮。

⑷ 计算几何的全部算法

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、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，
而处理数据的关键就在于这些算法，通常使用Matlab作为工具）
3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，
很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现）
4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，
涉及到图论的问题可以用这些方法解决，需要认真准备）
5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中）
6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法
（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，
但是算法的实现比较困难，需慎重使用）
7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，
当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具）
8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的）
9、数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比
如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用）
10、图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，
这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理）

⑹ 剩余矩形填充算法是优化算法吗

是，针对矩形件排样问题提出的一种新的空白矩形填充优化算法.
首先,设计空白矩形填充算法时,提出了消除多余空白矩形的方法,以减小计算时间复杂度.其次,利用邻域搜索算法优化矩形件排放顺序,通过挖掘矩形件排样的问题特征,设计了受限距离的交叉和插入两种邻域算子,并提出了特殊算子执行点选择策略.然后,设计了基于两种邻域算子交替迭代的邻域搜索算法.最后,对文献中的21个经典案例进行试验计算,4个案例的排样利用率达到了100％,绝大多数案例的排样利用率超过了99％,最小排样利用率超过了98％.将其他常用算法和文献中算法进行比较,验证了本文算法的有效性