Introduction

Counting how many points lie inside a rectangle is a classic range-query problem in computational geometry. The right solution depends on whether you have one query or many: a single query can be answered by scanning all points, while many queries justify preprocessing so each rectangle can be answered much faster.

Naive Scan for One-Off Queries

If you only need to answer a rectangle count occasionally, the simplest solution is to test each point directly.

1def count_points(points, x1, y1, x2, y2):
2    left = min(x1, x2)
3    right = max(x1, x2)
4    bottom = min(y1, y2)
5    top = max(y1, y2)
6
7    total = 0
8    for x, y in points:
9        if left <= x <= right and bottom <= y <= top:
10            total += 1
11    return total
12
13
14points = [(1, 2), (3, 4), (5, 1), (2, 3)]
15print(count_points(points, 2, 2, 4, 5))

This runs in O(n) time per query. That is perfectly fine when the dataset is small or the number of rectangle queries is low.

Use a 2D Prefix Sum for Many Queries on a Grid

If point coordinates are integer grid positions inside a bounded range and you need many rectangle queries, a 2D prefix sum is a strong option. First build a grid of point counts, then precompute cumulative sums.

1def build_prefix(points, width, height):
2    grid = [[0] * (width + 1) for _ in range(height + 1)]
3
4    for x, y in points:
5        grid[y][x] += 1
6
7    prefix = [[0] * (width + 1) for _ in range(height + 1)]
8    for y in range(1, height + 1):
9        for x in range(1, width + 1):
10            prefix[y][x] = (
11                grid[y][x]
12                + prefix[y - 1][x]
13                + prefix[y][x - 1]
14                - prefix[y - 1][x - 1]
15            )
16    return prefix
17
18
19def query(prefix, x1, y1, x2, y2):
20    left, right = sorted((x1, x2))
21    bottom, top = sorted((y1, y2))
22    return (
23        prefix[top][right]
24        - prefix[bottom - 1][right]
25        - prefix[top][left - 1]
26        + prefix[bottom - 1][left - 1]
27    )

After preprocessing, each rectangle query is O(1). The tradeoff is that this approach assumes bounded integer coordinates or coordinate compression.

When Coordinates Are Large or Continuous

If coordinates are large, sparse, or continuous, a dense grid may waste too much memory. In that case, more advanced data structures such as range trees, Fenwick trees with coordinate compression, or segment-tree-based sweep-line methods become more attractive.

The important decision is not which data structure sounds most sophisticated. It is whether your workload is:

• one query versus many queries
• dense grid versus sparse coordinates
• static points versus points that change over time

Those constraints determine the right algorithm much more than the rectangle query itself.

That is why range-query problems are usually discussed together with workload assumptions. The same mathematical question can justify a simple loop, a prefix table, or an advanced spatial index depending on how often the query is asked and how large the point set becomes.

Common Pitfalls

• Using an O(n) scan for a workload with thousands of repeated queries.
• Building a dense grid when coordinates are huge and sparse.
• Forgetting to normalize rectangle corners when x1 > x2 or y1 > y2.
• Miscounting boundary points by using strict comparisons instead of inclusive ones.
• Choosing a complex data structure before understanding the query pattern.

Summary

• A direct scan is the simplest answer for one-off rectangle queries.
• A 2D prefix sum is excellent for many queries on bounded integer grids.
• Sparse or large coordinates usually need coordinate compression or other range-query structures.
• Always normalize rectangle bounds before counting.
• Match the algorithm to the workload, not just to the geometry problem statement.