我有一个可变大小的矩形网格，但平均为 500x500，其中包含少量 x,y 点(少于 5 个)。我需要找到一种算法，该算法可以返回距离任何其他点最远的 x,y 对。
上下文:应用程序的屏幕(网格)和一组 x,y 点(敌人)。玩家死了，我需要一个算法让他们在远离敌人的地方重生，这样他们就不会在重生后立即死亡。
我目前所拥有的:我编写的算法有效但在较慢的手机上表现不佳。我基本上是将网格分成正方形(很像井字游戏)，然后为每个正方形分配一个数字。然后我检查每个方格是否有所有敌人，并存储每个方格最近的敌人。数字最大的方格是距离最近的敌人最远的方格。我还尝试对现有点进行平均并做类似的事情，虽然性能是可以接受的，但该方法的可靠性不是。
最佳答案
这是我能想到的最简单的算法，但仍能提供良好的结果。它只检查 9 个可能的位置:角、边的中间和中心点。大多数时候，玩家最终会被困在角落里，但显然你需要的位置比敌人多。
该算法在我的 i5 台式机上运行时间为 0.013 毫秒。如果您将 Math.pow() 替换为 Math.abs()，则可以减少到 0.0088 毫秒，但显然结果不太可靠。 (奇怪的是，这比我使用三角函数的其他答案慢。)
(重复)运行代码片段将显示在 Canvas 元素中随机放置敌人的结果。
function furthestFrom(enemy) {
var point = [{x:0,y:0},{x:250,y:0},{x:500,y:0},{x:0,y:250},{x:250,y:250},{x:500,y:250},{x:0,y:500},{x:250,y:500},{x:500,y:500}];
var dist2 = [500000,500000,500000,500000,500000,500000,500000,500000,500000];
var max = 0, furthest;
for (var i in point) {
for (var j in enemy) {
var d = Math.pow(point[i].x - enemy[j].x, 2) + Math.pow(point[i].y - enemy[j].y, 2);
if (d < dist2[i]) dist2[i] = d;
}
if (dist2[i] > max) {
max = dist2[i];
furthest = i;
}
}
return(point[furthest]);
}
// CREATE TEST DATA
var enemy = [];
for (var i = 0; i < 5; i++) enemy[i] = {x: Math.round(Math.random() * 500), y: Math.round(Math.random() * 500)};
// RUN FUNCTION
var result = furthestFrom(enemy);
// SHOW RESULT ON CANVAS
var canvas = document.getElementById("canvas");
canvas.width = 500; canvas.height = 500;
canvas = canvas.getContext("2d");
for (var i = 0; i < 5; i++) {
paintDot(canvas, enemy[i].x, enemy[i].y, 10, "red");
}
paintDot(canvas, result.x, result.y, 20, "blue");
function paintDot(canvas, x, y, size, color) {
canvas.beginPath();
canvas.arc(x, y, size, 0, 6.2831853);
canvas.closePath();
canvas.fillStyle = color;
canvas.fill();
}<BODY STYLE="margin: 0; border: 0; padding: 0;">
<CANVAS ID="canvas" STYLE="width: 200px; height: 200px; background-color: #EEE;"></CANVAS>
</BODY>关于algorithm - 与其他点相比，找到网格中最远的点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31952383/