Ограничивающая коробка логическое вычитание? - PullRequest
Новая
       62

Ограничивающая коробка логическое вычитание?

2 голосов
/ 25 октября 2010

Каков наилучший или эффективный метод вычитания ограничивающего прямоугольника из другого ограничивающего прямоугольника (т.е. создание n ограничивающих прямоугольников из ограничивающего прямоугольника логическим вычитанием)?

В идеале получающиеся ограничивающие прямоугольники должны быть максимально квадратнымичто существуют ограниченные «осколки» (т. е. 1 ширина, 1 высота, 100 глубина).

1 Ответ

0 голосов
/ 19 апреля 2017

Этот вопрос довольно старый, но так как я сделал это, я отвечу на него.

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

A----------------------------------B
|                                  |
|     A----------------------B     |
|     |                      |     |
|     |                      |     |
|     D----------------------C     |
|                                  |
D----------------------------------C

Затем вы получите 8 коробок. 

A----------------------------------B
|  1  |           2          |  3  |
|----------------------------------|
|     |                      |  4  |
|  8  |                      |     |
|----------------------------------|
|  7  |           6          |  5  |
D----------------------------------C

Итак, хитрость в том, чтобы сделать квадраты.Большинство графических библиотек имеют код для работы с «экстентами».Я буду использовать OpenLayers в Javascript для примера.Идея состоит в том, что вы создаете экстенты (ограничивающие прямоугольники), рисуя диагональ из каждой пары точек и получая ее ограничивающий прямоугольник, а затем каскадно опускаетесь, используя точки некоторых ранее созданных ограничивающих прямоугольников.Код ниже должен быть понятен.Мы вычитаем экстент e2, который изображается как внутренний экстент, из экстента e1, который изображается как внешний экстент: 

  var b1 = ol.extent.boundingExtent([ol.extent.getTopLeft(e1), ol.extent.getTopLeft(e2)]);
  var b2 = ol.extent.boundingExtent([ol.extent.getBottomLeft(b1), ol.extent.getBottomLeft(e2)]);
  var b3 = ol.extent.boundingExtent([ol.extent.getBottomLeft(e1), ol.extent.getBottomLeft(e2)]);
  var b4 = ol.extent.boundingExtent([ol.extent.getBottomLeft(b3), ol.extent.getBottomRight(e2)]);
  var b5 = ol.extent.boundingExtent([ol.extent.getBottomRight(e1), ol.extent.getBottomRight(e2)]);
  var b6 = ol.extent.boundingExtent([ol.extent.getBottomRight(b5), ol.extent.getTopRight(e2)]);
  var b7 = ol.extent.boundingExtent([ol.extent.getTopRight(e1), ol.extent.getTopRight(e2)]);
  var b8 = ol.extent.boundingExtent([ol.extent.getTopLeft(e1), ol.extent.getTopLeft(b7)]);

Например, обратите внимание, как мы используем координату из ограничительной рамки b1, чтобы сделатьb2, b3 - b4 и т. д.

Теперь мы знаем, что экстенты могут быть не концентрическими.Некоторые поля могут быть за пределами нашего ответа.Тем не менее, следует отметить одно замечательное условие: если угол экстента вычитания (e2) находится внутри базового экстента (e1), то нам нужны три его связанных блока.Итак, если верхний левый угол e2 находится в e1, то нам нужны b1, b2 и b8.Точно так же, если нижний левый угол e2 находится в e1, то нам нужны b6, b7 и b8.Вы можете заметить некоторые дубликаты, такие как b8, но мы отфильтруем их позже.Итак, давайте соберем наши результаты. 

  var results = [];
  if (ol.extent.containsCoordinate(e1, ol.extent.getTopLeft(e2))) {
    results.push(b1, b2, b3);
  }
  if (ol.extent.containsCoordinate(e1, ol.extent.getTopRight(e2))) {
    results.push(b8, b7, b6);
  }
  if (ol.extent.containsCoordinate(e1, ol.extent.getBottomRight(e2))) {
    results.push(b6, b5, b4);
  }
  if (ol.extent.containsCoordinate(e1, ol.extent.getBottomLeft(e2))) {
    results.push(b2, b3, b4);
  }

Удалите дубликаты, но также обратите внимание на тот факт, что, особенно в случае, когда экстенты имеют общие границы, некоторые из этих полей будут «пустыми».Обычно это можно выяснить с помощью функции getArea (), связанной с экстентом.Ниже представлен умный способ JavaScript, чтобы отфильтровать дублирующиеся объекты в массиве, так как Array.indexOf использует '===' и возвращает только первое совпадение.И мы собираем только те блоки, которые на самом деле имеют площадь. 

results = results.filter(function(a,i,arr) {
             return arr.indexOf(a) === i && ol.extent.getArea(a) > 0;
          });

Предостережения об использовании:

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

Например, если вы хотите загрузить потенциальный экстент (e1) минус тот, который вы уже загрузили (e2), и они не пересекаются,Вы, вероятно, просто хотите загрузить e1 прямо вверх.Зависит от вашего приложения.

Надеюсь, этот ответ кому-нибудь пригодится!

...