到目前为止，我最好的方法是：
每个包含点的圆都必须有最左边的点。因此，它将列出一个点右边的所有点，这些点可能在圆的范围内。首先将点按x排序，以使扫描保持理智。
然后，再次对它们进行排序，这一次是按其右边的邻居数量进行，以便首先检查邻居最多的那个点。
然后，它检查每个点，并为右边的每个点计算一个圆，该对点在左边界上。然后，它计算该圆圈内的点。
因为这些点已经按电位进行了排序，所以一旦考虑到所有可能导致更好解决方案的节点，它就可以提前淘汰。
import random, math, timefrom Tkinter import * # our UIdef sqr(x): return x*xclass 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 = 60diameter = radius*2width = 800height = 600points = []# make some pointsfor i in xrange(0,100): points.append(Point(random.randrange(width),random.randrange(height)))# sort points for find-the-right sweeppoints.sort(lambda a, b: int(a.x)-int(b.x))# work out those points to the right of each pointfor 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 firstpoints.sort(lambda a, b: len(b.right)-len(a.right))# debugfor p in points: print p, p.left, p.right# show itroot = Tk()vis = Vis()root.mainloop()
