Determining if a point lies between two bearings from a central point

Question

I am trying to determine if a point lies between two bearings from a central point.

The diagram below attempts to explain things

I have a central point labelled A
I have two points (labelled B & C) which provide the boundaries of the search area (based on bearing only - there is no distance element required).
I'm trying to determine if point D is within the sector formed by A-B and A-C
I've calculated the bearings from A to each B & C
In my real scenario the angle created between the bearings can be anything from 0 to 360.

There are some similar questions & answers however in my case I'm not interested in restricting my search to the radius of a circle. And there seems to be some implementation issues around angle size and the location of the points in terms of clockwise vs counter-clockwise

It seems so simple in theory but my maths is clearly not up to scratch :(

Any advice or pseudo-code would be greatly appreciated.

I should note in my graphic above I was thinking of a mapping context for bearings where north = 0 degrees — rowanwins, Apr 29 '20 at 23:20

score 1 · Accepted Answer · answered Apr 29 '20 at 12:51

Here would be my approach:

calculate first bearing angle X
calculate second bearing angle Y
calculate angle Z towards point D
if X < Z < Y, return true; otherwise, return false

In your example it looks like you'd calculate Z ~ 90deg and find 45 < 90 < 135 (is your picture wrong? is says 315).

You can use something like the "atan2" function in whatever language you're using. This is an extension of the basic arctangent function which takes not just the slope but both the rise and run and instead of returning an angle from only a 180-degree range, it returns the true angle from a 360-degree range. So

Z = atan2(Dy, Dx)

Should give you the angle (possibly in radians; be careful) that you can compare to your bearings to tell whether you're inside the search. Note that the order of X and Y matter since the order is what defines which of the two sections is in the search area (X to Y gives ~90 deg in your picture, but Y to X gives ~270 deg).

Thanks @Patrick87 , using degrees made sense. I come from a mapping background hence why I went down the path of bearings where I noted 315. The only modification I had to make to your approach was adding a bit of logic for where angle X was less than angle Y. Here is a gist showing my final approach https://gist.github.com/rowanwins/3edee82cd2b1acc4cee125e9a014fe40 — rowanwins, Apr 29 '20 at 22:56

Reblochon Masque · Answer 2 · 2020-04-29T23:48:03.130

You can calculate and compare the cross products of the vectors (AB X BD), and (AC X CD).

if (AB X BD) > 0, you have a counter clock wise turn
if (AC X CD) < 0, you have a clock wise turn
If both above tests are true, then the point D is in the sector BAC

This allows you to completely avoid using expensive trig functions.

class Point:
    """small class for point arithmetic convenience
    """

    def __init__(self, x: float = 0, y: float = 0) -> None:
        self.x = x
        self.y = y

    def __sub__(self, other: 'Point') -> 'Vector':
        return Vector(self.x - other.x, self.y - other.y)


class Vector:
    """small class for vector arithmetic convenience
    """
    def __init__(self, x: float = 0, y: float = 0) -> None:
        self.x = x
        self.y = y

    def cross(self, other: 'Vector') -> float:
        return (self.x * other.y) - (self.y * other.x)


def in_sector(A: Point, B: Point, C: Point, D: Point) -> bool:

    # construct vectors:
    ab = B - A
    bd = D - B
    ac = C - A
    cd = D - C

    print(f'ab x bc = {ab.cross(bd)}, ac x cd = {ac.cross(cd)}')

    return ab.cross(bd) > 0 and ac.cross(cd) < 0


if __name__ == '__main__':

    A = Point(0, 0)
    B = Point(1, 1)
    C = Point(-1, 1)
    D = Point(0, 1)

print(f'D in sector ABC: {in_sector(A, B, C, D)}', end='\n\n')
print(f'D in sector ACB: {in_sector(A, C, B, D)}')  # inverting the sector definition so D is now outside

Output:

ab x bc = 1, ac x cd = -1
D in sector ABC: True

ab x bc = -1, ac x cd = 1
D in sector ACB: False

I tried this to implement this approach however my results seemed incorrect, I'm not sure if I misinterpreted something in your suggestion. Here is a gist I made of my implementation https://gist.github.com/rowanwins/f665fa7be671827e0def6d6d475d926a — rowanwins, Apr 29 '20 at 23:10
You are correct, I had the signs of the cross products inverted in the test @rowanwins, thank you! I fixed it and added a python implementation — Reblochon Masque, Apr 29 '20 at 23:50

Determining if a point lies between two bearings from a central point

2 Answers2

Output: