Unity-使用耳切法将多边形三角化

一、参考文档：

https://blog.csdn.net/lxbhahaha/article/details/111687476

https://blog.csdn.net/qq_38523017/article/details/108885870

https://github.com/yiwei151/PolygonTriangulation

https://zhuanlan.zhihu.com/p/368191630

https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

二、适用情景

此方法只适用于不带岛洞的简单多边形绘制，但是如果是绘制复杂多边形则会返回null。

下图中只有第一种是简单多边形，其余两种则不是。

三、耳切法解释

算法简介：将一个简单多边分解成三角形集合的方法称之为多边形的三角形化（triangulation of the Polygon）。几何学的知识告诉我们，由n个顶点组成的简单多边形总是可以分解成n -2个三角形。最简单的算法就是耳切法，时间复杂度为 O(n²)。具体算法是找出n个顶点简单多边形的一个耳朵来构造一个三角形，并将这个耳朵的耳尖从简单多边形的顶点数组中剔除，剩下的n-1个顶点形成了一个新的简单多边形。递归执行上一步直到剩下2个顶点为止（因为构成一个三角形最少需要3个顶点），这样就把这样一个简单多边形构造成了一组三角形。

名词解释：

简单多边形：简单多边形是指由一组有序顶点组成的，点V0~点Vn-1。相邻的顶点之间通过边(Vi, Vi-1)连接，并且边（Vn-1,V0）连接起始点。每个顶点被两条边所共享，而边的所有交点都是顶点。

岛洞：简单理解就是多边形的镂空

耳朵：由连续顶点Vi-1,Vi和Vi+1组成的内部不包含其他任意顶点的三角形，其中Vi称为耳尖。

四、算法代码

函数是传入一个多边形顶点的List(按照我的需求多边形顶点给的是逆时针为顺序，并且是一个位于xOz平面上的多边形，所以比较轴我也设置的Y轴)，然后返回对应三角形的索引。

using System;
using System.Collections.Generic;
using UnityEngine;
 
namespace PolygonTool
{
 
    #region 耳切法对简单多边形进行三角形化
 
    /// <summary>
    /// 判断凹点，凸点，耳朵的比较轴
    /// </summary>
    public enum CompareAxle
    {
        X,
        Y,
        Z
    }
 
    /// <summary>
    /// 对多边形处理
    /// </summary>
    public class Triangulation
    {
 
        /// <summary>
        /// 判断凹凸的时候的比对轴
        /// </summary>
        private CompareAxle _compareAxle = CompareAxle.Y;
 
        /// <summary>
        /// 多边形顶点
        /// </summary>
        private List<Vector3> _polygonVertexs = new List<Vector3>();
 
        /// <summary>
        /// 顶点序列
        /// </summary>
        private List<int> _vertexsSequence = new List<int>();
 
        /// <summary>
        /// 节点管理器
        /// </summary>
        private NodeManager _nodeManager = new NodeManager();
 
        /// <summary>
        /// 初始化
        /// </summary>
        /// <param name="polygonVertexs">多边形顶点</param>
        public Triangulation(List<Vector3> polygonVertexs)
        {
            this._polygonVertexs = polygonVertexs;
            _nodeManager.Init(polygonVertexs);
        }
 
        /// <summary>
        /// 设置比较轴
        /// </summary>
        /// <param name="compareAxle"></param>
        public void SetCompareAxle(CompareAxle compareAxle)
        {
            this._compareAxle = compareAxle;
        }
 
        /// <summary>
        /// 获取三角形的顶点序列
        /// </summary>
        public int[] GetTriangles()
        {
            while (_nodeManager.LinkedListLength >= 3)
            {
                SplitResult sr = SplitPolygon();
                //
                if (sr == null)
                {
                    Debug.Log("null");
                    return null;
                }
            }
 
            return _vertexsSequence.ToArray();
        }
 
        /// <summary>
        /// 计算凹顶点，凸顶点，耳朵
        /// </summary>
        private SplitResult SplitPolygon()
        {
            //凹点
            List<Node> _concaveVertexs = new List<Node>();
            //凸点
            List<Node> _raisedVertexs = new List<Node>();
            //耳朵
            List<Node> _polygonEars = new List<Node>();
            //起始节点
            Node currentNode = _nodeManager.FirstNode;
 
            #region 计算凹顶点，凸顶点
 
            for (int i = 0; i < _nodeManager.LinkedListLength; i++)
            {
                Vector3 one = currentNode.vertex - currentNode.lastNode.vertex;
                Vector3 two = currentNode.nextNode.vertex - currentNode.vertex;
                Vector3 crossRes = Vector3.Cross(one, two);
 
                if (_compareAxle == CompareAxle.Y)
                {
                    if (crossRes.y > 0)
                    {
                        _concaveVertexs.Add(currentNode);
                    }
                    else
                    {
                        _raisedVertexs.Add(currentNode);
                    }
                }
 
                if (_compareAxle == CompareAxle.X)
                {
                    if (crossRes.x > 0)
                    {
                        _concaveVertexs.Add(currentNode);
                    }
                    else
                    {
                        _raisedVertexs.Add(currentNode);
                    }
                }
 
                if (_compareAxle == CompareAxle.Z)
                {
                    if (crossRes.z > 0)
                    {
                        _concaveVertexs.Add(currentNode);
                    }
                    else
                    {
                        _raisedVertexs.Add(currentNode);
                    }
                }
 
                _polygonEars.Add(currentNode);
                currentNode = currentNode.nextNode;
            }
 
            for (int i = 0; i < _concaveVertexs.Count; i++)
            {
                _polygonEars.Remove(_concaveVertexs[i]);
            }
            #endregion
 
            #region 计算耳朵
            List<int> needRemoveIdList = new List<int>();
            for (int i = 0; i < _polygonEars.Count; i++)
            {
                Node earNode = _polygonEars[i];
                Node compareNode = earNode.nextNode.nextNode;
 
                while (compareNode != earNode.lastNode)
                {
                    bool isIn = IsIn(compareNode.vertex, earNode.lastNode.vertex, earNode.vertex,
                        earNode.nextNode.vertex);
 
                    if (isIn == true)
                    {
                        if (_polygonEars.Contains(_polygonEars[i]))
                        {
                            needRemoveIdList.Add(_polygonEars[i].id);
                        }
                        break;
                    }
                    compareNode = compareNode.nextNode;
                }
            }
 
            for (int j = 0; j < needRemoveIdList.Count; j++)
            {
                for (int i = 0; i < _polygonEars.Count; i++)
                {
                    if (_polygonEars[i].id == needRemoveIdList[j])
                    {
                        _polygonEars.RemoveAt(i);
                    }
                }
            }
 
            #endregion
 
            #region 打印初始化结果
 
            Debug.Log("凸点");
            for (int i = 0; i < _raisedVertexs.Count; i++)
            {
                Debug.Log(_raisedVertexs[i].id);
            }
 
            Debug.Log("凹点");
            for (int i = 0; i < _concaveVertexs.Count; i++)
            {
                Debug.Log(_concaveVertexs[i].id);
            }
 
            Debug.Log("耳朵");
            for (int i = 0; i < _polygonEars.Count; i++)
            {
                Debug.Log(_polygonEars[i].id);
            }
 
            Debug.Log("-----------------------------------------------");
            #endregion
 
            //耳朵为空说明不是简单多边形 多边形三角化失败
            if (_polygonEars.Count == 0)
            {
                return null;
            }
 
            _vertexsSequence.Add(_polygonEars[0].lastNode.id);
            _vertexsSequence.Add(_polygonEars[0].id);
            _vertexsSequence.Add(_polygonEars[0].nextNode.id);
            _nodeManager.RemoveNode(_polygonEars[0]);
 
 
            return new SplitResult(_raisedVertexs, _concaveVertexs, _polygonEars);
        }
 
        /// <summary>
        /// 判断一点是否在三角形内
        /// </summary>
        /// <param name="p">一点</param>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <param name="c"></param>
        /// <returns></returns>
        public bool IsIn(Vector3 p,Vector3 a,Vector3 b,Vector3 c)
        {
            Vector3 pa = p - a;
            Vector3 pb = p - b;
            Vector3 pc = p - c;
 
            Vector3 t1 = Vector3.Cross(pa, pb);
            Vector3 t2 = Vector3.Cross(pb, pc);
            Vector3 t3 = Vector3.Cross(pc, pa);
 
            bool isIn2 = t1.y >= 0 && t2.y >= 0 && t3.y >= 0 || t1.y <= 0 && t2.y <= 0 && t3.y <= 0;
 
            return isIn2;
        }
 
        /// <summary>
        /// 管理多边形 构成一个双向链表
        /// </summary>
        public class NodeManager
        {
 
            private List<Node> _nodeList = new List<Node>();
 
            public int LinkedListLength
            {
                get { return _nodeList.Count; }
            }
 
            public Node FirstNode
            {
                get { return _nodeList[0]; }
            }
 
            public void Init(List<Vector3> vertexs)
            {
 
                for (int i = 0; i < vertexs.Count; i++)
                {
                    Node node = new Node(i, vertexs[i]);
                    _nodeList.Add(node);
                }
 
                for (int i = 0; i < LinkedListLength; i++)
                {
                    if (i == 0)
                    {
                        _nodeList[i].lastNode = _nodeList[LinkedListLength - 1];
                        _nodeList[i].nextNode = _nodeList[1];
                    }
                    else if (i == LinkedListLength - 1)
                    {
                        _nodeList[i].lastNode = _nodeList[LinkedListLength - 2];
                        _nodeList[i].nextNode = _nodeList[0];
                    }
                    else
                    {
                        _nodeList[i].lastNode = _nodeList[i - 1];
                        _nodeList[i].nextNode = _nodeList[i + 1];
                    }
                }
            }
 
            public void RemoveNode(Node node)
            {
                _nodeList.Remove(node);
                node.lastNode.nextNode = node.nextNode;
                node.nextNode.lastNode = node.lastNode;
            }
        }
 
        public class Node
        {
 
            public int id;
            public Vector3 vertex;
            public Node lastNode;
            public Node nextNode;
 
            public Node(int id, Vector3 vertex)
            {
                this.id = id;
                this.vertex = vertex;
            }
 
            public Node(int id, Vector3 vertex, Node lastNode, Node nextNode)
            {
                this.id = id;
                this.vertex = vertex;
                this.lastNode = lastNode;
                this.nextNode = nextNode;
            }
        }
 
        public class SplitResult
        {
            /// <summary>
            /// 凸顶点
            /// </summary>
            public List<Node> raisedVertexs;
 
            /// <summary>
            /// 凹顶点
            /// </summary>
            public List<Node> concaveVertexs;
 
            /// <summary>
            /// 耳朵
            /// </summary>
            public List<Node> polygonEars;
 
            public SplitResult(List<Node> raisedVertexs, List<Node> concaveVertexs, List<Node> polygonEars)
            {
                this.raisedVertexs = raisedVertexs;
                this.concaveVertexs = concaveVertexs;
                this.polygonEars = polygonEars;
            }
        }
    }
 
    #endregion
}

五、测试代码

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using PolygonTool;
 
public class T : MonoBehaviour
{
    //用物体的坐标来代替点
    public List<Transform> tList;
    //计算得到的三角形序列下标
    private List<int> resultList = new List<int>();
 
    private Triangulation triangulation;
 
    private void Start()
    {
        tList.Reverse();
 
        List<Vector3> posList = new List<Vector3>();
        for (int i = 0; i < tList.Count; i++)
        {
            posList.Add(tList[i].position);
        }
 
        triangulation = new Triangulation(posList);
 
        triangulation.SetCompareAxle(CompareAxle.Y);
 
        int[] a = triangulation.GetTriangles();
 
        if (a != null)
        {
            for (int i = 0; i < a.Length; i++)
            {
                Debug.Log("===:" + a[i]);
                resultList.Add(a[i]);
            }
        }
 
 
        GameObject go = new GameObject();
 
        MeshFilter mf = go.AddComponent<MeshFilter>();
 
        go.AddComponent<MeshRenderer>();
 
        Mesh m = new Mesh();
 
        Vector3[] vertexs = new Vector3[a.Length];
 
        for (int i = 0; i < vertexs.Length; i++)
        {
            Vector3 v = tList[a[i]].position;
            vertexs[i] = v;
        }
 
        m.vertices = vertexs;
        
        int[] tri = new int[a.Length];
 
        for (int i = 0; i < tri.Length; i += 3)
        {
            tri[i] = i;
            tri[i + 1] = i + 2;
            tri[i + 2] = i + 1;
        }
 
        m.triangles = tri;
 
        mf.mesh = m;
    }
 
    private void OnDrawGizmos()
    {
        for (int i = 0; i < tList.Count; i++)
        {
            if (i < tList.Count - 1)
            {
                Gizmos.DrawLine(tList[i].position, tList[i + 1].position);
            }
            else
            {
                Gizmos.DrawLine(tList[i].position, tList[0].position);
            }
 
        }
 
        Gizmos.color = Color.black;
 
        for (int i = 0; i < resultList.Count; i+=3)
        {
            int startIndex = resultList[i];
            int endIndex = resultList[i + 2];
            Gizmos.DrawLine(tList[startIndex].position, tList[endIndex].position);
        }
    }
 
}