在二维空间中，针对任意点[x,y]寻找离该点最近的可以放置圆形的空闲位置。

Question

在二维空间中，针对任意点[x,y]寻找离该点最近的可以放置圆形的空闲位置。

javaalgorithmgeometryprocessing

7

我正在制作一个游戏，用户可以在屏幕上放置圆形。重要的是，这些圆形不能重叠，因此我需要找到最接近光标的可用空间。我已经找到了圆形打包算法，但它们似乎不适合我的问题。我之前也解决过类似的盒子问题（here），但对于圆形，我似乎无法解决它。

我已经想出了如何在与一个圆相交或两个圆相交时找到最近的空闲位置。然而，我找不到一个能够处理复杂情况的强大算法，其中有任意数量的圆以任何方式排列。

问题的精确描述：我有一个二维空间，其中有任意数量的非交叉圆形，所有圆形都具有相同的半径（尽管可能并不重要）。我想找到下一个圆形的位置，使其不与任何其他圆形相交，并且其中心[x,y]最靠近指定位置[x,y]。

欢迎任何建议（参考资料，方法或（Java）库）。

p.s. 如果解决方案包括确保圆圈保持在特定的边界框内（即显示），则会获得额外加分。

我的最终解决方案：（基于David Wallace的建议）

计算两个圆心之间的最小距离（在我的情况下，所有圆都是相同大小的，因此始终为2*半径）
列出所有距离鼠标位置比最小距离更近的圆的列表
如果没有重叠：一切正常！
如果有1个重叠：将新圆的中心移动到与比较的圆的中心的最小距离处，沿着从比较圆的中心到鼠标位置的向量
如果有2个重叠：找出两个重叠圆的交点。将新圆置于最靠近鼠标位置的交点上。如果该位置仍然与任何圆重叠，请移动到另一个交点。如果那个交点不起作用，请将新圆留在原地。
如果有3个重叠：与2个重叠相同，只需选择最靠近新圆的两个圆。

请注意，这并不完美，但对于我的情况足够好了，在屏幕上拖动新圆时有效。它在大多数情况下都有效，在那些无法正常工作的情况下，通常是当有许多非常接近的圆时，新圆只是停留在最后一个位置（有效位置）。然后用户可以决定将其拖动到更远处，并更准确地确定他想要新圆去的位置。

- Walmink

2

我认为你应该检查用户点击点周围半径为20像素的位置，如果有任何一个位置适合，则绘制一个圆形，否则告诉用户不能在那里放置圆形。我猜你不希望出现这样的情况，即当用户在屏幕的一侧点击一个点时，圆形出现在另一侧，因为那里是唯一的空闲空间。 - svz

svz，这个方法是有效的，但不太用户友好。此外，找到最近的点将帮助用户将圆形与另一个圆形紧贴，如果用户自己来评估这个距离会很困难。 - Walmink

第二个最近位置重要的原因是，我想通过拖动鼠标来不断运行此操作以移动目标[x,y]。我预测，一个返回确切最近位置的系统将会产生流畅的“动画”，圆圈将沿着其他圆圈的边缘漂亮地移动。当然，在将其移动到一组圆圈上时，它可能会从一侧跳到另一侧，但这没关系。 - Walmink

3个回答

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）”，并检查是否有任何没有周围圆形的四叉树。

四叉树

可以根据圆形半径选择四叉树的深度。

因此，如果您在其中一个四叉树中有一个点，则会查看其周围的四叉树以检查是否有任何圆形，并朝着空的四叉树方向移动点。

希望您理解我的方法。

- RamonBoza

感谢您的建议。虽然四叉树可以帮助找到附近的位置，但它无法找到最近的位置（因为四叉树是离散的）。找到绝对最近的位置的好处在于它会更像物理模拟，即如果我拖动鼠标，活动圆圈会“滚动”到其他圆圈周围。物理模拟不适用，因为如果我尝试将具有大重叠的圆形定位到不可移动的其他圆形上，它很可能会出现问题。 - Walmink

RamonBoza，感谢您的建议！我想避免跨贴，但如果这里不行，我肯定会去其他地方尝试。 - Walmink

0

这里有一个解决方案适用于不同的半径，并且如果所有半径都相等，就可以简化，就像您的情况一样。我们首先稍微转换一下问题。不是在其他圆周中拟合圆周，而是通过将我们的圆周的半径延伸到所有其他圆周的半径上，尝试放置一个点在这些扩展的圆周之外。这相当于原始问题。我们按如下步骤进行：

首先是一个特殊情况。如果该点在所有圆周之外，则有一个平凡的解。
找到该点在内部的所有圆周。计算其周长上最近的点（沿半径从原始点向外移动即可）。
找到任意两个圆周之间的所有交点。
合并第 2 和第 3 步的点集，并通过查找未被任何其他圆包含的点来过滤它们。
从剩余集合中选择最近的点。完成！

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

- Dag Ågren

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dawood ibn Kareem · Accepted Answer

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

假设你已经放置了半径分别为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）中被困住该怎么办。也许只允许进行一定数量的步骤，然后退出。毕竟，可能没有合适的位置来放置圆。