algorithm - 在由 (x,y) 点定义的折线中查找双切线

Question

我有 `System.Windows.Media.Point3D 集合代表一个自由形式对象的横截面。

它的形状总是或多或少像“海鸥翅膀”，“M”型，带有两个凸起和中间的“谷”。它在空间中的朝向是任意的，不能保证截面中只有中心谷是凹面。

我已经有一种方法可以检测到一个点，该点保证位于这些山谷之间，现在我想找到一对代表中心点周围“双切线”的点，即穿过它们之间的线两点保持所有其他点在同一侧，并且也外接起点。

下图显示了我想要实现的目标:

我相信叉积是找出三个点是“凹”还是“凸”的好方法，但还没有弄清楚如何执行循环(如何开始，递增什么，何时递增)停止)。

另外，虽然我可以使用蛮力(没有那么多点)，但那肯定会伤害我的感情。

Answer 1

确定顶点的凸包。不属于凸包顶点的顶点序列对应于凹面。根据您的描述，听起来总是只有一个凹面。凹性顶点序列的第一个和最后一个顶点就是你要找的直线的端点。