查找封闭在一个固定大小的圆圈

Question

这上来时，一个朋友谈到一个编程竞赛，积分最高的，我们不知道什么是最好的办法是：

给出点的列表中，找到一个圆心覆盖最多点的预定大小。如果有几个这样的圈子，它唯一重要的就是找到其中之一。

输入示例：1000点，500x500空间，60圆直径的圆。

Answer 1

我的最好的办法，到目前为止是：含

每个圆点必须有一个最左边的点。因此，它列出了可能在圆圈范围内的点的右侧所有点。它首先用x对点进行排序，以使扫描清晰。

然后，它再次对它们进行排序，这次是根据它们所拥有的邻居的数量进行排序，以便首先检查最邻近点。

然后检查每个点，并且对于右边的每个点，它计算一个圆点，其中这对点位于左边界上。然后它计算这个圆圈内的点数。

因为这些点已经按潜力排序，所以一旦它被视为可能潜在地导致更好的解决方案的所有节点，它就可以提前。

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支持k-means algorithm的implementation，它给出了簇装置和相应的簇ID的二维阵列（准确地说是一个矩阵）。

k-means的一个众所周知的另一面是事先决定k（簇数）。这可以解决 - 可以从数据点中了解k的值。请检查这个paper。

我希望这会有所帮助。

欢呼声

Answer 4

除非我错过了明显的东西，我认为有一个简单的答案。

对于一个矩形区域的M×N，点P的数目，半径R：

• 初始化的映射（INT的例如2D阵列）您的M×N个区域的为全零
• 对于每个P指向的
  • 增量与最大值1个
• 查找地图元素半径R内的所有地图点 - 这将是你是圆心寻找

这是O（P），假设P是感兴趣的变量。