Geometry
Point-in-Rectangle
Computational-Geometry
Spatial-Analysis
Algorithms

Finding whether a point lies inside a rectangle or not

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Finding whether a point lies inside a rectangle is a common problem in computer science and computational geometry. This problem can arise in various applications such as computer graphics, geographical information systems, collision detection in games, and more. Below is a detailed article explaining the techniques and logic used to ascertain if a given point is inside a rectangle.

Background Concepts

Before diving into the methodology, let's solidify some foundational concepts related to points and rectangles:

Point: A point is defined in a 2D plane by two coordinates, usually denoted as (x,y)(x, y). • Rectangle: A rectangle is defined by its sides being parallel to the coordinate axes. In most scenarios, a rectangle is described by two corner points — the top-left and bottom-right corners, or alternatively by a single corner and its width and height.

Coordinate System

In a typical Cartesian coordinate system used in computer graphics:

• The top-left corner of the window/screen is typically (0, 0). • The x-axis increases to the right. • The y-axis increases as you move down the screen.

Algorithm for Axis-Aligned Rectangle

For axis-aligned rectangles, where the edges of the rectangle are parallel to the x or y axes, determining if a point lies inside the rectangle is straightforward. The rectangle can be defined using two corners, typically the bottom-left (xmin,ymin)(x_{\text{min}}, y_{\text{min}}) and top-right (xmax,ymax)(x_{\text{max}}, y_{\text{max}}) points.

Steps:

  1. A point (px,py)(p_x, p_y) lies inside or on the edge of this rectangle if: • xminpxxmaxx_{\text{min}} \leq p_x \leq x_{\text{max}}yminpyymaxy_{\text{min}} \leq p_y \leq y_{\text{max}}

If both conditions are met, the point is inside the rectangle; otherwise, it lies outside.

Algorithm Implementation:

Below is a sample function written in Python to implement this logic:

Vertices Representation: The rectangle is represented by its four vertices, say A(x1,y1)A(x_1, y_1), B(x2,y2)B(x_2, y_2), C(x3,y3)C(x_3, y_3), D(x4,y4)D(x_4, y_4), listed in a clockwise or counterclockwise direction.

Boundary Conditions: It must be clarified whether points on the edge or corner should be considered 'inside'. • Degenerate Cases: Situations like zero-width or zero-height rectangles deserve special handling. • Floating Point Arithmetic: Precision issues can affect the result due to representation errors in computers.


Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

All Rights Reserved.