求具有圆的二维空间中任意点[x，y]的圆的最近自由位置

Question

我正在做一个游戏，用户玩家在屏幕上放置圆圈。重要的是圆圈永远不会重叠，所以我需要找出离光标最近的可能的空闲点。我已经找到了圆包装算法，但它们似乎不适合我的问题。我也解决了一个类似的问题在过去的盒子（这里），但对于圆形，我似乎无法弄清楚。

我想出了当它与一个圆相交时，或者甚至涉及两个时，我如何才能找到最近的自由位置。然而，我找不到一个健壮的算法，可以处理在任何排列中有任何数目的圆的复杂情况。

问题的精确描述：我有一个2D空间，有任意数量的不相交的圆，都有相同的半径（尽管这可能不重要）。我想为下一个圆找到一个位置，使它不与任何其他圆相交，并且哪个中心[x，y]最接近一个指定的位置[x，y]。

附注。如果解决方案包括确保圆圈保持在特定的边界框内（即显示），则可获得奖励。

我的最终解决方案：（基于大卫·华莱士的建议）

• 计算两个圆的中心之间的最小距离（在我的例子中，所有的圆都是相同的大小，所以总是2*半径）
• 列出比最小距离更接近鼠标位置的所有圆圈
• 如果0重叠：全部良好！
• 如果1个重叠：沿着从比较圆心到鼠标位置的向量，将新圆心移动到与比较圆心的最小距离
• 如果2个重叠：找出两个重叠的圆相交的地方。将新圆圈放置在最接近鼠标位置的交叉点上。如果此位置仍与任何圆重叠，则移动到另一个交点。如果那一个不起作用，就离开新的圆圈。
• 如果3个重叠：与2个重叠相同，只取最接近新圆的两个圆。

请注意，这并不完美，但在我的例子中，用户正在屏幕上拖动新的圆圈，这已经足够好了。它在大多数情况下起作用，在那些情况下它不起作用，通常当有许多圈非常靠近时，新的圈只是停留在上一个位置（这是有效的）。然后，用户可以决定进一步拖动它，并更精确地确定他想要的新圆圈的位置。

Answer 1

这不是一个完整的答案，但你也许可以把它变成一个。

假设你已经放置了半径为r1,r2,r3...rn的圆圈,圆心为C1,C2,C3...Cn,而你要放置一个半径为rz的新圆圈,新圆圈的中心必须在一组“放大”的圆圈之外,圆心为C1,C2,C3...Cn；半径(R1+RZ),(R2+RZ),(R3+RZ)...(RN+RZ)。所以如果光标在点P，那么就有一些情况需要考虑。

（1）如果P不在任何一个放大的圆中，那么问题就解决了。

（2）如果P只在其中一个放大的圆内，那么沿着该圆的半径向外移动，直到你到达所有放大的圆外的一点，或者直到你到达另一个放大的圆。前一种情况简化为情景（1）；后者简化为设想方案（2）。如果P恰好是圆心，选择一个任意的方向。

（3）如果P在几个圆中，那么求出P到它所在的圆心的方向。找到两个方向之间有最宽间隔的方向，然后将这个角度平分，就可以算出该往哪个方向走。例如，如果圆心的方向是30deg、120deg和330deg，那么将120deg和330deg之间的夹角平分，然后朝225deg的方向移动。朝那个方向前进，直到你到达一个圆的边缘，然后重新计算。继续这样做，直到回到场景（2）。

我想不出的是，如果你陷入场景（3）该怎么办。也许只允许一定的步数，然后退出。毕竟有可能是没有合适的地方放圆圈。