Как определить, касается ли точка центроида линии или нет? - PullRequest
Новая
       81

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

1 голос
/ 17 марта 2020

Я работаю с алгоритмом обнаружения вторжения, который работает на основе обнаружения пересечения линии. Я разработал базовый c алгоритм, использующий уравнение y = mx + c, но он показывает некоторое неправильное обнаружение, когда человек приближается к линии. Мне нужно предложение, чтобы сделать его идеальным алгоритмом касания линии.

enter image description here

enter image description here

Ответы [ 2 ]

2 голосов
/ 17 марта 2020

Если ваша линия имеет начальную и конечную точки [x1, y1] и [x2, y2], то уравнение линии будет иметь вид:

y - y1 = m * (x - x1), где m = (y2 - y1)/(x2-x1)

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

В Pyhton: 

# the two points that define the line
p1 = [1, 6]
p2 = [3, 2]

# extract x's and y's, just for an easy code reading
x1, y1 = p1
x2, y2 = p2

m = (y2-y1)/(x2-x1)

# your centroid
centroid = [2,4]
x3, y3 = centroid

# check if centroid belongs to the line
if (m * (x3-x1) + y1) == y3:
    print("Centroid belongs to line")

Но, вероятно,. ..

... вы получите лучшие результаты, рассчитав расстояние между красной точкой и линией ( расстояние от точки до линии ), а затем проверите, достаточно ли близко (то есть расстояние меньше некоторого значения).

In Python: 

# points that define the line
p1 = [1, 6]
p2 = [3, 2]
x1, y1 = p1
x2, y2 = p2

centroid = [2,4]
x3, y3 = centroid

# distance from centroid to line
import math # to calculate square root
dist = abs((y2-y1)*x3 - (x2-x1)*y3 + x2*y1 - y2*x1)/math.sqrt((y2-y1)**2 + (x2-x1)**2)

if dist < some_value:
    print("Near enough")
1 голос
/ 17 марта 2020

Пусть линия go из точки l0 в точку l1. Тогда пусть центр тяжести будет точкой p1. Пусть вектор l будет вектором от l0 до l1 и p от l0 до p1. Затем вы можете найти расстояние от точки p1 до линии, используя точечное произведение, как описано здесь .

Возможно, вы хотите найти расстояние от вашей точки до отрезка , а затем оценить, находится ли точка на отрезке, на основе этого расстояния. Это можно сделать аналогичным образом, но с большим количеством логик c, как описано здесь .

Реализация в python с использованием numpy приведена ниже. Его можно легко расширить для обработки N центроидов, что позволяет вам параллельно отслеживать различные объекты. Он работает, проецируя точку на отрезок и находя расстояние от этой точки до центроида. 

import numpy as np

def distance_from_line_segment_points_to_point(l0, l1, p1):
    l0 = np.array(l0)
    l1 = np.array(l1)
    p1 = np.array(p1)

    l_vec = l1 - l0
    p_vec = p1 - l0

    if (l0 == l1).all():
        return np.linalg.norm(p_vec)

    l_norm = np.linalg.norm(l_vec)
    l_unit = l_vec / l_norm

    t = np.dot(l_unit, p_vec)
    if t >= l_norm:
        p_proj = l1
    elif t <= 0:
        p_proj = l0
    else:
        p_proj = l0 + t * l_unit
    return np.linalg.norm(p1 - p_proj)

print(distance_from_line_segment_points_to_point([0, 0], [0, 0], [1, 1]))  # sqrt(2), 1.4
print(distance_from_line_segment_points_to_point([0, 0], [1, 0], [1, 1]))  # 1
print(distance_from_line_segment_points_to_point([0, 0], [1, 1], [0, 1]))  # sqrt(2)/2, 0.707
...