Пересекающиеся прямоугольники в пространстве

Question

Пересекающиеся прямоугольники в пространстве

Мне нужно пересечь 1 миллион пространственных многоугольников (указанных с использованием их минимальных ограничивающих прямоугольников) с четырьмя полностью непересекающимися MBR (MBR1, MBR2, MBR3, MBR4) в пространстве. MBR1, MBR2, MBR3 и MBR4 делят все пространство на 4 непересекающиеся части. Для этого я написал следующий код. Однако оказывается, что на 1 миллион баллов код выполняется очень медленно. Есть ли способ, с помощью которого я могу улучшить код, чтобы он мог работать немного быстрее. Если да, то может кто-нибудь, пожалуйста, помогите с тем же

//---------------------------------------------------------------------------
struct MBR
{
double xRight, xLeft, yBottom, yTop;
};
bool intersects(MBR spatialId,MBR mbr)
{
if (mbr.yBottom > spatialId.yTop || mbr.yTop < spatialId.yBottom) return false;
if (mbr.xLeft > spatialId.xRight || mbr.xRight < spatialId.xLeft) return false;
return true;
}
//---------------------------------------------------------------------------
bool contains(MBR spatialId,MBR mbr)
{
if (mbr.yBottom > spatialId.yBottom || mbr.yTop < spatialId.yTop) return false;
if (mbr.xLeft > spatialId.xLeft || mbr.xRight < spatialId.xRight) return false;
return true;
}
//---------------------------------------------------------------------------
bool touches(MBR spatialId,MBR mbr)
{
if (    (mbr.yBottom >= spatialId.yBottom + std::numeric_limits<double>::epsilon() &&
mbr.yBottom <= spatialId.yBottom - std::numeric_limits<double>::epsilon()) ||
(mbr.yTop >= spatialId.yTop + std::numeric_limits<double>::epsilon() &&
mbr.yTop <= spatialId.yTop - std::numeric_limits<double>::epsilon()))
return true;
if (    (mbr.xLeft >= spatialId.xLeft + std::numeric_limits<double>::epsilon() &&
mbr.xLeft <= spatialId.xLeft - std::numeric_limits<double>::epsilon()) ||
(mbr.xRight >= spatialId.xRight + std::numeric_limits<double>::epsilon() &&
mbr.xRight <= spatialId.xRight - std::numeric_limits<double>::epsilon()))
return true;
return false;
}
//---------------------------------------------------------------------------
MBR MBR1,MBR2,MBR3,MBR4;
vector<unsigned> spatialIds; //contain 1 million spatial identifiers which are intersected with MBR1, MBR2, MBR3, MBR4
//MBR1, MBR2, MBR3, MBR4 are again specified using their Minimum Bounding Rectangles
vector<unsigned> result; //contains the resulting intersecting spatial ids
for(vector<MBR>::iterator itSpatialId=spatialIds.begin(),lSpatialId=spatialIds.end();itSpatialId!=lSpatialId;++itSpatialId)
{
if(intersects((*itSpatialId),MBR1)||contains((*itSpatialId),MBR1)||touches((*itSpatialId),MBR1))
{
result.push_back((*itSpatialId));
}

if(intersects((*itSpatialId),MBR2)||contains((*itSpatialId),MBR2)||touches((*itSpatialId),MBR2))
{
result.push_back((*itSpatialId));
}

if(intersects((*itSpatialId),MBR3)||contains((*itSpatialId),MBR3)||touches((*itSpatialId),MBR3))
{
result.push_back((*itSpatialId));
}

if(intersects((*itSpatialId),MBR4)||contains((*itSpatialId),MBR4)||touches((*itSpatialId),MBR4))
{
result.push_back((*itSpatialId));
}
}

1

c++data-structures spatial

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Я думаю, что вы можете упростить тест пересечения.

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

Во-вторых, вам нужно только проверить следующее:

bool intersectsContainsOrTouches(MBR spatialId,MBR mbr)
{
return (mbr.yBottom <= spatialId.yTop && mbr.yTop >= patialId.yBottom) &&
(mbr.xLeft <= spatialId.xRight && mbr.xRight >= spatialId.xLeft);
}

Обычно вы используете BSP или многомерный индекс для выполнения пространственной операции «JOIN». Но так как у вас есть только 4 прямоугольника, с которыми нужно соединиться, должно быть быстрее просто выполнить итерацию по всем 1M прямоугольникам и сравнить каждый из них с 4 MBR.
Я не уверен, что многомерные индексы или двоичное пространство разделение помогло бы здесь.

Кстати, сколько времени это займет? Это должно быть меньше минуты, это проблема?

РЕДАКТИРОВАТЬ

Если вам придется делать это неоднократно, я бы поместил данные в пространственный индекс, а затем вы можете выполнить четыре оконных запроса по индексу для каждого из ваших MBR.
Есть также специальные алгоритмы, такие как СЕНСОРНЫЙ.
Если вы используете Java, посмотрите на мой PH-Tree (что также хорошо, когда отдельные прямоугольники добавляются / удаляются или перемещаются. Для других языков выберите R-Tree (R + tree, X-Tree, ..), kd-tree или quadtree.

Для C ++ вы могли бы взглянуть на ОДА. Это движок физики трехмерных игр, в котором есть несколько алгоритмов для определения перекрытий MBR (Quadtrees, SAP-Space, …).

1