navmesh 生成网格信息 三角化切分多边形中检测有效分割的算法

Detecting Valid Partitions

Two algorithms are used to determine whether a group of three vertices can form a valid internal triangle. The first algorithm is fast and can quickly cull partitions that lie entirely outside of the polygon. If the partition is inside the polygon a more expensive algorithm is used to make sure it doesn't intersect any existing polygon edges.

两个算法用来实现这一点：

第一个算法简单，并且可以很快地排除掉完全在多边形外边的分割。

第二个算法是用来确保在多边形内部的分割不会与其它已经存在的多边形的边相交。

The Internal Angle Algorithm

如图：AB是要检测的潜在分割

Cast two rays out along the edges connected to vertex A. The interior angle is the angle in the direction of the polygon. If the partition endpoint (vertex B) is within the interior angle, then it is a potential valid partition.

找到点A所连接的两个边，如果分割的另一边B是在内角范围内，则说明是潜在有效的分割。（otential valid partition）

This second example is the same scenario with different vertices. Since the partition endpoint (vertex B) is outside the interior angle, it can't be a valid partition.

下图展现不同的顶点的情况，以B为结束点的分割，就在内角以外，不能被看成是有效分割。

The Edge Intersection Algorithm

This algorithm is much easier to understand. It simply loops through all edges in the polygon and checks to see if the potential partition intersects with any of them. If it does, it isn't a valid partition.

边相交算法就是遍历所有多边形的边以检查是否有潜在的分割线段与这些边相交，如果有，那么就不是一个有效分割。

Only if both algorithms pass is the partition considered valid.

两个算法都通过了 那就是有效分割拉。