Как найти ближайшую точку на многосегментной линии

Question

Я пытаюсь найти решение для лучшей производительности.

Мне нужно найти точку шкафа на многосегментной линии (точки списка) до заданной точки.

У моей линии есть тысячи точек, и мне нужно проверить расстояние до этой линии несколько раз в секунду. Поэтому решение должно быть очень быстрым.

Прямо сейчас у меня есть что-то вроде ниже. Он работает, но он будет медленным, если у линии есть 10000 + очков.

Возможно, у кого-то есть идея, как сделать это быстрее?

public static float GetSqrDistXZ(Vector3 a, Vector3 b) 
{ 
    Vector3 vector = new Vector3(a.x - b.x, 0, a.z - b.z); 
    return vector.sqrMagnitude; 
} 

public static Vector3 NearestPointOnFiniteLine(Vector3 start, Vector3 end, Vector3 pnt) 
    { 
     Vector3 line = (end - start); 
     float len = Mathf.Sqrt(line.sqrMagnitude); 
     line.Normalize(); 

     Vector3 v = pnt - start; 
     float d = (v.x * line.x) + (v.z * line.z); 
     d = Mathf.Clamp(d, 0f, len); 
     return start + line * d; 
    } 


int pointsCount = line.points3.Count - 1; // line - List<Vector3> points. 

float[] distances = new float[pointsCount]; 

    for (int i = 0; i < pointsCount+1; i++) { 
     if (i >= 1) { 
      distances [i - 1] = GetSqrDistXZ (point, NearestPointOnFiniteLine (line.points3 [i - 1], line.points3 [i], point)); 
     } 

    } 

int minListIndexLeft = System.Array.IndexOf (distances, Mathf.Min (distances)); 
float minimalDistance = distances[minListIndexLeft]; 

Vector3 closestPoint = NearestPointOnFiniteLine (line.points3[minListIndexLeft], line.points3[minListIndexLeft+1], point); 

Answer 1

Вы хотите подумать о разметке пространства. В этом примере я собираюсь предположить двумерное пространство, но это тоже работает в 3D. Также есть намного лучшие решения, такие как деревья BSP и прочее, но мы будем держать это здесь просто.

Представьте, что вы сетку над 2D-пространством. Каждый сегмент (расстояние между двумя точками) вашей линии пересекается с одной или несколькими ячейками этой сетки. Что вам нужно сделать, так это хранить пересекающиеся сегменты для каждой ячейки. Если ваша строка не изменяется, вы можете сделать это за один проход при запуске или даже сохранить эту информацию статически в Asset.

Но как только у вас есть эта информация, все, что вам нужно сделать, это вычислить ячейку, в которой находится ваша точка, а затем проверить только сегменты линий, которые пересекаются с этой конкретной ячейкой или рядом прямых соседей (см. Ниже). Это позволяет найти ближайшую точку молнии быстро в сравнении.

Если вы играете с этой идеей на листе бумаги, вы можете встретить случаи, когда это решение не дает ближайшей точки, поскольку оно не учитывает соседнюю ячейку, содержащую более близкую точку. Самый простой способ решить это следующий подход:

1. Find cell C, which is the cell your point is in 
2. Let cellRange = 0 
3. Let point B be undefined 

4. Find closest point P among all segments that intersect cell C and its neighboring cells of range cellRange* 
5. If B is the same as newly found point P then P is the solution. You are done. 
6. Increase cellRange by 1 
7. Let B = P 
8. Repeat from step 4 

* "neighboring cells of range cellRange" means: 
    cellRange 0: only cell C, no neighbours 
    cellRange 1: cell C and direct neighbours 
    cellRange 2: cell C, direct neighbours and their direct neighbours 
    ... 

Это решение в основном проверяет, увеличивая диапазон поиска улучшает решение. Как только увеличение диапазона не улучшило решение, вы нашли ближайшую точку.