Найти центр ограничивающей рамки с фиксированной шириной

Question

Учитывая набор точек, я хотел бы найти центр ограничивающей рамки (фиксированной длины и ширины), которая максимизирует количество точек в указанной коробке. Я в затруднении для эффективного способа сделать это.

Answer 1

алгоритм со сложностью O (N^2 * LogN) (я надеюсь, что лучше один существует):

Edit: article exploiting interval trees претензии O (NlogN) сложности массив

Сортировка данных Побочным X координат ,
Сканирование A с линии развертки влево-вправо.
Для каждой точки A получите LeftX = A[k].X - левая координата вертикальной полосы, найдите самую правую координату вертикальной полосы RightX = LeftX + Width.
Копирование точек внутри полосы на другую решетку B.

Сортировка по Y координате.
Сканирование ширины линии развертки B сверху вниз. Для каждой точки B [i] получите TopY = B[i].Y - верхнюю координату прямоугольника, вычислить BottomY = TopY + Height.
Использование двоичного поиска в B:
B [j] - последняя нижняя точка в B с B[j].Y <= BottomY.

Находим количество точек в текущем прямоугольнике:
Количество точек N(k, i) = j - i + 1

Проверьте N(k, i) является максимальным среди других

Answer 2

Это кажется трудной проблемой, вот моя идея: Держите график, каждый узел содержит прямоугольник и подмножество точек. прямоугольник определяет область, в которой размещение ограничивающего блока будет перекрывать все точки в подмножестве.

Чтобы построить график: Начнем с корневого узла, держащей пустой набор и прямоугольник [top:-inf, bottom:inf, left:-inf, right:inf]

Для каждой точки в дереве вызова этого рекурсивной функции с корневым узлом (псевдо-код):

function addPoint(node, point) 
    // check that you didn't already try to add this point to this node 
    // node.tested can be a hash set 
    if(node.tested contains point) 
     return   
    node.tested.add(point) 

    newRect = node.rect.intersectWith(boundingBoxAround(point)) 
    // if the bounding box around the point does not intersect the rectangle, return 
    if(newRect is invalid) // rect is invalid if right<left or bottom<top 
     return 

    node.addChild(new node(newRect, node.pointSet U {point}) 

    for each child of node 
     addPoint(child, point) 

Теперь вы просто выбираете узел с самым большим подмножеством, вы можете отслеживать это при построении графика, поэтому вам не нужно снова запускать график.

Надеюсь, моя идея понятна, дайте мне знать, если я могу объяснить это лучше.