Determine if points are within a rotated rectangle

Question

Using only Python 2.7 and the standard library (no imports):

Determine if a point is inside the rotated rectangle.

Test point 1: 670831  4867989
Test point 2: 675097  4869543

Rectangle:

Vertex 1:     670273   4879507
Vertex 2:     677241   4859302
Vertex 3:     670388   4856938
Vertex 4:     663420   4877144

---

Can the following code be improved?

vertices = [(670273, 4879507), (677241, 4859302), (670388, 4856938), (663420, 4877144)]

def dot_pdt(point1, point2, pointT):
    return ((point2[0] - point1[0]) * (pointT[0] - point1[0])) + ((point2[1] - point1[1]) * (pointT[1] - point1[1]))

def check_point(pointT):
    for i in range(len(vertices)):
        k = dot_pdt(vertices[i], vertices[(i + 1) % len(vertices)], pointT)
        if k <= 0:
            return False

    return True

point1 = (676455.270, 4861545.437)

print(check_point(point1))

Answer 1

Code Review

• Main guard

When running code outside a function / class, it is a good practice to put the code inside the main guard. See here for more explanation.

• Docstrings

It is a good practice to provide docstrings for functions. See here for more details. In Python 3.5+, adding type hints to function parameters and return values is also a good habit. (As a side remark, Python 2 has officially reached the end of life. It is recommended to move to Python 3.)

• Variable & function names should be clear, descriptive, and unambiguous

For example, check_point could be named as is_inside_rectangle.

• Function definition should include all necessary parameters

vertices should be a parameter of the function check_point.

• Other minor improvements

By exploiting the fact that vertices[-1] is the same as vertices[len(vertices)-1], the explicit modulo operation vertices[(i + 1) % len(vertices)] could be avoided.

The for-loop logic can be simplified using an all statement.

Here is an improved version of the code:

def dot_prod_with_shared_start(start, end1, end2):
    """
    Compute the dot product of the vectors pointing from start to end1 and end2

    Parameters
        start: starting point of both vectors
        end1: end point of first vector
        end2: end point of second vector

    Returns
        dot product of (end1 - start) and (end2 - start)
    """
    return (end1[0] - start[0]) * (end2[0] - start[0]) + (end1[1] - start[1]) * (end2[1] - start[1])

def is_inside_rectangle(vertices, point):
    """
    Given the vertices of a rectangle, determine whether a point is inside it.

    Parameters
        vertices: a list of tuples representing rectangle vertices in clockwise or
                  counter-clockwise order
        point: a tuple representing the point to check

    Returns
        True if the point is inside the rectangle. False otherwise.
    """
    return all(dot_prod_with_shared_start(vertices[i - 1], v, point) > 0 for i, v in enumerate(vertices))

if __name__ == "__main__":
   rect_vertices = [(670273, 4879507), (677241, 4859302), (670388, 4856938), (663420, 4877144)]
   test_point = (676455.270, 4861545.437)

   print(is_inside_rectangle(rect_vertices, test_point))

Another Solution

An alternative solution is to represent the vertices and the point as complex values, and apply complex number arithmetics to solve the problem.

def is_directed_angle_acute(start, end1, end2):
    """
    Check whether the directed angle from (end1 - start) to (end2 - start) is an acute angle, 
    i.e. within (0, pi / 4).

    Parameters
        start: a complex value representing the starting point of both vectors
        end1: a complex value representing the end point of first vector
        end2: a complex value representing the end point of second vector

    Returns
        True if the directed angle from (end1 - start) to (end2 - start) is within (0, pi / 4).
        False otherwise.
    """
    q = (end2 - start) / (end1 - start)
    return q.real > 0 and q.imag > 0

def is_inside_rectangle(vertices, point):
    """
    Given the vertices of a rectangle, determine whether a point is inside it.

    Parameters
        vertices: a list of complex values representing rectangle vertices in clockwise order
        point: a complex value representing the point to check

    Returns
        True if the point is inside the rectangle. False otherwise.
    """
    v0, v1, v2, v3 = vertices
    return is_directed_angle_acute(v0, point, v1) and is_directed_angle_acute(v2, point, v3)

if __name__ == "__main__":
   rect_vertices = [670273 + 4879507j, 677241 + 4859302j, 670388 + 4856938j, 663420 + 4877144j]
   test_point = 676455.270 + 4861545.437j

   print(is_inside_rectangle(rect_vertices, test_point))