Для простоты будем рассматривать задачу про прямоугольники (для кубов -- аналогично).
Задача состоит в том, чтобы подсчитать суммарную площадь пересечений прямоугольников (или любую другую аддитивную функцию от площади пересечений), которые ориентированы по осям стандартной системы координат (СК). Кажется, что задача решается быстрее чем брутфорсом, т.е. быстрее, чем за O(n2).
Решение можно построить так:
- Переберём все упорядоченные пары прямоугольников (их C2n).
- Для каждой пары посчитаем площадь пересечений.
Предложим решение задачи для случая двух прямоугольников.
Будем обозначать проекции точек на оси как Ax, Bx, Cx, Dx, Ay, By... и т.д.
Тогда, запишем все проекции и отсортируем их согласно возрастанию значению координат. Чтобы не дублировать координаты, для оси X будем брать только точки A, B, E, F:
Ax, Ex, Bx, Fx
Для оси y соответственно:
Hy, Dy, Ey, Ay
Заведём сет и будем поочередно класть точки в него. Если одновременно в сете есть две точки одного и того же прямоугольника, то удалим их. Если одновременно в сете есть точки различных прямоугольников по каждой из координат, то фиксируем пересечение.
Пример.
- Sx = {} // Сет Sx -- по оси х
- Sy = {} // Сет Sy -- по оси y
- Добавим в сет первые точки по каждой из координат: Sx = {Ax}, Sy = {Hy}
- Добавим ещё по одной точке: Sx = {Ax, Ex}, Sy = {Hy, Dy}. Фиксируем пересечение
- Sx = {Ax, Ex, Bx}, Sy = {Hy, Dy, Ey}. Вычисляем значение пересечения: (Bx - Ax) * (Hy - Ey)
- Удаляем точки из сетов: Sx = {Ex}, Sy = {Dy}
- Добавляем точки в сеты: Sx = {Ex, Fx}, Sy = {Dy, Ay}
- Удаляем точки одинаковых прямоугольников: Sx = {}, Sy = {}
Вопросы:
- Будет ли работать подобный алгоритм для 3 измерений?
- Помогите обобщить его на случай n прямоугольнков (кубов). Никак не соображу.
Для случая двойных пересечений требует вычислить суммарную площадь. Пусть есть 3 прямоугольника ABCD, EFGH, IJKL. Требуется вычислить либо площадь S(INMO) + S(EOPQ) + S(OSKL), либо S(INMO) + 2S(EOPQ) + S(OSKL), в зависимости от того, что проще посчитать.
Замечание
Для случая двух прямоугольников (кубов) задача решается легко. Пусть у нас заданы прямоугольники как левые нижние углы и размеры их сторон:
x0, y0, z0, dx, dy, dz
Тогда посмотрим, какой из прямоугольников лежит правее по каждой оси. Затем проверим условия пересечений и вычислим площадь. Напишем код (на golang):
type Box struct {
dx, dy, dz int
x, y, z int
}
func (c *Box) isLineIntersection(p00, p01, p10, p11 int) int {
if p00 > p10 {
p00, p01, p10, p11 = p10, p11, p00, p01
}
if (p10 >= p01) && (p01 <= p11) {
return p01 - p10
} else if (p10 <= p01) && (p11 <= p01) {
return p11 - p10
}
return 0
}
func (c *Box) isIntersection(box1 Box, box2 Box) (intersection int) {
dx := c.isLineIntersection(box1.x, box1.x+box1.dx, box2.x, box2.x+box2.dx)
dy := c.isLineIntersection(box1.y, box1.y+box1.dy, box2.y, box2.y+box2.dy)
dz := c.isLineIntersection(box1.z, box1.z+box1.dz, box2.z, box2.z+box2.dz)
return dx * dy * dz
}
O(n*(n-1)/2)