algorithm - 找到包含一组点的两个平行平面的算法

Question

我正在使用这篇论文来实现一种算法，用于确定无人机最安全的着陆点。

为此，我试图找到两个包含一组 9 个点的平行平面，同时最小化这两个平面之间的距离 r。

r 将代表地形的粗糙度。

我想要解决问题的一般策略或描述解决方案的论文的链接。

Answer 1

你能做到以下几点：

1. 找到9 个点的凸包
2. p对于凸包中的每个平面，找到最远的pt不在其中的点p，让第二个平面平行p并通过pt并计算距离
3. 取最小值

Answer 2

目标是找到正常的飞机。然后建造飞机很容易。

并且有有限数量的平面法线候选：凸包边缘向量的叉积（这包括但不限于面法线）。对于这个点数，您可以将它们全部计算在内。

为什么？

• 每个平面都接触一些非零数量的点（否则它可以移动得更近）。
• 如果我们可以稍微旋转平面而不会失去与这些点的连接，距离将会减小。
• 所以最优平面不能旋转。
• 如果一个平面接触两个点，它只能围绕这个边缘旋转。
• 如果一个平面接触两个不平行的边，它就不能旋转。
• 那么它的法线是那些边缘向量的叉积。