Introduction

Classic Ramer-Douglas-Peucker simplifies a polyline by removing points whose distance from the retained segments stays below an epsilon tolerance. If you want a fixed number of output points instead of a distance threshold, you are solving a slightly different problem: control the simplification budget directly rather than the geometric error directly.

Why epsilon and Point Count Are Different

Standard RDP answers this question:

• “How much error am I willing to tolerate?”

A fixed-point variant answers a different one:

• “How many points may remain?”

Those are related, but not identical. Lower epsilon often keeps more points, yet there is no simple closed-form formula that maps a desired point count to the correct tolerance.

That is why point-count control needs either:

• repeated search over epsilon
• or a direct algorithm that keeps splitting until exactly k points remain

A Practical Exact-Count Strategy

A good direct strategy is:

1. start with the first and last points retained
2. for every segment, find the interior point with the largest perpendicular error
3. split the segment with the largest error
4. repeat until you have the desired number of retained points

This behaves like “RDP with a priority queue” and gives direct control over the number of kept points.

Python Implementation

1import heapq
2import math
3
4
5def point_line_distance(point, start, end):
6    x0, y0 = point
7    x1, y1 = start
8    x2, y2 = end
9
10    if (x1, y1) == (x2, y2):
11        return math.hypot(x0 - x1, y0 - y1)
12
13    num = abs((y2 - y1) * x0 - (x2 - x1) * y0 + x2 * y1 - y2 * x1)
14    den = math.hypot(y2 - y1, x2 - x1)
15    return num / den
16
17
18def best_split(points, left, right):
19    best_index = None
20    best_distance = -1.0
21
22    for i in range(left + 1, right):
23        d = point_line_distance(points[i], points[left], points[right])
24        if d > best_distance:
25            best_distance = d
26            best_index = i
27
28    return best_index, best_distance
29
30
31def rdp_fixed_points(points, k):
32    if k >= len(points):
33        return points[:]
34    if k <= 2:
35        return [points[0], points[-1]]
36
37    kept = {0, len(points) - 1}
38    heap = []
39
40    idx, dist = best_split(points, 0, len(points) - 1)
41    if idx is not None:
42        heapq.heappush(heap, (-dist, 0, len(points) - 1, idx))
43
44    while len(kept) < k and heap:
45        _, left, right, split_idx = heapq.heappop(heap)
46        kept.add(split_idx)
47
48        left_idx, left_dist = best_split(points, left, split_idx)
49        if left_idx is not None:
50            heapq.heappush(heap, (-left_dist, left, split_idx, left_idx))
51
52        right_idx, right_dist = best_split(points, split_idx, right)
53        if right_idx is not None:
54            heapq.heappush(heap, (-right_dist, split_idx, right, right_idx))
55
56    return [points[i] for i in sorted(kept)]
57
58
59polyline = [(0, 0), (1, 0.1), (2, -0.1), (3, 5), (4, 6), (5, 7)]
60print(rdp_fixed_points(polyline, 4))

This keeps exactly k points as long as k is between 2 and the original number of points.

Binary Search on epsilon

Another approach is to run ordinary RDP repeatedly and binary-search the epsilon value until the result has roughly the desired number of points. That can work when “about k points” is acceptable.

But for exact point counts, binary search can be awkward because the number of retained points changes in discrete jumps. You may not hit the target exactly for every geometry.

That is why the direct priority-queue approach is often cleaner when the point budget is fixed.

Quality Tradeoff

The exact-count version gives strong control over output size, but it changes the primary optimization target. Standard RDP optimizes for distance tolerance; the fixed-count variant optimizes for “keep the most important splits until the point budget is exhausted.”

Those objectives are related, but not identical. So the output can differ from what you would get by choosing a particular epsilon.

When This Is Useful

A fixed number of points is useful when:

• a downstream model expects a fixed-length representation
• bandwidth or storage budget is strict
• you need the same output size for many shapes

In those cases, direct point-budget control is often more useful than geometric-tolerance control.

Common Pitfalls

• Treating “exactly k points” as if it were the same problem as standard epsilon-based RDP.
• Using binary search on epsilon and expecting it to always land on the exact desired point count.
• Forgetting that the first and last points are normally always retained, so the minimum practical count is usually 2.
• Using the fixed-count result as if it guaranteed the same maximum error bound as standard epsilon-based simplification.
• Recomputing every segment naively without thinking about the cost when simplifying many large polylines.

Summary

• Standard RDP is controlled by epsilon, not by a target point count.
• If you need exactly k points, a priority-queue split strategy is often the cleanest direct solution.
• Binary search on epsilon is useful for approximate count control, but not always for exact count control.
• Fixed-count simplification changes the optimization objective from “error threshold” to “point budget.”
• Choose the method based on whether geometric tolerance or output size is the more important requirement.