Базовый алгоритм проверки простых вложенных фигур в Java/Python с использованием наследования и полиморфизмов

Это была проблема, с которой я столкнулся, работая над программой на Java, которая включает в себя в основном некоторую геометрию и некоторый анализ алгоритмов, поэтому я надеюсь, что вам понравится.

Рассмотрим эту проблему. У вас есть куча 2D-фигур, хранящихся как объекты Shape, с размерными атрибутами, которые вам нужно проверить на возможность вложения друг в друга. Набор фигур, который вы получили, включает квадраты, круги и прямоугольники. Как бы вы создали алгоритм, который дает вам список форм, которые вписываются в некоторую «Форму»? Какую структуру данных вы используете и как вы вызываете сравнение?

Набор форм достаточно мал, чтобы просто перечислять требования в каждом конкретном случае. Для форм, сравниваемых с собственным типом, вы сравниваете функции формы 1-к-1, поэтому я перечислю менее ясные случаи с их решениями и тем, как получить верхние границы их внешней формы:

  1. Круги внутри квадратов и прямоугольников.
  2. Квадраты внутри кругов и прямоугольников.
  3. Прямоугольник внутри кругов и квадратов.
  • (1) Круги внутри квадратов: поскольку это симметричные фигуры, мы можем центрировать вложенный круг внутри квадрата и сравнить диаметр круга с длиной квадрата, чтобы получить верхнюю граница.
  • (1) Круги внутри прямоугольников: это просто еще один вариант квадрата.
  • (2) Квадраты внутри кругов: симметричные формы, поэтому сравните длину между самыми дальними краями квадрата с диаметром кругов. Это будет длина между противоположными углами или, возможно, поперечные пары точек.
  • (2) Квадраты внутри прямоугольников: самый большой квадрат расположен вдоль самой короткой стороны прямоугольника.

Пока достаточно легко, верно? Однако мы имели дело только с симметричными формами. Тут начинаются сложности:

  • (3) Прямоугольник внутри кругов: это следует той же логике, что и квадрат. Вы центрируете прямоугольник внутри круга и получаете наибольшую длину между двумя краями. Это будет от угла к противоположному углу, и убедитесь, что длина этого прямоугольника меньше диаметра круга.
  • (3) Прямоугольник внутри квадратов: самая длинная сторона прямоугольника должна быть меньше стороны квадрата.

… верно?

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

Ясно, что мы построили прямоугольник, который длиннее, но может быть вложен в квадрат. Но какие длины мы сравниваем, чтобы убедиться, что это правда?

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

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

Ниже мое решение.

Объяснение

  1. Нам нужно найти наибольшую длину и ширину прямоугольника, который может поместиться внутри любого заданного квадрата. Это означает, что наше решение должно включать обе переменные.
  2. Мы можем использовать классическую теорему Пифагора, чтобы найти длину и ширину прямоугольника. Мы разделяем прямоугольные треугольники вокруг точки H со сторонами a и b соответственно, чтобы сформировать треугольник с длиной L и ширина с.ст. для L: a² + a² = L² → L = sqrt(2a²). Мы можем сделать то же самое для ширины.
  3. Используя распределительное свойство показателей умноженных величин, мы можем заключить упрощенную версию представления длины и использовать алгебру, чтобы найти длины a и b, которые будут служить верхней границей .
  4. Мы можем заметить, что a + b фактически равно всей стороне квадрата. Это представление S служит верхней границей, поэтому нам требуются длина и ширина меньше, чем S, как показано.

Код

Теперь пришло время реализовать нашу логику в коде. Я использую Java, так как это был исходный язык, с которым я практиковался для завершения этого проекта, но буду использовать Python для простых частей.

Часть 1

Давайте совершим набег на инструментарий программиста следующего поколения, ChatGPT. Простой запрос к ChatGPT-3.5 типа «Дайте мне алгоритм проверки, поместится ли прямоугольник в квадрат» отображает рабочий код с логическими ошибками:

def can_fit_rectangle_in_square(rectangle_length, rectangle_width, square_side):
    if rectangle_length <= square_side and rectangle_width <= square_side:
        return True
    else:
        return False

# Example usage
rectangle_length = 6
rectangle_width = 4
square_side = 5

if can_fit_rectangle_in_square(rectangle_length, rectangle_width, square_side):
    print("The rectangle can fit inside the square.")
else:
    print("The rectangle cannot fit inside the square.")

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

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

    // Method inside Square object to handle various shapes inside a rectangle
    // Contains various methods that are invoked within class scope
    public boolean perimeterCanFitInside(TwoDimensionalShape shape) {
        if (shape instanceof Square) {
            Square square = (Square) shape;
            return getSide() > square.getSide();
        } else if (shape instanceof Circle) {
            Circle circle = (Circle) shape;
            return getSide() > circle.getRadius() * 2.0;
        } else if (shape instanceof Rectangle) {
            Rectangle rectangle = (Rectangle) shape;
            // IF rectangles length is less than the square's side
             
            // ELSE rectangles length is greater than ..
            double squareMaxLength = (rectangle.getBiggerSide() + rectangle.getSmallerSide())/Math.sqrt(2);
            return getSide() < squareMaxLength;
        }
        return false;
    }

Выше есть некоторые примечательные особенности. А именно, наш ввод имеет тип TwoDimensionalShape. Это пример полиморфизма, который определяется как возможность рассматривать разные классы как экземпляры одного и того же класса через общий интерфейс. Кроме того, из вызова методов getSide() и getRadius() следует, что некоторое наследование используется для уменьшения избыточности при написании кода.

Часть 2

Теперь мы должны создать алгоритм, который будет искать в нашей структуре данных, в которой хранится наш набор фигур. Есть много способов реализовать это, от используемой структуры данных до метода поиска. Мы будем использовать List (из-за динамического создания объектов формы) с вложенным циклом for для поиска по нашим объектам формы.

for firstShape in shapeList:
    for secondShape in shapeList:
        if isinstance(firstShape, Shape2D) and isinstance(secondShape, Shape2D):
            if firstShape.canFitInside(secondShape):
                # print nested shape success

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

Это означает, что для списка из n участников он проверяет n * n = n² раз. Подумайте о базовом случае, когда вы тестируете первую форму. Он сравнивает себя с собой и любой другой фигурой (до n). Это повторяется снова… n раз.

Этот алгоритм можно назвать алгоритмом с квадратичным временем, временная сложность которого составляет O(n²).

Есть способы оптимизировать наш алгоритм. Если фигура может быть вложена внутрь другой, нам не нужно проверять возможность вложения наоборот, поскольку вкладываемый объект никогда не будет больше, чем его внешняя оболочка. Он относительно асимметричен.

Как вы могли бы реализовать это?