CODEWITHSUNDEEP
algorithmgeometry
Caleb Biddulph
Caleb Biddulph

Reputation: 33

Given points A, B, and C, how to determine whether both angles ABC and ACB are acute?

I'm trying to figure out an efficient way to determine whether, given the x and y coordinates of points A, B, and C, both the angle going from A to B to C and the angle from A to C to B are less than 90 degrees.

Basically, if Point A falls within the green area in this image, strip defined by opposite points B and C on edgesthe method should return true, and false otherwise.

I could think of some convoluted ways to do this, but I feel like there should be a simpler one. Since my program will be doing it a lot, an efficient solution would be helpful. Thanks!

Upvotes: 1

Views: 162

Answers (1)

Walter Tross
Walter Tross

Reputation: 12624

You want the dot product BA·BC (i.e., |BA||BC|cosθ, where θ is the angle between BA and BC), to be between 0 and BC2. In Python:

def in_strip(ax, ay, bx, by, cx, cy):
    bcx = cx - bx
    bcy = cy - by
    strip_width_squared = bcx * bcx + bcy * bcy
    bax = ax - bx
    bay = ay - by
    dot_product = bax * bcx + bay * bcy
    return 0 < dot_product < strip_width_squared

If the dot product is less than 0, the point A lies outside the strip on the side closer to B, if it is greater than BC2, it lies outside the strip on the side closer to C.

You can look at the dot product BA·BC as the product of two lengths: the length of the vector BC, |BC|, and the length of the component of the vector BA parallel to the vector BC (i.e., the projection onto a line parallel to it), |BA|cosθ. This component is 0 when A is on the edge of the strip that contains B, and it is BC when A is on the edge of the strip that contains C.

Using the above dot product saves you almost half of the calculations if you have to check several points for inclusion in the same strip. E.g., like this (can be improved):

class Strip:
    def __init__(self, bx, by, cx, cy):
        self.bx,  self.by  = bx, by
        self.bcx, self.bcy = cx - bx, cy - by
        self.width_squared = self.bcx * self.bcx + self.bcy * self.bcy

    def contains(self, ax, ay):
        bax, bay = ax - self.bx, ay - self.by
        return 0 < bax * self.bcx + bay * self.bcy < self.width_squared

Upvotes: 1

Related Questions