Найдите идеальную позицию прямоугольника, которая содержит большинство заданных точек [duplicate]

Question

Найдите идеальную позицию прямоугольника, которая содержит большинство заданных точек [duplicate]

Использование фиктивных данных @Arun :) здесь решение lattice:

xyplot(val~x,type=c('l','p'),groups= variable,data=df,auto.key=T)

enter image description here [/g0]

7

geometry 2d rectangles

задан Harry Mexican 6 September 2015 в 23:32

1 ответ

Другие вопросы по тегам:

geometry 2d rectangles

Похожие вопросы:

score 5 · Accepted Answer

Сортировка точек слева направо. Установите указатель left в самой левой точке и указатель right в самой правой точке, которая попадает в left + width. Затем перебирайте все точки, пересчитывая положение указателя right каждый раз, пока он не окажется в последней точке.
Сортируйте каждое подмножество точек между левым и правым сверху вниз. Установите указатель top в наивысшей точке и указатель bottom в нижней точке, которая находится в пределах top + height. Затем перебирайте все точки, перечитывая положение указателя bottom каждый раз, пока он не окажется в последней точке.
Для каждого подмножества точек между левым, правым, верхним и нижним, проверьте, сколько у него очков, и сохраните оптимальное подмножество.
Как только найденное оптимальное подмножество найдено, центр прямоугольника находится на полпути между самой левой и самой правой точкой и на полпути между самой высокой и самой низкой точкой.

Ниже приведена простая реализация в Javascript, которая может быть оптимизирована во многих точках. Запустите фрагмент кода, чтобы просмотреть результаты со случайными данными.

function placeRectangle(p, width, height) {
    var optimal, max = 0;
    var points = p.slice();
    points.sort(horizontal);

    for (var left = 0, right = 0; left < points.length; left++) {
        while (right < points.length && points[right].x <= points[left].x + width) ++right;
        var column = points.slice(left, right);
        column.sort(vertical);

        for (var top = 0, bottom = 0; top < column.length; top++) {
            while (bottom < column.length && column[bottom].y <= column[top].y + height) ++bottom;
            if (bottom - top > max) {
                max = bottom - top;
                optimal = column.slice(top, bottom);
            }
            if (bottom == column.length) break;
        }
        if (right == points.length) break;
    }

    var left = undefined, right = undefined, top = optimal[0].y, bottom = optimal[optimal.length - 1].y;
    for (var i = 0; i < optimal.length; i++) {
        var x = optimal[i].x;
        if (left == undefined || x < left) left = x;
        if (right == undefined || x > right) right = x;
    }
    return {x: (left + right) / 2, y: (top + bottom) / 2};

    function horizontal(a, b) {
        return a.x - b.x;
    }

    function vertical(a, b) {
        return a.y - b.y;
    }
}

var width = 160, height = 90, points = [];
for (var i = 0; i < 10; i++) points[i] = {x: Math.round(Math.random() * 300), y: Math.round(Math.random() * 200)};
var rectangle = placeRectangle(points, width, height);

// SHOW RESULT IN CANVAS
var canvas = document.getElementById("canvas");
canvas.width = 300; canvas.height = 200;
canvas = canvas.getContext("2d");
paintRectangle(canvas, rectangle.x - width / 2, rectangle.y - height / 2, width, height, 1, "red");
for (var i in points) paintDot(canvas, points[i].x, points[i].y, 2, "blue");
function paintDot(canvas, x, y, size, color) {
    canvas.beginPath();
    canvas.arc(x, y, size, 0, 6.2831853);
    canvas.closePath();
    canvas.fillStyle = color;
    canvas.fill();
}
function paintRectangle(canvas, x, y, width, height, line, color) {
    canvas.beginPath();
    canvas.rect(x, y, width, height);
    canvas.closePath();
    canvas.lineWidth = line;
    canvas.strokeStyle = color;
    canvas.stroke();
}

<BODY STYLE="margin: 0; border: 0; padding: 0;">
<CANVAS ID="canvas" STYLE="width: 300px; height: 200px; float: left; background-color: #F8F8F8;"></CANVAS>
</BODY>

Это смехотворно полный ответ. Запуск кода, на который вы можете нажать! Хорошая работа, принимая ее. Не похоже, что я буду использовать его, хотя из-за того, что я внес некоторые изменения в геймплей, так что требование в вопросе больше не нужно выполнять. Думаю, это было бы слишком дорого. Требуется запустить каждый кадр со скоростью 60 кадров в секунду + все точки постоянно движутся. Сортировка, возможно, убила его. В любом случае, спасибо. — Harry Mexican, 8 September 2015 в 14:48
@HarryMexican Я написал код, чтобы продемонстрировать эту идею, но действительно ли вы можете это сделать, так как это действительно зависит от того, сколько очков есть и как быстро это должно быть; запуск его при частоте кадров в игре, скорее всего, будет проблематичным с чем-то большим, чем несколькими точками. Алгоритм опирается на сортировку, поэтому нет возможности пропустить это для повышения эффективности. Алгоритм, который смотрит только на точки, которые собираются покинуть прямоугольник, а затем постепенно перемещает его, вероятно, будет более эффективным в вашем случае. — m69, 8 September 2015 в 15:16
Да, это интересный мысленный эксперимент в любом случае. Надеюсь, у вас что-то получилось, и это помогает кому-то искать такой алгоритм. :) — Harry Mexican, 8 September 2015 в 15:19
@HarryMexican Если вы поместите точки в древовидную структуру, где каждая точка связана с четырьмя точками непосредственно выше, внизу, слева и справа от нее, это, вероятно, может устранить все повторные сортировки. Но это упражнение на другой день :-) — m69, 8 September 2015 в 15:31