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

Question

Для этой проблемы скорость очень важна. Я нарисовал красивое изображение, чтобы лучше объяснить проблему. Алгоритм должен вычислить, продолжаются ли края прямоугольника в пределах холста, пересекает ли край другой прямоугольник?

Мы знаем:

1. Размер холста
2. Размер каждого прямоугольника
3. Положение каждого прямоугольника

Чем быстрее решение, тем лучше! Я застрял на этом и не знаю, с чего начать.

альтернативный текст http://www.freeimagehosting.net/uploads/8a457f2925.gif

Приветствия

Answer 1

Просто создайте набор интервалов для каждой оси X и Y.Затем для каждого нового прямоугольника посмотрите, есть ли пересекающиеся интервалы по оси X или Y. См. Здесь для одного способа реализации наборов интервалов.

В вашем первом примере интервал, установленный на горизонтальной оси, будет { [0-8], [0-8], [9-10] }, а на вертикальной: { [0-3], [4-6], [0-4] }

Это всего лишь набросок, здесь я абстрагировал много деталей (например, обычно нужно задать набор / дерево интервалов «какие интервалы перекрывают этот», а не «пересекать этот», но ничего не выполнимо).

Редактировать

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

Answer 2

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

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

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

РЕДАКТИРОВАТЬ: Подождите ... как два прямоугольника, края которых уходят в бесконечность, не пересекаются? Прямоугольники в основном две линии, которые перпендикулярны друг другу. разве это не значит, что оно всегда пересекается с другим, если эти строки расширены до бесконечности?

Answer 3

Вот идея.Вместо создания каждого прямоугольника с помощью (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]

Сначала мы сравним Square 1 с Square 3 (без столкновений):

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

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

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

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

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

Дайте мне знать, если вам понадобятся какие-либо дополнительные детали:)

Answer 4

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

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

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

Answer 5

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

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

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)

теперь перебираем 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координаты

Answer 6

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

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