Bounding box boolean subtraction?

Question

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

В идеальном случае в результате ограничивающие коробки, как квадрат, насколько это возможно, так что ограничиваются «осколок» (т.е. 1width, 1height, 100depth).

Answer 1

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

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

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 прямо вверх. Зависит от вашего приложения.

Надеюсь, что этот ответ полезен кому-то!