Как проверить набор прямоугольников на наличие дырок и пересечений? - PullRequest
Новая
       15

Как проверить набор прямоугольников на наличие дырок и пересечений?

5 голосов
/ 15 февраля 2012

Я ищу способ проверить коллекцию (Java TreeSet) прямоугольников - реализованную "сопоставимым" Java-классом, используя google guavas Range для диапазона x и y - для пересечений и дырок. я знаю, что можно использовать kd-деревья, но я понятия не имею, как построить такое kd-дерево (для прямоугольников это должно быть 4d, не так ли?) и как решить проблему (пересечение, отверстия).

сортировка отдает приоритет оси X над осью Y.

РЕДАКТИРОВАТЬ: (попробуйте повторить проблему): сценарий использования для создания произвольных таблиц (состоящих из 2 или 3 блоков прямоугольников "заголовок", "до столбца", "данные"). я должен гарантировать, что в каждом блоке нет пересечений и дырок (то есть предоставленных недействительным html или другими источниками данных таблицы) (кроме того, блоки должны совмещаться). В настоящее время (только что понял) я пытаюсь сохранить в 2d-массив, позиции (x, y) которого заняты. в конце все позиции должны быть заняты ровно один раз.

1 Ответ

6 голосов
/ 15 февраля 2012

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

Пересечение пары прямоугольников + Сумма площади

Посмотрите на каждую пару прямоугольников - если эти два прямоугольника пересекаются, происходит наложение. Сложите прямоугольные области и проверьте, совпадает ли сумма с областью холста - если области не совпадают, есть пробел.

Живопись

Это подход, который вы упомянули: создайте 2D-массив, который имеет размеры вашего холста. Затем переберите прямоугольники и «закрасьте» их в массив.

Одной из оптимизаций этого подхода является сжатие координат. Допустим, у вас есть прямоугольники [(10,20), (15,25)] и [(7,3), (15, 25)]. Вы можете посмотреть на различные x-координаты (7, 10, 15) и переназначить их в (0, 1, 2), а также различные y-координаты (3, 20, 25) и переназначить их в (0, 1, 2). Затем у вас остаются прямоугольники [(1, 1), (2, 2)] и [(0,0), (2,2)], поэтому для рисования вам нужен только массив 3x3 вместо 26x26 массив.

Алгоритм развертки

Проведите линию слева направо, останавливаясь на «интересных» точках и отслеживая, какие области заняты.

Деревья 2D диапазона

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

Кого выбрать?

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

Подробнее

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

Вот пара ссылок на алгоритм строчной развертки:

  1. Что такое эффективный алгоритм для нахождения области перекрывающихся прямоугольников
  2. http://compgeom.cs.uiuc.edu/~jeffe/open/klee.html
  3. J. Л. Бентли, Алгоритмы для задач прямоугольника Кли. Неопубликованные заметки, факультет компьютерных наук, Университет Карнеги-Меллона, 1977

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

...