查找封閉在一個固定大小的圓圈

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是感興趣的變量。