Skip to content
TheChatArchiveThe Chat Archive
Mistralmistral-medium-2505· Mistral AIHugging Face LMArena Human Preference 140K

Для заданного списка полигонов, в котором каждый полигон имеет 4-ре вершины. Нужно найти…

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with grok-3-preview-02-24’s answer.
  1. User

    Для заданного списка полигонов, в котором каждый полигон имеет 4-ре вершины. Нужно найти прямоугольник максимальной площади, вписанный внутрь этих полигонов. Вписанный здесь означает, что когда граница прямоугольника касается вершины полигона, то двигать её уже нельзя.

    Будем решать методом выращивания прямоугольника из центра. И каждую его грань остановим при первом касании вершины любого из полигонов. Можешь такое реализовать?

    Пример списка полигонов:

    polygons = np.array([ [[-179., 253.], [-179., 230.], [ -19., 230.], [ -19., 253.]], [[-258., 189.], [-258., 164.], [ -55., 164.], [ -55., 189.]], [[-379., 190.], [-379., 164.], [-290., 164.], [-290., 190.]], [[ 614., 122.], [ 614., 114.], [ 626., 114.], [ 626., 122.]], [[ 525., -409.], [ 525., -436.], [ 616., -436.], [ 616., -409.]], [[ 418., -411.], [ 418., -435.], [ 499., -435.], [ 499., -411.]], [[ 57., -479.], [ 57., -505.], [ 154., -507.], [ 154., -481.]], [[-382., -486.], [-382., -510.], [ -10., -504.], [ -10., -480.]] ])

    Пример центра из которого надо начинать выращивание:

    center = np.array([0., 0.])

    Ещё важная деталь, что максимальный размер прямоугольника, до которого можно продолжать выращиватьнаш прямоугольник будет ограничен значениями (max_width, max_height).

  2. Mistral Assistant

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

    1. Начинаем с прямоугольника нулевого размера в заданном центре.
    2. Постепенно увеличиваем размеры прямоугольника в четырех направлениях (вверх, вниз, влево, вправо) до тех пор, пока его границы не коснутся вершин полигонов.
    3. Останавливаем рост границы при первом касании вершины любого полигона.
    4. Запоминаем максимальную площадь найденного прямоугольника.

    Вот реализация этого алгоритма на Python с использованием библиотеки NumPy:

    import numpy as np
    
    def find_max_inscribed_rectangle(polygons, center, max_width, max_height):
        # Инициализация границ прямоугольника
        left = center[0]
        right = center[0]
        bottom = center[1]
        top = center[1]
    
        # Шаг увеличения границ
        step = 1.0
    
        # Флаг для проверки касания вершин
        touched = False
    
        # Направления для проверки касания (вверх, вниз, влево, вправо)
        directions = [
            (0, 1),   # вверх
            (0, -1),  # вниз
            (-1, 0),  # влево
            (1, 0)    # вправо
        ]
    
        # Пока не коснулись вершин и не достигли максимальных размеров
        while not touched and (right - left < max_width) and (top - bottom < max_height):
            # Проверяем касание для каждой границы
            new_touched = False
    
            # Проверяем верхнюю границу
            if top - bottom < max_height:
                new_top = top + step
                # Проверяем, касается ли новая верхняя граница вершин полигонов
                for polygon in polygons:
                    for vertex in polygon:
                        if np.isclose(vertex[1], new_top) and left <= vertex[0] <= right:
                            new_touched = True
                            break
                    if new_touched:
                        break
                if not new_touched:
                    top = new_top
                else:
                    touched = True
    
            # Проверяем нижнюю границу
            if top - bottom < max_height and not touched:
                new_bottom = bottom - step
                for polygon in polygons:
                    for vertex in polygon:
                        if np.isclose(vertex[1], new_bottom) and left <= vertex[0] <= right:
                            new_touched = True
                            break
                    if new_touched:
                        break
                if not new_touched:
                    bottom = new_bottom
                else:
                    touched = True
    
            # Проверяем левую границу
            if right - left < max_width and not touched:
                new_left = left - step
                for polygon in polygons:
                    for vertex in polygon:
                        if np.isclose(vertex[0], new_left) and bottom <= vertex[1] <= top:
                            new_touched = True
                            break
                    if new_touched:
                        break
                if not new_touched:
                    left = new_left
                else:
                    touched = True
    
            # Проверяем правую границу
            if right - left < max_width and not touched:
                new_right = right + step
                for polygon in polygons:
                    for vertex in polygon:
                        if np.isclose(vertex[0], new_right) and bottom <= vertex[1] <= top:
                            new_touched = True
                            break
                    if new_touched:
                        break
                if not new_touched:
                    right = new_right
                else:
                    touched = True
    
            # Если ни одна граница не коснулась вершин, продолжаем увеличивать
            if not new_touched:
                touched = False
    
        # Вычисляем площадь найденного прямоугольника
        width = right - left
        height = top - bottom
        area = width * height
    
        return (left, right, bottom, top), area
    
    # Пример использования
    polygons = np.array([
        [[-179., 253.], [-179., 230.], [-19., 230.], [-19., 253.]],
        [[-258., 189.], [-258., 164.], [-55., 164.], [-55., 189.]],
        [[-379., 190.], [-379., 164.], [-290., 164.], [-290., 190.]],
        [[614., 122.], [614., 114.], [626., 114.], [626., 122.]],
        [[525., -409.], [525., -436.], [616., -436.], [616., -409.]],
        [[418., -411.], [418., -435.], [499., -435.], [499., -411.]],
        [[57., -479.], [57., -505.], [154., -507.], [154., -481.]],
        [[-382., -486.], [-382., -510.], [-10., -504.], [-10., -480.]]
    ])
    
    center = np.array([0., 0.])
    max_width = 1000.0
    max_height = 1000.0
    
    rectangle, area = find_max_inscribed_rectangle(polygons, center, max_width, max_height)
    print("Rectangle boundaries (left, right, bottom, top):", rectangle)
    print("Area:", area)
    

    Пояснение:

    1. Инициализация границ: Начинаем с прямоугольника нулевого размера в заданном центре.
    2. Увеличение границ: Постепенно увеличиваем границы прямоугольника в четырех направлениях (вверх, вниз, влево, вправо) с шагом step.
    3. Проверка касания: Для каждой новой границы проверяем, касается ли она вершин полигонов. Если да, то останавливаем рост в этом направлении.
    4. Ограничение размеров: Проверяем, чтобы размеры прямоугольника не превышали заданные max_width и max_height.
    5. Вычисление площади: После остановки роста вычисляем площадь найденного прямоугольника.

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

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.