Как оптимально найти все точки, которые попадут в радиус при движени из точки А в тчоку Б?

Question

Есть точка А=0 и точка Б=1000, и есть радиус С=3. Так же есть красные точки. Все на этом рисунке Vector3, кроме разумеется радиуса.

Как я могу оптимально получить все красные точки, которые попадут в радиус С при движении этого радиуса в точку Б?

Есть вариант в лоб - это в цикле for от i=0 до i<=1000 на каждой итерации вычислять дистацию i до красных точек, а потом проверять попадает ли она в радиус, но это как мне кажется неоптимально...

Есть какой-нибудь математический подход с минимальным числос итераций?

Answer 1

Можно, пожалуйста, вашу формулу самого движения и вычисления?

Математический подход это, как, кстати, уже упомянул @CrazyElf, вам нужно взять верхнюю точку вашего радиуса в начальной позиции и провести прямую к верхней точке этого же радиуса в конечной позиции. Аналогично сделать с нижней точкой радиуса.

Следующий шаг это перебор всех точек по критерию, если координата точки является решением уравнения нахождения точки между двух отрезков. Если пропустить много математики, возьмём первый отрезок A с координатами xA и yA, и аналогичную прямую B с координатами концов xB и yB, искомая точка P[xP, yP]. xP должна быть удовлетворять условие xA < xP < xB, если опустить факт, что прямые могут быть направлены в другую сторону (xA > xB). Аналогичное условие будет для координаты y. Условие для цикла будет примерно следующее:

foreach (var point in points)
{
    if ((a.X < point.X && point.X < b.X) &&
        (a.Y < point.Y && point.Y < b.Y))
        {
            // Точка между отрезками
        }
}

Answer 2

Находим нормализованный направляющий вектор (в шарпе есть готовый метод Vector3D.Normalize)

Len = (B-A).Magnitude
uAB = (B-A) / Len

Для каждой точки P из набора считаем квадрат расстояния до отрезка, используя скалярное произведение (Vector3D.DotProduct), и сравниваем с квадратом радиуса.

F = Clamp(uAB.dot.(P-A), 0, Len)
D = A + uAB*F
G = P - D
SquaredDist = G.dot.G

F - вспомогательная величина для нахождения проекции точки P на прямую, содержащую отрезок AB, численно она равна знаковому расстоянию от A до D (проекции P).

Для точек, проекция которых попадает вне отрезка, находим расстояние от соответствующего конца отрезка. Если же нужно учитывать только цилиндр, а не капсулу с полукруглыми крышечками (точки типа P1 на рисунке), то F меньше нуля и больше Len следует игнорировать.

Каждая точка проверяется только один раз

using System;
using System.Windows.Media.Media3D;

namespace ConsoleApp8
{
    class Program
    {
        static void Main(string[] args)
        {
            Vector3D A = new Vector3D(0, 0, 0);
            Vector3D B = new Vector3D(6, 0, 0);
            Vector3D AB = B - A;
            double Len = AB.Length;
            AB.Normalize();
            double R = 2.0;
            double RSq = R * R;
            double F;
            Vector3D C = new Vector3D();
            Vector3D G = new Vector3D();
            Vector3D[] P = new Vector3D[4];
            P[0] = new Vector3D(-1, -1, 0);
            P[1] = new Vector3D(2, 1, 1);
            P[2] = new Vector3D(5, 2, 2);
            P[3] = new Vector3D(8, 2, 2);

            for (int i = 0; i < 4; i++) {
                C = P[i] - A;
                F = Vector3D.DotProduct(C, AB);
                F = Math.Min(Math.Max(F, 0), Len);    //Math.Clamp
                G = C - F * AB;
                if (G.LengthSquared <= RSq)
                    Console.WriteLine(P[i].X + " " + P[i].Y + " " + P[i].Z + " близко");
                else
                    Console.WriteLine(P[i].X + " " + P[i].Y + " " + P[i].Z + " далеко");

            }
            Console.ReadKey();
        }
    }
}

Вывод:

-1 -1 0 близко
2 1 1 близко
5 2 2 далеко
8 2 2 далеко

Для полноты:
Кроме того, в зависимости от реальных условий задачи, может понадобиться грубо отфильтровывать те точки, которые ни за что не попадут в нужную окрестность. Например, если рабочее пространство большое, набор точек велик и не меняется, а отрезки разные (пример - перелеты космического корабля между звездами), то стоит построить некую структуру данных для деления пространства на области (space partition) - kd-tree, например. В простейшем случае - равные кубики, и каждом кубику соотнести точки, принадлежащие ему. Для очередного отрезка находим кубики, которые он пересекает и ближайшие в пределах радиуса. Таких кубиков может быть, например, всего сотая или тысячная доля от всего пространства, и проверяются только точки, находящиеся в этих кубиках.

БЛОГ НА HUSL

Как оптимально найти все точки, которые попадут в радиус при движени из точки А в тчоку Б?

Ответы (2 шт):