Unity中如何高效查找点云给定方向上的最远点？

核心逻辑很直接：点在目标方向上的远近，可以通过点与方向向量的点积大小来判断。点积的几何意义是该点在方向向量上的投影长度乘以方向向量的模长——不管方向向量是否单位化，点积的相对大小都能准确反映点在该方向上的延伸程度，点积越大，点在目标方向上越远。

最优实现方式是单次遍历数组，时间复杂度O(n)，这是理论上的最优解（必须检查每个点一次，无法做到比O(n)更快），同时内存开销仅为O(1)，不需要额外排序或数据结构。

Unity C# 实现代码 #

using System;
using UnityEngine;

public static class PointCloudUtility
{
    /// <summary>
    /// 查找点云中指定方向上的最远点
    /// </summary>
    /// <param name="pointCloud">未排序的点云Vector3数组</param>
    /// <param name="direction">目标方向向量（无需提前单位化）</param>
    /// <returns>指定方向上的最远点</returns>
    public static Vector3 FindFarthestPointInDirection(Vector3[] pointCloud, Vector3 direction)
    {
        if (pointCloud == null || pointCloud.Length == 0)
            throw new ArgumentException("点云数组不能为空或没有元素");

        float maxDot = float.MinValue;
        Vector3 farthestPoint = pointCloud[0];

        foreach (Vector3 point in pointCloud)
        {
            float currentDot = Vector3.Dot(point, direction);
            if (currentDot > maxDot)
            {
                maxDot = currentDot;
                farthestPoint = point;
            }
        }

        return farthestPoint;
    }
}

关键优化说明 #

• 无需单位化方向向量：单位化只会改变点积的绝对值，不影响最大值的判断，省去了Vector3.Normalize()的计算开销。
• 零额外内存分配：直接遍历原数组，没有创建新集合或排序结构，内存占用极低。
• 大数据量扩展方案：如果点云规模达百万级以上，可借助Unity的Job System（如IJobParallelFor）做并行遍历，但小数据量场景下线程调度开销可能抵消并行收益，需根据实际情况权衡。

内容的提问来源于stack exchange，提问作者asj