Simplify a trail
A hiking app stores trails in simplified form: only the points of a track without which the trail’s shape would be distorted by more than a tolerance of ε metres are kept. Simplification uses the Ramer–Douglas–Peucker algorithm, and so that the result is the same on every device, the rules are stated exactly.
- The first and last points always remain.
- For a pair of kept points i < j with other points between them, find the point farthest from the segment PiPj: the distance is to the nearest point of the segment (if Pi = Pj, simply to that point). Among several equally distant ones, take the point with the smaller number.
- If its distance is strictly greater than ε, it remains, and the rule is applied to the pairs (i, k) and (k, j). Otherwise all points between i and j are thrown out.
Print which points remain. Tests three to six and nine are mountain trails south of Almaty from OpenStreetMap in whole metres; the ninth is an out-and-back route that ends where it started.
Input
The first line holds the number of points n (2 ≤ n ≤ 20,000) and the tolerance ε (0 ≤ ε ≤ 10⁴). Then n lines with the coordinates of the track points x y in order. All numbers are integers, |x|, |y| ≤ 10⁴. Points may repeat, including consecutively.
Output
The first line holds how many points remain, the second their numbers (from one) in increasing order, separated by spaces.
Examples
Example 1
13 1 0 0 6 1 12 1 13 3 7 4 1 5 2 7 8 8 14 8 15 10 17 15 20 16 24 21
9 1 3 4 6 7 9 11 12 13
Example 2
7 2 0 0 4 1 8 0 14 1 30 2 20 1 10 0
3 1 5 7
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 12 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The algorithm from the article fits word for word; the question is precision. Distances are square roots, and comparing them in floating point risks equally distant points turning out “slightly” different. Can distances be compared without taking roots or dividing?
2Hint 2
All the points between i and j share the same segment. Multiply their squared distances by the same number L = |Pj − Pi|², and they all become integers. What is the squared distance to the line multiplied by L?
3The idea
Let d = Pj − Pi and p = Pm − Pi. The dot product p · d tells where the perpendicular falls: below zero, beyond the start of the segment; above L, beyond its end; otherwise onto the segment. In the first two cases the distance is to an end of the segment, and d²·L is an integer. In the third the distance to the line is |p × d| / √L, and d²·L = (p × d)². Compare these integers with each other, and with the tolerance compare the number ε²·L.
4Walkthrough
A stack of pairs (i, j), initially (1, n). For a pair compute vm = d²(m)·L for all m between them by the rules above and take the first maximum. If it exceeds ε²·L, mark the point and push both halves onto the stack. If L = 0 (the start and end coincide, as on an out-and-back route), compute the distance to that point and take the multiplier to be one.
A stack instead of recursion is not a whim: in the eighth test every split nips off a single point, and the recursion would go a thousand deep, which is Python’s default limit.
The numbers do not overflow: coordinates up to 10⁴, differences up to 2·10⁴, the squared length up to 8·10⁸, products up to 6.4·10¹⁷, with the int64 limit about 9.2·10¹⁸.
4+Solution
5Complexity
Each pair is a pass over the points between its ends. If the farthest point splits a piece roughly in half, O(n log n) in all; in the worst case, as in the eighth test, O(n²), half a million distances for a thousand points.
6Common mistakes
- The distance to the line rather than the segment. Many textbook versions of the algorithm do this, and it is a wrong solution to this problem. A point far beyond the end of a chord but close to its extension seems near and vanishes. In the second example the trail leads to a viewpoint and returns, and the viewpoint disappears. On the real trails in the tests this mistake happens not to show: their chords do not extend that far beyond their ends.
- Floating point. Roots and divisions give distances that may differ in the last digit for equidistant points, and “the first maximum” becomes a lottery.
- A non-strict comparison. A point at distance exactly ε is thrown out: the condition is “strictly greater”. In the test with zero tolerance this decides whether points lying exactly on a chord remain.
Algorithms behind it
O(n log n) typically, O(n²) in the worst case
2 problems
GEO
Technique
Vectors and orientation
The sign of the cross product is a left or right turn; almost all of computational geometry stands on it.
O(1) per turn
2 problems