Overview
Ramer-Douglas-Peucker recursively keeps the farthest point from a segment when that distance exceeds a tolerance.
CoreSource checked
Ramer-Douglas-Peucker
Simplifies a polyline by removing points whose deviation is below a tolerance.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Intermediate
- Family
- Curve Simplification
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 3
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Douglas-Peucker
Core Concepts
polyline simplificationdistance tolerancerecursive splitshape preservation
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n log n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use when collision and intersection tests needs polyline simplification.
- Use when the input matches the assumptions behind curve Simplification.
When Not to Use
- Avoid when floating-point robustness is critical and no tolerance strategy is defined.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Simplifies a polyline by removing points whose deviation is below a tolerance
- Uses polyline simplification and distance tolerance to guide the work.
- Produces geometric relation, simplified shape, or constructed geometry.
Use Cases
- Collision and intersection tests
- Shape analysis
- Geometry processing
Inputs
- Points, segments, polygons, or meshes
- Query shape or tolerance
Outputs
- Geometric relation, simplified shape, or constructed geometry
Key Formulas (1)
Simplification decision
keep point if maxdistance > ε
keep point if max_distance > epsilonKeeps a curve point only when it exceeds the simplification tolerance.
Pseudocode
- 1.Prepare the inputs and state needed for Ramer-Douglas-Peucker.
- 2.Apply the polyline simplification step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return geometric relation, simplified shape, or constructed geometry.
Canonical Example
- Input
- Ramer-Douglas-Peucker input with a small representative case
- Output
- Geometric relation, simplified shape, or constructed geometry
- Explanation
- Ramer-Douglas-Peucker applies polyline simplification to produce geometric relation, simplified shape, or constructed geometry.
Implementation Notes
- Use robust orientation and tolerance checks for boundary cases.
- Keep the polyline simplification step separate enough to test independently.
Common Pitfalls
- Degenerate cases such as collinear points or shared edges often need explicit handling.
- Forgetting to check edge cases can make Ramer-Douglas-Peucker look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasDraw the input shapes, active tests, and generated geometric result.
Step 1 of 4: Prepare the inputs and state needed for Ramer-Douglas-Peucker.
geometry-mechanismNotes
Ramer-Douglas-Peucker should be used with the assumptions and tradeoffs of curve Simplification in mind.
Sources (3)
What each reference supports for this entry.
Computational Geometry: Algorithms and Applications
BookComputational geometry textbook support for Ramer-Douglas-Peucker's geometric model, data structures, and robustness concerns.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Ramer-Douglas-Peucker's problem context, known alternatives, and practical selection tradeoffs.
Open sourceDouglas-Peucker Line Reduction
PaperOriginal line-reduction reference for recursively simplifying digitized polylines by distance tolerance.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborQuadric Error Mesh Simplification
Both simplify geometry while trying to preserve shape.
Related Algorithms
Tags
Computational GeometryCurve SimplificationGeometryDistance Metric