Поиск рациональной универсальной формулы для нахождения координат центров окружностей, вписанных в квадрат

Question

Доброго времени суток, начиная делать курсовую роботу по ооп на с++, я столкнулся с достаточно серьёзной проблемой, которую я не в состоянии толком нормально объяснить, но я постараюсь.

Есть классы:

Точка (x, y)

Окружность (координаты центра, радиус)

Окружность с надписью (окружность, надпись)

Квадрат (координаты центра, сторона)

Окружность, вписанная в квадрат (окружность, квадрат)

Массив фигур на экране (Список окружностей, вписанных в квадрат)

С классами и их иерархией всё вроде-как понятно, также как и с компоновкой окружностей в квадрат, но вникая в проблему глубже, возникает вопрос: каким образом найти координаты центов окружностей, который вписаны в квадрат? (Да, я не могу до этого додуматься и взываю о вашей помощи)

Примеры компоновки:

Рассмотрим пример: Есть квадрат со стороной равной 4. В него вписаны окружности с радиусом равным 1. Получается что в квадрат можно вписать 4 круга. Если есть 4 окружности, следовательно есть 4 точки, которые являются координатами центров самих окружностей. Из программы школьной математики мы знаем формулу окружности с центром x и y, а также радиусом r. (x^2 + y^2 = r^2). Если брать точку центра нашего квадрата (0,0), то получается что окружности можно описать следующими четырьмя формулами:

Итак, задача в том, что бы найти универсальную формулу для нахождения координат центров окружностей. Ведь в такой квадрат можно вписать не только 4, а также 16 и так далее окружностей.

Вот простая программа, которая считает сколько можно вписать окружностей с неким радиусом, в к квадрат с некой стороной:

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    double a, r, d, q, sqr_ar;
    cout << "Enter side of a square" << endl;
    cin >> a;
    cout << "Enter radius of a circle" << endl;
    cin >> r;
    sqr_ar = pow(a, 2);
    d = r * 2;
    q = sqr_ar / pow(d, 2);
    if (q == ((double)((int)q)))
    {
        cout << "You can put " << q << " circles with radius " << r << " in square with side " << a << endl;
    }
    else
    {
        cout << "Try again" << endl;
    }
    return 0;
}

Answer 1

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

Вы поставили задачу так: определить какое максимальное количество окружностей радиуса r можно поместить в квадрат размера a без пересечений. Оказывается что ответ зависит только от отношения r/a. Не умоляя общности положим a = 1: вписываем окружности в единичный квадрат.

Обозначим максимальное число окружностей через m(r). Это монотонно убывающая целочисленная функция. Чтобы её задать достаточно вычислить r(n) = max{r|m(r) = n}. Именно в такой формулировке этой задачей занимаются математики. Значения r(n), n <= 20 можно найти в этой статье.

r(n) можно вычислить приближенно. Один из подходов такой: бросаем n случайных точек в единичный квадрат. Затем начинаем двигать их случайным образом в цикле. Перед движением точки вычисляется минимум из расстояний от неё до сторон квадрата и половинок расстояний до других точек. Такой же минимум вычисляется после движения. Если новый минимум меньше старого движение отменяется. Это грубый аналог броуновского движения под действием внешней силы: точки отталкиваются друг от друга и от сторон квадрата.

Хотя это прототип, он способен получить 17 из 20 конфигураций из статьи за несколько минут. Чтобы получить более серьёзные результаты нужно оптимизировать математическую модель и программу.

Прототип на Python:

import itertools
import matplotlib.pyplot as plt
import random
import sys


def cycle(a):
    return a + a[:1]


def dist(a, b):
    return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5


def get_radius(centers, i, cc):

    def gen():
        yield cc[0]
        yield 1 - cc[0]
        yield cc[1]
        yield 1 - cc[1]

        for j, c in enumerate(centers):
            if j != i:
                yield dist(cc, c) / 2

    return min(gen())


def get_common_radius(centers):
    def gen():
        for c in centers:
            yield c[0]
            yield 1 - c[0]
            yield c[1]
            yield 1 - c[1]

        for i, j in itertools.combinations(range(len(centers)), 2):
            yield dist(centers[i], centers[j]) / 2

    return min(gen())


def plot_circles(centers):
    radius = get_common_radius(centers)
    poly = ((0, 0), (1, 0), (1, 1), (0, 1))
    circles = [plt.Circle(c, radius, fill=False) for c in centers]
    ax = plt.gca()
    ax.set_aspect('equal', adjustable='box')
    for c in circles:
        ax.add_artist(c)
    plt.plot(*zip(*cycle(poly)))
    plt.show()


def shake(centers, step, r):
    for i, c in enumerate(centers):
        radius = get_radius(centers, i, c)
        new_c = tuple(v + step * (2 * r.random() - 1) for v in c) 
        new_radius = get_radius(centers, i, new_c)
        if radius < new_radius:
            centers[i] = new_c


def main():
    n = int(sys.argv[1])
    r = random.Random()
    centers = [(r.random(), r.random()) for _ in range(n)]
    for p in range(0, 10):
        step = 0.5 ** p
        for _ in range(10 * 2 ** p):
            shake(centers, step, r)
    plot_circles(centers)


main()

БЛОГ НА HUSL

Поиск рациональной универсальной формулы для нахождения координат центров окружностей, вписанных в квадрат

Ответы (1 шт):