时间戳

首页 > 解决方案 > 使用大量顶点从多边形创建图形需要很长时间

c# - 使用大量顶点从多边形创建图形需要很长时间

问题描述

我正在尝试用多面体构建一个图形。当我没有大量顶点但使用 1M 时，代码工作正常。有什么性能改进建议吗？

public Graph(List<Polygon> PolygonsSet)
    {
        edges = new List<Edge>();
        graphID = Guid.NewGuid();
        //Setting up Graph instance by adding vertices, edges and polygons
        foreach (Polygon Polygon in PolygonsSet)
        {
            List<Vertex> vertices = Polygon.vertices;

            // Clear pre-existing edges in the case this is an updating process.
            Polygon.edges.Clear();

            //If there is only one polygon, treat it as boundary
            if (PolygonsSet.Count() == 1)
            {
                Polygon.isBoundary = true;
            }

            //If first and last point of vertices list are the same, remove last.
            if (vertices.First().Equals(vertices.Last()) && vertices.Count() > 1)
            {
                vertices = vertices.Take(vertices.Count() - 1).ToList();
            }


            //For each point, creates vertex and associated edge and adds them
            //to the polygons Dictionary
            int vertexCount = vertices.Count();

            // If valid polygon
            if (vertexCount >= 3)
            {
                int newId = GetNextId();
                for (var j = 0; j < vertexCount; j++)
                {
                    int next_index = (j + 1) % vertexCount;
                    Vertex vertex = vertices[j];
                    Vertex next_vertex = vertices[next_index];
                    Edge edge = new Edge(vertex, next_vertex);

                    //If is a valid polygon, add id to vertex and
                    //edge to vertices dictionary
                    if (vertexCount > 2)
                    {
                        vertex.polygonId = newId;
                        next_vertex.polygonId = newId;
                        Polygon gPol = new Polygon();
                        if (polygons.TryGetValue(newId, out gPol))
                        {
                            gPol.edges.Add(edge);
                        }
                        else
                        {
                            Polygon.edges.Add(edge);
                            Polygon.id = newId;
                            polygons.Add(newId, Polygon);
                        }
                    }
                    AddEdge(edge);
                }
            }

        }
    }

AddEdge 方法是；

public void AddEdge(Edge edge)
    {
        List<Edge> startEdgesList = new List<Edge>();
        List<Edge> endEdgesList = new List<Edge>();
        if (graph.TryGetValue(edge.StartVertex, out startEdgesList))
        {
            if (!startEdgesList.Contains(edge)) { startEdgesList.Add(edge); }
        }
        else
        {
            graph.Add(edge.StartVertex, new List<Edge>() { edge });
        }

        if (graph.TryGetValue(edge.EndVertex, out endEdgesList))
        {
            if (!endEdgesList.Contains(edge)) { endEdgesList.Add(edge); }
        }
        else
        {
            graph.Add(edge.EndVertex, new List<Edge>() { edge });
        }

        if (!edges.Contains(edge)) { edges.Add(edge); }
    }

代码工作正常，我唯一关心的是性能。

我试图简化多边形，甚至使用凸包来减少工作量，但在某些情况下，我需要按原样使用多边形。

所以任何帮助将不胜感激......

标签： c#performanceasp.net-coregraph

解决方案

在以 开头的代码行中if (vertexCount > 2)，您测试顶点计数，但自上次测试以来计数没有改变if (vertexCount >= 3)。放下这一秒if。然后用 . 创建一个新的多边形Polygon gPol = new Polygon();。该多边形随后立即被 in 中的out参数替换polygons.TryGetValue(newId, out gPol)。要么TryGetValue产生true，然后gPol成为集合中的多边形，要么TryGetValue产生false并gPol成为null。不分配gPol

Polygon gPol;
if (polygons.TryGetValue(newId, out gPol)) ...

或者使用 C# 7.0 语法

if (polygons.TryGetValue(newId, out Polygon gPol)) ...

在这种else情况下，您应该创建一个新多边形（因为gPolis null）。但是，您可以简化此代码，因为在两种情况下都添加了边缘：

if (!polygons.TryGetValue(newId, out Polygon gPol)) {
    gPol = new Polygon { id = newId };
    polygons.Add(newId, gPol);
}
gPol.edges.Add(edge);

您似乎也Polygon与gPol.

由于newId在 for 循环之前创建，您可以将代码查找或创建多边形移出循环

int vertexCount = vertices.Count();
if (vertexCount >= 3)
{
    int newId = GetNextId();
    if (!polygons.TryGetValue(newId, out Polygon gPol)) {
        gPol = new Polygon { id = newId };
        polygons.Add(newId, gPol);
    }
    for (var j = 0; j < vertexCount; j++)
    {
        int next_index = (j + 1) % vertexCount;
        Vertex vertex = vertices[j];
        Vertex next_vertex = vertices[next_index];
        Edge edge = new Edge(vertex, next_vertex);

        vertex.polygonId = newId;
        next_vertex.polygonId = newId;
        gPol.edges.Add(edge);
        AddEdge(edge);
    }
}

在AddEdge您重复覆盖刚刚创建的列表的相同错误TryGetValue。

推荐阅读