2

I am trying to find an existing API in Dlib/OpenCV/Numpy/Scipy to find out a point is on the left side or right side of the line.

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.

Searching Solution

A simple API that tells it is left/right side of a line.

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

My current solution

I wrote a math to find a point is left side or right side. So below functions returns a d, Based on sign of d I can tell it is left or right. Kind of hard coded way, not liking below solution.

    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
ajayramesh
  • 3,576
  • 8
  • 50
  • 75

1 Answers1

3

I would like you to refer to this point on Math StackExchange: https://math.stackexchange.com/questions/274712/calculate-on-which-side-of-a-straight-line-is-a-given-point-located. Simply put, given that you have three points: A point that denotes the beginning of the line, a point that denotes the end of the line and a query point, you can calculate the cross product between these three points and check the sign of the result. In fact, this answer on Stack Overflow uses this to determine if a point is on the left of a line: How to tell whether a point is to the right or left side of a line.

We can use this behaviour to help define if a point is to the left or right and can adjust based on the fact that you're using Python and DLib. Therefore, if the sign of the cross product is positive, the point is to the left of the line. If the sign is negative the point is to the right of the line. If the cross product is 0, then the point is collinear on the line. Because of numerical imprecision, comparing exactly with 0 is very dangerous as in most circumstances, getting exactly 0 is rare so comparing with exactly 0 may give you the wrong results. Therefore you'll want to see if the value is less than a small threshold, say 1e-9 for the collinear check.

With your example line, take note that it's essentially y = x so we can definitely define well-known points that should appear to the left and right of the line.

Therefore:

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"

To test this out:

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

I've defined points to be on the left, right and collinear on the line. We get:

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
rayryeng
  • 102,964
  • 22
  • 184
  • 193
  • thank you, I am not able to understand why we need threshold and how to determine the threshold since I am trying to run this code on edge device(Like Nano, TX2). Is there any thumb rule or we can use `1e-9` as standard value? – ajayramesh Jul 14 '20 at 15:50
  • 1
    The threshold is because of floating point precision. Specifically, it is very dangerous to compare with exactly zero, so you usually use a small constant instead. There is no rule here, but it's typically a small value that you would not expect to be significant to influence your calculations. 1e-9 is simply a value I've chosen. – rayryeng Jul 14 '20 at 15:58
  • 1
    @rayryeng is there is a way I can calculate this only using `numpy` without the need for using `dlib` since, I understand installing it on windows, requires a lot dependencies and I'd like to avoid it where I can. Thanks Again for your amazing answer. – Muneeb Ahmad Khurram Feb 24 '23 at 11:33
  • Hi upon further search, I have found an answer, you can visit the following StackOverlow Answer to calculate just that without using dlib. https://stackoverflow.com/a/1560510/11993925 – Muneeb Ahmad Khurram Feb 24 '23 at 11:34
  • 1
    @MuneebAhmadKhurram Please observe that the fundamental calculation to determine if a point is to the left or right of a line *does not use `dlib`*. `dlib` was only used to create the line and points. The way to determine whether a point is on the left or right uses the exact same post you're linking to (which I've also linked in my answer above). – rayryeng Feb 24 '23 at 13:33