2

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.

enter image description here

enter image description here

Adithya Raj
  • 95
  • 9
  • in your example, do you want to know if the red dot is to the left of the green line? or if the red dot is precisely a point of the green line? if it is the second option, you will probably have to think of a thin rectangle and very small circle. – Gustavo Kaneto Mar 17 '20 at 08:19
  • Thanks for the comment Gustavo, I want to find whether the red dot precisely a point on the green line. Could you explain how to do that – Adithya Raj Mar 17 '20 at 08:47

2 Answers2

5

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")
Gustavo Kaneto
  • 643
  • 7
  • 17
  • If you use the first solution, it's better to check before it the line is vertical (i.e. `if x1 == x2`). Treat this as a special case and just check if your centroid x is also equal to `x1`or `x2` (i.e `if x3 == x1`). – Gustavo Kaneto Mar 17 '20 at 09:40
  • Actually I am using the second solution. I understood the case, I was testing that. I think for the vertical line and horizontal line as well it shows the same issue right?? Division by zero – Adithya Raj Mar 17 '20 at 09:44
  • using the code above, division by zero only appears when the line is vertical. – Gustavo Kaneto Mar 17 '20 at 09:50
  • Also, if you want to use this to process frames of a live video, maybe you can increase performance by *not* using `sqrt`. Instead, you can use squared lenghts. – Gustavo Kaneto Mar 17 '20 at 09:53
  • But Gustavo, now I have encountered a new issue which is even though the centroid is not touching the line it is creating an alarm. I have updated the issue with an image, you can see the dist threshold value as I have included that piece of code also in the screenshot – Adithya Raj Mar 17 '20 at 10:02
  • oh, yes... the solution I provided considers the whole line, extended infinitely. For your needs, I think you can check before if your centroid is outside of some "square" that encloses your line segment. (check if centroid x and y is outside x's and y's of your line segment) – Gustavo Kaneto Mar 17 '20 at 10:06
  • in python, you can use things like `if x1 < x3 < x2` to chain comparisons. In this case, to check if x3 is between x1 and x2 – Gustavo Kaneto Mar 17 '20 at 10:08
  • 1
    Yes, Gustavo, I am using this now. I thought about the same. I very thankful to you for giving instant solution. Thank you so much. Let me check right now and I will get back to you after the final results. – Adithya Raj Mar 17 '20 at 10:11
1

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
Nicholas Dalhaug
  • 31
  • 5