使形状适合点

Question

我试图将已知明确定义的形状（例如盒子，圆柱体;具有可配置的位置，旋转和尺寸）拟合到一组点，其中法线通过采样3D网格生成。我目前的方法是为每个形状定义自定义拟合函数，并将其传递给第三方优化函数：

fitness = get_fitness(shape_parameters, points)
best_parameters = external.optimise(get_fitness, initial_parameters, points)

（作为参考，我目前正在使用带有边界的Python 3和scipy.optimize.minimize，但语言无关紧要）。

这个矩形的适应度函数看起来像

def get_fitness(parameters, points):
    side_fitnesses = []
    for side in [top, right, bottom, left, back, front]:
        dists = get_side_distances(parameters, points, side)
        ndevs = get_side_normal_deviations(parameters, points, side)
        side_fitnesses.append(combine_dists_and_ndevs(dists, ndevs))
    fitnesses = choose_best_side_for_each_point(side_fitnesses)
    return mean(fitnesses)

然而，这意味着我必须确定异常值（有/没有缓存），我一次只能拟合一个形状。

例如（在2D中），对于这些点（带法线），我想得到以下结果：

请注意，返回了多个形状，并忽略异常值。通常，输入数据中可以有许多，一个或零个形状。后处理可以删除无效（例如太小）的结果。

注意：我的真正问题是3D。我有真实世界对象的3D网格表示的片段，这意味着我有更多的信息，而不仅仅是上面例子中的点/法线（如面部区域和连接）。

进一步阅读：

• Not well-defined shape-fitting
• Highly technical n-dimensional fitting
• Primitive shape-fitting thesis
• Unanswered SO question on something similar

PS：我不确定StackOverflow是否是此问题的最佳StackExchange站点

Answer 1

那么你将不得不处理带有体积的网格。这改变了很多事情......

1. 细分对象 选择所有封闭其内部的面孔......所以它类似于： Finding holes in 2d point sets? 所以只需在未使用的网格中找到一个点...并“填充”该体积，直到你击中它所组成的所有面。选择这些面作为新对象。并将它们设置为使用...当心触摸对象可能导致使用两次或更多的面孔... 您也可以在矢量数学/空间上执行此操作，以便测试从某个内部点到面部的线是否正在击中任何其他面...如果没有找到您的表面...类似于Hit test
2. 过程对象（可选） 您可以进一步将对象网格划分为“平面”对象，它由对属于同一平面的面进行分组......或者在封闭边/轮廓内...然后检测它们是什么 三角形 长方形 多边形 圆盘 从计数和面部类型，您可以检测基本对象，如：

   cone = 1 disc + 1 curved surface with singular edge point parallel to disc center
   box/cube = 6 rectangles/squares
   cylinder = 2 discs + 1 curved surface with center axis going through discs centers

3. 计算单个对象的基本几何属性（可选） 像BBOX或OBB，表面，体积，geom。中心，群众中心，... 现在只需确定它是什么类型的对象。例如，表面积和体积之间的比率可以提示球体或椭圆体，如果OBB匹配侧面它暗示框，如果geom和mass center是相同的，它暗示对称物体...
4. 将网格传递给可能的对象类型拟合函数 所以根据子弹＃2，＃3你有一个想法，哪个对象可以是哪个形状，所以只需用你的拟合函数确认它... 为了简化这个过程，您可以使用＃3中的属性，例如： ellipse matching 所以你可以为基本的3D形状提出类似的技术......