A Linear-Time Online Simplification Algorithm for Polylines and Polygons using a Sliding-Window Area Threshold

Abstract. This paper introduces the Cumulative Triangle Routine (CTR), a novel linear-time algorithm for simplification of polylines and polygons. CTR is designed as an online algorithm, processing points sequentially without requiring the complete geometry to be available in advance. So it can be used for real-time stream of data received from various sensors. The algorithm employs a cumulative areal threshold approach to preserve important points while achieving proper data reduction without introducing sever visual distortion. We present an evaluation comparing CTR against three established simplification methods: Ramer-Douglas-Peucker (RDP), Visvalingam-Whyatt (VW), and Normal Opening Window (NOPW). Experimental results demonstrate CTR's superior computational efficiency, maintaining consistent O(n) performance across datasets ranging from hundreds to millions of points. Qualitative analysis reveals that CTR produces visual outputs comparable to VW, particularly for man-made structures and right-angle features, while avoiding the angular distortions characteristic of RDP. Key advantages of CTR include: (1) linear-time complexity, (2) the ability to produce visually comparable results to established simplification algorithms, and (3) support for online processing of streaming data. The algorithm is useful for web-based mapping, real-time visualization, and large-scale spatial data applications where both performance and visual fidelity are essential.