获取网格的边界边缘 - 按顺序排列

Question

我有一个三角网格.假设它看起来像一个凹凸不平的表面.我希望能够找到落在网格周围边缘的所有边缘.(忘记内顶点)

我知道我必须找到只连接到一个三角形的边缘,并将所有这些收集在一起,这就是答案.但我想确保这些边的顶点按顺时针顺序排列.

我想这样做是因为我想在网格外部得到一条多边形线.

我希望这很清楚,可以理解.在某种意义上,我试图"去三角化"网格.哈!如果有这样一个词.

Answer 1

边界边缘仅由网格中的单个三角形引用,因此要找到它们,您需要扫描网格中的所有三角形并使用单个引用计数获取边缘.您可以O(N)通过使用哈希表有效地(in )执行此操作.

要将边集转换为有序多边形循环,可以使用遍历方法:

1. 选择任何未访问的边线段[v_start,v_next]并将这些顶点添加到多边形循环中.
2. 找到未访问的边缘段[v_i,v_j],其具有任一v_i = v_next或v_j = v_next和其他顶点(该一个添加不等于v_next),以多边形环.重置v_next为此新添加的顶点,将边标记为已访问并从2继续.
3. 当我们回到时,遍历就完成了v_start.

遍历将给出一个多边形循环,该循环可以具有时钟顺序或逆时针顺序.通过考虑多边形的有符号区域,可以建立一致的排序.如果遍历导致错误的方向,则只需要反转多边形循环顶点的顺序.

Answer 2

俗话说得好 - 让它运转起来 - 然后让它更好地运作.我在上面的例子中注意到它假设edge数组中的所有边实际上都链接在一个漂亮的边框中.在现实世界中可能不是这种情况(正如我从我正在使用的输入文件中发现的那样!)实际上我的一些输入文件实际上有很多多边形,并且都需要检测到边框.我还想确保绕线顺序正确.所以我也解决了这个问题.见下文.(觉得我终于取得了进展!)

    private static List<int> OrganizeEdges(List<int> edges, List<Point> positions)
    {
        var visited = new Dictionary<int, bool>();
        var edgeList = new List<int>();
        var resultList = new List<int>();
        var nextIndex = -1;
        while (resultList.Count < edges.Count)
        {
            if (nextIndex < 0)
            {
                for (int i = 0; i < edges.Count; i += 2)
                {
                    if (!visited.ContainsKey(i))
                    {
                        nextIndex = edges[i];
                        break;
                    }
                }
            }

            for (int i = 0; i < edges.Count; i += 2)
            {
                if (visited.ContainsKey(i))
                    continue;

                int j = i + 1;
                int k = -1;
                if (edges[i] == nextIndex)
                    k = j;
                else if (edges[j] == nextIndex)
                    k = i;

                if (k >= 0)
                {
                    var edge = edges[k];
                    visited[i] = true;
                    edgeList.Add(nextIndex);
                    edgeList.Add(edge);
                    nextIndex = edge;
                    i = 0;
                }
            }

            // calculate winding order - then add to final result.
            var borderPoints = new List<Point>();
            edgeList.ForEach(ei => borderPoints.Add(positions[ei]));
            var winding = CalculateWindingOrder(borderPoints);
            if (winding > 0)
                edgeList.Reverse();

            resultList.AddRange(edgeList);
            edgeList = new List<int>();
            nextIndex = -1;
        }

        return resultList;
    }




    /// <summary>
    /// returns 1 for CW, -1 for CCW, 0 for unknown.
    /// </summary>
    public static int CalculateWindingOrder(IList<Point> points)
    {
        // the sign of the 'area' of the polygon is all we are interested in.
        var area = CalculateSignedArea(points);
        if (area < 0.0)
            return 1;
        else if (area > 0.0)
            return - 1;        
        return 0; // error condition - not even verts to calculate, non-simple poly, etc.
    }

    public static double CalculateSignedArea(IList<Point> points)
    {
        double area = 0.0;
        for (int i = 0; i < points.Count; i++)
        {
            int j = (i + 1) % points.Count;
            area += points[i].X * points[j].Y;
            area -= points[i].Y * points[j].X;
        }
        area /= 2.0f;

        return area;
    }