Найти наибольшее количество очков, вложенные в фиксированный размер круга

Question

Это придумал, когда друг говорил о конкуренции программирования, и мы задавались вопросом, что лучший подход:

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

Пример ввода: 1000 точек в пространстве 500x500 и круге диаметром 60 мм.

Answer 1

Мой лучший подход до сих пор:

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

Затем он сортирует их снова, на этот раз по количеству соседей справа, которые у них есть, так что точка с самыми соседями сначала исследуется.

Затем он анализирует каждую точку, и для каждой точки справа вычисляет круг, где эта пара точек находится по левому периметру. Затем он подсчитывает точки внутри такого круга.

Поскольку точки были отсортированы по потенциалу, это может быть раньше, если считать все узлы, которые потенциально могут привести к лучшему решению.

import random, math, time 
from Tkinter import * # our UI 

def sqr(x): 
    return x*x 

class Point: 
    def __init__(self,x,y): 
     self.x = float(x) 
     self.y = float(y) 
     self.left = 0 
     self.right = [] 
    def __repr__(self): 
     return "("+str(self.x)+","+str(self.y)+")" 
    def distance(self,other): 
     return math.sqrt(sqr(self.x-other.x)+sqr(self.y-other.y)) 

def equidist(left,right,dist): 
    u = (right.x-left.x) 
    v = (right.y-left.y) 
    if 0 != u: 
     r = math.sqrt(sqr(dist)-((sqr(u)+sqr(v))/4.)) 
     theta = math.atan(v/u) 
     x = left.x+(u/2)-(r*math.sin(theta)) 
     if x < left.x: 
      x = left.x+(u/2)+(r*math.sin(theta)) 
      y = left.y+(v/2)-(r*math.cos(theta)) 
     else: 
      y = left.y+(v/2)+(r*math.cos(theta)) 
    else: 
     theta = math.asin(v/(2*dist)) 
     x = left.x-(dist*math.cos(theta)) 
     y = left.y + (v/2) 
    return Point(x,y) 

class Vis: 
    def __init__(self): 
     self.frame = Frame(root) 
     self.canvas = Canvas(self.frame,bg="white",width=width,height=height) 
     self.canvas.pack() 
     self.frame.pack() 
     self.run() 
    def run(self): 
     self.count_calc0 = 0 
     self.count_calc1 = 0 
     self.count_calc2 = 0 
     self.count_calc3 = 0 
     self.count_calc4 = 0 
     self.count_calc5 = 0 
     self.prev_x = 0 
     self.best = -1 
     self.best_centre = [] 
     for self.sweep in xrange(0,len(points)): 
      self.count_calc0 += 1 
      if len(points[self.sweep].right) <= self.best: 
       break 
      self.calc(points[self.sweep]) 
     self.sweep = len(points) # so that draw() stops highlighting it 
     print "BEST",self.best+1, self.best_centre # count left-most point too 
     print "counts",self.count_calc0, self.count_calc1,self.count_calc2,self.count_calc3,self.count_calc4,self.count_calc5 
     self.draw() 
    def calc(self,p): 
     for self.right in p.right: 
      self.count_calc1 += 1 
      if (self.right.left + len(self.right.right)) < self.best: 
       # this can never help us 
       continue 
      self.count_calc2 += 1 
      self.centre = equidist(p,self.right,radius) 
      assert abs(self.centre.distance(p)-self.centre.distance(self.right)) < 1 
      count = 0 
      for p2 in p.right: 
       self.count_calc3 += 1 
       if self.centre.distance(p2) <= radius: 
        count += 1 
      if self.best < count: 
       self.count_calc4 += 4 
       self.best = count 
       self.best_centre = [self.centre] 
      elif self.best == count: 
       self.count_calc5 += 5 
       self.best_centre.append(self.centre) 
      self.draw() 
      self.frame.update() 
      time.sleep(0.1) 
    def draw(self): 
     self.canvas.delete(ALL) 
     # draw best circle 
     for best in self.best_centre: 
      self.canvas.create_oval(best.x-radius,best.y-radius,\ 
       best.x+radius+1,best.y+radius+1,fill="red",\ 
       outline="red") 
     # draw current circle 
     if self.sweep < len(points): 
      self.canvas.create_oval(self.centre.x-radius,self.centre.y-radius,\ 
       self.centre.x+radius+1,self.centre.y+radius+1,fill="pink",\ 
       outline="pink") 
     # draw all the connections 
     for p in points: 
      for p2 in p.right: 
       self.canvas.create_line(p.x,p.y,p2.x,p2.y,fill="lightGray") 
     # plot visited points 
     for i in xrange(0,self.sweep): 
      p = points[i] 
      self.canvas.create_line(p.x-2,p.y,p.x+3,p.y,fill="blue") 
      self.canvas.create_line(p.x,p.y-2,p.x,p.y+3,fill="blue") 
     # plot current point 
     if self.sweep < len(points): 
      p = points[self.sweep] 
      self.canvas.create_line(p.x-2,p.y,p.x+3,p.y,fill="red") 
      self.canvas.create_line(p.x,p.y-2,p.x,p.y+3,fill="red") 
      self.canvas.create_line(p.x,p.y,self.right.x,self.right.y,fill="red") 
      self.canvas.create_line(p.x,p.y,self.centre.x,self.centre.y,fill="cyan") 
      self.canvas.create_line(self.right.x,self.right.y,self.centre.x,self.centre.y,fill="cyan") 
     # plot unvisited points 
     for i in xrange(self.sweep+1,len(points)): 
      p = points[i] 
      self.canvas.create_line(p.x-2,p.y,p.x+3,p.y,fill="green") 
      self.canvas.create_line(p.x,p.y-2,p.x,p.y+3,fill="green") 

radius = 60 
diameter = radius*2 
width = 800 
height = 600 

points = [] 

# make some points 
for i in xrange(0,100): 
    points.append(Point(random.randrange(width),random.randrange(height))) 

# sort points for find-the-right sweep 
points.sort(lambda a, b: int(a.x)-int(b.x)) 

# work out those points to the right of each point 
for i in xrange(0,len(points)): 
    p = points[i] 
    for j in xrange(i+1,len(points)): 
     p2 = points[j] 
     if p2.x > (p.x+diameter): 
      break 
     if (abs(p.y-p2.y) <= diameter) and \ 
      p.distance(p2) < diameter: 
      p.right.append(p2) 
      p2.left += 1 

# sort points in potential order for sweep, point with most right first 
points.sort(lambda a, b: len(b.right)-len(a.right)) 

# debug 
for p in points: 
    print p, p.left, p.right 

# show it 
root = Tk() 
vis = Vis() 
root.mainloop() 

Answer 2

Очень быстро идея, не обязательно прямо один:

• для каждой точки P вы рассчитали «кандидат охватывающих область» - континуум точек, где центр его накрытия окружности может быть. Естественно, это также круг диаметром D с центром в P.
• для каждой точки P вы пересекаете свою область покрытия кандидата с соответствующими областями других точек. Некоторые из областей, покрывающих кандидаты, могут пересекаться с P и друг с другом. Для каждого пересечения вы подсчитываете количество пересекаемых областей. Фигура, которая пересекается большинством областей кандидатов, является областью кандидата для центра охватывающего круга, который охватывает P и как можно больше других точек.
• найти кандидат область с наибольшим числом пересечений

, кажется, N^2 сложностями, при условии, что вычисления пересечений в форме круга областей легко

Answer 3

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

MATLAB поддерживает implementation из k-means algorithm и возвращает 2-мерный массив (точную матрицу) средств кластера и соответствующих идентификаторов кластера.

Одна хорошо известная оборотная сторона k-средств принимает решение о k (количество кластеров) перед рукой. Это можно решить, хотя - можно узнать значение k из точек данных. Пожалуйста, проверьте это paper.

Надеюсь, это поможет.

веселит

Answer 4

Если я не скучал что-то очевидное, я думаю, что есть простой ответ.

Для прямоугольной области MxN, число точек P, радиус R:

• Инициализировать карту (например, 2D массив Int) вашей области MxN для всех нулей
• Для каждого из точек Р
  • прибавка все пункты карты в пределах радиуса R от 1
• Find карте элемент с максимальным значением - это будет центр круга вы

Это O (P), если P - представляющая интерес переменная.