7

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

我想出了如何在它与一个圆相交时找到最近的自由位置，甚至当涉及两个圆时。但是，我找不到一个健壮的算法来处理任何排列中具有任意数量的圆的复杂情况。

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

任何形式的建议（参考、方法或（Java）库）。

ps 如果解决方案包括确保圆保持在特定边界框内（即显示），则加分。

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

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

请注意，这并不完美，但在我的情况下已经足够好了，用户在屏幕上拖动新圆圈。它在大多数情况下都有效，而在某些情况下则无效，通常当有许多圈子非常靠近时，新圈子只会停留在最后一个位置（这是有效的）。然后，用户可以决定将其拖得更远，并更精确地确定他希望新圆圈去哪里。

4

3 回答 3

4

这不是一个完整的答案，但您可以将其合二为一。

假设您已经放置了半径为 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）中该怎么办。也许只允许一定数量的步骤，然后退出。毕竟，可能没有合适的地方放圆圈。

于 2013-10-15T09:02:27.727 回答
2

要计算一个点和一个圆之间的距离是中心，考虑到你的 Circle 类是这样的：

public class Circle{
    int x;
    int y;
    int radius;
}

public interface CircleHelper{
    public int distanceBetweenCircleAndPoint(Circle c, Point p);
    public int distanceBetweenTwoCircles(Circle c1, Circle c2);
}

首先，我会考虑使用Quadtrees并检查是否有没有周围圆圈的四边形

四叉树

可以考虑圆的半径来选择四叉树深度。

因此，如果您在其中一个四边形中有一个点，您将查看其周围的四边形以检查那里是否有任何圆圈，然后从该点向空四边形的方向移动。

我希望你能理解我的方法

于 2013-10-15T07:34:26.727 回答
0

这是一个适用于不同半径的解决方案，如果所有半径都相等，则可以简化，就像您的情况一样。我们首先稍微变换一下问题。我们不是在其他圆中拟合一个圆，而是将所有其他圆的半径扩大到我们要放置的圆的半径，而是尝试在这些延伸的圆之外放置一个点。这相当于原来的问题。我们进行如下：

  1. 首先是一个特殊情况。如果该点在所有圆圈之外，我们有一个简单的解决方案。
  2. 找到该点所在的所有圆圈。计算其圆周上的最近点（只需沿半径从原点移出）。
  3. 找到圆对之间的所有交点。
  4. 合并第 2 步和第 3 步中的点集，并通过查找未被任何其他圆圈覆盖的点来过滤这些点。
  5. 从剩余的集合中选择最近的点。完毕！

这似乎是 O(n^3)，所以不是非常快，但如果你的集合不是太大的话应该是可行的。

于 2020-03-25T20:19:27.837 回答