我正在制作一个游戏，其中用户玩家在屏幕上放置圆圈。重要的是，圆圈切勿重叠，因此我需要找出光标附近最可能的自由点。我发现了圆形填充算法，但是它们似乎不适合我的问题。过去，我也为box（here）解决了类似的问题，但是对于圆圈，我似乎无法弄清楚。
我想出了如何在与一个圆相交甚至是两个圆相交时找到最近的自由位置。但是，我找不到能够处理复杂情况的健壮算法，该复杂情况具有任意排列的任何数量的圆圈。
问题的精确描述：我有一个2D空间，其中包含任意数量的不相交的圆，并且所有圆都具有相同的半径（尽管这可能无关紧要）。我想找到下一个圆的位置，该位置将使其不与任何其他圆相交，并且其中心[x，y]最接近指定的位置[x，y]。
任何形式的建议都值得赞赏（参考，方法或（Java）库）。
ps奖励积分，如果解决方案包括确保圆保持在特定的边界框内（即显示）。
我的最终解决方案：（基于David Wallace的建议）
请注意，这并不完美，但在我的情况下（用户在屏幕上拖动新圆圈）就足够了。它在大多数情况下都起作用，而在大多数情况下却不起作用，通常是当有许多非常靠近的圆圈时，新圆圈仅停留在最后一个位置（有效）。然后，用户可以决定将其进一步拖动为适合，并更加精确地将其拖动到新的圆弧所在的位置。
这不是一个完整的答案，但是您可以将其合并为一个。
假设您已经放置了半径为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），该怎么办呢？也许只允许一定数量的步骤，然后退出。毕竟，可能没有合适的位置放置圆圈。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句