找到离线最远的点

Question

我有一个点数组，以及另外两个点（A 和 B）。最后两个点形成一条线，我试图找到数组中距离该线最远的点。我将如何在 Java 中做到这一点？

我想知道这是否类似于求 A 和 B 之间的距离，但这在我的脑海中不太合适。

附加信息：我认为这是一条线段。鉴于这是 QuickHull，我不知道它是否有区别。在数学和公式方面，我从来都不是最优秀的，所以更多的解释更好。谢谢！

Answer 1

请注意，数组中的每 3 个点形成一个三角形，其面积表示为：[a,b,p][其中 是到 的距离]p(ab) * h /2hpab

您可以计算这些三角形创建的面积，并选择最小的。由于ab对于所有人来说都是恒定的 - 它保证具有最小面积的三角形也将具有最小面积h。

您可以使用以下方法找到它[每个三角形的面积]

T=(1/2)* abs((x_a - x_p) * (y_b-y_a) - (x_a - x_b)* (y_p - y_a))

[其中x_a,x_b,x_p和分别y_a,y_b,y_p是x,y的坐标a,b,p]。

• 虽然我发现这种方法非常优雅，但我相信还有更好的方法可以做到。