关于如何找到三个点的算法

Question

给定一组名为 S 的点和一个点 P。如何在集合 S 中找到三个点，s.t 这三个点可以形成三角形 T 并且 P 在三角形 T 中且时间复杂度最低？

任何编程语言都可以。伪代码也很好。

非常感谢!

Answer 1

在三角形内画一个点，然后从该点到角绘制直线。您应该看到这些线之间的角度都小于 180 度，并且当点移动到三角形之外时，其中一条线之间的角度在穿过三角形的一侧时达到 180 度。

因此，如果您将点视为 map 上的点，则将罗盘方位从 P 到其他每个点，然后对结果进行排序。如果排序后的值之间存在大于或等于 180 度的间隙(包括从 360 到 0 的环绕)，则 P 不在任何三角形内。

假设测试通过，考虑根据圆盘方位在圆上布置的所有点，然后选择一个任意点并在该点绘制通过圆的直径，将其一分为二。该直径的任一侧必须有其他点，否则我们将有 180 的间隙。在每一半中选择距离任意点最远的两个点。如果它们 >= 180 度，我们就有 180 度的差距。如果不是，则所有点彼此都在 180 度以内，并且我们有三个点包围原始点。

这个的复杂度是 O(n log n)，这对我来说似乎是合理的，但不一定是平均情况下最快的，尽管我怀疑它的最坏情况是合理的。根据您的数据及其呈现方式，可能会出现加速，这涉及首先随机选择少量点，希望它们包含一个包围 P 的三角形。