Как вы определяете, находится ли точка впереди или позади отрезка, используя тест Half Space? - PullRequest
Новая
       57

Как вы определяете, находится ли точка впереди или позади отрезка, используя тест Half Space?

0 голосов
/ 28 апреля 2018

Как вы определяете, находится ли точка перед линией с тестом полупространства? Я попробовал следующее. Он работает в большинстве случаев , но не работает с другими. Есть ли обстоятельства, когда это не сработает? Например, будет ли это работать, только если все точки находятся в определенных квадрантах? Если нет, то что я делаю неправильно?

Я пробовал: 

bool PointInFrontOfLine(Point testPoint, Point v1, Point v2)
{
    // Compute line normal
    double dx = v2.x - v1.x;
    double dy = v2.y - v1.y;
    double nx = -dy;
    double ny = dx;
    double length = sqrt(dx * dx + dy * dy);
    nx /= length;
    ny /= length;
    glm::vec3 normal(nx, 0, ny);

    glm::vec3 vec(testPoint.x - v1.x, 0, testPoint.y - v1.y);

    double distance = glm::dot(vecTemp, normal);

    if (distance > 0)
        return true;
    else
        return false;
}

1 Ответ

0 голосов
/ 28 апреля 2018

Что вы на самом деле делаете, так это вычисляете (повернутый влево) вектор нормали к линии, которая определяется точками v1 и v2: 

double dx = v2.x - v1.x;
double dy = v2.y - v1.y;
double nx = -dy;
double ny = dx;
double length = sqrt(dx * dx + dy * dy);
nx /= length;
ny /= length;
glm::vec3 normal(nx, 0, ny);

Это можно упростить: 

glm::vec3 normal(v1.y - v2.y, 0, v2.x - v1.x);
normal = glm::normalize(normal);

Обратите внимание, что для алгоритма вы можете даже пропустить нормализацию, тогда вы не получите правильную нормаль distance, но знак distance все еще корректен. В вашем случае этого достаточно, потому что вы проверяете только distance > 0: 

glm::vec3 normal(v1.y - v2.y, 0, v2.x - v1.x);

Затем вы проверяете, больше ли угол между вектором normal и вектором от v1 до testPoint -90 градусов и меньше +90 градусов: 

glm::vec3 vec(testPoint.x - v1.x, 0, testPoint.y - v1.y);
double distance = glm::dot(vecTemp, normal);

Это работает, потому что в общем случае произведение точек из 2 векторов равно косинусу угла между двумя векторами, умноженного на величину (длину) обоих векторов. Если угол косинус равен> = 0, то угол находится в диапазоне [-90 °, 90 °]. 

dot( A, B ) == length( A ) * length( B ) * cos( angle_A_B )

A dot B

Но алгоритм работает, только если v2.x < v1.x (на следующих рисунках ось X указывает слева направо, а ось Y - снизу вверх):

v2.x < v1.x

Если 2 точки поменялись местами (v2.x > v1.x), то вы получите противоположный результат:

image v1.x">

Наконец, код можно выразить примерно так: 

glm::dot(glm::vec2(testPoint.x-v1.x, testPoint.y-v1.y),
         glm::vec2(v1.y-v2.y, v2.x-v1.x)) * glm::sign(v1.x-v2.x) > 0

Конечно, результат все еще зависит от того, что означает «перед». В моих предположениях это означает, что координата y testPoint меньше, чем координата y точки пересечения линии от v1 до v2 с параллельной линией к оси y через testPoint. Это означает, что зависит от вашей программной логики и системы координат, если этот алгоритм всегда вычисляет «спереди» или «сзади».

...