python - 从集群中返回面积最大的圆

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

由于您只对保留最大的圆圈感兴趣，因此我们可以应用贪心算法。在这里，我们首先对最大半径上的所有圆圈进行排序，然后循环遍历它们，如果我们已经包含在结果集中的圆圈没有任何交集，则只将它们添加到我们的结果集中。

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 循环，以便用户可以根据需要输入更多的圈子。没有错误处理，如果有意外输入，应用程序只会崩溃。由你来使它更漂亮。

print("""Give each circle with three numbers using the decimal as a dot.
The three numbers should be resp. x y r and should be seperated by a space.""")
c1 = Circle(*map(float, input("Give first circle >> ").split()))
circles = [c1]
while "y" in input("Do you want to give another circle? >> "):
    circles.append(Circle(*map(float, input("Give another circle >> ").split())))

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