algorithm - 找到离其他 n 个点最远的点

Question

我正在尝试创建一个“逃离”算法，并希望首先找到“安全”点。也就是说，它们与其他点相对较远的点。

这是二维的(不是很重要)并且发生在一个固定大小的圆圈内。

我猜测平方距离之和会产生一个很好的起始方程，其中最高分离得最远。

至于选择点，我认为不可能求解 X,Y，但近似值就足够了。

我做了一些阅读并确定为了覆盖一个圆的面积，你需要 7 个半尺寸的圆(中心形成一个六边形，第七个在中心)

我可以遍历这些，所有这些都在开始的圆圈内。当我选择得分最高的球体时，我可以继续将它们分成 7 个球体。当然，不包括任何落在原圆之外的点。

然后我可以迭代到所需的精度或所需的级别。

为了扩展该方法，假设到达某个位置需要时间，虽然该位置可能是安全的，但中间的行程可能不安全。我应该如何将距离纳入等式，以便得出一个好的解决方案。

我想我可以将到新点的距离平方，然后乘以分数，然后从那里开始迭代。它会强烈支持本地景点，但我认为这是一种很好的行为。它会尝试解决附近的安全点，然后在重新计算后找到“出路”并继续潜入安全地点。

对此有什么想法，或者这个问题以前解决过吗？我看的时候没能具体找到这个问题。

编辑:

我引入了 Fortune 算法的 C# 实现，并在我的点周围添加了一些点以创建伪循环约束，因为我对算法的理解不够深入，无法手动调整它。

我现在意识到蓝线在节点之间创建了一条路径。我可以使用这些长度和周围点之间的距离来计算路径(遍历时间和危险)并将其与安全性(它试图到达的空心圆)进行权衡以确定最佳路线行动。通过研究这些相互作用的方式，我可以消除大部分我必须做的工作，只需使用 voronoi。此外，我的生成算法现在将使用它来确定 LEC 并在该位置生成。

Answer 1

你可以拿convex hull您的一组位置 - 凸包的顶点将为您提供一组“最远”点。接下来，取 centroid你逃离的点，然后确定凸包的哪个顶点离质心最远。例如，您可以通过将运动场划分为象限来加快速度 - 您只需要测试最远象限中的顶点(例如，如果质心位于正 x 正 y 象限中，那么你只需要检查负 x 负 y 象限中的顶点)；如果运动场的形状不规则，那么这可能不是一个选择。

作为逃到最远点的替代方法，如果您有一个要逃离的起点(例如，您要逃离的点是敌人，并且玩家角色当前位于 X 点，这表示它起点)，那么不是让玩家逃到最远的点，而是让玩家沿着最快将他们从敌人的质心带到他们的轨迹 - 从敌人的质心穿过玩家的位置绘制一条射线，那条射线会告诉你玩家应该逃离的方向。

如果玩家角色被包围，那么这两种算法都会给出无意义的结果，但在那种情况下，玩家角色实际上并没有任何可行的选择。