# Estimating the local compression/expansion ratio for a transformation on a point cloud

Let's say we have an unorganized point cloud P1 with N points, each with coordinates {x,y,z}. We apply non-rigid transformation to P1 (translation + rotation + warping), to obtain point cloud P2. Given a pair of corresponding points in P1 and P2, how can we efficiently estimate the change in local point density around this point without performing explicit meshing? In other words, how to estimate the local space compression/expansion around each point after the transformation? Consider that the expansion/compression may not be isotropic.

If you also wish to know about the anisotropy of the stretching you should look at computing the right Cauchy-Green deformation tensor, $\Delta$, and it's associated eigenvalues and eigenvectors. The eigenvectors of this tensor define the primary axes of deformation and the eigenvalues are equal to the squares of the stretching ratios along these axes. The density ratio is given by the square root of the determinant of $\Delta$ which equals the square root of the eigenvalues: $\rho_2/\rho_1 = \sqrt{\det(\Delta)}= \sqrt{\lambda_1 \lambda_2 \lambda_3}$.
If you are not able to perform the transformation on arbitrary points you can use the points you know to estimate the deformation tensor. The simplest method involves choosing N neighbors of a given point and using those to estimate the deformation tensor. This can be formulated as a least-squares problem to determine the components of a 3x3 transformation matrix, $\Phi$, such that $\Phi~(\text{P}1_i-\text{P}1_0) = (\text{P}2_i-\text{P}2_0)$ where subscript $0$ denotes the point of interest and $i$ denotes the neighbors. In 3D you will need a minimum of 3 neighbors to determine $\Phi$ (3 points x 3 components {x,y,z} gives 9 linear equations for the 9 entries in $\Phi$). The deformation tensor is then given by $\Delta = \Phi^\intercal \Phi$. This method is first order accurate in the point spacing and quickly loses accuracy when the points are far enough apart so that the transformation is not locally linear on the neighborhood being used. If my memory is correct, this is the method that is used for computing the deformation tensor to find LCS on unstructured meshes in this paper. As a side note, this method is provably equivalent to using centered finite differences (and recovers second order accuracy) if the you use 6 neighbors at the locations of the points in the finite difference stencil.