Encuentra más puntos encerrados en un tamaño fijo círculo

Question

Esto ocurrió cuando un amigo hablaba de un concurso de programación, y nos preguntamos cuál es el mejor enfoque era:

Dada una lista de puntos, encontrar el centro de un círculo de tamaño predeterminado que cubre la mayoría de los puntos. Si hay varios círculos, solo es importante encontrar uno.

Ejemplo de entrada: 1000 puntos, en un espacio de 500x500, y un círculo de 60 de diámetro.

Answer 1

Mi mejor enfoque hasta ahora es: puntos que contienen

Cada círculo debe tener una izquierda más puntos. Por lo tanto, hace una lista de todos los puntos a la derecha de un punto que están potencialmente dentro de los límites de un círculo. Primero ordena los puntos por x, para hacer que el barrido esté sano.

Luego los ordena de nuevo, esta vez por el número de vecinos a la derecha que tienen, para que el punto con la mayoría de los vecinos se examine primero.

Luego examina cada punto, y para cada punto a la derecha, calcula un círculo donde este par de puntos está en el perímetro izquierdo. Luego cuenta los puntos dentro de dicho círculo.

Dado que los puntos se han ordenado por potencial, se pueden eliminar una vez que se consideran todos los nodos que podrían conducir a una mejor solución.

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

idea muy rápida, no necesariamente correcta:

• para cada punto P que calcular un "área que cubre candidato" - un continuo de puntos en el centro de su círculo de cobertura podría ser. Naturalmente, también es un círculo de diámetro D con el centro en P.
• por cada punto P que interseca su área de cobertura candidata con las áreas correspondientes de otros puntos. Algunas de las áreas que cubren candidatos pueden cruzarse con las P y entre ellas. Para cada intersección, se cuenta el número de áreas intersecadas. Una figura que se cruza con la mayoría de las áreas candidatas es un área candidata para el centro de un círculo de cobertura que cubre P y tantos otros puntos como sea posible.
• encuentra una zona candidato con el mayor número de intersecciones

parece ser N^2 complejidad, siempre que el cálculo de las intersecciones de las zonas en forma de círculo es fácil

Answer 3

¿Cómo sobre el uso de un algoritmo de agrupamiento para identificar el grupo de puntos. A continuación, determine el clúster con la cantidad máxima de puntos. Tome el punto medio del grupo que tiene los puntos máximos como el centro de su círculo y luego dibuje el círculo.

MATLAB soporta implementation de k-means algorithm y devuelve una matriz 2-D (una matriz para ser exactos) de los medios de racimo y los correspondientes identificadores de racimo.

Un lado de la moneda muy conocido de k-means es decidir k (número de conglomerados) de antemano. Sin embargo, esto se puede resolver: uno puede aprender el valor de k de los puntos de datos. Por favor, consulte este paper.

Espero que esto ayude.

aplausos

Answer 4

A menos que me he perdido algo obvio Creo que hay una respuesta simple.

Para un área rectangular MxN, número de puntos P, el radio R:

• Inicializar un mapa (por ejemplo, matriz 2D de int) de su área de MxN a todos los ceros
• Para cada uno de sus puntos P
  • incremento de todos los puntos del mapa dentro de un radio R de elemento de mapa 1
• encuentra con valor máximo - esto va a ser el centro del círculo que está buscando

Esto es O (P), suponiendo que P es la variable de su interés.