去听了Ming-Ting Sun老师的一个讲座,大概内容是如何通过RGB-D Image进行物体的3D重建,忽然就想起了两年前的那道题...

给定两个点集,如何判定其中一个是否可以通过平移、旋转和缩放使得与另一个重合。

如果能够找到一种合理表示方式去描述点集,就能比较方便地在点集上做运算。这就要求选取的表示方式既能唯一地表示出点集,又能在这种表示下,对点集进行操作的时候可以操作到整体而不破坏其原有的作为整体的性质..有点拗口,大概就是能体现出又不改变点集作为一个整体的性质,每次的操作针对的都是整体,和坐标本身没有多大关系。

不难想到可以用某个点作为中心点,用其他所有点到该点的距离和偏角去表示整个点集,但是这两个点集其实是分布在不同的坐标系中,这就说明不能用一个固定坐标的点去表示。此时就需要选取一个和点集本身有关的点或者表示方式去表示,其中一个是质心,另一个是相对位置。

如果选取了质心,我们可以计算出每一个点到质心的距离和偏角,并且可以把距离归一化,质心有一个很好的性质,就是无论怎么缩放,平移,旋转,其他所有点到质心的归一化距离和偏角都是不会改变的,此时可以把一个点集表示成距离、偏角间隔分布的序列;

如果选取了相对位置,可以首先把所有点进行极角排序,然后每次计算相邻两个点的距离和偏角,进而归一化距离,这样也能够通过距离和偏角的序列把点集表示出来;

现在两个点集的表示都有了,如果把其中一个的序列重复两遍,那么在起点未知,点集重合的情况下,一定存在序列的匹配,此时无论使用O(n * m)的大暴力还是O(n + m)的kmp都能够优雅地解决本题了..

Orz ... 翔神 ...