Расчет ограничительной рамки - PullRequest
Новая
       47

Расчет ограничительной рамки

0 голосов
/ 16 мая 2018

Наш алгоритм вычисления ограничивающего прямоугольника реализован следующим образом. Что еще мы можем сделать, чтобы улучшить скорость? Или другой подход к решению той же проблемы?

Спасибо. 

boxMin.X = boxMax.X = points[0].X;
boxMin.Y = boxMax.Y = points[0].Y;
boxMin.Z = boxMax.Z = points[0].Z;

for (int i = 1; i < points.Length; i++)
{
    UpdateMinMaxQuick(points[i], boxMin, boxMax);
}

Это исходный код метода UpdateMinMaxQuick(): 

public static void UpdateMinMaxQuick(double x, double y, double z, Point3D min, Point3D max)
{
    if (x < min.X)

        min.X = x;

    else if (x > max.X)

        max.X = x;

    if (y < min.Y)

        min.Y = y;

    else if (y > max.Y)

        max.Y = y;

    if (z < min.Z)

        min.Z = z;

    else if (z > max.Z)

        max.Z = z;
}

1 Ответ

0 голосов
/ 16 мая 2018

Вы не можете значительно ускорить среднее время, но можете избежать наихудшего случая (для повышения последовательности координат, к которой вы подходите, используется около 2n сравнений на координату):

Для каждой пары соседних элементов сравните их и сравните глобальные min и max с парой min и max. Этот метод всегда использует 3n / 2 сравнения (по координате). 

 if points[2*i].X > points[2*i+1].X:
       if min.X > points[2*i+1].X:
            min.X = points[2*i+1].X 
       if max.X < points[2*i].X:
            max.X = points[2*i].X 
 else:
       if min.X > points[2*i].X:
            min.X = points[2*i].X 
       if max.X < points[2*i+1].X:
            max.X = points[2*i+1].X
...