Ответ 1

Вот эскиз решения O (n ^ 2 log n).

Во-первых, предварительные данные делились с другими ответами. Когда у нас есть линия, проходящая через некоторые прямоугольники, мы можем перевести ее на любую из двух сторон, пока она не пройдет через угол некоторого прямоугольника. После этого мы фиксируем этот угол как центр вращения и поворачиваем линию на любую из двух сторон, пока она не пройдет через другой угол. В течение всего процесса все точки пересечения между нашей линией и сторонами прямоугольника оставались на этих сторонах, поэтому количество пересечений оставалось неизменным, равно как и число прямоугольников, пересекаемых линией. В результате мы можем рассматривать только линии, проходящие через два прямоугольника, которые ограничены O (n ^ 2), и являются приятным улучшением по сравнению с бесконечным пространством произвольных строк.

Итак, как мы эффективно проверяем все эти строки? Во-первых, давайте иметь внешний цикл, который фиксирует одну точку A, а затем рассматривает все линии, проходящие через A. Есть O (n) выбор A.

Теперь мы фиксируем одну точку A и хотим рассмотреть все прямые AB, проходящие через все остальные углы B. Для этого сначала отсортируйте все остальные углы B в соответствии с полярным углом AB, или, другими словами, угол между осью Ox и вектором AB. Углы измеряются от -PI до + PI или от 0 до 2 PI или иначе, точка, в которой мы разрезаем круг для сортировки углов, может быть произвольной. Сортировка выполняется в O (n log n).

Теперь у нас есть точки B ₁, B ₂,..., B _k, отсортированные по полярному углу вокруг точки A ( их число k является чем-то вроде 4n-4, все углы всех прямоугольников, кроме тех, где точка A является углом). Сначала просмотрите строку AB ₁ и подсчитайте количество прямоугольников, пересекаемых этой строкой в ​​O (n). После этого рассмотрите возможность поворота AB ₁ на AB ₂, затем AB ₂ на AB ₃, вплоть до AB <югу > ксуб > . События, которые происходят во время вращения, следующие:

• Когда мы поворачиваем на AB _i, а B _i - это первый угол некоторого прямоугольника в нашем порядке, число скрещенных прямоугольников увеличивается на 1 как как только вращающаяся линия попадает в B _i.

• Когда мы поворачиваем на AB _j, а B _j является последним углом некоторого прямоугольника в нашем порядке, число скрещенных прямоугольников уменьшается на 1 как вскоре, когда линия вращается мимо B _j.

Какие углы первыми и последними могут быть установлены с некоторой предварительной обработкой O (n) после сортировки, но до рассмотрения упорядоченных событий.

Короче говоря, мы можем повернуть на следующее такое событие и обновить количество прямоугольников, скрещенных в O (1). И есть k = O (n) событий в целом. Остается сделать так, чтобы отслеживать глобальный максимум этой величины во всем алгоритме. Ответ - именно этот максимум.

Весь алгоритм работает в O (n * (n log n + n + n)), который является O (n ^ 2 log n), так же, как рекламируется.

Ответ 2

(Отредактируйте мой более ранний ответ, который рассмотрел поворот плоскости.)

Здесь набросок алгоритма O(n^2), который объединяет идею Гасса с Евгением Клуевым, ссылается на двухлинейные устройства в виде отсортированных последовательностей angular.

Мы начинаем с двусвязного реберного списка или подобной структуры, позволяя нам разделить ребро в O(1) время и метод для перемещения лиц, которые мы создаем, когда мы заполняем двумерную плоскость. Для простоты позвольте использовать только три из двенадцати углов на прямоугольниках ниже:

9|     (5,9)___(7,9)
8|         |   |
7|    (4,6)|   |
6|    ___C |   |
5|   |   | |   |
4|   |___| |   |
3|  ___    |___|(7,3)
2| |   |  B (5,3)
1|A|___|(1,1)
 |_ _ _ _ _ _ _ _
   1 2 3 4 5 6 7

Вставляем три точки (углы) в двойную плоскость в соответствии со следующим преобразованием:

point p => line p* as a*p_x - p_y
line l as ax + b => point l* as (a, -b)

Введем точки порядка A, B, C. Введем сначала A => y = x - 1. Поскольку на данный момент имеется только один край, мы вставляем B => y = 5x - 3, который создает вершину (1/2, -1/2) и разбивает наше ребро. (Один элегантный аспект этого решения состоит в том, что каждая вершина (точка) в двойной плоскости на самом деле является двойной точкой линии, проходящей через углы прямоугольников. Наблюдайте 1 = 1/2*1 + 1/2 и 3 = 1/2*5 + 1/2, точки (1,1) и (5,3).)

Ввод последней точки, C => y = 4x - 6, теперь мы ищем крайнее левое лицо (может быть неполное лицо), где оно будет пересекаться. Этот поиск O(n) времени, так как мы должны попробовать каждое лицо. Мы найдем и создаем вершину (-3, -18), раскалывая нижний край 5x - 3 и пересекаем края, чтобы разделить правую половину x - 1 на вершине (5/3, 2/3). Каждая вставка имеет O(n) время, так как мы должны сначала найти самую левую грань, затем пересечь каждую грань, чтобы разделить ребра и пометить вершины (точки пересечения для линии).

В дуальной плоскости мы имеем:

После построения компоновки строк мы начинаем нашу итерацию на наших трех примерных точках (прямоугольные углы). Часть магии при восстановлении упорядоченной последовательности angular по отношению к одной точке состоит в разбиении углов (каждый из которых соответствует упорядоченному пересечению линий в двойной плоскости) на те, которые соответствуют точке справа (с большей координатой x ) и слева, и конкатенировать две последовательности, чтобы получить упорядоченную последовательность от -90 до -270 градусов. (Точки справа преобразуются в линии с положительными наклонами по отношению к неподвижной точке, а слева - с отрицательными склонами. Поворачивайте селектор/экран по часовой стрелке до тех пор, пока линия для (C*) 4x - 6 не станет горизонтальной, и вы увидите, что B* теперь имеет положительный наклон и A* отрицательный.)

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

(Давайте суммируем прямоугольник-счет-логику, обновляем count_array для текущего прямоугольника при повторении через последовательность angular: если он 1, увеличивайте текущий счет пересечения, если он 4 и строка не находится непосредственно на угол, установите его в 0 и уменьшите текущий счет пересечения.)

Pick A, lookup A*
=> x - 1.

Obtain the concatenated sequence by traversing the edges in O(n)
=> [(B*) 5x - 3, (C*) 4x - 6] ++ [No points left of A]

Initialise an empty counter array, count_array of length n-1

Initialise a pointer, ptr, to track rectangle corners passed in
the opposite direction of the current vector.

Iterate:
  vertex (1/2, -1/2)
  => line y = 1/2x + 1/2 (AB)

  perform rectangle-count-logic

  if the slope is positive (1/2 is positive):
    while the point at ptr is higher than the line:
      perform rectangle-count-logic

  else if the slope is negative:
    while the point at ptr is lower than the line:
      perform rectangle-count-logic

  => ptr passes through the rest of the points up to the corner
     across from C, so intersection count is unchanged

  vertex (5/3, 2/3)
  => line y = 5/3x - 2/3 (AC)

Мы можем видеть, что (5,9) находится над линией через AC (y = 5/3x - 2/3), что означает, что в этот момент мы бы подсчитали пересечение с самым правым прямоугольником и еще не reset счетчик для него, всего 3 прямоугольника для этого линия.

Мы также можем видеть на графике двойной плоскости, другие последовательности angular:

for point B => B* => 5x - 3: [No points right of B] ++ [(C*) 4x - 6, (A*) x - 1]

for point C => C* => 4x - 6: [(B*) 5x - 3] ++ [(A*) x - 1]
(note that we start at -90 deg up to -270 deg)

Ответ 3

Решение

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

И для каждой строки, которая проходит по крайней мере на один угол, существует соответствующая строка, проходящая по двум углам с одинаковым числом пересечений.

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

Сложность времени

Это решение сначала должно восстановить все линии, которые проходят по двум углам. Число таких линий равно O (n ^ 2).

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

Может быть, более эффективный способ продолжения, но мы знаем, что этот алгоритм тогда не более O (n ^ 3).

Реализация Python3

Вот реализация этого алгоритма на Python. Я ориентировал его скорее на читаемость, чем на эффективность, но он делает именно то, что указано выше.

def get_best_line(rectangles):
    """
    Given a set of rectangles, return a line which intersects the most rectangles.
    """

    # Recover all corners from all rectangles
    corners = set()
    for rectangle in rectangles:
        corners |= set(rectangle.corners)

    corners = list(corners)

    # Recover all lines passing by two corners
    lines = get_all_lines(corners)

    # Return the one which has the highest number of intersections with rectangles
    return max(
        ((line, count_intersections(rectangles, line)) for line in lines),
        key=lambda x: x[1])

В этой реализации используются следующие помощники.

def get_all_lines(points):
    """
    Return a generator providing all lines generated
    by a combination of two points out of 'points'
    """
    for i in range(len(points)):
        for j in range(i, len(points)):
            yield Line(points[i], points[j])

def count_intersections(rectangles, line):
    """
    Return the number of intersections with rectangles
    """
    count = 0

    for rectangle in rectangles:
        if line in rectangle:
           count += 1

    return count

И вот определение класса, которое служит структурой данных для прямоугольников и строк.

import itertools
from decimal import Decimal

class Rectangle:
    def __init__(self, x_range, y_range):
        """
        a rectangle is defined as a range in x and a range in y.
        By example, the rectangle (0, 0), (0, 1), (1, 0), (1, 1) is given by
        Rectangle((0, 1), (0, 1))
        """
        self.x_range = sorted(x_range)
        self.y_range = sorted(y_range)

    def __contains__(self, line):
        """
        Return whether 'line' intersects the rectangle.
        To do so we check if the line intersects one of the diagonals of the rectangle
        """
        c1, c2, c3, c4 = self.corners

        x1 = line.intersect(Line(c1, c4))
        x2 = line.intersect(Line(c2, c3))

        if x1 is True or x2 is True \
                or x1 is not None and self.x_range[0] <= x1 <= self.x_range[1] \
                or x2 is not None and self.x_range[0] <= x2 <= self.x_range[1]:

            return True

        else:
            return False

    @property
    def corners(self):
        """Return the corners of the rectangle sorted in dictionary order"""
        return sorted(itertools.product(self.x_range, self.y_range))


class Line:
    def __init__(self, point1, point2):
        """A line is defined by two points in the graph"""
        x1, y1 = Decimal(point1[0]), Decimal(point1[1])
        x2, y2 = Decimal(point2[0]), Decimal(point2[1])
        self.point1 = (x1, y1)
        self.point2 = (x2, y2)

    def __str__(self):
        """Allows to print the equation of the line"""
        if self.slope == float('inf'):
            return "y = {}".format(self.point1[0])

        else:
            return "y = {} * x + {}".format(round(self.slope, 2), round(self.origin, 2))

    @property
    def slope(self):
        """Return the slope of the line, returning inf if it is a vertical line"""
        x1, y1, x2, y2 = *self.point1, *self.point2

        return (y2 - y1) / (x2 - x1) if x1 != x2 else float('inf')

    @property
    def origin(self):
        """Return the origin of the line, returning None if it is a vertical line"""
        x, y = self.point1

        return y - x * self.slope if self.slope != float('inf') else None

    def intersect(self, other):
        """
        Checks if two lines intersect.
        Case where they intersect: return the x coordinate of the intersection
        Case where they do not intersect: return None
        Case where they are superposed: return True
        """

        if self.slope == other.slope:

            if self.origin != other.origin:
                return None

            else:
                return True

        elif self.slope == float('inf'):
            return self.point1[0]

        elif other.slope == float('inf'):
            return other.point1[0]

        elif self.slope == 0:
            return other.slope * self.origin + other.origin

        elif other.slope == 0:
            return self.slope * other.origin + self.origin

        else:
            return (other.origin - self.origin) / (self.slope - other.slope)

Пример

Вот рабочий пример приведенного выше кода.

rectangles = [
    Rectangle([0.5, 1], [0, 1]),
    Rectangle([0, 1], [1, 2]),
    Rectangle([0, 1], [2, 3]),
    Rectangle([2, 4], [2, 3]),
]

# Which represents the following rectangles (not quite to scale)
#
#  *
#  *   
#
# **     **
# **     **
#
# **
# **

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

print('{} with {} intersections'.format(*get_best_line(rectangles)))
# prints: y = 0.50 * x + -5.00 with 3 intersections

Ответ 4

Как насчет следующего алгоритма:

RES = 0 // maximum number of intersections
CORNERS[] // all rectangles corners listed as (x, y) points

for A in CORNERS
    for B in CORNERS // optimization: starting from corner next to A
        RES = max(RES, CountIntersectionsWithLine(A.x, A.y, B.x, B.y))

return RES

Другими словами, начните рисовать линии из каждого угла прямоугольника друг к другу в прямоугольник и найдите максимальное количество пересечений. Как было предложено @weston, мы можем избежать вычисления одной и той же строки дважды, запустив внутренний цикл из угла рядом с A.

Ответ 5

Если вы рассматриваете вращающуюся линию под углом Θ, и если вы проецируете все прямоугольники на эту строку, вы получите N отрезков. Максимальное количество прямоугольников, пересекаемых перпендикуляром к этой линии, легко получается путем сортировки конечных точек за счет увеличения абсциссы и сохранения отсчета интервалов, встречающихся слева направо (следите за тем, является ли конечная точка началом или концом). Это отображается зеленым цветом.

Теперь два прямоугольника пересекаются всеми линиями под углом, заключенным между двумя внутренними касательными (пример красным), так что все рассматриваемые углы "события" должны рассматриваться (т.е. все углы, для которых можно наблюдать изменение счетчика ) - эти N (N-1) углы.

Тогда схема преобразования грубой силы

• для всех предельных углов (O (N²) из них),

  • проектируйте прямоугольники на вращающейся линии (операции O (N)),

  • подсчитайте перекрытия и сохраните самый большой (O (N Log N) для сортировки, затем O (N) для подсчета).

Это относится к общим операциям O (N³Log N).

Предполагая, что сортировки не нужно перерабатывать полностью для каждого угла, если мы можем сделать их поэтапно, мы можем надеяться на снижение сложности до O (N³). Это нужно проверить.

Примечание:

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

Ответ 6

У нас может быть метод динамического программирования O(n^2 (log n + m)), адаптировав идею Андрея Берестовского к итерации по углам, чтобы вставить отношение текущего угла по всем другим прямоугольникам в дерево интервалов для каждого из наших 4n итерационные циклы.

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

В приведенном ниже примере для фиксированного нижнего угла прямоугольника R при вставке записи для среднего прямоугольника мы вставляем углы, обозначающие дугу от p2 до p1 по отношению к R ( около (37 deg, 58 deg)). Затем, когда мы проверим высокий прямоугольник относительно R, мы вставим интервал углов, обозначающий дугу от p4 до p3 по отношению к R (около (50 deg, 62 deg)).

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

(Обратите внимание, что поскольку любая дуга на 360-градусном круге для нашей цели имеет аналог, повернутый на 180 градусов, нам может потребоваться сделать произвольное отсечение (любые альтернативные идеи будут приветствоваться). Например, это означает, что дуга из 45 градусов до 315 градусов разделили бы на два: [0, 45] и [135, 180]. Любая нерасширенная дуга могла пересекаться только с одним или другим, но в любом случае, нам может понадобиться дополнительный хеш, чтобы убедиться, что прямоугольники не считаются двойными.)