New approaches for Delaunay triangulation and optimisation

Sensor Placement in an Irregular 3D Surface for Improving Localization Accuracy Using a Multi-Objective Memetic Algorithm

Accurate localization is a critical task in underwater navigation. Typical localization methods use a set of acoustic sensors and beacons to estimate relative position, whose geometric configuration has a significant impact on the localization accuracy. Although there is much effort in the literature to define optimal 2D or 3D sensor placement, the optimal sensor placement in irregular and constrained 3D surfaces, such as autonomous underwater vehicles (AUVs) or other structures, is not exploited for improving localization. Additionally, most applications using AUVs employ commercial acoustic modems or compact arrays, therefore the optimization of the placement of spatially independent sensors is not a considered issue. This article tackles acoustic sensor placement optimization in irregular and constrained 3D surfaces, for inverted ultra-short baseline (USBL) approaches, to improve localization accuracy. The implemented multi-objective memetic algorithm combines an evaluation of the geometric sensor's configuration, using the Cramer-Rao Lower Bound (CRLB), with the incidence angle of the received signal. A case study is presented over a simulated homing and docking scenario to demonstrate the proposed optimization algorithm.

A Novel Type of Boundary Extraction Method and Its Statistical Improvement for Unorganized Point Clouds Based on Concurrent Delaunay Triangular Meshes

Currently, three-dimensional (3D) laser-scanned point clouds have been broadly applied in many important fields, such as non-contact measurements and reverse engineering. However, it is a huge challenge to efficiently and precisely extract the boundary features of unorganized point cloud data with strong randomness and distinct uncertainty. Therefore, a novel type of boundary extraction method will be developed based on concurrent Delaunay triangular meshes (CDTMs), which adds the vertex-angles of all CDTMs around a common data point together as an evaluation index to judge whether this targeted point will appear at boundary regions. Based on the statistical analyses on the CDTM numbers of every data point, another new type of CDTM-based boundary extraction method will be further improved by filtering out most of potential non-edge points in advance. Then these two CDTM-based methods and popular α-shape method will be employed in conducting boundary extractions on several point cloud datasets for comparatively analyzing and discussing their extraction accuracies and time consumptions in detail. Finally, all obtained results can strongly demonstrate that both these two CDTM-based methods present superior accuracies and strong robustness in extracting the boundary features of various unorganized point clouds, but the statistically improved version can greatly reduce time consumption.

Variable Density Filling Algorithm Based on Delaunay Triangulation

The quality of the filling algorithm in additive manufacturing directly affects the strength of the part. The commonly used 3D printing filling algorithm at this stage is the classic filling algorithm. The density of each part in the filling region is the same, and there is a cavity structure in the transverse direction, which makes the strength of the part in the transverse direction lower. Therefore, this paper proposed a new filling algorithm-variable density filling algorithm based on Delaunay triangulation. First, we performed concave-polygon-convex decomposition on the filling area to form printing sub-regions; then, the filling density value was set according to the required intensity of each region, and we used the Poisson disk sampling algorithm to generate the filling point set. Finally, Delaunay triangulation was performed on the generated point set to generate filled traces. The comparison with the two commonly used classical filling algorithms proves that the algorithm can improve the strength of the part to a certain extent, and the printing time and the consumption of consumables will not increase significantly.

Unsupervised Machine Learning for Improved Delaunay Triangulation

Physical oceanography models rely heavily on grid discretization. It is known that unstructured grids perform well in dealing with boundary fitting problems in complex nearshore regions. However, it is time-consuming to find a set of unstructured grids in specific ocean areas, particularly in the case of land areas that are frequently changed by human construction. In this work, an attempt was made to use machine learning for the optimization of the unstructured triangular meshes formed with Delaunay triangulation in the global ocean field, so that the triangles in the triangular mesh were closer to equilateral triangles, the long, narrow triangles in the triangular mesh were reduced, and the mesh quality was improved. Specifically, we used Delaunay triangulation to generate the unstructured grid, and then developed a K-means clustering-based algorithm to optimize the unstructured grid. With the proposed method, unstructured meshes were generated and optimized for global oceans, small sea areas, and the South China Sea estuary to carry out data experiments. The results suggested that the proportion of triangles with a triangle shape factor greater than 0.7 amounted to 77.80%, 79.78%, and 79.78%, respectively, in the unstructured mesh. Meanwhile, the proportion of long, narrow triangles in the unstructured mesh was decreased to 8.99%, 3.46%, and 4.12%, respectively.