Introduction

Finding all points inside an axis-aligned rectangle is a standard spatial range-query problem. The fastest solution depends less on abstract asymptotic theory and more on workload shape: how many points exist, how often queries run, and whether the point set changes between queries. In many systems, the right answer starts with a simple scan and only moves to indexing when repeated queries justify the extra structure.

Define the Inclusion Rule First

Before optimizing anything, decide what "inside" means. A common rule is inclusive bounds:

x_min <= x <= x_max and y_min <= y <= y_max

That seems trivial, but boundary disagreements are a common source of false bug reports. If one component treats border points as included and another treats them as excluded, you can benchmark the perfect algorithm and still ship the wrong result.

A Linear Scan Is the Correct Baseline

For one query or a small point set, the simplest approach is usually the best.

1def points_in_rectangle(points, x_min, x_max, y_min, y_max):
2    return [
3        (x, y)
4        for x, y in points
5        if x_min <= x <= x_max and y_min <= y <= y_max
6    ]
7
8
9points = [(1, 2), (4, 1), (3, 5), (7, 2), (2, 4)]
10print(points_in_rectangle(points, 1, 4, 1, 4))

This costs O(n) per query. That may sound slow, but it has zero setup cost and is hard to get wrong. Many real systems never need anything more complex.

Sort by One Axis for Repeated Queries

If the points are mostly static and rectangle queries happen often, a sorted index on one axis is a practical upgrade. Sort once by x, use binary search to find the candidate slice, and then filter those candidates by y.

1import bisect
2
3class RectangleIndex:
4    def __init__(self, points):
5        self.points = sorted(points, key=lambda p: p[0])
6        self.x_values = [x for x, _ in self.points]
7
8    def query(self, x_min, x_max, y_min, y_max):
9        left = bisect.bisect_left(self.x_values, x_min)
10        right = bisect.bisect_right(self.x_values, x_max)
11        return [
12            (x, y)
13            for x, y in self.points[left:right]
14            if y_min <= y <= y_max
15        ]

This is often a good middle ground: much faster than a full scan for narrow queries, but far simpler than a full spatial tree.

Use Grid Bucketing for Uniform Spatial Data

When the points are spread fairly evenly over a large space and you expect many queries, a grid index can work well. Each point is assigned to a cell, and the query only touches the cells overlapped by the rectangle.

1from collections import defaultdict
2
3class GridIndex:
4    def __init__(self, points, cell_size=4):
5        self.cell_size = cell_size
6        self.buckets = defaultdict(list)
7        for x, y in points:
8            key = (x // cell_size, y // cell_size)
9            self.buckets[key].append((x, y))
10
11    def query(self, x_min, x_max, y_min, y_max):
12        cx0, cx1 = x_min // self.cell_size, x_max // self.cell_size
13        cy0, cy1 = y_min // self.cell_size, y_max // self.cell_size
14        result = []
15
16        for cx in range(cx0, cx1 + 1):
17            for cy in range(cy0, cy1 + 1):
18                for x, y in self.buckets.get((cx, cy), []):
19                    if x_min <= x <= x_max and y_min <= y <= y_max:
20                        result.append((x, y))
21        return result

This can be very fast, but it depends on the data distribution. If most points fall into a few crowded cells, the benefit drops quickly.

Choose by Query Pattern, Not by Habit

A useful rule of thumb is:

• Few queries or constantly changing data: use a scan.
• Many queries on static data: use a sorted index or another reusable structure.
• Large, even spatial workloads: consider bucketing or a dedicated spatial tree.

That is more helpful than memorizing one "best" algorithm. Real performance depends on setup cost, memory overhead, update cost, and the shape of the rectangles you actually query.

Keep the Baseline for Verification

Once you add an index, keep the brute-force scan around as a correctness oracle. Randomized comparison tests are easy to write and catch subtle boundary bugs.

1import random
2
3random_points = [(random.randint(0, 20), random.randint(0, 20)) for _ in range(200)]
4rect = (5, 12, 4, 10)
5
6baseline = sorted(points_in_rectangle(random_points, *rect))
7indexed = sorted(RectangleIndex(random_points).query(*rect))
8
9assert baseline == indexed

This is worth doing because an optimized spatial search that returns the wrong set of points is a regression, not an optimization.

Common Pitfalls

The most common mistake is jumping to a complex index before measuring whether a scan is already good enough. Another is leaving the boundary rule ambiguous. Grid approaches also fail when cell size is poorly chosen, and sorted one-axis indexes become awkward when the point set changes constantly.

Summary

• Rectangle point lookup is a range-query problem, and workload shape determines the best solution.
• A linear scan is the correct baseline and often the correct final answer.
• Sorting by one axis is a practical optimization for repeated queries on static data.
• Grid bucketing can help when spatial data is large and fairly uniform.
• Validate every optimized method against a simple brute-force implementation.