我想出了当它与一个圆相交时,或者即使涉及两个圆时,我如何找到最近的自由位置.但是,我找不到一个可以处理任何排列中具有任意数量圆圈的复杂情况的稳健算法.
准确描述问题：
我有一个2D空间,任意数量的非相交圆,都具有相同的半径(虽然这可能无关紧要).我想找到下一个圆的位置,使其不与任何其他圆相交,并且哪个中心[x,y]最接近指定位置[x,y].
任何类型的建议(参考,方法或(Java)库).
附：如果解决方案包括确保圆圈保持在特定边界框(即显示)内,则奖励积分.
我的最终解决方案:(根据David Wallace的建议)
>计算两个圆心之间的最小距离(在我的例子中,所有圆都是相同的大小,所以总是2 *半径)
>列出距离最小距离更近的鼠标位置的所有圆圈
>如果0重叠：一切都好！
>如果1重叠：将新圆的中心移动到比较圆的中心的最小距离,沿着从比较圆的中心到鼠标位置的矢量
>如果2重叠：找出两个重叠圆相交的位置.将新圆放在最靠近鼠标位置的交叉点上.如果此位置仍与任何圆重叠,请移至另一个交叉点.如果那个不起作用,请保留新的圆圈.
>如果3重叠：与2重叠相同,只需取最接近新圆的两个圆.
请注意,这不能很好地完成,但在我的情况下,用户正在拖动屏幕上的新圆圈就足够了.它适用于大多数情况下,有些情况下没有,通常当很多圆圈非常靠近时,新圆圈只停留在最后一个位置(这是有效的).然后,用户可以决定进一步拖动它,并且更准确地在他想要新圆圈去的地方.
解决方法
假设你已经放置了半径为r1,r2,r3 … rn的圆圈,其中心为C1,C2,C3 …… Cn,你想要放置一个半径为rz的新圆圈,新圆圈的中心将会有在所有一组“放大”的圆圈之外,以C1,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),该怎么办.也许只允许一定数量的步骤,然后退出.毕竟,可能没有合适的地方放置圆圈.
