首页 文章

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

提问于
浏览
7

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

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

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

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

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

My final solution: (based on David Wallace's suggestions)

  • 计算两个圆心之间的最小距离(在我的例子中,所有圆都是相同的大小,所以总是2 *半径)

  • 列出距离最小距离更近的鼠标位置的所有圆圈

  • 如果0重叠:一切都好!

  • 如果1重叠:沿着从比较圆的中心到鼠标位置的矢量移动新圆's center to the minimum distance from the compared circle'的中心

  • 如果2重叠:找出两个重叠圆相交的位置 . 将新圆放在最靠近鼠标位置的交叉点上 . 如果此位置仍与任何圆重叠,请移至另一个交叉点 . 如果那个不起作用,请保留新的圆圈 .

  • 如果3重叠:与2重叠相同,只需取最接近新圆的两个圆 .

请注意,这不能很好地完成,但在我的情况下,用户正在拖动屏幕上的新圆圈就足够了 . 它适用于大多数情况下,有些情况下没有,通常当有很多圆圈非常接近时,新圆圈只停留在最后一个位置(这是有效的) . 然后,用户可以决定进一步拖动它,并且在他想要新圆圈的位置更精确 .

2 回答

  • 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 并检查是否存在没有周围圆圈的四边形

    A quadtree

    可以选择四叉树深度圆的半径 .

    因此,如果你在其中一个四边形中有一个点,你会看到它周围的四边形,检查那里是否有任何圆圈,然后从空四边形的方向移动 .

    我希望你理解我的方法

  • 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),该怎么办 . 也许只允许一定数量的步骤,然后退出 . 毕竟,可能没有合适的地方放置圆圈 .

相关问题