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

Question

Если у нас есть отрезок линии (A.x, A.y, B.x, B.y) и точка (C.x, C.y), как я могу определить, находится ли точка слева или справа, вверху или внизу отрезка линии? Я пробовал решения с перекрестными продуктами из предыдущих сообщений, но это привело меня к другой проблеме. Использование перекрестных произведений сделало порядок A и B. Какой еще есть метод, чтобы порядок A и B не имел значения?

Решение из предыдущих сообщений:

Используйте знак определителя векторов (AB, AM) , где M (X, Y) - точка запроса:

position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))

Это 0 в строке и +1 с одной стороны, -1 с другой.

Источник: Как определить, находится ли точка справа или слева от линии

Answer 1

(я принял декартову систему координат с положительными значениями x и y, указывающими вправо и вверх соответственно)

Дана линия, проходящая через точки (a, b), (c, d) , его уравнение:

Теперь у вас есть точка (e, f). Если вы подставляете x = e, y = f, и они удовлетворяют уравнению, это означает, что точка находится на прямой.

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

Чтобы вычислить левую / правую сторону, вам также необходимо учитывать градиент. Если градиент положительный, то нахождение под линией означает, что вы находитесь справа от нее. Если градиент отрицательный, то нахождение под линией означает, что вы находитесь слева от нее. Наоборот.

Обратите внимание, что вам нужно обрабатывать вертикальные линии как особый случай.

In Java,

double lhs = e;
double gradient = (b - d)/(a - c);
if (Double.isInfinite(gradient)) {
    // vertical line, compare only x coordinates
    if (e < a) {
        // on the left
    } else if (e > a) {
        // on the right
    } else {
        // on the line
    }
}
double rhs = (gradient * (e - a)) + b;
if (lhs > rhs) {
    if (gradient > 0) {
        // on the left
    } else if (gradient < 0) {
        // on the right
    } else {
        // on the top
    }
} else if (lhs < rhs) {
    if (gradient > 0) {
        // on the right
    } else if (gradient < 0) {
        // on the left
    } else {
        // below
    }
} else {
    // on the line
}

Чтобы доказать, что изменение порядка очков не меняет результат это довольно просто. Изменение порядка точек приводит к следующему уравнению (a меняется на c, b меняется на d):

Если вы развернете оба приведенных выше уравнения и тот, что в начале, вы увидите, что на самом деле это одно и то же уравнение, а именно: