Алгоритм для решения простой (?) проблемы массива

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

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

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

EDIT: Подождите... как два прямоугольника, края которых уходят в бесконечность, могут не пересекаться? Прямоугольник - это две линии, перпендикулярные друг другу. Разве это не означает, что он всегда пересекается с другим, если эти линии уходят в бесконечность?

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

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

1. пронумеруйте все прямоугольники, присвоив им индивидуальные идентификаторы
2. создайте пустую коллекцию бинарных деревьев (btc). в этой коллекции должен быть метод для вставки целочисленного узла с информацией btc::insert(key, value)
3. для всех прямоугольников сделайте:

foreach rect in rects do
    btc.insert(rect.top, rect.id)
    btc.insert(rect.bottom, rect.id)

4. теперь пройдитесь по btc (это даст вам отсортированный порядок)

btc_item = btc.first()
do
    id = btc_item.id
    btc_item = btc.next()
    if(id != btc_item.id)
    then report_invalid_placement(id, btc_item.id)
    btc_item = btc.next()
while btc_item is valid

5,7,8 - повторите шаги 2,3,4 для координат rect.left и rect.right

Мне нравится этот вопрос. Вот моя попытка разобраться с ним:

Если возможно: Создайте многоугольник из каждого прямоугольника. Рассматривайте каждую грань как линию максимальной длины, которая должна быть обрезана. Используйте алгоритм обрезания, чтобы проверить, пересекается ли линия с другой. Например, вот этот: Line Clipping

Но имейте в виду: Если вы нашли пересечение, которое находится в позиции вершины, то оно допустимо.

Вот идея. Вместо того чтобы создавать каждый прямоугольник с помощью (x, y, width, height), создайте их с помощью (x1, y1, x2, y2), или, по крайней мере, пусть он интерпретирует эти значения, учитывая ширину и высоту.

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

Пример:

Данные прямоугольники имеют следующие значения:

• Квадрат 1: [0, 0, 8, 3]
• Квадрат 3: [0, 4, 8, 6]
• Квадрат 4: [9, 0, 10, 4]

Сначала сравним Квадрат 1 с Квадратом 3 (без столкновения):

• Сравните значения x.
  • [0, 8] - [0, 8] Они абсолютно одинаковы, так что пересечения нет.
• Сравните значения y
  • [0, 4] к [3, 6] Ни одно из этих чисел не похоже, поэтому они не являются фактором

Далее сравниваем Квадрат 3 с Квадратом 4 (столкновение):

• Сравниваем значения x
  • [0, 8] - [9, 10] Ни одно из этих чисел не похоже, поэтому они не являются множителем
• Сравните значения y
  • [4, 6] к [0, 4] Прямоугольники имеют общее число 4, но 0 != 6, следовательно, происходит столкновение

Мы знаем, что столкновение произойдет, поэтому метод закончится, но давайте оценим Квадрат 1 и Квадрат 4 для дополнительной ясности.

• Сравните значения x
  • [0, 8] - [9, 10] Ни одно из этих чисел не похоже, поэтому они не являются множителем
• Сравните значения y
  • [0, 3] - [0, 4] Прямоугольники имеют общее число 0, но 3 != 4, поэтому происходит столкновение

Дайте мне знать, если вам нужны дополнительные детали :)

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

Немного сложнее понять, что допустимые линии разреза не будут пересекать границы прямоугольника вдоль оси, поэтому вы можете комбинировать перекрывающиеся интервалы в один интервал. В итоге вы получаете простой отсортированный массив (который вы заполняете за O (n) раз) и поиск O (log n) для каждой линии разреза.