Найдите наибольшее количество точек, заключенных в круг фиксированного размера

Ответ 1

Мой лучший подход до сих пор:

Каждый круг, содержащий точки, должен иметь самую левую точку. Таким образом, он составляет список всех точек справа от точки, потенциально находящейся в пределах круга. Сначала он сортирует точки по х, чтобы сделать развертку нормальным.

Затем он сортирует их снова, на этот раз числом соседних справа, что они имеют, так что точка с большинством соседей сначала будет рассмотрена.

Затем он анализирует каждую точку, а для каждой точки справа вычисляет круг, где эта пара точек находится по левому периметру. Затем он подсчитывает точки внутри такого круга.

Поскольку точки были отсортированы по потенциалу, он может быть удален, как только он рассмотрит все узлы, которые потенциально могут привести к лучшему решению.

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()

Ответ 2

Если я пропустил что-то очевидное, я думаю, что есть простой ответ.

Для прямоугольной области MxN число точек P, радиус R:

• Инициализировать карту (например, 2D-массив int) вашей области MxN ко всем нулям
• Для каждой из ваших точек P
  • приращение всех точек карты радиуса R на 1
• Найти элемент карты с максимальным значением - это будет центр круга, который вы ищете

Это O (P), считая P представляющей интерес переменной.

Ответ 3

Очень быстрая идея, не обязательно правильная:

• для каждой точки P вы вычисляете "область покрытия кандидата" - континуум точек, где может быть центр его охватывающего круга. Естественно, это также круг диаметром D с центром в P.
• для каждой точки P вы пересекаете область покрытия кандидата с соответствующими областями других точек. Некоторые из областей покрытия кандидатов могут пересекаться с P и друг с другом. Для каждого пересечения вы подсчитываете количество пересекаемых областей. Фигура, которая пересекается большей частью областей-кандидатов, является областью-кандидатом для центра охватывающего круга, который охватывает P и как можно больше других точек.
• найти область кандидата с наибольшим количеством пересечений

Кажется, сложность N ^ 2 при условии, что вычисление пересечений областей с круглой формой легко

Ответ 4

Как насчет использования алгоритма кластеризации для определения кластера точек. Затем определите кластер с максимальным количеством точек. Возьмите среднюю точку кластера с максимальными точками в качестве центра вашего круга, а затем нарисуйте круг.

MATLAB поддерживает реализация алгоритм k-mean и возвращает 2-мерный массив (точную матрицу) кластерных средств и соответствующих идентификаторов кластера.

Одна хорошо известная оборотная сторона k-средства определяет перед собой k (количество кластеров). Это можно решить, хотя - можно узнать значение k из точек данных. Пожалуйста, проверьте paper.

Надеюсь, это поможет.

веселит