Как найти все квадраты определенного размера в круговой сетке

Question

Я пытаюсь нарисовать различные непересекающиеся квадраты в области круга на холсте.

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

Мне нужен алгоритм, который использует центр круга, координаты, радиус круга и размер квадратной сетки и возвращает массив координат для позиций каждого квадрата в сетке, у которой есть все ее ребра внутри круга.

Answer 1

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

const size = 4; // The size of each square.
const squareCoords = []; // The top-left corners of each valid square.
const circle = [10, 10, 10]; // The circle, in the form [centerX, centerY, radius]

function DistanceSquared(x1, y1, x2, y2) {
    return (x2-x1) ** 2 + (y2-y1) ** 2;
}
function isInsideCircle(x, y, cx, cy, r) {
    return (DistanceSquared(x, y, cx, cy) <= r ** 2);
}

let topLeftInside = false, bottomRightInside = false, topRightInside = false, bottomLeftInside = false;
for (let xx = circle[0] - circle[2]; xx < circle[0] + circle[2]; xx += size) {
    for (let yy = circle[1] - circle[2]; yy < circle[1] + circle[2]; yy += size) {
        topLeftInside = isInsideCircle(xx, yy, circle[0], circle[1], circle[2]);
        bottomRightInside = isInsideCircle(xx + size, yy + size, circle[0], circle[1], circle[2]);
        bottomLeftInside = isInsideCircle(xx, yy + size, circle[0], circle[1], circle[2]);
        topRightInside = isInsideCircle(xx + size, yy, circle[0], circle[1], circle[2]);
        if (topLeftInside && bottomRightInside && bottomLeftInside && topRightInside) {
            squareCoords.push([xx, yy]);
        }
    }
}