一个JavaScript算法，通过检查点是否在固定大小的圆内来确定其位置。

Question

因此，我有一个位于未知位置的点，需要通过编程方式找到它。我们只能通过调用一个特殊的函数 sThePointWithin500MetersOfLocation(x, y) 来尝试确定其位置，该函数如果传入的坐标点与目标点距离在500米以内，将返回真。我的目标是找出该点的确切位置或尽可能接近的位置。可以使用哪些算法来实现这一目标呢？

需要注意的是，isThePointWithin500MetersOfLocation 函数执行一次大约耗时30秒，所以调用次数越少越好。

已知该点始终位于以[0, 0]为中心、半径为500米的范围内（即isThePointWithin500MetersOfLocation(0, 0)恒为真）。

Steve · Answer

以下是用于测试某点是否位于另一点周围一定半径内的代码示例：

function testForPointInCircle(cx, cy, radius, tx, ty) {
    let dx = tx - cx;
    let dy = ty - cy;
    let distance = dx * dx + dy * dy;
    return distance < (radius * radius);
}

let p1 = { x: 0, y: 500 };
let p2 = { x: 25, y: 450 };

console.log(
    testForPointInCircle(p1.x, p1.y, 70, p2.x, p2.y),
    testForPointInCircle(p1.x, p1.y, 10, p2.x, p2.y),
    p1.y
);

let p3 = { x: 10, y: 1000 };

// 如果你不知道测试点的坐标，可以使用循环配合猜测值调用该函数，直到返回真值。
while (!testForPointInCircle(p3.x, p3.y, 25, p1.x, p1.y)) {
    p1.y += 5;
}
console.log(p1.y);

JLRishe · Answer

让我们先略过如何找到isThePointWithin500MetersOfLocation的第一个结果，因为这听起来像是一个过于简化的问题，不太可能完全解决。但是一旦找到首个结果，我们可以开始进行二分搜索。或者，考虑到我们处理的是圆形，初始阶段可以采用三元搜索：任意半径为r的圆可以通过三个相同半径的圆完全覆盖，这三个圆的中心位于原始圆上，并且它们的中心彼此相隔120度。

接下来就按照这个思路操作：

customElements.whenDefined(`graphics-element`).then(() => {

const graphics = document.getElementById(`illustration`);
  let code = circleGraphics.toString();
  code = code.substring(code.indexOf(`{`)+1, code.lastIndexOf(`}`));
  graphics.loadSource(code);
});

function circleGraphics() {
  let p, circles = [], current, a=0, s=TAU/3, nextButton, matches = [];
  let bisecting = false;

  function setup() {
    setSize(150, 150);
    let angle = random(0,TAU);
    let radius = random(0, 40);
    p = new Point(50, 50);
    current = new Circle(75, 75, 50)
    circles.push(current);
    matches.push(current);
    nextButton = addButton(`next`, tryNext);
  }

  function draw() {
    clear();
    setColor(`black`);
    point(p.x, p.y);
  
    if (bisecting) {
      matches.forEach(c => {
        setFill(c.fill ?? `#F001`);
        circle(c.x, c.y, c.r);
      });
      showBisection();
    } else {
      circles.forEach(c => {
        setFill(c.fill ?? `#F001`);
        circle(c.x, c.y, c.r);
      });
    }
    
    if (matches.length === 2 && !bisecting) {
      nextButton.remove();
      nextButton = addButton(`which means...`, () => {
        nextButton.remove();
        bisecting = true;
        redraw();
      });
    }
  }
  
  function showBisection() {
    // 此时我们已经缩小了点可能所在的区域。如何最佳地对该区域进行分割呢？
    // 答案是：放置更多的圆圈。
    // 由于这些圆圈具有相同的半径，找到它们的交点非常简单：
    const [c1,c2] = matches;
    const { r } = c1;
    const a = atan2(c1.y - c2.y, c1.x - c2.x);
    
    // 两个圆圈的交点坐标分别是？
    setColor(`black`);
    const p1 = new Point(
      c1.x + r * cos(a - s),
      c1.y + r * sin(a - s),
    );
    const p2 = new Point(
      c1.x + r * cos(a + s),
      c1.y + r * sin(a + s),
    );
    
    // 两交点之间的法向量是什么？
    let dx = p2.x - p1.x;
    let dy = p2.y - p1.y;
    const mag = (dx**2 + dy**2)**0.5;
    dx /= mag;
    dy /= mag;
    
    // 好的，现在我们关注新的感兴趣区域：
    setColor(`#FFF9`);
    rect(0,0,width,height);
    setStroke(`#0C0`);
    setFill(`#0C03`);
    arc(c1.x, c1.y, r, a+s, a-s+TAU);
    arc(c2.x, c2.y, r, a+s+PI, a-s+PI);
    
    // 使用交点和通过它们的直线作为视觉辅助：
    setColor(`black`);
    point(p.x, p.y);
    setColor(`#0004`);
    line(
      p1.x - huge * dx,
      p1.y - huge * dy,
      p2.x + huge * dx,
      p2.y + huge * dy
    );
    point(p1.x, p1.y);
    point(p2.x, p2.y);
  }  
  
  function tryNext() {
    const { x, y, r } = current;
    // 在原始圆周上放置一个新的圆，并检查点是否在这个新圆内。如果是，则我们已经缩小了点可能所在的区域。
    const c = new Circle(x + r * cos(a), y + r * sin(a), r);
    circles.push(c);
    const d = dist(c.x, c.y, p.x, p.y);
    const pointIsInCircle = d < c.r;
    if (pointIsInCircle) {
      c.fill = `#0F01`;
      matches.push(c);
      a = 0;
    } else {
      // 不合适，尝试下一个圆       
      a += s;
    }
    redraw();
  } 
}

当然，这仅是第一轮迭代：当我们有两个圆重叠时，下一步需要找出放置两个新圆的位置，用以对重叠区域进行细分。计算这两个新圆中心所需的三角函数运算，留给读者自行完成。

对于每个新圆的评估，要么得到“点在其中一个内”，这样我们得到了一个类似三角形的形状；要么得到“点在两者之内”，这时我们面临与之前相同的情况，只是形状更小：

示意图

我们可以分别对这些形状进行三分割和二分割，从而越来越接近“点的确切位置”。具体实现则留给读者（或发帖者）作为练习。