多边形最佳算法

‘壹’ 游戏任意多边形切割算法

1. 判断一个点与一个多边形关系的算法是计算机图形学的一个算法. 关于具体的算法, 你可以参考 http://blog.csdn.net/okvee/archive/2010/06/02/5643407.aspx 里面的描述很详细.
2. 人在冰上走的时候记录他的行走路线的方法: 新建一个容量为N的点的队列, 每隔一定时间(例如0.3秒)取人物的位置点, 判断队列里是否已经存在这个点, 若不存在则把该点压到队列里; 若存在则表明形成了一个多边形(严格来说, 只有间隔超过两个点才能形成一个多边形,至少3点才能确定一个面嘛) [队列就是类似于堆栈的数据结构, 可以压入元素, 当压入的元素个数超过队列的容量后, 最先压入的元素会被删除]用队列来保存人物的轨迹再好不过了.
3. 那个层次感的实现: 其实就是将多边形轨迹往下偏移几个像素, 并删除不在原多边形区域内的点即可.

‘贰’ 泰森多边形计算公式

泰森多边形没有固定计算公式，泰森多边形算法的关键是对离散数据点合理地连成三角网，即构建Delaunay三角网。

对与每个离散点相邻的三角形按顺时针或逆时针方向排序，以便下一步连接生成泰森多边形。排序的方法可如图所示。设离散点为o。

找出以o为顶点的一个三角形，设为A；取三角形A除o以外的另一顶点，设为a，则另一个顶点也可找出，即为f；则下一个三角形必然是以of为边的，即为三角形F；三角形F的另一顶点为e，则下一三角形是以oe为边的；如此重复进行，直到回到oa边。

(2)多边形最佳算法扩展阅读：

泰森多边形可用于定性分析、统计分析、邻近分析等。例如，可以用离散点的性质来描述泰森多边形区域的性质。

可用离散点的数据来计算泰森多边形区域的数据；判断一个离散点与其它哪些离散点相邻时，可根据泰森多边形直接得出。

‘叁’ 基于图论的最小多边形自动搜索算法

图是由点集和边集所构成的抽象概念，图的性质实质上可以表现为拓扑关系。如图4.8b所示，点集由分叉点构成(4个分叉点，分别是1，2，3，4)，边集则由地层线构成(7条地层线，分别是①，②，③，④，⑤，⑥，⑦)。需要说明的是，这里的边是广义上的边，可能是直线段，也可能是多线段。

最小多边形的自动搜索在GIS的空间分析中应用较多，搜索可分为无拓扑和含拓扑两类。无拓扑自动搜索则完全依靠几何计算来判断，如夹角变化趋势的多边形自动搜索算法(梁晓文等，2005)，该算法主要依靠弧段间夹角计算来判断，通过“左转”或“右转”的方法能够唯一确定最小多边形，原理简单，但程序设计过程极其烦琐。采用图论的方法来实现，原理相对复杂，需要掌握数据结构知识，但程序代码设计过程比较简洁，具有扩展性。

为了简单起见，以图4.8b中地层线①为例，说明搜索过程。从分叉点1开始，沿地层线①在分叉点2与地层线②和③邻接，地层线②和③又分别在分叉点3和4与两地层线邻接。整个邻接关系可以用一个树(tree)型结构来表示(图4.10)，终止条件是回到分叉点1，形成闭合回路或者出现自相交，则停止搜索。这样，产生4条有意义的多边形为：1-①-2-②-3-⑥-1，1-①-2-②-3-④-4-⑤-1，1-①-2-③-4-④-3-⑥-1，1-①-2-③-4-⑤-1。

图4.10 分叉点1沿①为起始方向的连通图

在上述4条连通多边形中，面积最小者对应的就是一个最小多边形(周秋生，1996)。若多边形点对为(x₁，y₁)，(x₂，y₂)，…，(x_n，y_n)，面积可采用下式来计算：

S=

×[(x₁×y₂-y₁×x₂)+(x₂×y₃-y₂×x₃)+…+(x_n×y₁-y_n×x₁)](4.1)可确定1-①-2-②-3-⑥-1为当前循环的最小多边形，同时，删除广义边①与②，②与⑥，及⑥与①之间的指针联系，从而可以避免重复查找该最小多边形。接下来，从分叉点1沿另外两个方向⑤和⑥分别搜索最小多边形，完成分叉点1的查找。然后，进入下一分叉点。

最终，得到3个最小多边形。从图论的观点来看，所研究的图是一个连通的平面图。若图有n个分叉点，m条广义边，p个最小多边形，则平面图的面数(包括外部面)f=p+1。

根据欧拉公式(孙家广，1998)：

f+m-n=2 (4.2)

可以得到最小多边形数目为

p=m-n+1 (4.3)

见图4.4b中，m=7，n=5，则p=7-5+1=3。据此可以作为搜索结果正确与否的判断方式之一。

‘肆’ 对于地图上的不规则区域，有什么好的算法把它变为规则的多边形

复制的。
/*在GIS（地理信息管理系统）中，判断一个坐标是否在多边形内部是个经常要遇到的问题。乍听起来还挺复杂。
根据W. Randolph Franklin 提出的PNPoly算法，只需区区几行代码就解决了这个问题。
假设多边形的坐标存放在一个数组里，首先我们需要取得该数组在横坐标和纵坐标的最大值和最小值，
根据这四个点算出一个四边型，首先判断目标坐标点是否在这个四边型之内，如果在这个四边型之外，那可以跳过后面较为复杂的计算，直接返回false。*/

if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY) {
// 这个测试都过不了。。。直接返回false；
}
接下来是核心算法部分：
int pnpoly (int nvert, float *vertx, float *verty, float testx, float testy) {
int i, j, c = 0;
for (i = 0, j = nvert-1; i < nvert; j = i++)
{
if
(
( (verty[i]>testy) != (verty[j]>testy) ) &&(testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i])
)
c = !c;
}
return c;
}

额，代码就这么简单，但到底啥意思呢：
首先，参数nvert 代表多边形有几个点。浮点数testx, testy代表待测试点的横坐标和纵坐标，*vertx,*verty分别指向储存多边形横纵坐标数组的首地址。
我们注意到，每次计算都涉及到相邻的两个点和待测试点，然后考虑两个问题：
1. 被测试点的纵坐标testy是否在本次循环所测试的两个相邻点纵坐标范围之内？即
verty[i] <testy <="" verty[j]或者
verty[j] <testy <="" verty[i]2. 待测点test是否在i,j两点之间的连线之下？看不懂后半短if statement的朋友请自行在纸上写下i,j两点间的斜率公式，
要用到一点初中解析几何和不等式的知识范畴，对广大码农来说小菜一碟。
然后每次这两个条件同时满足的时候我们把返回的布尔量取反。
可这到底是啥意思啊？
这个表达式的意思是说，随便画个多边形，随便定一个点，然后通过这个点水平划一条线，先数数看这条横线和多边形的边相交几次，
（或者说先排除那些不相交的边，第一个判断条件），然后再数这条横线穿越多边形的次数是否为奇数，如果是奇数，那么该点在多
边形内，如果是偶数，则在多边形外。详细的数学证明这里就不做了，不过读者可以自行画多边形进行验证。

‘伍’ 几何题，多边形算法

左边的图形，条件不足 ，无法确定红线上方直角三角形内锐角的度数，因而无法计算红色线处的长度，若锐角为45º，则非常简单，如图，点击放大：

‘陆’ 如何求得任意多边形的面积（包括内多边形）

应当是化成三角形。
一、
对于一个三角形的三个顶点坐标知道的情况下，也就是说各个边的边长知道，另外还可以计算出各个顶角（因为知道了三个边，根据余弦定理就可以求出，或者你学过矢量的话，用两个矢量的夹角算也成），最后用面积公式S=0.5*a*b*Sin(C)
二、
固定住一个点（比如最上面那个点），然后把与这个点不相邻的点与这个固定点连起来。这样就把多边形全变成三角形。而且这里的三角形，三个边全部知道，如上面所说的。就可以求出各个三角形的面积。

‘柒’ 多边形游戏问题的算法可以采用什么来实现

在GIS（地理信息管理系统）中，判断一个坐标是否在多边形内部是个经常要遇到的问题。乍听起来还挺复杂。根据W. Randolph Franklin 提出的PNPoly算法，只需区区几行代码就解决了这个问题。 假设多边形的坐标存放在一个数组里，首先我们需要取得该

‘捌’ 泰森多边形法的泰森多边形的建立步骤

建立泰森多边形算法的关键是对离散数据点合理地连成三角网，即构建Delaunay三角网。建立泰森多边形的步骤如下：
1、离散点自动构建三角网，即构建Delaunay三角网。对离散点和形成的三角形编号，记录每个三角形是由哪三个离散点构成的；
2、找出与每个离散点相邻的所有三角形的编号，并记录下来。这只要在已构建的三角网中找出具有一个相同顶点的所有三角形即可；
3、对与每个离散点相邻的三角形按顺时针或逆时针方向排序，以便下一步连接生成泰森多边形。排序的方法可如图所示。设离散点为o。找出以o为顶点的一个三角形，设为A；取三角形A除o以外的另一顶点，设为a，则另一个顶点也可找出，即为f；则下一个三角形必然是以of为边的，即为三角形F；三角形F的另一顶点为e，则下一三角形是以oe为边的；如此重复进行，直到回到oa边；
4、计算每个三角形的外接圆圆心，并记录之；
5、根据每个离散点的相邻三角形，连接这些相邻三角形的外接圆圆心，即得到泰森多边形。对于三角网边缘的泰森多边形，可作垂直平分线与图廓相交，与图廓一起构成泰森多边形。
参考
泰森多边形的建立