Оптимизированный алгоритм поиска точки на линии

Question

Я ищу оптимизированный целочисленный точечный алгоритм, в котором вы можете определить линию, используя начальную и конечную координаты, а также найти точку на основе ввода x или y.

Я знаю, как это сделать, используя деление dy / dx, но я ищу алгоритм, который устраняет все деления.

Вот что я сейчас делаю:

int mult = ((px - v0.x)<<16) / (v1.x - v0.x);
vec2 result{px, v0.y + (lerpmult*(v1.y - v0.y))>>16};

Разделение в первой строке - это проблема, которую я пытаюсь устранить.

Answer 1

Ответ, который вы найдете, следующий:

Допустим, наше линейное уравнение равно Ax + By + C = 0. Тогда нам просто нужно это три коэффициента (A, B и C).

Скажем, эта линия проходит через точки P(P_x, P_y) и Q(Q_x, Q_y). затем легко вычислить три вышеуказанных коэффициента.

A = P_y - Q_y,
B = Q_x - P_x,
C = - A P_x - B P_y

Как только мы получим наше линейное уравнение, мы можем легко вычислить x или y координата для данного y или x с уважением.

Вот мой c++ шаблон:

#include <iostream>
using namespace std;

// point struct
struct pt {
    int x, y;
};

// line struct
struct line {
    int a, b, c;

    // create line object
    line() {}
    line (pt p, pt q) {
        a = p.y - q.y;
        b = q.x - p.x;
        c = - a * p.x - b * p.y;
    }

    // a > 0; is must be true otherwise runtime error will occure
    int getX(int y) {
        return (-b * y - c) / a;
    }

    // b > 0; is must be true otherwise runtime error will occure
    int getY(int x) {
        return (-a * x - c) / b;
    }
};

int main() {
    pt p, q;
    p.x = 1, p.y = 2;
    q.x = 3, q.y = 6;
    line m = line(p, q);
    cout << "for y = 4, x = " << m.getX(4) << endl;
    cout << "for x = 2, y = " << m.getY(2) << endl;

    return 0;
}

Выход:

for y = 4, x = 2
for x = 2, y = 4

Ссылка: http://e -maxx.ru / algo / сегментов_сечение

Answer 2

Один из способов решения этой проблемы - использование скалярного произведения для определения косинуса угла между двумя векторами:

def line_test(a, b, p):
    v_ap = tuple(m - n for n, m in zip(a, p))
    v_ab = tuple(m - n for n, m in zip(a, b))

    scp = sum(m * n for m, n in zip(v_ap, v_ab))

    return scp > 0 and scp * scp == sum(n * n for n in v_ap) * sum(n * n for n in v_ab) and all(m <= n for m, n in zip(v_ap, v_ab))

Параметры вышеупомянутой функции - это конечные точки линии (a и b) и точка p (c на изображении), которую мы хотим проверить.

Шаг за шагом в каждой строке происходит следующее:

1. v_ap = tuple(m - n for n, m in zip(a, p))
   Мы вычисляем вектор от a до p (v_ap)
2. v_ab = tuple(m - n for n, m in zip(a, b))
   Вектор от a до b (v_ab)
3. scp = sum(m * n for m, n in zip(v_ap, v_ab))
   В этой строке скалярное произведение v_ap и v_abрассчитывается.В результате получается scp = cos(v_ab, v_ap) * euclidean_length(v_ab) * euclidean_length(v_ap), где евклидова длина вектора определяется как sqrt(sum(n * n for n in vector)) (стандартное определение геометрической длины вектора).
4. return scp > 0 and scp * scp == sum(n * n for n in v_ap) * sum(n * n for n in v_ab) and all(m <= n for m, n in zip(v_ap, v_ab)
   Эта строка довольно сложнапоэтому я разбью его на несколько частей:

scp * scp == sum(n * n for n in v_ap) * sum(n * n for n in v_ab)
Поскольку деление недопустимо, мы также не должны использовать квадратный корень, так как обычно это вычислениевключает в себя подразделения.Таким образом, вместо вычисления квадратного корня, мы берем квадрат как евклидовой длины обоих векторов, так и скалярного произведения, тем самым исключая вычисление квадратного корня:

scp = cos(v_ab, v_ap) * euclidean_length(v_ab) * euclidean_length(v_ap) =
    = cos(v_ab, v_ap) * sqrt(sum(n ^ 2 for n in v_ab)) * sqrt(sum(n ^ 2 for n in v_ap))

scp ^ 2 = cos(v_ab, v_ap) ^ 2 * sum(n ^ 2 for n in v_ab) * sum(n ^ 2 for n in v_ap)

Косинус угла междудва вектора должны быть 1, если они указывают в одном направлении.Таким образом, квадрат скалярного произведения, если векторы имеют одинаковое направление, будет

euclidean_length(v_ap) ^ 2 * euclidean_length(v_ab) ^ 2

, который мы затем сравним с фактическим скалярным произведением scp.

Это, однако, оставляет одну проблему:взятие квадрата исключает знак, который мы проверяем отдельно при сравнении scp > 0.Поскольку евклидова длина всегда положительна, только знак косинуса определяет значение scp.Отрицательное значение scp означает, что угол между v_ap и v_ab составляет не менее pi / 4 и не более pi * 3/4.Однако знак scp get теряется при возведении в квадрат, что означает, что мы можем только проверить, параллельны ли два вектора, а не если они указывают в одном направлении.Эта проблема решается проверкой scp > 0 дополнительно.

И наконец, что не менее важно, мы должны проверить, меньше ли расстояние от a до p, чем расстояние от a до b.Это можно сделать, проверив, имеет ли v_ap меньшую длину, чем v_ab.Поскольку мы уже проверили, что два вектора указывают в одном и том же направлении, достаточно проверить, все ли элементы в v_ap не больше, чем соответствующий элемент в v_ab, что делается с помощью

all(m <= n for m, n in zip(v_ap, v_ab))