Delaunay: triangulation point-to-point kits with the best matching mesh

Question

I got a cloud with randomly distributed points and another cloud with the same points, but moved randomly. Thus, each point of cloud A has a corresponding point in cloud B.

Now I want to triangulate both clouds with the same triangle mesh, finding the mesh with the smallest intersections in both clouds.

Any ideas?

thanks

Answer 1

Create a random triangulation of points in cloud A and measure the number of intersections in both A and B. Then apply simulated annealing to randomly add / remove / move edges that retain the triangulation functions that you are interested in saving and measuring the number of intersections after each iteration .

As a starting point, if you do not want to start with a random set of edges, you can start by triangulating Delauny in A, and then measure the total number of intersections in B. Continue the simulated annealing as before.

Answer 2

First a very simple approach, (Delaunay) triangulate half the positions moved and use it for both clouds. This can lead to a good result if the movement is not too large.

Triangulation has intersections if negative oriented triangles exist. So, good triangulation for both clouds consists of triangles that are positively oriented in both clouds.

The approach may be similar to that, as mentioned, to create an initial triangulation in cloud A and try to locally eliminate negative oriented triangles in cloud B. Probably, standard flipping can solve the problem.

I think that you can check which points (region) cannot be triangulated well in both clouds, with the intersection of positive oriented triangles on both clouds and searching for points that are not in any intersection triangle. To do this, it is enough (necessary) to take the triangles node for the neighboring region (with neighboring nodes).