在固定大小的圆中查找最多的点

除非我错过了一些显而易见的事情,我想有一个简单的答案。

对于矩形区域mxn,点数p,半径r:

• 将MXN区域的映射(例如,二维int数组)初始化为所有零
• 每一个P点
  • 将半径R内的所有地图点增加1
• 查找具有最大值的地图元素-这将是您要查找的圆的中心

这是O(P),假设P是兴趣变量。

想法很快,不一定是正确的:

• 对于每一个点p,你计算一个“候选覆盖面积”——一个覆盖圆中心可能所在的点的连续体。当然,它也是一个直径为d的圆,圆心为p。
• 对于每个点P,你将它的候选覆盖区域与其他点的对应区域相交。一些候选覆盖区域可能与P和彼此相交。对于每个交叉点,您计算交叉区域的数量。与大多数候选区域相交的图形是覆盖圆中心的候选区域,该覆盖圆覆盖P和尽可能多的其他点。
• 找到交叉口数量最多的候选区域

似乎是n^2复杂性,前提是计算圆形区域的交点很容易

到目前为止,我最好的方法是:

每个包含点的圆必须有最左边的点。所以它列出了一个点右边的所有点,这些点可能在一个圆的边界内。它首先按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()

使用聚类算法来识别点的聚类怎么样?然后用最大点数确定集群。以具有最大点的簇的平均点作为圆的中心,然后绘制圆。

matlab支持 implementation 属于 k-means algorithm 它还返回了一个二维数组(精确的矩阵)的集群手段和相应的集群ID。

一个众所周知的k-means的反面是在手之前决定k(簇的数量)。但这可以解决——人们可以从数据点学习k的值。请检查这个 paper .

我希望这有帮助。

干杯