时间戳

首页 > 解决方案 > 合并连接的平行 3D 线段的最优算法

c# - 合并连接的平行 3D 线段的最优算法

问题描述

我有一个带有 3D 线段的草图。每个段都有开始和结束 3D 点。我的任务是合并段，如果它们是并行和连接的。我已经在 C# 上实现了它。该算法是递归的。这段代码可以优化吗？可以不递归吗？

/// <summary>
/// Merges segments if they compose a straight line.
/// </summary>
/// <param name="segments">List of segments.</param>
/// <returns>Merged list of segments.</returns>
internal static List<Segment3d> MergeSegments(List<Segment3d> segments)
{
    var result = new List<Segment3d>(segments);
    for (var i = 0; i < result.Count - 1; i++)
    {
        var firstLine = result[i];
        for (int j = i + 1; j < result.Count; j++)
        {
            var secondLine = result[j];
            var startToStartConnected = firstLine.P1.Equals(secondLine.P1);
            var startToEndConnected = firstLine.P1.Equals(secondLine.P2);
            var endToStartConnected = firstLine.P2.Equals(secondLine.P1);
            var endToEndConnected = firstLine.P2.Equals(secondLine.P2);
                   
            if (firstLine.IsParallel(secondLine) && (startToStartConnected || startToEndConnected || endToStartConnected || endToEndConnected))
            {
                Segment3d mergedLine = null;
                if (startToStartConnected)
                {
                    mergedLine = new Segment3d(firstLine.P2, secondLine.P2);
                }

                if (startToEndConnected)
                {
                    mergedLine = new Segment3d(firstLine.P2, secondLine.P1);
                }

                if (endToStartConnected)
                {
                    mergedLine = new Segment3d(firstLine.P1, secondLine.P2);
                }

                if (endToEndConnected)
                {
                    mergedLine = new Segment3d(firstLine.P1, secondLine.P1);
                }

                // Remove duplicate.
                if (firstLine == secondLine)
                {
                    mergedLine = new Segment3d(firstLine.P1, firstLine.P2);
                }

                result.Remove(firstLine);
                result.Remove(secondLine);

                result.Add(mergedLine);
                result = MergeSegments(result);
                return result;
            }
        }
    }

    return result;
}

Segment3D 和 Point3D 类非常简单：

类 Segment3D：

 internal class Segment3d{
    public Segment3d(Point3D p1, Point3D p2)
    {
        this.P1 = p1;
        this.P2 = p2;
    }

    public bool IsParallel(Segment3d segment)
    {
        // check if segments are parallel
        return true;
    }

    public Point3D P1 { get; }

    public Point3D P2 { get; }
}

internal class Point3D
{
    public double X { get; set; }
    public double Y { get; set; }
    public double Z { get; set; }

    public override bool Equals(object obj)
    {
        // Implement equality logic,
        return true;
    }
}

标签： c#algorithm3dlinear-algebra

解决方案

优化

您正在询问删除递归的方法。但是，这不是您当前解决方案的唯一问题，也不是最大的问题。因此，我将尝试为您概述可能的优化方向。不幸的是，由于您的代码仍然不是独立的最小可重现示例，因此调试起来相当棘手。如果以后有时间，我可能会再次访问。

第一步：限制比较次数。

目前，您正在执行不必要的比较次数，因为您比较每两个可能的线段以及它们可能具有的每个可能的对齐方式。这是不必要的。

降低比较次数的第一步是按方向分隔线段。目前，当您尝试比较两个向量时，您会检查它们是否对齐。如果是这种情况，您将继续进行其余的比较。
如果我们按方向对段进行排序，我们自然会将它们分组到排序桶中。对段进行排序可能听起来很奇怪，有三个轴可供排序。这很好，因为我们真正关心的唯一事实是，如果两个归一化向量 (x,y,z) 和 (a,b,c) 在至少一个坐标上不同，则它们不平行。这种排序可以通过实现IComparable接口然后调用sort像往常一样的方法。例如，这里已经对此进行了描述。
排序的复杂度为 O(N * log(N))，比您当前的 O(N^2) 方法要好得多。（实际上，您的算法甚至比这更糟糕，因为在每个递归步骤中，您都会再执行 N^2 步。因此，您可能很危险地接近 O(N^4) 区域。有龙。）
注意：如果您是感觉冒险并且 O(Nlog(N) 是不够的，可以通过实现System.HashCode方向向量的函数来到达 O(N) 区域并使用Sets或找到平行线组Dictionaries. 然而，它可能相当棘手，因为浮点数和相等性比较并不是一个友好的组合。需要谨慎。对于大多数用例，排序应该足够了。

所以现在我们有了由方向向量分隔的线段。即使您现在继续使用当前方法，结果也应该会好得多，因为我们降低了要比较的组的大小。但是，我们可以走得更远。

第二步：分段智能比较结束。

由于您希望在它们的任一端点对齐的情况下合并这些段（正如您在问题中介绍的开始-开始、开始-结束、结束-开始、结束组合），我们很可能开始合并我们找到的任何两个相同点。最简单的方法是再次排序或散列。由于我们不会进行可能导致边际差异的标准化，因此散列应该是可行的。然而，排序仍然是更直接和“更安全”的方式。

可以做到这一点的众多方法之一：

  1. 将所有端点作为元组（端点，父向量）放入单链表中。数组不适合，因为删除成本很高。
  2. 按端点对列表进行排序。（再一次，您需要IComparable为您的积分实现接口）
  3. 浏览列表。每当两个相邻点相等时，删除它们并将它们的兄弟姐妹合并到一个新的线段中（或者如果邻居都是线段的起点或终点，则删除其中一个和更近的兄弟节点）。
  4. 当您传递整个列表时，所有段要么被合并，要么不再有邻居。
  5. 拿起你的幸存者，你就完成了。

这一步的复杂性再次是 O(N * log(N)) ，与前一种情况一样。不需要递归，加速应该很好。

推荐阅读