找到固定大小的圆圈中的最多点 [英] Find the most points enclosed in a fixed size circle
问题描述
当一位朋友谈到编程比赛时，我们想知道最好的方法是什么:
This came up when a friend talked about a programming competition, and we wondered what the best approach was:
给定一个点列表，找到一个预定大小的圆的中心，该圆覆盖了最多的点.如果有多个这样的圈子，找到其中一个很重要.
Given a list of points, find the centre of a circle of predetermined size that covers the most points. If there are several such circles, its only important to find one of them.
示例输入:1000 个点，在 500x500 的空间中，一个直径为 60 的圆.
Example input: 1000 points, in a 500x500 space, and a circle of 60 diameter.
推荐答案
到目前为止我最好的方法是:
My best approach so far is:
每个包含点的圆都必须有一个最左边的点.因此，它列出了一个点右侧可能在圆范围内的所有点.它首先按 x 对点进行排序，以使扫描更加合理.
Every circle containing points must have a left-most point. So it makes a list of all the points to the right of a point that are potentially within the bounds of a circle. It sorts the points by x first, to make the sweep sane.
然后它再次对它们进行排序，这次是根据它们右侧的邻居数量，以便首先检查具有最多邻居的点.
It then sorts them again, this time by the number of neighbours to the right that they have, so that the point with the most neighbours get examined first.
然后它会检查每个点，并为右侧的每个点计算一个圆，其中这对点位于左周边.然后它计算这样一个圆圈内的点.
It then examines each point, and for each point to the right, it computes a circle where this pair of points is on the left perimeter. It then counts the points within such a circle.
因为这些点是按潜力排序的，所以一旦考虑到所有可能导致更好解决方案的节点，它就可以提前退出.
Because the points have been sorted by potential, it can early-out once it's considered all the nodes that might potentially lead to a better solution.
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()
这篇关于找到固定大小的圆圈中的最多点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
