Ramer–Douglas–Peucker algorithm
The Ramer–Douglas–Peucker algorithm, also known as the Douglas–Peucker algorithm and iterative end-point fit algorithm.
선분으로 구성된 곡선을 더 적은 수의 점을 사용하여 유사한 곡선으로 줄이는 알고리즘입니다.
이는 지도 제작 일반화 (cartographic generalization)를 위해 개발된 최초의 성공적인 알고리즘 중 하나였습니다.
Idea
알고리즘의 목적은 선분으로 구성된 곡선(일부 상황에서는 폴리라인이라고도 함)에서 더 적은 수의 점이 있는 유사한 곡선을 찾는 것입니다. 알고리즘은 원래 곡선과 단순화된 곡선 사이의 최대 거리(즉, 곡선 사이의 Hausdorff 거리)를 기반으로 '비유사'를 정의합니다. 단순화된 곡선은 원래 곡선을 정의한 점의 하위 집합으로 구성됩니다.