俱乐部面积最大的回圈

Question

列表以（x，y，r）的形式给出，其中x和y是中心坐标，r是半径。 对于每个簇，保留面积最大的圆，并删除该簇中的所有其他圆。返回结果元组。在

代码

import math

class Circle(object):
    def __init__(self, x, y, r):
        super(Circle, self).__init__()
        self.x = x
        self.y = y
        self.r = r

    def get_distance(self, circle):
        return math.sqrt(math.pow(self.x - circle.x, 2) + math.pow(self.y - circle.y, 2))

    def is_intersect(self, circle):
        return self.get_distance(circle) < self.r + circle.r

    @staticmethod
    def has_intersections(list_circles):
        list_circles.sort(key=lambda a: a.x - a.r)
        sweep_intersected = []
        for circle in list_circles:
            for in_sweep in sweep_intersected:
                if circle.is_intersect(in_sweep):
                    return True
                if in_sweep.x + in_sweep.r < circle.x - circle.r:
                    sweep_intersected.remove(in_sweep)
            sweep_intersected.append(circle)
        return False

cir = [(12,5,0.9),(2,4,0.8),(2,3,0.4)]
cv1 = cir[0]
cv2 = cir[1]
cv3 = cir[2]
#cv4 = cir[3]
c1 = Circle(cv1[0], cv1[1], cv1[2])
c2 = Circle(cv2[0], cv2[1], cv2[2])
c3 = Circle(cv3[0], cv3[1], cv3[2])

a = []
cval = Circle.has_intersections([c1, c2, c3])
if cval == False:
  for num in range(len(cir)):
    break
  print(cir)
if cval == True:
  for n in range(len(cir)):
    #max(cir[n][2])
    a.append(cir[n][2])
    max_value = max(a)
    max_index = a.index(max_value)
  print(cir[max_index])

我有两个主要问题 1我如何接受来自用户和返回列表的元组列表？ 2我不能通过下面的测试用例。谢谢

测试用例 输入：[（0.5,0.5,0.4），（1.7,1.3,1），（0.4,0.6,0.3）] 输出：[（1.7,1.3,1）]

Answer 1

做一个简单的方法，对于每一个圆元组，你可以计算它到所有其他圆元组的距离，他们计算这个距离是否大于它们的半径之和。这样你就知道如果某个圆与另一个圆重叠，那么半径之和将小于它们的中心距离。在

所以你可以定义一些函数：

import math
def distance(p1, p2):
    return math.sqrt((p2[0] - p1[0])**2 + (p2[1] - p1[1])**2)

它们为重叠定义了一个函数：

^{pr2}$

所以，如果上面的函数返回真，你将不得不忽略较小的圆。为此，可以创建一个计算圆面积并返回较大值的函数：

def greatercircle(circle1, circle2):
    area1 = math.pi * circle1[2]
    area2 = math.pi * circle2[2]
    return circle1 if area1 >= area2 else circle2

现在只需要把他连接成一个循环：

output = []

# 1: Iterate over circles array, comparing every position with the others.
for index, circle in enumerate(circles):
#     2: get the other circles in array
    another_circles = circles[:index] + circles[index+1:]
    for another_circle in another_circles:
#         3: Iterate over the other circles
        if isoverlapping(circle, another_circle):
#         if an overlap ocurrs then get the greater circle.
#         Now this will be the current circle for comparison.
            greater = greatercircle(circle, another_circle)
            circle = greater
#   4: If this circle is already in output, do not append it.
    if circle not in output:
        output.append(circle)

print(output)

希望能对你有所帮助！在

Answer 2

因为你只对保持最大的圆感兴趣，我们可以应用贪婪算法。在这里，我们首先对最大半径上的所有圆进行排序，然后将它们循环到我们的结果集中，如果它们没有相交，如果我们已经在结果集中包含了这些圆。在

circles = [c1, c2, c3, c4]

from operator import attrgetter


def largest_non_overlapping_circles(circles):
    circles.sort(key=attrgetter('r'), reverse=True)  # sort on largest radius
    res = []  # list of circles we want to keep
    for c in circles:
        if not Circle.has_intersections(res + [c]):
            res.append(c)
    return res


print([(c.x, c.y, c.r) for c in largest_non_overlapping_circles(circles)])

对于您的第二个问题，我们可以使用Python的input()函数。在这里，我选择在一行（x，y，r）中询问所有数字。我还使用了while循环，这样用户可以根据需要输入更多的圆。没有错误处理，如果有意外的输入，应用程序将崩溃。由你来做得更漂亮。在

^{pr2}$