Check if values are inside a specific area around a predefined linear function

Question

My research on solving my issue was unfortunately unsuccessful and I hope you can help me. I have defined the following linear function for a straight line

x = [298358.3258395831, 298401.1779180078]
y = [5625243.628060675, 5625347.074197255]
m, b = np.polyfit(x, y, 1)

and I want to check, if values in an array are inside an area around this function. The area around the function could look like this:

I couldn't find a solution how to create an area around this straight line function and so I couldn't find a way how to check if the points in the array are inside or outside of the area.

Thanks in advance!

Or is it better to define two parallel line functions and do the comparison with the generated area in between these functions? — QuagTeX, Jul 13 '21 at 13:02
I would break it down in a few steps: finding the transformation making the rectangle horizontal, applying it to your band and your array, using the formula check if a point is inside an horizontal box. — Learning is a mess, Jul 13 '21 at 13:02
your area is not given by two lines starting and ending on the same x values. — Learning is a mess, Jul 13 '21 at 13:03
One possibilty is to use one function and let's say we create an area with +-5 (so bidirectional) around it or only one way with e.g. +10 in one direction. Another possibility would be to create a parallel function and create the area in between and there wouldn't be any intersections of these two functions — QuagTeX, Jul 13 '21 at 13:05

score 2 · Accepted Answer · answered Jul 13 '21 at 13:20

2

For a line given by the equation ax + by + c = 0, the distance from a point A = (x_a,y_a) to this line is given by the following formula :

dist = np.abs(a * x_a + b * y_a + c) / np.sqrt(a**2 + b**2)

Source here.

That way, if you have an array of points and a threshold above which you consider your points to be too far away from your line, you can simply do :

array_points = ... # Format : [[x_1,y_1], [x_2,y_2],...]
a, b, c = ... # Your line's parameters here
thresh = 1e-2 # For example

def is_close_line(array, threshold) :
  array_dist = np.abs(a * array[:,0] + b * array[:,1] + c) / np.sqrt(a**2 + b**2)
  return (array_dist < threshold)

is_close_line(array_points, thresh) will then output a boolean array, where the i-th item indicates wether or not the i-th element of array_points is close to your line.

answered Jul 13 '21 at 13:20

RandomGuy

1,076
6
17

Your approach looks like that what I would like to have and I comprehend it but I am messing up with the equations... I constructed a straight line in the form f(x) = mx + b with those two given points x and y (which are UTM coordinates) and if I transfer it to ax + bx + c = 0 this would give m = -(a/b) and my_b = -(c/your_b). Using your answer would mean that I have to solve a 3x3 system of linear equations to get a, b and c. I think I am missunderstanding the relation between both linear equations... – QuagTeX Jul 14 '21 at 13:51
1

No no no, it's far much simple ! You have `a = m`, `my_b = -1` and `c = your_b`. That's it ! As your line is currently on the format `y = f(x) = mx + your_b`. The notations overlaps, my bad, but forget about your initials `x` and `y` points. – RandomGuy Jul 15 '21 at 07:01
It felt a little bit wrong but I tested it with two simple samples and it worked for both cases. So thanks to you at this point. Another approach I've found would be to take the inverse of `m` to get an orthogonal straight line to the given linear function and equalize both functions to get the closest point to the given point `A = (x_a,y_a)`. Then you just have to calculate the distance between both points. – QuagTeX Jul 15 '21 at 09:58
Yup that should also work, with a little bit more of calculations though as you'd have to project your point onto this orthogonal line. – RandomGuy Jul 15 '21 at 10:03

score 1 · Answer 2 · answered Jul 13 '21 at 13:22

A possible solution could be:

Take a distance and project it onto the x axis
Build two new lines by shifting your line according to the distance projection
Compare a new point with the so-built lines

Here a sample code (note that m=0 should be handled differently):

def near_line(point, dist, m, b):
    # Data preparation
    x, y = point
    dist = abs(dist)
    
    if m != 0:
        # Case positive ramp
        dist_projection = dist/np.sin(np.arctan(abs(m)))
        return m*(x-dist_projection)+b < y < m*(x+dist_projection)+b
    
    else:
        # Case horizontal line
        return b-dist < y < b+dist


print( near_line([298359, 5625244], dist=5, m=m, b=b) )
print( near_line([298400, 5625250], dist=5, m=m, b=b) )

Out:

True
False

Ric S · Answer 3 · 2021-07-13T13:47:51.030

My answer is based on this post where the concept of cross-product and norm are considered. This solution applies also to an infinite line like yours, where it's constructed starting from two points.

import numpy as np

def dist_array_line(a, l1, l2, threshold):
    """
    a : numpy.array
        Array of points of shape (M,2)
        M is the total number of points to test
    l1 : numpy.array
        Array of shape (2,) indicating the first point standing on the line
    l2 : numpy.array
        Array of shape (2,) indicating the second point standing on the line
    threshold : float
        Maximum distance allowed between line and points
        
    Returns
        numpy.array
        Array of shape (M,) with True/False indicating whether the points in `a`
        are within/outside the rectangle around the line
    """
    distances = np.abs(np.cross(a - l1, a - l2)) / np.linalg.norm(l1 - l2)
    return (distances < threshold)

If you want to return the actual distances instead of a True/False array, just make the function return the distances object.

Example

# points on the line
p1 = np.array([298358.3258395831, 5625243.628060675])
p2 = np.array([298401.1779180078, 5625347.074197255])

# array of points to test
my_arr = np.array([
    [298359.3258395831, 5625243.628060675],
    [298368.3258395831, 5625243.628060675],
    [(p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2]
])

dist_array_line(my_arr, p1, p2, threshold=5.)
# array([ True, False,  True])

Check if values are inside a specific area around a predefined linear function

3 Answers3

Example