Unity中创建多边形并计算面积
2021-02-06 16:14
阅读：412
标签：list -- count end 索引数据 描述 名称 rtl 问题
问题背景：
我这边最近需要实现动态去画多边形（不规则的），类似于高德地图中那种面积测量工具一般。
方案：
”割耳“算法实现三角化平面。
具体实现：
割耳算法类：
/* ******************************************************* * * 文件名称：EarCut * 文件描述：三角化相关算法集合 * * 版本：V1.0.0 * 支持带洞的多边形，需要保证多边形为顺时针，而洞为逆时针顺序 * ***************************************************** */ using System; using System.Collections; using System.Collections.Generic; using UnityEngine; namespace Tx3d.Framework { public class EarCut { #region Sub Class ////// “割耳”点 /// private class Node : IComparable { #region Members & Properties /// /// vertice index in coordinates array /// public int i = -1; /// /// vertex coordinates /// public float x = 0.0f; public float z = 0.0f; /// /// previous and next vertice nodes in a polygon ring /// public Node prev = null; public Node next = null; /// /// z-order curve value /// public int zOrder = -1; /// /// previous and next nodes in z-order /// public Node prevZ = null; public Node nextZ = null; /// /// indicates whether this is a steiner point /// public bool steiner = false; #endregion #region IComparable Implemention public int CompareTo(object obj) { try { Node node = obj as Node; if (this.x > node.x) { return 1; } else { return 0; } } catch (Exception ex) { throw new Exception(ex.Message); } } #endregion } #endregion #region Members & Properties private static float EPSINON = 0.1f; #endregion #region Public Methods /// /// “割耳” /// public static Listint> CutEar(List data, Listint> holeIndices) { var triangles = new Listint>(); bool hasHoles = holeIndices != null && holeIndices.Count > 0; int outerLength = hasHoles ? holeIndices[0] : data.Count; Node outerNode = LinkedList(data, 0, outerLength, true); if (outerNode == null) { return triangles; } if (hasHoles) { outerNode = EliminateHoles(data, holeIndices, outerNode); } float minX = 0.0f; float minZ = 0.0f; float maxX = 0.0f; float maxZ = 0.0f; float size = 0.0f; // if the shape is not too simple, we‘ll use z-order curve hash later; calculate polygon bbox // if (data.Count > 80) if (data.Count > 100) { minX = maxX = data[0].x; minZ = maxZ = data[0].z; for (int i = 1; i ) { float x = data[i].x; float z = data[i].z; if (x x; if (z z; if (x > maxX) maxX = x; if (z > maxZ) maxZ = z; } // minX, minY and size are later used to transform coords into integers for z-order calculation size = Mathf.Max(maxX - minX, maxZ - minZ); } EarCutLinked(outerNode, triangles, minX, minZ, size, 0); return triangles; } #endregion #region Private Methods /// /// 使用多边形顶点按照指定顺序创建一个双向循环链表 /// private static Node LinkedList(List data, int start, int end, bool clockwise) { Node last = null; if (clockwise == (SignedArea(data, start, end) >= 0.0)) { for (int i = start; i ) { last = InsertNode(i, data[i].x, data[i].z, last); } } else { for (int i = end - 1; i >= start; i--) { last = InsertNode(i, data[i].x, data[i].z, last); } } if (last != null && Equals(last, last.next)) { var next = last.next; RemoveNode(last); last = next; } return last; } /// /// “割耳”主循环 /// /// /// main ear slicing loop which triangulates a polygon (given as a linked list) /// private static void EarCutLinked(Node ear, Listint> triangles, float minX, float minZ, float size, int pass) { if (ear == null) return; // interlink polygon nodes in z-order if (pass == 0 && size > 0.0f) { IndexCurve(ear, minX, minZ, size); } Node stop = ear; Node prev = null; Node next = null; // iterate through ears, slicing them one by one while (ear.prev != ear.next) { prev = ear.prev; next = ear.next; if (size > 0.0f ? IsEarHashed(ear, minX, minZ, size) : IsEar(ear)) { // cut off the triangle triangles.Add(prev.i); triangles.Add(ear.i); triangles.Add(next.i); RemoveNode(ear); // skipping the next vertice leads to less sliver triangles ear = next.next; stop = next.next; continue; } ear = next; // if we looped through the whole remaining polygon and can‘t find any more ears if (ear == stop) { // try filtering points and slicing again if (pass == 0) { EarCutLinked(FilterPoints(ear, null), triangles, minX, minZ, size, 1); } else if (pass == 1) // if this didn‘t work, try curing all small self-intersections locally { ear = CureLocalIntersections(ear, triangles); EarCutLinked(ear, triangles, minX, minZ, size, 2); } else if (pass == 2) // as a last resort, try splitting the remaining polygon into two { SplitEarCut(ear, triangles, minX, minZ, size); } return; } } } /// /// 尝试将多边形分割成两个，并分别进行三角化 /// private static void SplitEarCut(Node start, Listint> triangles, float minX, float minZ, float size) { // look for a valid diagonal that divides the polygon into two var a = start; do { var b = a.next.next; while (b != a.prev) { if (a.i != b.i && IsValidDiagonal(a, b)) { // split the polygon in two by the diagonal var c = SplitPolygon(a, b); // filter colinear points around the cuts a = FilterPoints(a, a.next); c = FilterPoints(c, c.next); // run earcut on each half EarCutLinked(a, triangles, minX, minZ, size, 0); EarCutLinked(c, triangles, minX, minZ, size, 0); return; } b = b.next; } a = a.next; } while (a != start); } /// /// link every hole into the outer loop, producing a single-ring polygon without holes /// private static Node EliminateHoles(List data, Listint> holeIndices, Node outerNode) { var queue = new List (); for (int i = 0, len = holeIndices.Count; i ) { var start = holeIndices[i]; var end = i 1 ? holeIndices[i + 1] : data.Count; var list = LinkedList(data, start, end, false); if (list == list.next) { list.steiner = true; } queue.Add(GetLeftmost(list)); } // Sort queue.Sort(); // process holes from left to right for (int i = 0; i ) { var node = EliminateHole(queue[i], outerNode); if (node != null) { outerNode = FilterPoints(node, node.next); } } return outerNode; } /// /// find a bridge between vertices that connects hole with an outer ring and and link it /// private static Node EliminateHole(Node hole, Node outerNode) { outerNode = FindHoleBridge(hole, outerNode); if (outerNode != null) { var b = SplitPolygon(outerNode, hole); return FilterPoints(b, b.next); } return null; } /// /// 遍历多边形所有结点，校正局部自相交情形 /// private static Node CureLocalIntersections(Node start, Listint> triangles) { var p = start; do { var a = p.prev; var b = p.next.next; if (!Equals(a, b) && Intersects(a, p, p.next, b) && LocallyInside(a, b) && LocallyInside(b, a)) { triangles.Add(a.i); triangles.Add(p.i); triangles.Add(b.i); var next = p.next; // remove two nodes involved RemoveNode(p); RemoveNode(next); p = start = b; } p = p.next; } while (p != start); return p; } /// /// 插入一个结点 /// private static Node InsertNode(int i, float x, float z, Node last) { var p = new Node { i = i, x = x, z = z }; if (last == null) { p.prev = p; p.next = p; } else { p.next = last.next; p.prev = last; last.next.prev = p; last.next = p; } return p; } /// /// 移除一个结点 /// private static void RemoveNode(Node p) { p.next.prev = p.prev; p.prev.next = p.next; if (p.prevZ != null) { p.prevZ.nextZ = p.nextZ; } if (p.nextZ != null) { p.nextZ.prevZ = p.prevZ; } } /// /// 判断两个结点是否相等 /// /// true相等，false不相等 private static bool Equals(Node p1, Node p2) { if (p1 == null || p2 == null) { Debug.Log("null"); } return p1.x == p2.x && p1.z == p2.z; } /// /// 判断是否是“耳朵” /// /// /// private static bool IsEar(Node ear) { var a = ear.prev; var b = ear; var c = ear.next; if (Area(a, b, c) >= 0.0f) { // reflex, can‘t be an ear return false; } // now make sure we don‘t have other points inside the potential ear var p = ear.next.next; while (p != ear.prev) { if (PointInTriangle(a, b, c, p) && (Area(p.prev, p, p.next) >= 0.0f)) { return false; } p = p.next; } return true; } /// /// 判断是否是“耳朵”散列？ /// private static bool IsEarHashed(Node ear, float minX, float minZ, float size) { var a = ear.prev; var b = ear; var c = ear.next; if (Area(a, b, c) >= 0.0f) { // reflex, can‘t be an ear return false; } // triangle bbox; min & max are calculated like this for speed var minTX = a.x b.x : c.x); var minTZ = a.z b.z : c.z); var maxTX = a.x > b.x ? (a.x > c.x ? a.x : c.x) : (b.x > c.x ? b.x : c.x); var maxTZ = a.z > b.z ? (a.z > c.z ? a.z : c.z) : (b.z > c.z ? b.z : c.z); // z-order range for the current triangle bbox; int minZOrder = ZOrder(minTX, minTZ, minX, minZ, size); int maxZOrder = ZOrder(maxTX, maxTZ, minX, minZ, size); // first look for points inside the triangle in increasing z-order var p = ear.nextZ; while (p != null && p.zOrder maxZOrder) { if (p != ear.prev && p != ear.next && PointInTriangle(a, b, c, p) && Area(p.prev, p, p.next) >= 0.0f) { return false; } p = p.nextZ; } // then look for points in decreasing z-order p = ear.prevZ; while (p != null && p.zOrder >= minZOrder) { if (p != ear.prev && p != ear.next && PointInTriangle(a, b, c, p) && Area(p.prev, p, p.next) >= 0.0f) { return false; } p = p.prevZ; } return true; } /// /// 通过对角线分割多边形 /// /// /// link two polygon vertices with a bridge; if the vertices belong to the same ring, it splits polygon into two; /// if one belongs to the outer ring and another to a hole, it merges it into a single ring /// private static Node SplitPolygon(Node a, Node b) { var a2 = new Node { i = a.i, x = a.x, z = a.z }; var b2 = new Node { i = b.i, x = b.x, z = b.z }; var an = a.next; var bp = b.prev; a.next = b; b.prev = a; a2.next = an; an.prev = a2; b2.next = a2; a2.prev = b2; bp.next = b2; b2.prev = bp; return b2; } /// /// 对结点进行排序 /// /// /// Simon Tatham‘s linked list merge sort algorithm /// private static Node SortLinked(Node list) { int numMerges = 0; int pSize = 0; int qSize = 0; int inSize = 1; Node p = null; Node q = null; Node e = null; Node tail = null; do { p = list; list = null; tail = null; numMerges = 0; while (p != null) { numMerges++; q = p; pSize = 0; for (int i = 0; i ) { pSize++; q = q.nextZ; if (q == null) break; } qSize = inSize; while (pSize > 0 || (qSize > 0 && q != null)) { if (pSize == 0) { e = q; q = q.nextZ; qSize--; } else if (qSize == 0 || q == null) { e = p; p = p.nextZ; pSize--; } else if (p.zOrder q.zOrder) { e = p; p = p.nextZ; pSize--; } else { e = q; q = q.nextZ; qSize--; } if (tail != null) { tail.nextZ = e; } else { list = e; } e.prevZ = tail; tail = e; } p = q; } tail.nextZ = null; inSize *= 2; } while (numMerges > 1); return list; } /// /// 相邻多边形节点次序（interlink polygon nodes in z-order） /// private static void IndexCurve(Node start, float minX, float minZ, float size) { var p = start; do { if (p.zOrder == -1) { p.zOrder = ZOrder(p.x, p.z, minX, minZ, size); } p.prevZ = p.prev; p.nextZ = p.next; p = p.next; } while (p != start); p.prevZ.nextZ = null; p.prevZ = null; SortLinked(p); } /// /// 判断两条线段是否相交 /// /// /// private static bool Intersects(Node p1, Node q1, Node p2, Node q2) { if ((Equals(p1, q1) && Equals(p2, q2)) || (Equals(p1, q2) && Equals(p2, q1))) { return true; } return (Area(p1, q1, p2) > 0.0 != Area(p1, q1, q2) > 0.0) && (Area(p2, q2, p1) > 0.0 != Area(p2, q2, q1) > 0.0); } /// /// 检测多边形的对角线是否与多边形的边相交 /// private static bool IntersectsPolygon(Node a, Node b) { var p = a; do { if (p.i == a.i && p.next.i != a.i && p.i != b.i && p.next.i != b.i && Intersects(p, p.next, a, b)) { return true; } p = p.next; } while (p != a); return false; } /// /// 查找多边形最坐标结点 /// private static Node GetLeftmost(Node start) { var p = start; var leftmost = start; do { if (p.x leftmost.x) { leftmost = p; } p = p.next; } while (p != start); return leftmost; } /// /// 查找多边形内部洞与外边的连接点 /// /// David Eberly‘s algorithm private static Node FindHoleBridge(Node hole, Node outerNode) { var p = outerNode; var hx = hole.x; var hz = hole.z; var qx = float.NegativeInfinity; Node m = null; // find a segment intersected by a ray from the hole‘s leftmost point to the left; // segment‘s endpoint with lesser x will be potential connection point do { if ((hz = p.next.z) || (hz = p.z)) { var x = p.x + (hz - p.z) * (p.next.x - p.x) / (p.next.z - p.z); if (x qx) { qx = x; if (x == hx) { if (hz == p.z) { return p; } if (hz == p.next.z) { return p.next; } } m = p.x p : p.next; } } } while (p != outerNode); if (m == null) { return null; } // hole touches outer segment; pick lower endpoint if (hx == qx) { return m.prev; } // look for points inside the triangle of hole point, segment intersection and endpoint; // if there are no points found, we have a valid connection; // otherwise choose the point of the minimum angle with the ray as connection point var stop = m; var mx = m.x; var mz = m.z; var tanMin = float.PositiveInfinity; p = m.next; while (p != stop) { if (hx >= p.x && p.x >= mx && PointInTriangle(hz qx : hx, hz, p.x, p.z)) { var tan = Mathf.Abs(hz - p.z) / (hx - p.x); // tangential if ((tan m.x)) && LocallyInside(p, hole)) { m = p; tanMin = tan; } } p = p.next; } return m; } /// /// 检测多边形的对角线是否在多边形内部 /// private static bool LocallyInside(Node a, Node b) { return Area(a.prev, a, a.next) != 0.0f ? Area(a, b, a.next) >= 0.0f && Area(a, a.prev, b) >= 0.0f : Area(a, b, a.prev) >= 0.0f && Area(a, a.next, b) 0.0f; } /// /// 检测多边形对角线中心点是否在多边形内部 /// private static bool MiddleInside(Node a, Node b) { var p = a; var inside = false; var px = (a.x + b.x) * 0.5f; var pz = (a.z + b.z) * 0.5f; do { if (((p.z > pz) != (p.next.z > pz)) && (px p.x))) { inside = !inside; } p = p.next; } while (p != a); return inside; } /// /// 判断多边形中的两点是否构成有效对角线 /// private static bool IsValidDiagonal(Node a, Node b) { return a.next.i != b.i && a.prev.i != b.i && !IntersectsPolygon(a, b) && LocallyInside(a, b) && LocallyInside(b, a) && MiddleInside(a, b); } /// /// 过滤掉共线或重复的结点 /// private static Node FilterPoints(Node start, Node end) { if (start == null) return start; if (end == null) end = start; var p = start; var again = false; do { again = false; if (!p.steiner && (Equals(p, p.next) || Area(p.prev, p, p.next) == 0.0f)) { var prev = p.prev; RemoveNode(p); p = end = prev; if (p == p.next) { return null; } again = true; } else { p = p.next; } } while (again || p != end); return end; } /// /// 计算给定坐标点和外包大小的结点z-order（z-order of a point given coords and size of the data bounding box） /// private static int ZOrder(float x, float z, float minX, float minZ, float size) { // coords are transformed into non-negative 15-bit integer range int _x = (int)(32767 * (x - minX) / size); int _z = (int)(32767 * (z - minZ) / size); _x = (_x | (_x 8)) & 0x00FF00FF; _x = (_x | (_x 4)) & 0x0F0F0F0F; _x = (_x | (_x 2)) & 0x33333333; _x = (_x | (_x 1)) & 0x55555555; _z = (_z | (_z 8)) & 0x00FF00FF; _z = (_z | (_z 4)) & 0x0F0F0F0F; _z = (_z | (_z 2)) & 0x33333333; _z = (_z | (_z 1)) & 0x55555555; return _x | (_z 1); } /// /// 判断一个点是否在三角形内 /// /// true在，false不在 private static bool PointInTriangle(Node a, Node b, Node c, Node d) { var SABC = Mathf.Abs(Area(a, b, c)) * 0.5f; var SADB = Mathf.Abs(Area(a, d, b)) * 0.5f; var SBDC = Mathf.Abs(Area(b, d, c)) * 0.5f; var SADC = Mathf.Abs(Area(a, d, c)) * 0.5f; var S = SABC - (SADB + SBDC + SADC); if (S > -EPSINON && S EPSINON) { return true; } return false; } /// /// 判断一个点是否在三角形内 /// /// true在，false不在 private static bool PointInTriangle(float x0, float y0, float x1, float y1, float x2, float y2, float x3, float y3) { var SABC = Mathf.Abs(Area(x0, y0, x1, y1, x2, y2)) * 0.5f; var SADB = Mathf.Abs(Area(x0, y0, x3, y3, x1, y1)) * 0.5f; var SBDC = Mathf.Abs(Area(x1, y1, x3, y3, x2, y2)) * 0.5f; var SADC = Mathf.Abs(Area(x0, y0, x3, y3, x2, y2)) * 0.5f; var S = SABC - (SADB + SBDC + SADC); if (S > -EPSINON && S EPSINON) { return true; } return false; } /// /// 计算三角形有向面积（三角形面积的2倍） /// /// /// 结果大于0.0，p、q、r按逆时针排列 /// 结果等于0.0，p、q、r在一条直线上 /// 结果小于0.0，p、q、r按顺时针排列 /// /// 三角形有向面积 private static float Area(Node p, Node q, Node r) { return Area(p.x, p.z, q.x, q.z, r.x, r.z); } /// /// 计算三角形有向面积（三角形面积2倍） /// /// 三角形有向面积 private static float Area(float x0, float y0, float x1, float y1, float x2, float y2) { return x0 * y1 + x2 * y0 + x1 * y2 - x2 * y1 - x0 * y2 - x1 * y0; } /// /// 计算多边形有向面积（多边形面积的2倍） /// /// 顶点数据 /// 起始顶点索引 /// 结束顶点索引 /// /// 结果大于等于0.0，多边形顶点按顺时针排序 /// 结果小于0.0，多边形顶点按逆时针排序 /// /// 多边形有向面积 private static float SignedArea(List data,
评论
亲，登录后才可以留言！