A Selection Method of Massive Point Cluster Using the Delaunay Triangulation to Support Real-Time Visualization

One of the goals of map generalization is to achieve real-time visualization of massive entities while adapting to zoom-in/zoom-out conditions. Unlike traditional map generalization, this type of scaling operation does not simplify the data to produce a final result; it only outputs temporary visualization data. To meet the current visualization scale requirements, we insert a simplification algorithm prior to visualization to process the data. Taking point simplification as an example, this study proposes a novel massive point selection method and optimizes the entire algorithmic process, enabling the method to quickly and efficiently handle point selection for datasets ranging from tens of thousands to millions of points. The method employs a geometric construction, namely a Delaunay triangulation, is applied to discover the distribution characteristics with real-time efficiency. Initially, we construct the Delaunay triangulation of the point cluster. Subsequently, we calculate the mean distance of each point as the selection feature. Finally, we incorporate a ‘fixed point’ concept to rank and stabilize the points during the selection process. Experimental results indicate that our method not only achieves commendable performance in considering spatial structure, comparable to both traditional and state-of-the-art methods but also demonstrates significantly higher efficiency. This method can efficiently handle point selection for datasets ranging from tens of thousands to millions of points in a short time, thereby greatly enhancing the practicality of the algorithm in complex point selection scenarios.