SandTraySystem_BaoLiJiaJiuDdian/Assets/Scripts/Tool/SetArea/Polygon.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

[RequireComponent(typeof(MeshFilter))]
[RequireComponent(typeof(MeshRenderer))]
[RequireComponent(typeof(MeshCollider))]
public class Polygon : MonoBehaviour
{
    private MeshCollider meshCollider;
    private Material material;
    private Mesh mesh;    
    void Awake()
    {
        material = GetComponent<MeshRenderer>().material;
        mesh = GetComponent<MeshFilter>().mesh;
        meshCollider = GetComponent<MeshCollider>();      
    }

    public void SetVertices(Vector3[] vertices)
    {
        mesh.Clear();
        mesh.vertices = vertices;
        //mesh.triangles = GetTriangles(vertices);
        List<int> indexes = new List<int>();
        int index = 0;
        for (int i=0;i< vertices.Length;i++)
        {
            indexes.Add(index++);
        }       
        mesh.triangles=WidelyTriangleIndex(vertices.ToList(), indexes).ToArray();
        // 实时调整碰撞器形状，以便可以正确响应碰撞
        meshCollider.sharedMesh = mesh;       
    }

    public Color Color
    {
        get { return material.color; }
        set { material.color = value; }
    }
    /// <summary>
    /// 计算多边形重心
    /// </summary>
    /// <param name="mPoints"></param>
    /// <returns></returns>
    public Vector3 getCenterOfGravityPoint(List<Vector3> mPoints)
    {
        float area = 0.0f;//多边形面积  
        float Gx = 0.0f, Gz = 0.0f;// 重心的x、y  
        for (int i = 1; i <= mPoints.Count; i++)
        {
            float iLat = mPoints[(i % mPoints.Count())].x;
            float iLng = mPoints[(i % mPoints.Count())].z;
            float nextLat = mPoints[(i - 1)].x;
            float nextLng = mPoints[(i - 1)].z;
            float temp = (iLat * nextLng - iLng * nextLat) / 2.0f;
            area += temp;
            Gx += temp * (iLat + nextLat) / 3.0f;
            Gz += temp * (iLng + nextLng) / 3.0f;
        }
        Gx = Gx / area;
        Gz = Gz / area;
        return new Vector3(Gx, mPoints[0].y, Gz);
    }

    //FIXME: 这个算法有缺陷，能较好地处理凸多边形，但在处理复杂多边形(比如重复点，自交，带洞，反向折叠)时会有问题
    private int[] GetTriangles(Vector3[] vertices)
    {
        var count = vertices.Length - 2;
        var triangles = new int[count * 3];
        var front = 0;
        var back = vertices.Length - 1;

        for (var i = 1; i <= count; i++)
        {
            if (i % 2 == 1)
            {
                triangles[i * 3 - 3] = front++;
                triangles[i * 3 - 2] = front;
                triangles[i * 3 - 1] = back;
            }
            else
            {
                triangles[i * 3 - 1] = back--;
                triangles[i * 3 - 2] = back;
                triangles[i * 3 - 3] = front;
            }
        }

        return triangles;
    }
    /// <summary>
    /// 三角剖分
    /// 1.寻找一个可划分顶点
    /// 2.分割出新的多边形和三角形
    /// 3.新多边形若为凸多边形，结束；否则继续剖分
    /// 
    /// 寻找可划分顶点
    /// 1.顶点是否为凸顶点：顶点在剩余顶点组成的图形外
    /// 2.新的多边形没有顶点在分割的三角形内
    /// </summary>
    /// <param name="verts">顺时针排列的顶点列表</param>
    /// <param name="indexes">顶点索引列表</param>
    /// <returns>三角形列表</returns>
    public  List<int> WidelyTriangleIndex(List<Vector3> verts, List<int> indexes)
    {
        int len = verts.Count;
        if (len <= 3) return ConvexTriangleIndex(verts, indexes);

        int searchIndex = 0;
        List<int> covexIndex = new List<int>();
        bool isCovexPolygon = true;//判断多边形是否是凸多边形

        for (searchIndex = 0; searchIndex < len; searchIndex++)
        {
            List<Vector3> polygon = new List<Vector3>(verts.ToArray());
            polygon.RemoveAt(searchIndex);
            if (IsPointInsidePolygon(verts[searchIndex], polygon))
            {
                isCovexPolygon = false;
                break;
            }
            else
            {
                covexIndex.Add(searchIndex);
            }
        }

        if (isCovexPolygon) return ConvexTriangleIndex(verts, indexes);

        //查找可划分顶点
        int canFragementIndex = -1;//可划分顶点索引
        for (int i = 0; i < len; i++)
        {
            if (i > searchIndex)
            {
                List<Vector3> polygon = new List<Vector3>(verts.ToArray());
                polygon.RemoveAt(i);
                if (!IsPointInsidePolygon(verts[i], polygon) && IsFragementIndex(i, verts))
                {
                    canFragementIndex = i;
                    break;
                }
            }
            else
            {
                if (covexIndex.IndexOf(i) != -1 && IsFragementIndex(i, verts))
                {
                    canFragementIndex = i;
                    break;
                }
            }
        }

        if (canFragementIndex < 0)
        {
            Debug.LogError("数据有误找不到可划分顶点");
            return new List<int>();
        }

        //用可划分顶点将凹多边形划分为一个三角形和一个多边形
        List<int> tTriangles = new List<int>();
        int next = (canFragementIndex == len - 1) ? 0 : canFragementIndex + 1;
        int prev = (canFragementIndex == 0) ? len - 1 : canFragementIndex - 1;
        tTriangles.Add(indexes[prev]);
        tTriangles.Add(indexes[canFragementIndex]);
        tTriangles.Add(indexes[next]);
        //剔除可划分顶点及索引
        verts.RemoveAt(canFragementIndex);
        indexes.RemoveAt(canFragementIndex);

        //递归划分
        List<int> leaveTriangles = WidelyTriangleIndex(verts, indexes);
        tTriangles.AddRange(leaveTriangles);

        return tTriangles;
    }
    /// <summary>
    /// 凸多边形，顺时针序列，以第1个点来剖分三角形，如下：
    /// 0---1
    /// |   |
    /// 3---2  -->  (0, 1, 2)、(0, 2, 3)
    /// </summary>
    /// <param name="verts">顺时针排列的顶点列表</param>
    /// <param name="indexes">顶点索引列表</param>
    /// <returns>三角形列表</returns>
    public  List<int> ConvexTriangleIndex(List<Vector3> verts, List<int> indexes)
    {
        int len = verts.Count;
        //若是闭环去除最后一点
        if (len > 1 && Vector3Equal(verts[0], verts[len - 1]))
        {
            len--;
        }
        int triangleNum = len - 2;
        List<int> triangles = new List<int>(triangleNum * 3);
        for (int i = 0; i < triangleNum; i++)
        {
            triangles.Add(indexes[0]);
            triangles.Add(indexes[i + 1]);
            triangles.Add(indexes[i + 2]);
        }
        return triangles;
    }
    /// <summary>
    /// 点与多边形的位置关系
    /// </summary>
    /// <param name="point">判定点</param>
    /// <param name="polygonVerts">剩余顶点按顺序排列的多边形</param>
    /// <returns>true:点在多边形之内，false:相反</returns>
    private  bool IsPointInsidePolygon(Vector3 point, List<Vector3> polygonVerts)
    {
        int len = polygonVerts.Count;
        Ray ray = new Ray(point, new Vector3(0, 0, 1)); //y方向射线
        int interNum = 0;

        for (int i = 1; i < len; i++)
        {
            if (IsDetectIntersect(ray, polygonVerts[i - 1], polygonVerts[i]))
            {
                interNum++;
            }
        }

        //不是闭环
        if (!Vector3Equal(polygonVerts[0], polygonVerts[len - 1]))
        {
            if (IsDetectIntersect(ray, polygonVerts[len - 1], polygonVerts[0]))
            {
                interNum++;
            }
        }
        int remainder = interNum % 2;
        return remainder == 1;
    }
    /// <summary>
    /// 是否是可划分顶点:新的多边形没有顶点在分割的三角形内
    /// </summary>
    private  bool IsFragementIndex(int index, List<Vector3> verts)
    {
        int len = verts.Count;
        List<Vector3> triangleVert = new List<Vector3>();
        int next = (index == len - 1) ? 0 : index + 1;
        int prev = (index == 0) ? len - 1 : index - 1;
        triangleVert.Add(verts[prev]);
        triangleVert.Add(verts[index]);
        triangleVert.Add(verts[next]);
        for (int i = 0; i < len; i++)
        {
            if (i != index && i != prev && i != next)
            {
                if (IsPointInsidePolygon(verts[i], triangleVert))
                {
                    return false;
                }
            }
        }
        return true;
    }
    /// <summary>
    /// 射线与线段相交性判断
    /// </summary>
    /// <param name="ray">射线</param>
    /// <param name="p1">线段头</param>
    /// <param name="p2">线段尾</param>
    /// <returns></returns>
    private  bool IsDetectIntersect(Ray ray, Vector3 p1, Vector3 p2)
    {
        float pointZ;//交点z坐标，x固定值
        if (floatEqual(p1.x, p2.x))
        {
            return false;
        }
        else if (floatEqual(p1.z, p2.z))
        {
            pointZ = p1.z;
        }
        else
        {
            //直线两点式方程：(y-y2)/(y1-y2) = (x-x2)/(x1-x2)
            float a = p1.x - p2.x;
            float b = p1.z - p2.z;
            float c = p2.z / b - p2.x / a;

            pointZ = b / a * ray.origin.x + b * c;
        }

        if (floatLess(pointZ, ray.origin.z))
        {
            //交点y小于射线起点y
            return false;
        }
        else
        {
            Vector3 leftP = floatLess(p1.x, p2.x) ? p1 : p2;//左端点
            Vector3 rightP = floatLess(p1.x, p2.x) ? p2 : p1;//右端点
            //交点x位于线段两个端点x之外，相交与线段某个端点时，仅将射线L与左侧多边形一边的端点记为焦点(即就是：只将右端点记为交点)
            if (!floatGreat(ray.origin.x, leftP.x) || floatGreat(ray.origin.x, rightP.x))
            {
                return false;
            }
        }

        return true;
    }
    const double epsilon = 1e-7;

     bool floatLess(float value, float other)
    {
        return (other - value) > epsilon;
    }

     bool floatGreat(float value, float other)
    {
        return (value - other) > epsilon;
    }

     bool floatEqual(float value, float other)
    {
        return Mathf.Abs(value - other) < epsilon;
    }

     bool Vector3Equal(Vector3 a, Vector3 b)
    {
        return floatEqual(a.x, b.x) && floatEqual(a.y, b.y) && floatEqual(a.z, b.z);
    }
}