Papers by Keyword: Delaunay Triangulation

Abstract: A new algorithm for TSP which is an improved ACO combined with MMAS and CSDT is proposed. MMAS can prevent the search from local optimum and search stagnation. We use candidate set strategy based on the Delaunay triangle (CSDT) in order to reduce serch space and accelerate the speed of the algorithm. Additionally, pheromone update and parameter optimization are detailed in this paper. The comparison analysis of the new algorithm, basic ant colony algorithm and MMAS algorithm is also given by using TSPLIB experimental data. Finally, we give an actual TSP case and compute the optimum solution by our new algorithm.The results show that the new algorithm is validity and effectively.

Abstract: Aiming at the folds caused by the sparse data in the process of DTM (Digital Terrain Model), this article proposed a method of interpolating spatial control points based on Delaunay triangulation and Kriging interpolation algorithm. The terrain data of an area with complex terrain in Xianyang was used to construct terrain model according to the proposed algorithm. Experimental results show that the method can finish the interpolation of the terrain denser data quickly and accurately, and it provides an efficient technological tool for building a true three-dimensional terrain model.

Abstract: Evaluation methods for the spatial distribution uniformity of a large number of particles have important applications in a range of scientific and industrial problems. We report a quantitative image-processing method to evaluate the spatial distribution uniformity of particles using the Voronoi tessellation and Delaunay triangulation. Given the geometric particle centroids, we constructed the Voronoi tessellation and Delaunay triangulation. For each of the Voronoi cell, the volume, facet area, and number of neighbors (facets) were calculated. For the Delaunay simplices, the volume and the distance between neighbors were calculated and the distributive characteristics were compared between different particle patterns. Simulation results demonstrated that distributions of the above metrics were numerically related to the uniformity of the particle spatial displacement. More studies are needed to further validate the results and refine the method.

Abstract: Fingerprints are graphical ridge and valley patterns on the tips of human fingers. Owing to their uniqueness and permanence, the use of fingerprints is considered to be one of the most reliable methods of personal verification. Fingerprints are today among the most popularly used biometric modalities in automatic verification systems. At the same time, Protecting the privacy of Fingerprint is an important one, here a novel system propose protecting fingerprint by combining two different fingerprints. In the enrolment stage, fingerprints will be captured from two different fingers. Minutiae positions are extracted from one fingerprint (its the detailed pattern of the fingerprint). The orientation, (it indicates the flow of ridges and valleys) from other fingerprint, and the reference points are calculated from both the two fingerprints. Extracted combined minutiae templates are stored into database. Here A Delaunay Triangulation indexing scheme has been designed for protecting biometric template and non-invertible template are calculated for verifies the authorized person. By using the Delaunay triangulation method fingerprint privacy has to be improved.

Abstract: This paper uses OpenMP parallel standardsin massive data Delaunay triangulation.Based on the Fork/Join parallel mode in OpenMP, a quad-tree is designed to divide and map the point cloud data.And the hierarchical implementation of triangulation and merging operations are based on it. A WFM-JLP algorithm is used to schedule triangulationand merging operations in order to achieve better load balancing. Experiment show the proposed method can greatly reduce the real-time memory and computing time.

Abstract: Amongst the flourishing Delaunay Triangulation methods, growth algorithm has been widely accepted because of its reputation of being simple and elegant. However, the parallelization of growth algorithm has not been fully exploited. In this work, a novel Growth algorithm of Delaunay Triangulation is proposed. The point cloud is first divided into two parts by a suitable curve and the separated areas are calculated by incremental algorithm. Triangles which cross with the curve are generated by a growth algorithm associated with uniform grid. At the process of merging, these grew triangles are used to detect incorrect triangles of the incremental algorithm areas. Method about generating triangles on curve is elaborated and a simple way to detect interferential triangles is also explained. With above method, triangulation calculation can be parallelized. Unlike the traditional divide-and-conquer method, no flip operation is needed in the proposed methodology. Thus, three dimensional applications are also made possible. A comparative research between tradition incremental algorithm and the proposed method has been conducted. Results show, the algorithm has a higher performance with less computation time.

Abstract: Target position is a critical step in the process of constructing Delaunay triangulation. This paper establishes an improved incremental insertion method which realizes fast location based on moving center of gravity along the search direction. It is effective to solve unstable searching path problem usually occurring in some special cases, such as the line from target point to current center of gravity passes through a vertex of a triangle or coincides with a triangle edge. Simulation results show that there exists only location path using this method and the constructing efficiency is increased.

Abstract: This paper proposes an easy approach to obtaining 3D surface models in parametric CAD software products from random sets of points, based on the analogy of level curves from geodesic disciplines. The points could be obtained from measurements on existing mechanical parts, as a stage in reverse engineering processes, or can be defined arbitrary in space, as part of the design process. The present research shows that good approximations of the true surface can be obtained by measuring a relative small group of carefully selected points and constructing level curves, following the same procedure as in the case of topography. The instrument to build level curves is an original application developed for AutoCAD using VB.NET which allows the user to construct the level curves parallel to the xy plane for any number of points in space. We tested the application on more set of points sampling the same surface, obtaining the level curves in AutoCAD and using these to build the final 3D model. The surfaces obtained this way were then compared to draw some conclusions regarding the influence of the number of sampled points on the precision of the model.

Abstract: The need for sensor interoperability has increased tremendously in many large-scale fingerprint applications such as e-commerce, welfare-disbursement and e-education. In this paper, we present fingerprint scaling, an innovative fingerprint system module, which resizes the fingerprint images to solve the problem of sensor interoperability with minimum modification to existing system. In template-based scaling methods, we have developed an estimation method using Delaunay triangulation algorithm. The efficacy of the scaling technique has been assessed by embedding a scaling module into a traditional fingerprint recognition system. Our experiments have shown very positive results. Experimental results indicated that the accuracy and robustness of fingerprint system can be improved effectively by embedding such a scaling module into the traditional framework of fingerprint systems under multi-sensor situation.

Abstract: Cellular mobile communication system divides the service area into several adjacent cells; each cell sets up a base station. In the traditional cellular representation, we always use regular hexagon to represent the cell. In the practical engineering applications and wireless network planning simulation systems, as the programming environment is complex and diverse, using the regular hexagon to represent the cellular network has limitation. This paper used Thiessen polygon and spatial analysis method to describe the cell service area with a polygon. This method intuitively displayed the relationship between the scope of service and its place with each other in space. For the Pre-construction and later optimization of wireless network planning it has a positive role.