在圆形的2D空间中为任意点[x,y]找到圆的最近自由位置

Question

我正在制作一个用户玩家在屏幕上放置圆圈的游戏.重要的是圆圈永远不会重叠,所以我需要从光标中找出最近的可能自由点.我找到了圆形打包算法,但它们似乎不适合我的问题.我也在过去为盒子(这里)解决了类似的问题,但是用圆圈,我似乎无法弄明白.

我想出了当它与一个圆相交时,或者甚至当涉及两个时,我如何找到最近的自由位置.但是,我找不到一个可以处理任何排列中具有任意数量圆圈的复杂情况的稳健算法.

问题的精确描述:我有一个2D空间,任意数量的非交叉圆,都具有相同的半径(虽然这可能无关紧要).我想找到下一个圆的位置,使其不与任何其他圆相交,并且哪个中心[x,y]最接近指定位置[x,y].

任何类型的建议(参考,方法或(Java)库).

ps如果解决方案包括确保圆圈保持在特定的边界框内(即显示),则奖励积分.

我的最终解决方案:(根据David Wallace的建议)

• 计算两个圆心之间的最小距离(在我的例子中,所有圆都是相同的大小,所以总是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 到其所在圆的每个圆心的方向。找到它们之间间隔最宽的一对方向，并将该角度平分，从而计算出哪个方向前进的方向。例如，如果到圆心的方向是 30 度、120 度和 330 度，则平分 120 度和 330 度之间的角度 - 然后朝 225 度的方向前进。朝那个方向前进，直到到达圆的边缘，然后重新计算。继续这样做，直到回到场景 (2)。

我无法解决的是如果你陷入场景（3）该怎么办。也许只允许执行一定数量的步骤，然后退出。毕竟，有可能没有合适的地方放置法阵。