最近读到一段将多边形分割成三角形的程序，设计的很精巧，在这里做一下总结。
程序原作者是John W. Ratcliff，原始程序网址是：
https://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml
子程序一 利用 叉乘 判断一个点是否在任意三角形内
注意这里用的是叉乘的方法判断，还有使用面积、角度等的判断方法，感兴趣可以直接搜索。
这里P为需要判断的点，ABC为组成三角形的三个点。
/*
InsideTriangle decides if a point P is Inside of the triangle
defined by A, B, C.
*/
bool Triangulate::InsideTriangle(float Ax, float Ay,
float Bx, float By,
float Cx, float Cy,
float Px, float Py)
//程序的功能是判断一个点是否在某个三角形内，p为需要判断的点， ABC为需要判断的三角形的三个顶点
//用叉乘的方法判断一个点是否在三角形内
//返回true: 在三角形ABC之内
//返回false: 在三角形ABC之内
{
float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
float cCROSSap, bCROSScp, aCROSSbp;
ax = Cx - Bx; ay = Cy - By;
bx = Ax - Cx; by = Ay - Cy;
cx = Bx - Ax; cy = By - Ay;
apx = Px - Ax; apy = Py - Ay;
bpx = Px - Bx; bpy = Py - By;
cpx = Px - Cx; cpy = Py - Cy;
aCROSSbp = ax * bpy - ay * bpx;
cCROSSap = cx * apy - cy * apx;
bCROSScp = bx * cpy - by * cpx;
return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
};
这里还有一个扩展，即可以判断一个点是否在一个多边形内。方法和上面的这个程序差不多。
子程序二 判断是否有一点在三角形内，或者按照某个顺序组成的三角形为顺时针
bool Triangulate::Snip(const Vector2dVector& contour, int u, int v, int w, int n, int* V)
//如果没有点在uvw所组成的三角形之内->return true
//如果存在一个点在uvw所组成的三角形内->return false
{//判断除u、v和w之外的点是否有在这三个点之外的点，如果有则返回
int p;
float Ax, Ay, Bx, By, Cx, Cy, Px, Py;
Ax = contour[V[u]].GetX();
Ay = contour[V[u]].GetY();
Bx = contour[V[v]].GetX();
By = contour[V[v]].GetY();
Cx = contour[V[w]].GetX();
Cy = contour[V[w]].GetY();
//若叉乘小于0说明是顺时针的，这时三个点组成的三条连线会有存在于整个图形之外的情况
//如果叉乘大于0说明是逆时针的组合，所有点都在图形之内，这个时候是可以的
if (EPSILON > (((Bx - Ax) * (Cy - Ay)) - ((By - Ay) * (Cx - Ax)))) return false;
for (p = 0; p < n; p++)
{
if ((p == u) || (p == v) || (p == w)) continue;
Px = contour[V[p]].GetX();
Py = contour[V[p]].GetY();
if (InsideTriangle(Ax, Ay, Bx, By, Cx, Cy, Px, Py)) return false;//若当前的p点在三角形uvw之内，则返回false，
}
//若所有的点都不在当前三角形uvw之内，则返回true
return true;//都不在三角形之内，才返回true
}
子程序三 核心网格化程序
这里应注意，输入到Process的第一个参数是图形所有端点组成的数组，这个数组的顺序应是从某一点开始按图形边界逆时针排列或顺时针排列，而不是随机取点。程序中利用叉乘判断这些点是顺时针还是逆时针，如果顺时针则倒序将所有点存入数组V，如果是逆时针则直接存入数组V。
数组V中存储的是所有还未作为起始点参与组成三角形的点，如果一个点成功参与则将该点从数组V中删除，并且将参与组成的三个点存入数组result。理论上nv个点组成的图形可以划分成nv-2个三角形网格，所以最后数组V中会剩余两个未作过起始点的点，所以一共循环判断了nv-2次。
因为数组V中的点是逆时针顺序，所以判断从某个起始点开始的三个点是否可以组成三角形时也是判断这三个点是否可以逆时针地组成一个不包含任何点的三角形（调用Snip函数进行判断，只有既满足逆时针顺序并且没有任何其他点在所组成的三角形内时才返回true）。
另外，第一轮首先判断的是从某一点开始，相邻的三个点是否可以组成逆时针三角形，将所有可以组成的顶点从V中刨除。第二轮在剩下的所有点V中逆时针逐个判断三个点是否可以组成三角形....一直按照这个逻辑进行直到仅剩下两个点为止。uvw是V中相邻点的序号，abc是这三个序号中存储的位置值。
bool Triangulate::Process(const Vector2dVector& contour, Vector2dVector& result)
{
/* allocate and initialize list of Vertices in polygon */
int n = contour.size();
if (n < 3) return false;
int* V = new int[n];
/* we want a counter-clockwise polygon in V */
//用下面的程序可以判断出顺时针还是逆时针
if (0.0f < Area(contour))
for (int v = 0; v < n; v++)
V[v] = v;//则按顺序取点时是逆时针的
else
for (int v = 0; v < n; v++)
V[v] = (n - 1) - v;//则按照相反顺序取点时时逆时针的
int nv = n;
/* remove nv-2 Vertices, creating 1 triangle every time */
int count = 2 * nv; /* error detection */
for (int m = 0, v = nv - 1; nv > 2; )
{
/* if we loop, it is probably a non-simple polygon */
if (0 >= (count--))
{
//** Triangulate: ERROR - probable bad polygon!
return false;
}
/* three consecutive vertices in current polygon, <u,v,w> */
int u = v;
if (nv <= u)
u = 0; /* previous */
v = u + 1;
if (nv <= v)
v = 0; /* new v */
int w = v + 1;
if (nv <= w)
w = 0; /* next */
if (Snip(contour, u, v, w, nv, V))//如果没有点在uwv所组成的三角形之内
{
int a, b, c, s, t;
/* true names of the vertices */
a = V[u];
b = V[v];
c = V[w];
/* output Triangle */
result.push_back(contour[a]);
result.push_back(contour[b]);
result.push_back(contour[c]);
m++;
/* remove v from remaining polygon */
for (s = v, t = v + 1; t < nv; s++, t++)
V[s] = V[t];
nv--;
/* resest error detection counter */
count = 2 * nv;
}
}
delete V;
return true;
}
测试程序
下面这个主函数是对上面算法的一个实际测试，具体查找过程按照下图的顺序进行。
Triangulate.png
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "TriangulateMesh.h"
void main(int argc, char** argv)
{
// Small test application demonstrating the usage of the triangulate
// class.
// Create a pretty complicated little contour by pushing them onto
// an stl vector.
Vector2dVector a;
a.push_back(Vector2d(0, 6));//0
a.push_back(Vector2d(0, 0));//1
a.push_back(Vector2d(3, 0));//2
a.push_back(Vector2d(4, 1));//3
a.push_back(Vector2d(6, 1));//4
a.push_back(Vector2d(8, 0));//5
a.push_back(Vector2d(12, 0));//6
a.push_back(Vector2d(13, 2));//7
a.push_back(Vector2d(8, 2));//8
a.push_back(Vector2d(8, 4));//9
a.push_back(Vector2d(11, 4));//10
a.push_back(Vector2d(11, 6));//11
a.push_back(Vector2d(6, 6));//12
a.push_back(Vector2d(4, 3));//13
a.push_back(Vector2d(2, 6));//14
// allocate an STL vector to hold the answer.
Vector2dVector result;
// Invoke the triangulator to triangulate this polygon.
Triangulate::Process(a, result);
// print out the results.
int tcount = result.size() / 3;
for (int i = 0; i < tcount; i++)
{
const Vector2d& p1 = result[i * 3 + 0];
const Vector2d& p2 = result[i * 3 + 1];
const Vector2d& p3 = result[i * 3 + 2];
printf("Triangle %d => (%0.0f,%0.0f) (%0.0f,%0.0f) (%0.0f,%0.0f)\n", i + 1, p1.GetX(), p1.GetY(), p2.GetX(), p2.GetY(), p3.GetX(), p3.GetY());
}
}
网友评论