Возвращение круга с самой большой областью из кластера - PullRequest
Новая
       33

Возвращение круга с самой большой областью из кластера

0 голосов
/ 24 февраля 2019

Список дается в форме (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])

У меня есть 2 основных вопроса 1. Как мне принять список кортежей от пользователя и список возврата?2. Я не могу пройти тест ниже.Спасибо

Тестовый ввод: [(0.5,0.5,0.4), (1.7,1.3,1), (0.4,0.6,0.3)] вывод: [(1.7,1.3,1)]

Ответы [ 2 ]

0 голосов
/ 24 февраля 2019

Поскольку вас интересует только сохранение кругов с наибольшим, мы можем применить жадный алгоритм.Здесь мы сначала сортируем все круги по наибольшему радиусу, а затем зацикливаем их, только добавляя их в наш результирующий набор, если они не делают пересечений, если окружности мы уже включили в наш результирующий набор.

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)])
0 голосов
/ 24 февраля 2019

Делая наивный подход, для каждого набора окружностей вы можете рассчитать расстояние от него до всех других наборов окружностей, которые они вычисляют, если это расстояние больше, чем сумма их радиуса.Таким образом, вы будете знать, если какой-то круг перекрывает другой, тогда сумма радиуса будет меньше расстояния их центра.

Таким образом, вы можете определить некоторую функцию: 

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

, и они определяютфункция для перекрытия: 

def isoverlapping(circle1, circle2):
    sum_of_radius = circle1[2] + circle2[2]
    distance_bettwen_circles = distance(circle1, circle2)
    return sum_of_radius >= distance_bettwen_circles

Итак, если функция выше возвращает true, вам придется игнорировать меньший круг.Для этого вы можете сделать функцию, которая вычисляет площадь окружностей и возвращает большее: 

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)

Надеюсь, чтоэто может помочь вам!

...