合并连接的平行 3D 线段的最佳算法

Question

我有一个带有 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 非常简单：

Class 3D 段：

 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;
    }
}

Answer 1

优化

你问的是去除递归的方法。然而，这不是您当前解决方案的唯一问题，也不是最大的问题。所以我会尽量给你一个可能的优化方向的大纲。不幸的是，由于您的代码仍然不是独立的最小可重现示例，因此调试起来相当棘手。以后有时间的话，我可能会再去看看。

第一步：限制比较次数。

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

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

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

第二步：分段智能比对结束

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

可以通过多种方式之一完成此操作：

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

这一步的复杂度再次为 O(N * log(N))，与之前的情况一样。不需要递归，加速应该不错。

合并连接的平行 3D 线段的最佳算法

Optimal algorithm for merging connected parallel 3D line segments

c#

algorithm

3d

linear-algebra

优化

第一步：限制比较次数。

第二步：分段智能比对结束