Поиск ближайшей точки к кривой
Возможно ли быстро вычислить ближайшую точку к кривым 3го/4го порядка без деления на более мелкие отрезки? Если да, то как?
Вообще в идеале задача звучит как "поиск ближайшей точки на кривой относительно луча". Может даже такой вариант кто знает?

Лучший ответ:
Насколько мне известно, в общей виде - нельзя. Если вкратце опишешь, какую проблему решаешь, то есть вероятность найти альтернативные варианты.



Просмотров: 220

alexprey #1 - 3 месяца назад 0
Найти ближайшую точку из списка доступных?
Devion #2 - 3 месяца назад 0
без деления на более мелкие отрезки
Clamp #3 - 3 месяца назад (отредактировано ) 0

Насколько мне известно, в общей виде - нельзя. Если вкратце опишешь, какую проблему решаешь, то есть вероятность найти альтернативные варианты.
Doc #4 - 3 месяца назад 2
Откуда кривая то собственно взялась, если не из набора точек? Какая-то формула? Можно спроецировать её на прямую и найти локальные минимумы.
Clamp #5 - 3 месяца назад 2
Doc, очевидно, что если известен порядок кривой, то она строится по известной формуле =)
Devion #6 - 3 месяца назад 0
есть безье 3/4 порядка. т.е. да как сказал кламп - по формуле.
Формула кривой безье третьего порядка выглядит так:
        public static Vector3 Bezier(Vector3 a, Vector3 b, Vector3 c, float t)
        {
            var c0 = (1 - t)*(1 - t);
            var c1 = (1 - t)*2*t;
            var c2 = t*t;
            return c0*a + c1*b + c2*c;
        }
формула безье 4го порядка вот так:
        public static Vector3 Bezier(Vector3 a, Vector3 b, Vector3 c, Vector3 d, float t)
        {
            float c0 = (1 - t)*(1 - t)*(1 - t);
            float c1 = (1 - t)*(1 - t)*3*t;
            float c2 = (1 - t)*t*3*t;
            float c3 = t*t*t;
            return c0*a + c1*b + c2*c + c3*d;
        }
Применений несколько, все даже не назову, но вот ближайший кейс.
Есть некоторая камера, которая смотрит на построенную кривую безье. В точке, на которую мы указали/нажали должен появиться новый объект.
Т.е. наши базовые данные: 3 точки кривой, луч (позиция+направление) направленный из камеры.
Задача: определить ближайшую к кривой точку и выполнить с ней нужные манипуляции.
Использовать дробление на более мелкие отрезки я не хочу, т.к. это очень затратно, особенно если кандидатов на пересечение будет больше. Габаритный тест решит проблему, но только частично.
Пробовал делить на отрезки более экономно (поделить на три отрезка, вычислить квадрат расстояния, отсеять, снова поделить, и так несколько раз), но результат такого деления становится некорректным, когда указатель оказывается чуть дальше.
В принципе ладно, ответ "нельзя" меня устраивает, просто надеялся, мало ли.
Clamp #7 - 3 месяца назад 0
Devion, как именно располагается и чем задаётся вектор камеры относительно кривой? Модель плоская или всё-таки пространственная?
Doc #8 - 3 месяца назад 2
Очень сомневаюсь в "нельзя". Если искать пересечение между линией и плоскостью, но используя вместо уравнения плоскости уравнение безье то наверное может получиться. Советую спросить не здесь, а на stackoverflow/math.stackexchange
Clamp #9 - 3 месяца назад 0
Очень сомневаюсь в "нельзя".
Собственно, я говорил про "в общем виде", когда ещё не было внесено никаких уточнений. И да, действительно, "в общем виде" в целом редко что оказывается "льзя".
Советую спросить не здесь, а на stackoverflow/math.stackexchange
Совет дня, если честно.