как найти точку слева или справа от линии, используя Python и DLib? - PullRequest
Новая
       104

как найти точку слева или справа от линии, используя Python и DLib?

1 голос
/ 13 июля 2020

Я пытаюсь найти существующий API в Dlib / OpenCV / Numpy / Scipy, чтобы узнать, что точка находится слева или справа от строки. 

import dlib
a = dlib.point(0, 0)
b = dlib.point(20, 20)
line = dlib.line(a, b)
dlib.distance_to_line(line, dlib.point((-50, 4))) # provides absolute distance.

Решение для поиска

Простой API, который сообщает, что это левая / правая сторона строки. 

example 
dlib.where_is_the_point(line, dlib.point((-50, 4)) # if returns negative means left side.

Мое текущее решение

Я написал математику, чтобы найти точку слева или справа . Итак, нижеприведенные функции возвращают d. Основываясь на знаке d, я могу сказать, что он слева или справа. Вид жестко запрограммированного способа, не нравится нижеприведенное решение. 

    def where_it_is(self, target: Point):
        d = (target.x - self.p1[0]) * (self.p2[1] - self.p1[1]) - (target.y - self.p1[1]) * (self.p2[0] - self.p1[0])
        return d

1 Ответ

2 голосов
/ 14 июля 2020

Я хотел бы, чтобы вы сослались на этот пункт на Math StackExchange: https://math.stackexchange.com/questions/274712/calculate-on-which-side-of-a-straight-line-is-a-given-point-located. Проще говоря, учитывая, что у вас есть три точки: точка, обозначающая начало строки, точка, обозначающая конец строки и точка запроса, вы можете вычислить перекрестное произведение между этими тремя точками и проверить знак результат. Фактически, этот ответ на Stack Overflow использует это, чтобы определить, находится ли точка слева от строки: Как определить, находится ли точка справа или слева от строки .

Мы можем использовать это поведение, чтобы помочь определить, находится ли точка слева или справа, и можем отрегулировать в зависимости от того, что вы используете Python и DLib. Следовательно, если знак перекрестного произведения положительный, точка находится слева от линии. Если знак отрицательный, точка находится справа от линии. Если перекрестное произведение равно 0, то точка коллинеарна на линии. Из-за числовой неточности точное сравнение с 0 очень опасно, так как в большинстве случаев получение точно 0 редко, поэтому сравнение с точно 0 может дать вам неправильные результаты. Поэтому вы захотите увидеть, меньше ли значение, чем небольшой порог, скажем, 1e-9 для проверки коллинеарности.

В строке вашего примера обратите внимание, что это, по сути, y = x, поэтому мы можем точно определить хорошо известные точки, которые должны появиться слева и справа от линии.

Следовательно: 

def where_it_is(line, point):
    aX = line.p1.x
    aY = line.p1.y
    bX = line.p2.x
    bY = line.p2.y
    cX = point.x
    cY = point.y

    val = ((bX - aX)*(cY - aY) - (bY - aY)*(cX - aX))
    thresh = 1e-9
    if val >= thresh:
        return "left"
    elif val <= -thresh:
        return "right"
    else:
        return "point is on the line"

Чтобы проверить это: 

import dlib

a = dlib.point(0, 0)
b = dlib.point(20, 20)
line = dlib.line(a, b)

pt1 = dlib.point(2, -2) # Should appear on the right
pt2 = dlib.point(5, 10) # Should appear on the left
pt3 = dlib.point(2, 2) # Point should be collinear

print(where_it_is(line, pt1))
print(where_it_is(line, pt2))
print(where_it_is(line, pt3))

Я Определенные точки должны быть слева, справа и коллинеарны на линии. Получаем: 

In [40]: %paste
print(where_it_is(line, pt1))
print(where_it_is(line, pt2))
print(where_it_is(line, pt3))

## -- End pasted text --
right
left
point is on the line
...