找出围绕固定大小圆圈的最多点 [英] Find the most points enclosed in a fixed size circle
本文介绍了找出围绕固定大小圆圈的最多点的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
当朋友谈论编程竞赛的时候，这就出现了，我们想知道最好的方法是什么：
给出一个点列表，找到一个覆盖最多点的预定大小的圆圈。如果有几个这样的圆圈，它唯一重要的就是找到其中的一个圆圈。
示例输入：500x500空间中的1000个点和60个直径的圆圈。 / p>
解决方案
到目前为止，我的最佳做法是：
必须有一个最左边的点。因此它列出了可能在圆圈范围内的点的右边所有点。它先用x对点进行排序，以使扫掠健全。
然后它再次对它们进行排序，这次是靠近右边的邻居数量，所以先检查最邻近的点。然后它检查每个点，并且对于每个右边的点计算一个圆圈，其中的这对点是在左边。然后计算这样一个圆圈内的点。
由于点已经按潜在值排序，所以一旦它被认为可能导致潜在的所有节点一个更好的解决方案。
导入随机，数学，时间
从Tkinter导入*＃我们的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）
返回Point（x，y）
$ b $ class Vis：
def __init __（self）：
self.frame = Frame（root）
self.canvas = Canvas（self.frame，bg =白色，宽度=宽度，高度=高度）
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 = []
用于xrange中的self.sweep（0，len（分））：
self.count_calc0 + = 1
if len（points [self.sweep] .right）< = self.best：
break
self.calc（points [self.sweep]）
self.sweep = len（points）＃让draw（）停止突出显示它
打印BEST，self.best + 1，self.best_centre＃计算最左边的点数
print （自我，p）：$ b self.count_calc1，self.count_calc2，self.count_calc3，self.count_calc4，self.count_calc5 $ b for self.right in p.right：
self.count_calc1 + = 1
if（self.right.left + len（self.right.right））< self.best：
＃这永远不能帮助我们
继续
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）
＃绘制最佳圈子
在self.best_centre中获得最佳效果：
self.canvas.create_oval （best.x-radius，best.y-radius，\
best.x + radius + 1，best.y + radius + 1，fill =red，\
outline =红色）
＃绘制当前圈子
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）
＃绘制所有连接
为p点：$ b $ b为p2 p .right：
self.canvas.create_line（px，py，p2.x，p2.y，fill =lightGray）
＃绘制了访问点数
for xrange（0 ，self.sweep）：
p = points [i]
self.canvas.create_line（px-2，py，p.x + 3，py，fill =blue）
self .canvas.create_line（px，py-2，px，p.y + 3，fill =blue）
＃绘制当前点
if self.sweep< len（points）：
p = points [self.sweep]
self.canvas.create_line（px-2，py，p.x + 3，py，fill =red）
self.canvas.create_line（px，py-2，px，p.y + 3，fill =red）
self.canvas.create_line（px，py，self.right.x，self.right。 y，fill =red）
self.canvas.create_line（px，py，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）
＃绘制未访问点
在xrange中我（self.sweep + 1，len（points））：
p = points [i]
self.canvas.create_line（px-2，py，p.x + 3，py，fill =green）
self.canvas.create_line（px，py-2，px，p.y + 3，fill =green）
半径= 60
直径=半径* 2
$ width = 800
height = 600
points = []
＃为xrange（0,100）中的i创造点数
：
points.append（Point（random.randrange（width），random.randrange（height） ））
＃查找右边扫描的排序点
points.sort（lambda a，b：int（ax）-int（bx））
＃在xrange（0，len（points））中计算每个点右边的
：
p = points [i]
for xrange（i + 1 ，len（点））：
p2 = points [j]
if p2.x> （p.x +直径）：
断开
if（abs（p.y-p2.y）<=直径）和\ $ b $ b p.distance（p2）直径：
p.right.append（p2）
p2.left + = 1
排序点的扫描可能顺序，点右上第一个
points.sort（lambda a，b：len（b.right）-len（a.right））
＃debug
对于p分：
print p，p .left，p.right
＃显示
root = Tk（）
vis = Vis（）
root.mainloop（）
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.
Example input: 1000 points, in a 500x500 space, and a circle of 60 diameter.
解决方案
My best approach so far is:
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屋！
查看全文
