How to identify if the centroid point touches a line or not?

Question

I am working with an intrusion detection algorithm which works on the basis of line crossing detection. I have developed a basic algorithm using the equation y = mx+c, but it is showing some wrong detection when the person reaches nearer to the line. I need some suggestion for making it a perfect line touching algorithm.

Answer 1

If your line has starting and ending points [x1, y1] and [x2, y2], then the line equation is:

y - y1 = m * (x - x1), where m = (y2 - y1)/(x2-x1)

Then you can check if a point belongs to the line or not, substituting either x or y, and checking if the other matches the line equation.

In 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")

But probably...

...you'll have better results calculating the distance between red dot and the line (distance from a point to a line), and then checking if it is near enough (i.e. distance less than some value).

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")

Answer 2

Let the line go from point l0 to point l1. Then let the centroid be point p1. Let the vector l be the vector from l0 to l1 and p from l0 to p1. Then you can find the distance from the point p1 to the line using dot product as described here.

You probably want to find the distance from your point to the line segment and then evaluate if the point is on the line segment based on that distance. This can be done in a similar fashion but with more logic around it, as described here.

An implementation in python using numpy is given below. It can easily be extended to handle N centroids, enabling you to track different objects in parallel. It works by projecting the point onto the line segment and finding the distance from this point to the centroid.

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