找到重叠圆圈的新位置

我正在尝试编写一个代码，对于给定的圆列表（list1），它能够找到新圆（list2）的位置。 list1 和 list2 具有相同的长度，因为对于 list1 中的每个圆，都必须有一个来自 list2 的圆。

1. 每对圆（假设 list1 中的 Circle1 和 list2 中的 Circle2）必须尽可能靠近，
2. list2 中的圆圈不得与 list1 中的圆圈重叠，而单个列表中的圆圈可以相互重叠。

list1 是固定的，所以现在我必须从 list2 中找到圆圈的正确位置。

我编写了这个简单的函数来识别两个圆是否重叠：

def overlap(x1, y1, x2, y2, r1, r2):
    distSq = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
    radSumSq = (r1 + r2) * (r1 + r2)
    if (distSq >= radSumSq):
        return False # no overlap
    else:
        return True  #overlap

这是列表1：

with:

x=[14.11450195 14.14184093 14.15435028 14.16206741 14.16951752 14.17171097
 14.18569565 14.19700241 14.23129082 14.24083233 14.24290752 14.24968338
 14.2518959  14.26536751 14.27209759 14.27612877 14.2904377  14.29187012
 14.29409599 14.29618549 14.30615044 14.31624985 14.3206892  14.3228569
 14.36143875 14.36351967 14.36470699 14.36697292 14.37235737 14.41422081
 14.42583466 14.43226814 14.43319225 14.4437027  14.4557848  14.46592999
 14.47036076 14.47452068 14.47815609 14.52229309 14.53059006 14.53404236
 14.5411644 ] 
y=[-0.35319126 -0.44222349 -0.44763246 -0.35669261 -0.24366629 -0.3998799
 -0.38940558 -0.57744932 -0.45223859 -0.21021004 -0.44250247 -0.45866323
 -0.47203487 -0.51684451 -0.44884869 -0.2018993  -0.40296811 -0.23641759
 -0.18019417 -0.33391538 -0.53565156 -0.45215255 -0.40939832 -0.26936951
 -0.30894437 -0.55504167 -0.47177047 -0.45573688 -0.43100587 -0.5805912
 -0.21770373 -0.199422   -0.17372169 -0.38522363 -0.56950212 -0.56947368
 -0.48770753 -0.24940367 -0.31492445 -0.54263926 -0.53460872 -0.4053807
 -0.43733299]
radius = 0.014

复制并粘贴...

x = [14.11450195,14.14184093,14.15435028,14.16206741,14.16951752,
     14.17171097,14.18569565,14.19700241,14.23129082,14.24083233,
     14.24290752,14.24968338,14.2518959,14.26536751,14.27209759,
     14.27612877,14.2904377,14.29187012,14.29409599,14.29618549,
     14.30615044,14.31624985,14.3206892,14.3228569,14.36143875,
     14.36351967,14.36470699,14.36697292,14.37235737,14.41422081,
     14.42583466,14.43226814,14.43319225,14.4437027,14.4557848,
     14.46592999,14.47036076,14.47452068,14.47815609,14.52229309,
     14.53059006,14.53404236,14.5411644]

y = [-0.35319126,-0.44222349,-0.44763246,-0.35669261,-0.24366629,
     -0.3998799,-0.38940558,-0.57744932,-0.45223859,-0.21021004,
     -0.44250247,-0.45866323,-0.47203487,-0.51684451,-0.44884869,
     -0.2018993,-0.40296811,-0.23641759,-0.18019417,-0.33391538,
     -0.53565156,-0.45215255,-0.40939832,-0.26936951,-0.30894437,
     -0.55504167,-0.47177047,-0.45573688,-0.43100587,-0.5805912,
     -0.21770373,-0.199422,-0.17372169,-0.38522363,-0.56950212,
     -0.56947368,-0.48770753,-0.24940367,-0.31492445,-0.54263926,
     -0.53460872,-0.4053807,-0.43733299]

现在我不确定我必须做什么，我的第一个想法是绘制 list2 的圆圈，从列表一中获取 x 和 y 并执行类似的操作x+c and y+c, where c是一个固定值。然后我可以调用我的重叠函数，如果存在重叠，我可以增加c价值。 这样我就有了 2for循环。现在，我的问题是：

1. 有一个方法可以避免for loops?
2. 是否有一个聪明的解决方案来为 list1 中的每个圆找到邻居（list2 中的圆）（不与 list2 中的其他圆重叠）？

使用 numpy 数组，可以避免 for 循环。

根据您的示例进行设置。

import numpy as np

#Using your x and y
c1 = np.array([x,y]).T

# random set of other centers within the same range as c1
c2 = np.random.random((10,2))
np.multiply(c2, c1.max(0)-c1.min(0),out = c2)
np.add(c2, c1.min(0), out=c2)

radius = 0.014
r = radius
min_d = (2*r)*(2*r)

plot_circles(c1,c2)    # see function at end

距每个中心的距离的数组c1到每个中心c2

def dist(c1,c2):
    dx = c1[:,0,None] - c2[:,0]
    dy = c1[:,1,None] - c2[:,1]
    return dx*dx + dy*dy

d = dist(c1,c2)

或者你可以使用 scipy.spatial

from scipy.spatial import distance
d = distance.cdist(c1,c2,'sqeuclidean')

为相交的圆创建一个二维布尔数组。

intersect = d <= min_d

从两个集合中找出重叠圆的索引。

a,b = np.where(intersect)
plot_circles(c1[a],c2[b])

Using intersect or a and b对于索引 c1、c2 和 d，您应该能够获得相交圆组，然后找出如何移动 c2 中心 - 但我将把它留给另一个问题/答案。如果一个list2圆与一相交list1圆圈 - 找到两者之间的线并沿着该线移动。如果一个list2圆与多个相交list1圆 - 找到两者之间的线closestlist1circles and move thelitst2` 沿着垂直于该线的线画圆。您没有提到移动圆圈的任何限制，因此可能会随机移动，然后再次找到相交，但这可能会出现问题。在下图中，弄清楚如何移动大部分红色圆圈可能很简单，但蓝色圆圈中的组可能需要不同的策略。

以下是获取组的一些示例：

>>> for f,g,h in zip(c1[a],c2[b],d[a,b]):
    print(f,g,h)
>>> c1[intersect.any(1)],c2[intersect.any(0)]
>>> for (f,g) in zip(c2,intersect.T):
    if g.any():
            print(f.tolist(),c1[g].tolist())

import matplotlib as mpl
from matplotlib import pyplot as plt

def plot_circles(c1,c2):

    bounds = np.array([c1.min(0),c2.min(0),c1.max(0),c2.max(0)])
    xmin, ymin = bounds.min(0)
    xmax, ymax = bounds.max(0)

    circles1 = [mpl.patches.Circle(xy,radius=r,fill=False,edgecolor='g') for xy in c1]
    circles2 = [mpl.patches.Circle(xy,radius=r,fill=False,edgecolor='r') for xy in c2]
    fig = plt.figure()
    ax = fig.add_subplot(111)
    for c in circles2:
        ax.add_artist(c)
    for c in circles1:
        ax.add_artist(c)

    ax.set_xlim(xmin-r,xmax+r)
    ax.set_ylim(ymin-r,ymax+r)

    plt.show()
    plt.close()